Lucene的索引结构包含三部分

Term Index（前缀树用于快速查找词项），Term Dictionary（存储词项及其关联信息），和Posting List（包含某词项的文档ID列表）。

倒排索引通过分词创建文档与词项的映射。

联合索引查询时，两个Posting List通过skip list或bitset进行合并。

Lucene还使用FST优化内存和Roaring Bitmap压缩文档存储，并通过嵌套文档减少文档数。

相比MySQL，Lucene通过内存缓存加快检索。

01.倒排索引原理

0、Lucene索引构成

1）索引构成

• Lucene索引由下面三部分构成构成

• 1）Term Index（词项索引）

  • Term Index是一个索引结构，用于快速查找Term Dictionary中的词项
  • Term Index通常是用Trie树（也称为 前缀树，字典树）实现的
    • 在Trie树中，每个节点代表一个字符串（前缀），每条边代表一个字符
    • 从根节点到叶子节点的路径代表一个完整的字符串
    • 当我们查找一个词项时，可以从根节点开始，沿着词项的每个字符对应的边找下去
    • 直到找到词项或确定词项不存在

• 2）Term Dictionary（词项字典）

  • Term Dictionary是所有索引词项的集合
  • 每个词项都关联着一个Posting List
  • 词项字典一般会存储词项的相关信息，如词项的文档频率等
  • 注：ES根据数据规模，动态选择使用 哈希表、跳表、还是 B+ 树

• 3）Posting List（倒排列表）

  • Posting List是包含了某个词项的所有文档的ID列表
  • 每个Posting List一般会包含词项频率、位置信息、偏移信息

2）查找过程

• ① 前缀树

  • 前缀树 通常它用于需要 前缀匹配 或 模糊查询 的场景（并不是每次查询都必须经过）

• ② 项字典（Term Dictionary）

  • 一旦通过前缀树找到了某个词项，ES 会在 词项字典 中查找这个词项的具体信息
  • 项字典 根据数据规模选择不同结构存 哈希表、跳表、还是 B+ 树，可以不使用前缀树

• ③ 倒排列表（Posting List）

  • 在找到词项后，ES 会定位到对应的 倒排列表
  • 倒排列表是倒排索引的核心部分，记录了所有文档中出现该词项的位置信息

• ④ 查询优化

  • 在查找到相关的 倒排列表 后，ES 会对符合条件的文档进行进一步处理
  • 如果查询包含多个词项（例如 AND 查询），ES 会将多个倒排列表合并
  • 在查询结果返回前，ES 会计算每个文档的相关性得分，并根据得分对文档进行排序

1、Posting List 倒排列表

[1,2,3]是Posting List（倒排列表）

• 0）我们有如下4 条文档数据

文档ID	文档内容
1	人工智能成为互联网大会焦点
2	谷歌推出开源人工智能系统工具
3	互联网的未来在人工智能
4	谷歌开源机器学习工具

• 1）分词
  • 对于文档内容，先要经过词条化处理
  • 与英文不同的是，英文通过空格分隔单词(中文需要分词工具)
  • 经过分词系统进行中文分词以后把矩阵切分成一个个的词条
• 2）给这些document建立的倒排索引如下
  • 人工，智能叫做Term（词项）
    • ES会将文档的内容分词，每个分词就是一个词项
  • [1,2,3]是Posting List（倒排列表）
    • ES会为每个词项建立一个"Posting List”
    • 倒排列表是指包含了一个词项的所有文档的ID列表
    • 第一条"[1,2,3]"，表示词项“人工”在文档1,2,3 中都出现过

词项	文档频率	倒排记录表
人工	3	1,2,3
智能	3	1,2,3
成为	1	1
互联网	2	1,3
大会	1	1
焦点	1	1
谷歌	2	2,4
推出	1	2

2、Term Index 词项索引

• Term Index是一个索引结构，用于快速查找Term Dictionary中的词项
• Term Index通常是用Trie树（也称为前缀树）实现的
  • 在Trie树中，每个节点代表一个字符串（前缀），每条边代表一个字符
  • 从根节点到叶子节点的路径代表一个完整的字符串
  • 当我们查找一个词项时，可以从根节点开始
  • 沿着词项的每个字符对应的边找下去，直到找到词项或确定词项不存在
• 下面是一个包含 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的 trie 树
  • 这棵树不会包含所有的term，它包含的是term的一些前缀
  • 通过term index可以快速地定位到term dictionary的某个offset，然后从这个位置再往后顺序查找
  • 再加上一些压缩技术term index 的尺寸可以只有所有term的尺寸的几十分之一
  • 使得用内存缓存整个term index变成可能

3、Term Dictionary 词项字典

ES 下面情况，动态选择使用 哈希表、跳表、还是 B+ 树

• 小规模数据（哈希表）
  • 可能会选择哈希表，尤其是在内存中，哈希表能够提供非常快速的查找
• 中等规模数据（跳表）
  • 跳表通常会作为一个折中选择，适合需要动态更新并且支持范围查询的场景。
• 大规模数据（B+Tree）
  • 对于需要存储大量词项并支持高效范围查询的情况
  • B+树是首选，特别是在存储在磁盘中的倒排索引部分

• Term Dictionary是所有索引词项的集合
• 每个词项都关联着一个Posting List
• 词项字典一般会存储词项的相关信息，如词项的文档频率等

4、总结

• 1）为什么 ES 比 MySQL 快
  • MySQL只有term dictionary这一层，是以b-tree排序的方式存储在磁盘上的
  • 检索一个term需要若干次的random access的磁盘操作
  • 而Lucene在term dictionary的基础上添加了term index来加速检索，term index以树的形式缓存在内存中
  • 从term index查到对应的term dictionary的block位置之后，再去磁盘上找term，大大减少了磁盘的random access次数
• 2）FST（finite state transducers）
  • term index在内存中是以FST（finite state transducers）的形式保存的，其特点是非常节省内存
  • Term dictionary在磁盘上是以分block的方式保存的，一个block内部利用公共前缀压缩
  • 比如都是Ab开头的单词就可以把Ab省去。这样term dictionary可以比b-tree更节约磁盘空间

02.如何联合索引查询

0、查询合并

• 如何过滤 age=18 AND gender=女 的文档

• 给定查询过滤条件 age=18 的过程就是先从term index找到18在term dictionary的大概位置

• 然后再从term dictionary里精确地找到18这个term，然后得到一个posting list或者一个指向posting list位置的指针

• 然后再查询 gender=女 的过程也是类似的

• 最后得出 age=18 AND gender=女 就是把两个 posting list 做一个“与”的合并

• 如何将两个索引结构合并提供了两种方法

  • 使用skip list数据结构。同时遍历gender和age的posting list，互相skip

  • 使用bitset数据结构，对gender和age两个filter分别求出bitset，对两个bitset做AN操作

1、 Skip List 合并

• 以上是三个posting list，我们现在需要把它们用AND的关系合并，得出posting list的交集

• 首先选择最短的posting list，然后从小到大遍历
• 遍历的过程可以跳过一些元素，比如我们遍历到绿色的13的时候，就可以跳过蓝色的3了，因为3比13要小
• 最后得出的交集是[13,98]，所需的时间比完整遍历三个posting list要快得多
• 但是前提是每个list需要指出Advance这个操作，快速移动指向的位置

2、bitset合并

# Bitset是一种很直观的数据结构，对应posting list如
[1,3,4,7,10]
# 对应的bitset就是
[1,0,1,1,0,0,1,0,0,1]

• 每个文档按照文档id排序对应其中的一个bit，Bitset自身就有压缩的特点

• 其用一个byte就可以代表8个文档，所以100万个文档只需要12.5万个byte

• 但是考虑到文档可能有数十亿之多，在内存里保存bitset仍然是很奢侈的事情

• 而且对于个每一个filter都要消耗一个bitset，比如age=18缓存起来的话是一个bitset

• 18<=age<25是另外一个filter缓存起来也要一个bitset

• 所以秘诀就在于需要有一个数据结构

• 可以很压缩地保存上亿个bit代表对应的文档是否匹配filter

• 这个压缩的bitset仍然可以很快地进行AND和 OR的逻辑操作

• Lucene使用的这个数据结构叫做 Roaring Bitmap

  • 其压缩的思路其实很简单，与其保存100个0，占用100个bit
  • 还不如保存0一次，然后声明这个0重复了100遍

3、如何减少文档数

• 一种常见的压缩存储时间序列的方式是把多个数据点合并成一行

• Opentsdb支持海量数据的一个绝招就是定期把很多行数据合并成一行，这个过程叫compaction

• 类似的vivdcortext使用MySQL存储的时候，也把一分钟的很多数据点合并存储到MySQL的一行里以减少行数

• 这个过程可以示例如下

• Elasticsearch有一个功能可以实现类似的优化效果，那就是Nested Document
• 我们可以把一段时间的很多个数据点打包存储到一个父文档里，变成其嵌套的子文档
• 示例如下

{timestamp:12:05:01, idc:sz, value1:10,value2:11}
{timestamp:12:05:02, idc:sz, value1:9,value2:9}
{timestamp:12:05:02, idc:sz, value1:18,value:17}

• 可以打包成

{
    "max_timestamp": "12:05:02",
    "min_timestamp": "1205:01",
    "idc": "sz",
    "records": [
        {
            "timestamp": "12:05:01",
            "value1": 10,
            "value2": 11
        },
        {
            "timestamp": "12:05:02",
            "value1": 9,
            "value2": 9
        },
        {
            "timestamp": "12:05:02",
            "value1": 18,
            "value2": 17
        }
    ]
}

• 这样可以把数据点公共的维度字段上移到父文档里，而不用在每个子文档里重复存储，从而减少索引的尺寸
  • 如果我们可以在一个父文档里塞入50个嵌套文档，那么posting list可以变成之前的1/50
  • 对于term的posting list只需要保存父文档的doc id，比保存所有的数据点的doc id要少很多
  • 把父子关系也理解为一个filter，那么查询时检索的时候不过是又AND了另外一个filter而已