Эффективный поиск в трехуровневой иерархии

Question

Допустим, у меня есть иерархия Имя > Отчество > Фамилия (~ 10 тыс. строк, ради вопроса).Это означает, что у вас может быть строка «Джон > Мэри-Энн > Эдди» или «Эдди > Джон > Джейкоб».Дело в том, что иерархия не имеет особого смысла и очень чужда пользователю (в отличие, скажем, от структуры Страна > Штат > Город).

Поскольку он настолько неструктурирован и запутан, я хочу предоставить пользователю поле ввода с автоматическим заполнением.По мере ввода он должен искать возможные совпадения подстроки, и когда они «укореняют» свою строку поиска на уровне, он ограничивает результаты ниже этого уровня.

Теперь, поскольку есть много людей с именем «Джон», нет особого смысла в том, что, если они наберут «Джон», они получат только такие результаты, как

• Джон > Аллен > Александр
• Джон > Аллен > Буршавиц
• Джон > Аллен...повторить 100 раз...

Потому что они никогда не увидят уникальную строку «Джейсон > Джон > Смит».

Вместо этого они должны вернуть что-то вроде («*» — это просто произвольный индикатор для пользователя «эй, ниже этой строки существует еще много строк»):

• Джон > Аллен > *
• Джейсон > Джон > Смит
• Майк > Джон > *
• Мэри > Елена > Джонасон

Если они введут «Джон > Эл», то результаты будут ограничены всем, что находится в разделе «Джон >», но их следует сгруппировать аналогично приведенному выше.

Надеюсь, объяснение понятно.Требования немного свободные.Только разумные, чтобы человек мог поискать по дереву и найти то, что ему нужно.

Прямо сейчас у меня есть интересный SQL, который ищет поисковый запрос в строке, определяет его позицию, выполняет подстроку, группирует и упорядочивает, чтобы получить вышеуказанные результаты, но работает недостаточно хорошо.

Я пытаюсь решить эту проблему в типичном стеке LAMP (кроме Oracle).Это не общий хостинг, поэтому я имею полный контроль над сервером.Данные меняются небольшими порциями каждые несколько недель, и результаты поиска могут оставаться устаревшими в течение разумного периода времени (например, не исключено использование cron, обновляющего поисковый индекс).

Answer 1

Ага.Извините, я не смог описать свою проблему.В любом случае, вот решение, которое я придумал.

По сути, создайте вторую таблицу из таблицы с тремя столбцами, которая будет содержать все различные значения для каждого последующего уровня иерархии, а также столбец для указания глубины этой строки в иерархии.

Например.От mytable(A, B, C), создавать search_t(A, B, C, level)

Итак, с помощью «Один > Два > Три» вы создаете 3 ряда (A, B, C, уровень):

• «Один», ноль, ноль, 1
• «Один», «Два», ноль, 2
• «Один», «Два», «Три», 3

При поиске вы можете ограничить уровень, выбрав значение уровня и указав значения для столбцов верхнего уровня:

WHERE A='One' and level > 1 and (B like '%t%' or C like '%t')

Это может быть немного упрощено и обобщено, если вы создадите search_str столбец и выполните LIKE вместо этого сопоставление с этим.

WHERE A='One' and level > 1 and search_str like '%t%'

Оглядываясь назад, можно сказать, что это, вероятно, было бы более очевидным, если бы данные уже находились в модели списка смежности.