[每日五分钟学习大数据] 系列 No.20
上一篇文章简单地介绍过了 ES 的相关概念, 还没看的同学快去复习下:
ES 是什么? 看完这篇就不要再问这种低级问题了!
文章的最后提到了倒排索引, 不知道有没有勾起大家的好奇心, ES 的索引是怎么做, 为什么他会被广泛地叫做搜索引擎而不是数据库? 根源在它的索引, 所以这一篇带你一探究竟.
言归正传, 说起索引肯定是绕不开经典的 B-Tree, 来看两张图简单回顾下你们大学的课本内容.
B-Tree
B+Tree
B+Tree 是 B-Tree 的优化, 两者的区别由图应该是可以看得比较清楚的.
非叶子节点只存储键值信息.
所有叶子节点之间都有一个链指针.
数据记录都存放在叶子节点中.
笼统的来说, b-tree 索引是为写入优化的索引结构. 所以当我们不需要支持快速的更新的时候, 可以用预先排序等方式换取更小的存储空间, 更快的检索速度等好处, 其代价就是更新慢. 要进一步深入的化, 还是要看一下 Lucene 的倒排索引是怎么构成的.
看个具体的倒排索引实例, 写入如下三条数据;
ID
| Name
| Sex
|
1
| Kate
| Female
|
2
| John
| Male
|
3
| Bill
| Male
|
ID 是 Elasticsearch 自建的文档 id, 那么 Elasticsearch 建立的索引如下:
Name
Term
| Posting List
|
Kate
| 1
|
John
| 2
|
Bill
| 3
|
Sex
Term
| Posting List
|
Female
| 1
|
Male
| [2,3]
|
问题来了, 在 Term 量非常大的时候, 怎么快速找到目标 Term 的位置? 来看看 ES 是怎么做的.
Term Dictionary: 把 Term 按字典序排列, 然后用二分法查找 Term (存在磁盘)
Term Index: 是 Term Dictionary 的索引, 存 Term 的前缀, 和与该前缀对应的 Term Dictionary 中的第一个 Term 的 block 的位置, 找到这个第一个 Term 后会再往后顺序查找, 直到找到目标 Term.(存在内存)
Term Index 的压缩
所以, 理论上 Term Index 的数据结构就是:
Map<Term 的前缀, 对应的 block 的位置>
但是 Term 量大的情况下同样会把内存撑爆. 所以有了基于 FST 的压缩技术.
Finite State Transducers(FST) : 有穷状态转换器, Term Index 采用的压缩技术.
举个例子:
Map["cat" -> 5, "deep" -> 10, "do" -> 15, "dog" -> 2, "dogs" -> 8 ]
每条边有两条属性, 一个表示 label(key 的元素, 上图有点问题, 应该是指向 a 的), 另一个表示 Value(out).
每个节点有两个属性, Final=true/false(有 key 再这个节点结束则为 true); final 为 true 时, 还有个 FinalOut,FinalOut=entry 的 value 值 - 该路径 out 值之和.
举个例子: 8 号节点, 对应的 entry 的 key 是 do,value 是 15, 而该路径 out 值之和是 2, 所以 FinalOut=15-2=13
out 值怎么来的?
当只有一条数据写入时如 cat, 则第一个字节即 "c" 的 out 值就等于该 entry 的 value 值即 "5";
当 deep 写入时因为后面 d 开头的数据还没写, 所以 "d" 的 out 值就是 "10";
当 do 写入时, 因为 "d"="10", 所以 "o"="15"-"10"="5"
当 dog 写入时, 因为 "d"="10","o"="5", 已经超过了 dog 的值 "2", 此时, 会把 "d" 设为 "2","o" 设为 "0", 这样才能满足 dog="2" 的情况.
但是, 这样 deep 和 do 的 out 值就要重新分配了
deep 的整条路径和为 "10", 已知 "d"="2", 所以 "e" 承包剩下的 "8".
do 的整条路径和为 "15", 已经 "d"="2","o"="0", 没有 label 了, 所以 FinalOut=15-2-0=13.
由上所述, 不难得出, FST 查询的复杂度时 O(1), 能快速定位到目的 Term 前缀的 Block 位置.
Posting List 的压缩
关键在于: 增量编码压缩, 将大数变小数, 按字节存储.
原理就是通过增量, 将原来的大数变成小数仅存储增量值, 再精打细算按 bit 排好队, 最后通过字节存储.
BitMaps
假设有某个 posting list: [1,3,4,7,10]
对应的 bitmap 就是: [1,0,1,1,0,0,1,0,0,1]
用 0/1 表示某个值是否存在, 比如 10 这个值就对应第 10 位, 对应的 bit 值是 1, 这样用一个字节就可以代表 8 个文档 id, 旧版本 (5.0 之前) 的 Lucene 就是用这样的方式来压缩的, 但这样的压缩方式仍然不够高效, 如果有 1 亿个文档, 那么需要 12.5MB 的存储空间, 这仅仅是对应一个索引字段(我们往往会有很多个索引字段).Bitmap 的缺点是存储空间随着文档个数线性增长.
Roaring bitmaps
将 posting list 按照 65535 为界限分块, 比如第一块所包含的文档 id 范围在 0~65535 之间, 第二块的 id 范围是 65536~131071, 以此类推.
再用 <商, 余数> 的组合表示每一组 id, 这样每组里的 id 范围都在 0~65535 内了, 剩下的就好办了, 既然每组 id 不会变得无限大, 那么我们就可以通过最有效的方式对这里的 id 存储.
short[] 占的空间: 2bytes(65535 = 2^16-1 是 2bytes 能表示的最大数)
bitmap 占的空间: 65536/8 = 8192bytes
当 block 块里元素个数不超过 4096, 用 short[], 因为 4096 个 short[]才等于 8192bytes; 而一个 bitmap 就等于 8192bytes 了, 虽然它能存 65536 个元素.
联合索引
联合索引通俗地说就是找到满足多个搜索条件的文档 ID. 那么这种场景下, 倒排索引如何满足快速查询的要求呢?
利用跳表 (Skip list) 的数据结构快速做 "与" 运算, 或者
利用上面提到的 bitset 按位 "与"
先看看跳表的数据结构:
将一个有序链表 level0, 挑出其中几个元素到 level1 及 level2, 每个 level 越往上, 选出来的指针元素越少, 查找时依次从高 level 往低查找, 比如 55, 先找到 level2 的 31, 再找到 level1 的 47, 最后找到 55, 一共 3 次查找, 查找效率和 2 叉树的效率相当, 但也是用了一定的空间冗余来换取的.
假设有下面三个 posting list 需要联合索引:
如果使用跳表, 对最短的 posting list 中的每个 id, 逐个在另外两个 posting list 中查找看是否存在, 最后得到交集的结果.
如果使用 bitset, 就很直观了, 直接按位与, 得到的结果就是最后的交集.
>> 想学大数据? 点击找大叔! <<
智能人工推荐:
选方向? 大数据的职位你了解多少
戏说数据中台 - 大佬玩概念, 小弟写接口
在阿里一年, 我颠覆了曾经坚信不疑的技术思维
Spark 比 MR 快是因为在内存中计算? 错!
觉得有价值请关注 ▼
来源: http://www.tuicool.com/articles/iURZ7b2