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

Question

Допустим, у меня есть иерархия FirstName> MiddleName> LastName (~ 10k строк, для вопроса). Это означает, что у вас может быть строка «John> Mary-Anne> Eddy» или «Eddy> John> Jacob». Дело в том, что иерархия имеет мало смысла и очень чужда пользователю (в отличие, скажем, от страны> Состояние> Городская структура).

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

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

• John> Allen> Александр
• John> Allen> Burschawitz
• Джон> Аллен ... повторить 100 раз ...

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

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

• John> Allen> *
• Джейсон> John> Смит
• Mike> John> *
• Mary> Елена> Johnason

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

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

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

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

Answer 1

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

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

E.g.Из mytable(A, B, C), создать search_t(A, B, C, level)

Так, с "Один> Два> Three", вы создаете 3 строки (A, B, C, уровень):

• "One", NULL, NULL, 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%'

В ретроспективе, это, вероятно, было более очевидным, если данные уже были в модели смежности списка.