本文主要是介绍关于倒排索引表的总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
最近在研究elasticsearch的技术栈 ,发现ES底层是基于luence技术进行检索,检索的原理是倒排索引表。那么什么是倒排索引表呢?在知乎上看到一个讲解elasticsearch的倒排索引表的帖子。
链接是:https://zhuanlan.zhihu.com/p/33671444
为什么说elasticsearch的倒排索引表的检索速度是比关系型数据库的索引查新更快呢?首先,关系型数据库的底层索引的数据结构是b-tree树, B-tree树最大的缺点就是牺牲了一定的读取的效率换来更高的写入效率。当我们不需要支持快速的更新的时候,可以用预先排序等方式换取更小的存储空间,更快的检索速度等好处,其代价就是更新慢。要进一步深入的化,还是要看一下Lucene的倒排索引是怎么构成的。
首先介绍一个简单的例子。
比如有如下的数据:
在es中每一行对应着一个document, 每个文档都是有docid的,而且我们现在是针对document来建立倒排索引操作。
这里面的倒排索引是针对每一个字段 其中18,20叫做term ,[1,2]就是post list.
那么term index 和term dictionary 是什么呢?
假设我们有很多个term,比如:
Carla,Sara,Elin,Ada,Patty,Kate,Selena
如果按照这样的顺序排列,找出某个特定的term一定很慢,因为term没有排序,需要全部过滤一遍才能找出特定的term。排序之后就变成了:
Ada,Carla,Elin,Kate,Patty,Sara,Selena
这样我们可以用二分查找的方式,比全遍历更快地找出目标的term。这个就是 term dictionary。有了term dictionary之后,可以用 logN 次磁盘查找得到目标。但是磁盘的随机读操作仍然是非常昂贵的(一次random access大概需要10ms的时间)。所以尽量少的读磁盘,有必要把一些数据缓存到内存里。但是整个term dictionary本身又太大了,无法完整地放到内存里。于是就有了term index。term index有点像一本字典的大的章节表。比如:
A开头的term ……………. Xxx页
C开头的term ……………. Xxx页
E开头的term ……………. Xxx页
如果所有的term都是英文字符的话,可能这个term index就真的是26个英文字符表构成的了。但是实际的情况是,term未必都是英文字符,term可以是任意的byte数组。而且26个英文字符也未必是每一个字符都有均等的term,比如x字符开头的term可能一个都没有,而s开头的term又特别多。实际的term index是一棵trie 树:
例子是一个包含 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的 trie 树。这棵树不会包含所有的term,它包含的是term的一些前缀。通过term index可以快速地定位到term dictionary的某个offset,然后从这个位置再往后顺序查找。再加上一些压缩技术(搜索 Lucene Finite State Transducers) term index 的尺寸可以只有所有term的尺寸的几十分之一,使得用内存缓存整个term index变成可能。整体上来说就是这样的效果。
现在我们可以回答说“为什么elasticsearch/Lucene 比mysql的检索速度快了?” 其实对于mysql来说的话 他缺少了term index这一层, 在写入数据的时候是按照b-tree的结构进行排序写入磁盘的。当检索一个term的时候需要若干次的磁盘random access操作这样效率就比较低(一次random access的时间消耗大约是10ms)。然而对于Lucene来说的话 分装了一层term index,并且term index按照trie树的结果在内存中,从term index查到对应的term dictionary的block位置之后,再去磁盘上找term,大大减少了磁盘的random access次数。
额外值得一提的两点是:term index在内存中是以FST(finite state transducers)的形式保存的,其特点是非常节省内存。Term dictionary在磁盘上是以分block的方式保存的,一个block内部利用公共前缀压缩,比如都是Ab开头的单词就可以把Ab省去。这样term dictionary可以比b-tree更节约磁盘空间。
关于elasticsearch数据压缩的技术---"增量编码压缩 就是将大数变成小数 按照字节存储"
这篇关于关于倒排索引表的总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!