Быстрый, масштабируемый поиск строк

У меня есть набор из 5 миллионов строк. Они хранятся в одной таблице MySQL MySQL. Мое приложение должно выполнять поиск и проверять, задана ли данная строка в наборе. Конечно, это можно сделать с помощью HashSet (на Java). Но вместо того, чтобы создавать собственное решение, мне было интересно, существуют ли какие-либо существующие широко используемые проверенные решения? Это похоже на общий сценарий. Решение должно быть масштабируемым (набор может увеличиться более чем на 5 миллионов), иметь отказоустойчивость (возможно, распределенную) и хорошо работать под огромным количеством запросов. Какие-либо предложения?Быстрый, масштабируемый поиск строк

Обновление: Мое приложение также может запросить проверку наличия заданного набора строк в глобальном (5 миллионов экземпляров).

источник

2010-09-29 talonx

Возможно, я не понимаю, что вы подразумеваете под «выполнением поиска» и «проверьте, задана ли данная строка в наборе» - не это просто то, для чего используется оператор выбора SQL? Отказоустойчивость и масштабирование также являются более или менее нормальными функциями РСУБД. – Sorpigal

Tries используются для быстрого поиска строк. Они намного эффективнее памяти, чем hashtables/hashsets, и не намного медленнее. – leppie

@Sorpigal: Да, но обычные запросы RDBMS не достаточно быстры. Я также обновил свой вопрос с точным сценарием. Надеюсь, что это очистит. – talonx

Вы можете попробовать Trie или Patricia-trie .Отель второй больше памяти efficient.Also here вы можете найти сравнение 2 структур данных [TRIE, TreeSet], В памяти базы данных и их производительность.

источник

2010-09-29 11:35:10 Emil

сообщение перед проектом Trie не очень обнадеживает - «Обратите внимание на любых посетителей, это прекрасный код SAMPLE, но не производственный код. Он был написан неопытным программистом (мне в то время) за один вечер». – talonx

В то время как Trie может быть лучшим решением, двоичный поиск в отсортированном списке строк также должен хорошо выполнять время работы.

источник

2010-09-29 11:47:03 michid

Попробуйте memcached, высокопроизводительную систему кеширования с распределенной памятью. Вы просматриваете, используя хэши ключей/значений. Facebook uses memcached, как и многие другие высоко масштабируемые сайты. Нужно хранить больше строк? Просто добавьте в кластер больше memcached-экземпляров. Кроме того, вы можете использовать в двухуровневой системе кэширования, где вы сначала запрашиваете memcached, если пропустить кеш, а затем запросить полную базу данных.

Рассматривали ли вы добавление column indexing в свою базу данных MySQL? Поддерживаются hash, b-tree и r-tree.

MySQL также может быть replicated and clustered для высокой масштабируемости.

источник

2010-09-29 11:51:54 burkestar

Как это решить проблему? – reinierpost

Это распределенная система хэширования для эффективного поиска ключей/значений. – burkestar

Быстрый, масштабируемый поиск строк

ответ

Смежные вопросы