NingG +

Elastic 系列:Lucene 的索引结构和查询效率

0.概要

焦点问题:SQL 检索效率(MySQL 为例)和 NoSQL 检索效率(ES 为例)

1.ElasticSearch 底层数据结构

ElasticSearch 通过 Lucene 的倒排索引技术,实现比关系型数据库(MySQL)更快的过滤。

焦点问题

当我们不需要支持「快速的更新」的时候,可以用「预先排序」等方式:

1.1.Lucene 倒排索引

Lucene 倒排索引,具体的索引层级:

具体几个要点:

  1. 词项索引term index
    1. 使用技术:字典数(Trie Tree)、压缩技术、内存存储
    2. 目标:接近 O(1) 时间复杂度,定位「词项-字典」对应 block 的 offset
    3. 注意:词项索引,只需要映射到 block,不需要映射到每一个词项
  2. 词项字典term dictionary
    1. 使用技术:分 block 存储,同一个 block 上,词项共享「同一个前缀」
    2. 目标:定位到最终的 term
  3. 倒排列表posting list
    1. 使用技术:分块差值编码,再对每块进行 bit 压缩存储。
    2. 目标:有序 docId,高效压缩,放入内存

为了说明 Lucene 的数据结构,以下面的原始数据为例:

DocId 年龄 性别
1 18
2 20
3 18

其中的数据模型:

可以看到:

  1. term词项:18,20 这些叫做 term,关键字,搜索的关键字;
  2. Posting list倒排-列表:而 [1,3] 就是 Posting list,Posting list 就是一个 int 的数组,存储了所有符合某个 term 的「文档 id」。

1.2.term dictionary 和 term index

那么什么是 term dictionary 和 term index?

假设我们有很多个 term,比如:

如果按照这样的顺序排列,找出某个特定的 term 一定很慢,因为 term 没有排序,需要全部过滤一遍才能找出特定的 term。排序之后就变成了:

这样我们可以用二分查找的方式,比全遍历更快地找出目标的 term。这个就是 term dictionary

有了 term dictionary 之后,可以用 logN 次磁盘查找得到目标。但是磁盘的随机读操作仍然是非常昂贵的(一次 random access 大概需要 10ms 的时间)。所以尽量少的读磁盘,有必要把一些数据缓存到内存里。但是整个 term dictionary 本身又太大了,无法完整地放到内存里。于是就有了 term index

term index 有点像一本字典的大的章节表。比如:

如果所有的 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 树。

  1. 这棵树不会包含所有的 term,它包含的是 term 的一些前缀。
  2. 通过 term index 可以快速地定位到 term dictionary 的某个 offset,然后从这个位置再往后顺序查找。
  3. 再加上一些压缩技术(搜索 Lucene Finite State Transducers) term index 的尺寸可以只有所有 term 的尺寸的几十分之一,使得用内存缓存整个 term index 变成可能。

1.3.ElasticSearch 查询效率

从上述分析可知:

关于 Lucene,额外值得一提的两点是:

后续内容

2.参考资料

3.附录:思考一个场景

焦点问题:SQL 检索效率(MySQL 为例)和 NoSQL 检索效率(ES 为例)

场景描述

  1. 数据量: n kw
  2. 检索条件: status字段等于 0,其中,status 可能取值为 0-9
  3. MySQL 上已经针对 status 字段建立了索引,ES 也已经建立索引
  4. 查询结果为 limit 10,10 条记录的所有字段都输出,而不是 select count(0) 统计计数

我的看法: ES 更快

Think

几个疑问,后续思考下:

同类文章:

微信搜索: 公众号 ningg ,即可联系我

Top