NoSQL или YesSQL

Question

У меня есть огромный словарь слов:

"word1" => [value1]
"word2" => [value2]
"word3" => [value3, value2]
...
"word400000000" => [value455, value3435, ..., value3423]

количество слов действительно велико.

Теперь я хочу иметь возможность быстро и быстро найти, все values, на которые указывает word.word - это строковое значение.

Какие инструменты лучше всего использовать?Я думал о простом решении БД, но ребята из DBA сказали, что оно не будет работать очень быстро .

Итак, прежде чем я открою книгу Кормен , есть ли какая-тоготовые решения для этой проблемы?

Answer 1

Посмотрите на механизмы хранения ключей / значений, такие как Berkeley DB.Они очень быстры в таких вещах.

Answer 2

В СУБД (YesSQL) вы, скорее всего, будете искать значения с помощью LIKE или = операторов на всех записях , т.е. поиск займет O (n).Что вам действительно нужно, так это структура данных с именем инвертированный индекс , которая позволяет найти список необходимых значений в O (1).Описание структуры и алгоритмов см. В статье в Википедии, готовые к использованию инструменты продолжайте читать.

Существует множество реализаций инвертированного индекса в поисковых системах , подобных Lucene / Solr , Sphinx (которые, поКстати, поддерживает несколько баз данных в качестве источника данных), а также в некоторых хранилищах ключей-значений , таких как Berkeley DB или Apache Cassandra .Различие между поисковыми системами и хранилищами значений ключей заключается в том, что:

1. Поисковые системы реализуют инвертированный индекс более непосредственно (AFAIK, базы данных значений ключей используют BigTable -подобные структуры, которые намного сложнее, чем сам перевернутый индекс).
2. В поисковых системах имеется множество инструментов для анализа текста (синтаксический анализ, определение поочередно) .Я не знаю, действительно ли вам это нужно, но если вам это нужно, используйте поисковые системы.
3. Базы ключей-значений являются реальными базами данных.Т.е. в отличие от поисковых систем они имеют реальных типов данных, а не только строки .Более того, некоторые из таких БД (например, Беркли БД) могут хранить родные типы данных языка программирования без преобразования их в какой-либо внутренний формат.Поэтому, если вам нужна реальная база данных со всеми функциями, используйте хранилища значений ключей.

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

Answer 3

Это действительно зависит от того, какое поведение вы хотите.Если вы просто хотите иметь возможность выполнять точный текстовый поиск, то, вероятно, отличная идея - хеш-таблица.Он ожидал O (1) поиска, что примерно так же быстро, как вы собираетесь получить.

Если вам нужны элементы в отсортированном порядке (например, так что вы можете перебирать их в разумном порядке), то одним из множества сбалансированных деревьев поиска может быть хороший кандидат;например, красно-черное дерево или дерево AVL.

Если вы работаете с огромным набором данных, который не может вписаться в основную память, тогда очень хорошим выбором может быть B-дерево, который является типом сбалансированного бинарного дерева поиска, которое минимизирует количество операций чтения с диска, необходимых для поиска данного элемента.Большинство систем баз данных используют некоторые разновидности B-деревьев для поиска.

Answer 4

Если вы знаете , что вам нужно будет искать значения только по словам, а не наоборот, используйте простое хранилище Key-Value. Может быть, Redis будет лучше.

Если вы думаете, что вам когда-нибудь понадобится искать по значениям, вам, скорее всего, понадобятся вторичные индексы или автономные задания MapReduce. Может быть, Кассандра будет лучше.

Answer 5

Вы можете использовать cassandra (http://cassandra.apache.org/). Легко начать, имеет довольно много документации и действительно быстрое решение вашей проблемы.

Надеюсь, это поможет,