算法 – NoSQL或YesSQL

发布时间：2020-12-13 13:31:20 所属栏目：百科来源：网络整理

导读：我有一个庞大的单词词典： "word1" = [value1]"word2" = [value2]"word3" = [value3,value2]..."word400000000" = [value455,value3435,...,value3423] 单词的数量真的很大. 现在我希望能够非常快速地检索所有用词指向的值.单词是字符串值. 什么是最好的工具

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

"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 DB或Apache Cassandra).搜索引擎和密钥之间的区别 – 值商店在：

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!