算法 – NoSQL或YesSQL

我有一个庞大的单词词典:

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

单词的数量真的很大.

现在我希望能够非常快速地检索所有用词指向的值.单词是字符串值.

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

那么,在我打开Cormen的书之前,是否有针对该问题的一些现成解决方案?

在RDMS(YesSQL)中,您很可能在所有记录上使用LIKE或=运算符搜索值,即搜索将采用O(n).您实际需要的是一个名为 inverted index的数据结构,它允许您在O(1)中查找所需值的列表.有关结构和算法的描述,请参阅维基百科文章,对于即用型工具,请继续阅读.

搜索引擎中存在大量反向索引的实现,如Lucene/Solr,Sphinx(顺便提一下,支持多个数据库作为数据源),以及一些键值存储(如Berkeley DBApache Cassandra).搜索引擎和密钥之间的区别 – 值商店在:

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

另请注意,反向索引的结构非常简单,因此如果以前的选项都不适合您,您可以自己轻松实现它.

相关文章
相关标签/搜索