的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作業。也許卡桑德拉將是最好的。