以前
熟悉的复杂的树无外乎2-3-4树到红黑树… 说实话RBTree的代码已经没法写出来了…因为理解都比较费劲,然后就是之前花了一整天研究的B树家族. 包括B/B+/B* 以及没有研究的三维R树. (其实还有个很常用的LST..google-paper的,以及SSTables)红黑树主要是用于hash表中,其实我理解的hash就是一维桶排序的一种进化(二维桶排不太一样.) 然后桶里面的结构多了,开始用链表.数据多了效率低了,就换成树,慢慢换成boss红黑树..
B树家族则主要用于计算机存储数据以及索引里面. 但是接触ES之后学到一个新的词…倒排索引,一定程度让我很好奇,索引其实我简单理解就是桶,只不过桶有低级高级之分.那么倒排的桶到底是什么样的呢? 上一篇入门ES的文章说过,Index是ES的核心. 其中我们理解的索引 = 倒排索引,自然是重中之重了.参考文章
0x00.什么是倒排索引
首先索引本质无外乎用空间换时间,给一个额外的映射表,然后我们来看看其中ES做了什么手脚.首先假设有如下一组es数据:
| id | name | gender | age |
|---|---|---|---|
| 1 | jin | xy | 22 |
| 2 | yin | xx | 19 |
| 3 | tong | xx | 103 |
其实这样看就是传统的关系型db.只不过es是用对象方式存储的.
0x01.数据结构与算法(重点)
从整体上说,先构建索引的时候都是排序后放入字典树(trie tree),最后利用FST(有限状态转换机)做前后缀压缩?然后根据单查还是组合查询分为:
- 单查
- 两个单查后的结果实时或后续取∩,这又有两种做法
- 基于SkipList(跳表),然后做压缩 .关于跳表详细实现待补.
- 基于改良后的Bitmap
这里出现了几个数据结构: (依次讲解)
- trie tree
- skip list
- roaming-bitmap
- FST(本质是有带权的向无环字典图?)
- FOR压缩
0x02.算法复杂度
这里同时分析一下时间跟空间复杂度. 然后之后对比一下B+树的.看看为什么比mysql快呢?
排序,因为term也就是桶的值不只是数字.所以按通用算,至少是O(nlogn)平均时间
不过这也不能这么简单粗暴的下结论,因为我们可以发现用字段的可能值作为桶其实是不多的. 就好比常见年龄字段,取值范围是固定的,兴趣这种很多也是共同的.小众的可以单独抽出来走一次O(n),这时候term的排序时间就可能会小不少
综合的二分查找. O(logn).放入字典树中.这里只放入前缀部分,然后做FST压缩.空间全丢内存.消耗应该怎么算? S(n/a)? – a代表前缀长度
如果是组合条件查询,需要开个跳表或者位图. (貌似因为压缩效率高,主要用的跳表)
- 如果是用跳表,时间复杂度最低接近二分? O(logn),然后多消耗空间是
层数×(段数递减的数列?)×2? - 如果是用位图,那么差不多占用空间从每个int 4字节转为了1bit.相当于减少了32倍.(接近),但是数据转为bit所需时间? 时间提升?待补充..
- 如果是用跳表,时间复杂度最低接近二分? O(logn),然后多消耗空间是