的NoSQL或YesSQL

Question

我有话的巨大词典：

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

数量的单词是非常大的。

现在我希望能够检索到所有正在被word指向的values。 word是字符串值。

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

因此，在我打开Cormen的书之前，是否有一些针对该问题的现成解决方案？

Answer 1

在RDMSs（YesSQL），你将最有可能与LIKE或=运营商在所有记录搜索值，即搜索将耗费为O（n）。您实际需要的是一种称为inverted index的数据结构，它允许您在O（1）中查找所需值的列表。有关结构和算法的说明，请参阅维基百科文章，以了解随时可用的工具。

有大量反向索引的实施方式的在搜索引擎像Lucene/Solr，Sphinx（其中，顺便说一下，支持几个数据库作为数据源），以及在一些键值存储像Berkeley DB或Apache Cassandra。搜索引擎和关键值存储之间的区别在于：

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

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

Answer 2

这真的取决于你想要的行为。如果你只是想做一个精确的文本搜索，那么一个哈希表可能是一个非常好的主意。它预计O（1）查找，这与您将要获得的速度一样快。

如果你需要排序顺序的元素（例如，所以你可以按照合理的顺序遍历它们），那么无数的平衡搜索树中的一个可能是一个很好的候选者;例如，红黑树或AVL树。

如果你正在处理一个庞大的数据集，而这些数据集不能全部放入主内存中，那么一个非常好的选择可能是一个B树，它是一种平衡二叉搜索树，可以减少磁盘读取需要找到一个给定的元素。大多数数据库系统使用一些B树来进行查找。

Answer 3

查看关键/值存储引擎，如Berkeley DB。他们在这种事情上非常快。

Answer 4

您可以使用cassandra（http://cassandra.apache.org/）。易于启动，具有非常多的文档，并且是针对您的问题的非常快速的解决方案。

希望这有助于

Answer 5

如果你知道，你只需要基于单词而不是其他方式搜索值，使用一个简单的键值存储。也许Redis将是最好的。

如果您认为您将需要根据这些值进行搜索，那么您可能需要二级指标或离线MapReduce作业。也许卡桑德拉将是最好的。