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

Question

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

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

Answer 1

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

Рассматривали ли вы добавление индексация столбцов в базу данных MySQL?Поддерживаются хэш, b-дерево и r-дерево.

MySQL также может быть реплицирован и кластеризован для высокой масштабируемости.

Answer 2

Вы можете попробовать Trie или Patricia-trie . Второе более эффективно использует память. Также здесь вы можете найти сравнение 2 структур данных, TreeSet], база данных в памяти и их производительность.

Answer 3

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