reverse prefix search
Nov. 16th, 2015 01:53 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
109столкнулся с проблемой, из которой, кажется, получится хороший вопрос для интервью на продвинутого девелопера.
проблема такая: есть относительно длинная строка, например "lasdkfbvaouvyaou". и есть в базе таблица с миллиардом записей, в которой хранятся потенциальные подстроки, например "la", "las", "lasdk". надо их все найти как можно быстрее.
поверхностное гуглование нашло только кошмарное решение, гордо опубликованное на http://www.loganbibby.com/2011/03/reverse-pattern-matching-in-mysql
это решение сканирует всю таблицу, весь миллиард, вне зависимости от существования индексов.
чисто датабазное решение, которое приходит в голову, это поиск по индексу для каждой подстроки типа "l", "la", "las", и так далее. это даёт O(M log N), где M - количество букв в строке, а N - количество записей в таблице.
если надо лучше, то придётся в памяти строить trie, и делать по нему лукап. для дополнительного ускорения, вместо традиционного trie, где дети лежат в списке, можно держать детей в Dictionary, тогда будет чуть быстрее (насколько - непонятно, зависит от статистики), но памяти съест больше.
проблема такая: есть относительно длинная строка, например "lasdkfbvaouvyaou". и есть в базе таблица с миллиардом записей, в которой хранятся потенциальные подстроки, например "la", "las", "lasdk". надо их все найти как можно быстрее.
поверхностное гуглование нашло только кошмарное решение, гордо опубликованное на http://www.loganbibby.com/2011/03/reverse-pattern-matching-in-mysql
это решение сканирует всю таблицу, весь миллиард, вне зависимости от существования индексов.
чисто датабазное решение, которое приходит в голову, это поиск по индексу для каждой подстроки типа "l", "la", "las", и так далее. это даёт O(M log N), где M - количество букв в строке, а N - количество записей в таблице.
если надо лучше, то придётся в памяти строить trie, и делать по нему лукап. для дополнительного ускорения, вместо традиционного trie, где дети лежат в списке, можно держать детей в Dictionary, тогда будет чуть быстрее (насколько - непонятно, зависит от статистики), но памяти съест больше.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
(no subject)
Date: 2015-11-17 07:43 pm (UTC)> Потребуется выполнить не более N запросов.
о, отлично. это тоже M log N в моей терминологии, но основание логарифма побольше, потому что индекс уже.
> А разве для этого не потребуется просканировать всю таблицу?
ну имеется в виду, что трие строится один раз в начале, и потом отвечает на много запросов, так что это не считается.