倒排索引

1. 倒排索引原理

1.1. Lucene索引构成

  • Lucene索引由下面三部分构成构成
  • 1）Term Index（词项索引）
    • Term Index是一个索引结构，用于快速查找Term Dictionary中的词项
    • Term Index通常是用Trie树（也称为 前缀树，字典树）实现的
      • 在Trie树中，每个节点代表一个字符串（前缀），每条边代表一个字符
      • 从根节点到叶子节点的路径代表一个完整的字符串
      • 当我们查找一个词项时，可以从根节点开始，沿着词项的每个字符对应的边找下去
      • 直到找到词项或确定词项不存在
  • 2）Term Dictionary（词项字典）
    • Term Dictionary是所有索引词项的集合
    • 每个词项都关联着一个Posting List
    • 词项字典一般会存储词项的相关信息，如词项的文档频率等
  • 3）Posting List（倒排列表）
    • Posting List是包含了某个词项的所有文档的ID列表
    • 每个Posting List一般会包含词项频率、位置信息、偏移信息
  • 查找过程
    • 在构建索引时，首先会对文档进行分词处理，得到一系列的词项
    • 然后将这些词项添加到词项字典中，并更新相关的Posting List
    • 在此过程中，还会更新Term Index，以保证可以快速定位到词项字典中的词项
    • 在进行搜索时，首先会在Term Index中查找词项
    • 然后通过Term Dictionary找到对应的Posting List，从而找到包含该词项的所有文档

1.2. 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

1.3. 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变成可能

1.4. Term Dictionary 词项字典

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

1.5. 总结

  • 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更节约磁盘空间

2. 如何联合索引查询

2.1. 查询合并

  • 如何过滤 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操作

2.2. Skip List 合并

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

2.3. 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遍

2.4. 如何减少文档数

  • 一种常见的压缩存储时间序列的方式是把多个数据点合并成一行
  • 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而已

results matching ""

    No results matching ""