Где самый быстрый поиск?

Question

[Роман Вакульчик]

Необходимо будет искать по регуляркам в какой-нибудь структуре данных. Самое главное скорость поиска. Где же будет самый быстрый поиск: SQL (можно использовать только Postgresql), JSON, либо что-то другое? Размер json до 3 Мбайт

Comments

[Сергей Протько]

Зависит от объема данных и специфики задачи, не находите?

[Роман Вакульчик]

Сергей Протько: Так расскажите, если знаете, когда что применяется

Answer 1

[Сергей Протько]

Роман Вакульчик: начнем с того что поиск в базе регулярками это плохая идея. Есть всякие там сфинксы, эластик серчи и т.д. у которых есть вполне себе приличная индексация текста.

Опишите задачу более конкретно. Пока все варианты медленнее и самый быстрый - держать данные в памяти (СУБД, массивы, как хотите) и искать там. Сложность поиска будет все-равно O(N).

Comments

[Роман Вакульчик]

Надо будет по заданной строке найти совпадение в базе данных и вернуть соответствующий title. Пока имеется json размером 3 KB, базы пока нет. Понятно что скорость поиска O(N), но меня волнует вопрос, что будет быстрее: json (распарсить, найти строку и т.д) или SQL

[Сергей Протько]

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

p.s. 3-х килобайтый json проще загрузить один раз в память разобранным и перебирать в коде.

[Роман Вакульчик]

Сергей Протько: сильно не знаком с эластик, но будет ли он эффективен, если одинаковые запросы никогда не будут повторяться

[Сергей Протько]

Роман Вакульчик: да, в этом случае индекс не поможет.... тогда самый быстрый вариант на самом деле хранить весь JSON в памяти и рекурсивно его обходить постоянно. Можно это дело распаралелить, можно еще кучу всего придумать... но не зная задачи (что за JSON, вложенность, что содержит и что ищем) больше сказать ничего не могу.

Если данных реально 3 килобайта - то можно просто решение в лоб. На таких объемах данных разницы вы не сильно почувствуете.

[Пума Тайланд]

Сергей Протько: почему он вдруг не будет эффективен то ? он будет искать по индексу, а там ситуация намного лучше чем O(n)
не вспомню как там все устроено но даже в худшем случае там будет максимум o(log(n))

да на 3 кб оно везде будет быстро работать

[Сергей Протько]

Пума Тайланд: для регулярок разве работают индексы? Да и толку от индексов если повторений не будет судя по словам автора.

[Пума Тайланд]

Сергей Протько: у вас вроде не регулярки а поиск строки и какое то совпадение, что вообще легко ложится в сфинкс.
Повторения это кеширование, индекс это дерево. Это две не связанные никак друг с другом вещи. Это как сказать я поеду на такси в аэропорт чтобы не опоздать, нет не едь на такси ведь они груши. Вот точно такой же смысл в вашей фразе как в этой.

[Сергей Протько]

Пума Тайланд: сори, был пьян.

[Роман Вакульчик]

Анатолий K: задача выполнить это с помощбю rails, так как никакой вьюшки не будет, а только post запросы

Answer 2

[kompi]

В данном случае, если уже стоит postgresql, я бы использовал его.