NoSQL或YesSQL

Question

我有一个庞大的词典:

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

单词的数量真的很大.

现在我希望能够非常快速地检索所有values被指出的东西word.word是字符串值.

什么是最好的工具？我想到了简单的数据库解决方案,但DBA的人说它不会真的很快.

所以,在我打开Cormen的书之前,是否有一些现成的解决方案可以解决这个问题？

Answer 1

查看键/值存储引擎,例如Berkeley DB.他们在这种事情上非常快.

Answer 2

在 RDMS (YesSQL) 中，您很可能会在所有记录LIKE上使用或=运算符搜索值，即搜索将花费 O(n)。您实际需要的是一种称为倒排索引的数据结构，它允许您在 O(1) 中找到所需值的列表。有关结构和算法的描述，请参阅维基百科文章，有关即用型工具的信息，请继续阅读。

在Lucene / Solr、Sphinx （顺便说一下，它支持多个数据库作为数据源）等搜索引擎以及Berkeley DB或Apache Cassandra等一些键值存储中，有大量倒排索引的实现。搜索引擎和键值存储之间的区别在于：

1. 搜索引擎更直接地实现倒排索引（据我所知，键值数据库使用类似BigTable的结构，比倒排索引本身复杂得多）。
2. 搜索引擎有大量的文本分析工具（解析、词干提取）。我不知道你是否真的需要它，但如果你需要，请使用搜索引擎。
3. 键值数据库是真正的数据库。即，与搜索引擎不同，它们具有真实的数据类型，而不仅仅是字符串。此外，一些这样的数据库（例如Berkeley DB）可以存储编程语言本机数据类型，而无需将它们转换为任何内部格式。因此，如果您需要一个具有所有功能的真实数据库，请使用键值存储。

另请注意，倒排索引的结构非常简单，因此如果前面的选项都不适合您，您可以轻松地自己实现它。