Elasticsearch-倒排索引原理

爱被打了一巴掌 2022-12-28 11:25 165阅读 0赞

# 转载声明 #

***本文大量内容系转载自以下文章，有删改，并参考其他文档资料加入了一些内容：***

*  [时间序列数据库的秘密(2)——索引][2]  
    作者：陶文  
    出处：infoq
 *  [掌握它才说明你真正懂 Elasticsearch - Lucene （一）][Elasticsearch - Lucene]  
    作者：CrazyZard  
    出处：learnku
 *  [Lucene 查询原理][Lucene]  
    作者：阿里云云栖号  
    出处：CSDN
 *  [关于Lucene的词典FST深入剖析][Lucene_FST]  
    作者：申艳超  
    出处：申艳超个人博客

# 1 背景知识-Lucene #

## 1.1 概述 ##

Elasticsearch是通过Lucene的倒排索引技术实现比关系型数据库更快的过滤。特别是它对多条件的过滤支持非常好，比如年龄在18和30之间，性别为女性这样的组合查询。倒排索引很多地方都有介绍，但是其比关系型数据库的`b-tree`索引快在哪里？到底为什么快呢？

笼统的来说，b-tree索引是为读优化化的索引结构。当我们不需要支持快速的更新的时候，可以用预先排序等方式换取更小的存储空间，更快的检索速度等好处，其代价就是更新慢。要进一步深入的话还是要看一下Lucene的倒排索引是怎么构成的。

## 1.2 Lucene核心模块 ##

Lucene 采用了基于倒排表的设计原理，可以非常高效地实现文本查找，在底层采用了分段的存储模式，使它在读写时几乎完全避免了锁的出现，大大提升了读写性能。

Lucene 的写流程和读流程如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]  
其中，

*  虚线箭头（a、b、c、d）表示写索引的主要过程
 *  实线箭头（1-9）表示查询的主要过程

Lucene 中的主要模块及模块说明如下：

*  analysis  
    主要负责词法分析及语言处理，也就是我们常说的分词，通过该模块可最终形成存储或者搜索的最小单元 Term。
 *  index 模块  
    主要负责索引的创建工作。
 *  store 模块  
    主要负责索引的读写，主要是对文件的一些操作，其主要目的是抽象出和平台文件系统无关的存储。
 *  queryParser 模块  
    主要负责语法分析，把我们的查询语句生成 Lucene 底层可以识别的条件。
 *  search 模块  
    主要负责对索引的搜索工作。
 *  similarity 模块  
    主要负责相关性打分和排序的实现

## 1.3 核心术语 ##

*  Term  
    是索引里最小的存储和查询单元，对于英文来说一般是指一个单词，对于中文来说一般是指一个分词后的词。
 *  词典（Term Dictionary，也叫作字典）  
    是 Term 的集合。词典的数据结构可以有很多种，每种都有自己的优缺点。
    
     *  如排序数组通过二分查找来检索数据：HashMap（哈希表）比排序数组的检索速度更快，但是会浪费存储空间。
     *  FST (finite-state transducer) 有更高的数据压缩率和查询效率，因为词典是常驻内存的，而 FST 有很好的压缩率，所以 FST 在 Lucene 的最新版本中有非常多的使用场景，也是默认的词典数据结构。
 *  倒排序（Posting List）  
    一篇文章通常由多个词组成，倒排表记录的是某个词在哪些文章中出现过，Posting List是DocId 集。`Filter Cache`是一种加速常用Filter执行的技术，是一个简单的`Map<Pair<filter, segment>, 匹配的DocIdList>`。通常Filter Cache在内存，而posting list一般是在磁盘中。需要一种简单、快速的技术来实现Filter Cache，否则还不如重新执行。
 *  正向信息  
    原始的文档信息，可以用来做排序、聚合、展示等。
    
     *  DocValues  
        非分词String的采用的是DocValues，随倒排索引一起生成，且是在堆外内存（序列化后存到操作系统的文件系统缓存）和磁盘间弹性存储的。
        
        其实，Doc Values本质上是一个序列化了的列式存储结构，非常适合排序、聚合以及字段相关的脚本操作。而且这种存储方式便于压缩，尤其是数字类型。压缩(如多个相同值记录个数、最大公约数、最小值+偏移量等)后能够大大减少磁盘空间，提升访问速度。
     *  FieldData  
        分词String采用FieldData，是懒加载到内存(**JVM堆内存**)的，即FieldData是在第一次将该filed用于聚合，排序或在脚本中访问时按需构建（如果加载大数据量的时候会很慢（几个GB的数据可能需要几十秒），就会让习惯亚秒级响应的用户必须忍受长时间的等待，可将FieldData和Global Ordinals加载提前到一个新段对搜索可见之前。）。
        
        FieldData是通过从磁盘读取每个段来读取整个反向索引，然后逆置term↔︎doc的关系，并将结果存储在JVM堆中构建的。所以，加载FieldData是开销很大的操作，一旦它被加载后，就会在整个段的生命周期中保留在内存中。
        
        可以设置FieldData内存驱逐。
        
        也可以设置断路器 Circuit Breaker(断路器)。FieldData是在数据被加载后再检查的，那么如果一个查询导致尝试加载超过可用内存的数据就会导致OOM异常。ES中使用了FieldData Circuit Breaker来处理上述问题，他可以通过分析一个查询涉及到的字段的类型、基数、大小等来评估所需内存。如果估计的查询大小大于配置的堆内存使用百分比限制，则断路器会跳闸，查询将被中止并返回异常。断路器是工作是在数据加载前，所以你不用担心遇到FieldData导致的OOM异常。
 *  段（Segment）  
    索引中最小的独立存储单元。一个索引文件由一个或者多个段组成。在 Luence 中的段有不变性，也就是说段一旦生成，在其上只能有读操作，不能有写操作。

## 1.4 Lucene数据模型 ##

Lucene中包含了四种基本数据类型，分别是：

*  Index  
    索引，由很多的Document组成。
 *  Document  
    由很多的Field组成，是Index和Search的最小单位。
 *  Field  
    由很多的Term组成，包括Field Name和Field Value。
 *  Term  
    由很多的字节组成。一般将Text类型的Field Value分词之后的每个最小单元叫做Term。

## 1.5 Lucene倒排索引 ##

一个Lucene倒排索引大致结构如下图  
![在这里插入图片描述][20201216214050149.png]

整体上来说就以下效果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 1]

*  Term Index  
    通过Trie树存储Term的某些前缀，并会对`Term Index`进行某些压缩。
    
    把Term Index加载到内存后，可快速查找到Term在Term Dictionary中的大致位置，再利用`Term Dictionary`在磁盘上二分查找目标Term。这已经大大减少了直接对Term Dictionary在磁盘进行二分查找带来的随机IO操作消耗。
    
    Term index实际上在内存中是以FST（finite state transducers）的形式保存的，其特点是非常节省内存。可以在FST上实现单Term、Term范围、Term前缀和通配符查询等。
 *  Term Dictionary 词典表  
    按字典序排序的所有Term，可以用二分查找的`logN`次磁盘查找得到目标Term，然后通过指针找到指向的Posting List。
    
    Term dictionary在磁盘上是以分block的方式保存的，一个block内部利用公共前缀压缩，比如都是Ab开头的单词就可以把Ab省去，这样term dictionary可以比b-tree更节约磁盘空间。
 *  Posting List  
    posting list是一个int的数组，存储了所有包含某个对应的Term的文档id和词频等信息。
    
    压缩方法有基于磁盘的FOR和基于内存的RoaringBitmap等

## 1.6 Lucene写入-读写分离 ##

在lucene中，读写路径是分离的：

*  写入的时候创建一个IndexWriter，
 *  而读的时候会创建一个IndexSearcher，

在lucene中查询是基于segment。每个segment可以看做是一个独立的subindex，在建立索引的过程中，lucene会不断的flush内存中的数据持久化形成新的segment。

多个segment也会不断的被merge成一个大的segment，在老的segment还有查询在读取的时候，不会被删除；没有被读取且被merge的Segment会被删除。

这个过程类似于LSM数据库的merge过程。下面我们主要看在一个segment内部如何实现高效的查询。

# 2 Posting List #

## 2.1 概述 ##

![在这里插入图片描述][20201216213938862.png]  
那么给这些document建立的倒排索引就是：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 2]  
可以看到，倒排索引是per field的，即每个字段都有一个自己的倒排索引。

18,20这些叫做 term，而\[1,3\]就是posting list，是一个int的数组，存储了所有包含某个term的文档id。

所谓文档id是Segment级别的，从0到Segment文档数量上限（最小0，最大上限`2^31-1`）的一个标识，文档在Segement中按序存储。

## 2.2 Posting List 压缩 ##

### 2.2.1 概述 ###

`Filter Cache`是一种加速常用Filter执行的技术，是一个简单的`Map<Pair<filter, segment>, 匹配的DocIdList>`。通常Filter Cache在内存，而posting list一般是在磁盘中。需要一种简单、快速的技术来实现Filter Cache，否则还不如重新执行。我们现在思考下怎么存储这些匹配的DocIdList。

*  整形数组  
    最简单，但是最占内存空间
 *  BitMap  
    适合命中数据稠密场景，但稀疏场景不适用，造成空间浪费，所以Lucene在5.0放弃了他转投RoaringBitMap。
 *  RoaringBitMap  
    少于4096个元素就用`short[]`，多余4096就用Bitset，合理利用空间。DocId高16位用来分Block，低16存到对应容器内。关于RoaringBitmap详见[数据结构-BitSet和RoaringBitmap][-BitSet_RoaringBitmap]
 *  FOR 压缩  
    基于磁盘

### 2.2.2 FOR 压缩( `Frame Of Reference`) ###

本压缩算法是完全基于磁盘的，不需要任何内存。

为了高效对posting list 计算交集和union，需要posting list有序。排序后，我们就能利用有序性进行delta-encoding即差值压缩。其压缩方式叫做 `Frame Of Reference`（FOR）编码。示例如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 3]

1.  delta-encode  
    将数字计算差值存放
2.  Split into blocks  
    将1中结果拆分为多个block，每个Block有256个Doc Id(示意图只画了3个方便展示)，以便按各个Block最大值分别按不同bit数表示从而有效压缩
3.  Bit packing  
    根据最大值，比如第一个block最大值是227，则需要8个bit存放（`2^8 = 256`足够存放最大值227），所以每个值都用8bit存放就肯定够了；第二个block最大值30，需要5个bit存放（`2^5 = 32`足够存放最大值30），所以每个值都用5bit存放就肯定够了。将最大bit位数放入Block头部，然后使用该bit数来编码所有Block内所有delta数字。这就是所谓`Frame Of Reference (FOR)`。

考虑到频繁出现的term（所谓low cardinality的值），比如gender里的男或者女。如果有1百万个文档，那么性别为男的posting list里就会有50万个int值。用Frame of Reference编码进行压缩可以极大减少磁盘占用。这个优化对于减少索引尺寸有非常重要的意义。当然mysql b-tree里也有一个类似的posting list的东西，但是未经过这样压缩的。

因为这个Frame of Reference的编码是有解压缩成本的。所以如果利用skip list，除了跳过了遍历的成本，也跳过了解压缩这些压缩过的block的过程，从而节省了cpu。

### 2.2.3 Bitset ###

*  查询问题  
    对于普通搜索时，query和filter返回一个满足搜索条件的文档的已排序的iterator。
    
    对于term级别的query和filter，此时只需从倒排索引中返回这个term对应的posting list的迭代器即可。
    
    其他查询要复杂一些，比如同时查询`termA` 和 `termB`，此时就需要合并posting list。见4.3

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。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 4]

1.  解压缩每个数字为 (N/65536, N%65536)
2.  按N/65536结果划分Block
3.  将每个block编码，方法是使用`short[]`或`bitset`存储，依据是该Block是否超过4096个元素。

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

# 3 Term Dictionary 和 Term index #

## 3.1 Term Dictionary ##

假设我们有很多个term，比如：

Carla,Sara,Elin,Ada,Patty,Kate,Selena

如果按照这样的顺序排列，找出某个特定的term一定很慢，因为term没有排序，需要全部过滤一遍才能找出特定的term。

按字典序排序之后就变成了：

Ada,Carla,Elin,Kate,Patty,Sara,Selena

此时可以用二分查找的方式，比全遍历更快地找出目标的term。这个就是`term dictionary`。

有了term dictionary之后，可以用`logN`次磁盘查找得到目标。但是磁盘的随机读操作仍然是非常昂贵的（一次random access大概需要10ms的时间）。

## 3.2 Term Index ##

### 3.2.1 概述 ###

前面说了磁盘的随机读操作仍然是非常昂贵，所以应该尽量少读磁盘，有必要把一些数据缓存到内存里。但是整个term dictionary本身又太大了，无法完整地放到内存里。而且就算term字典里我们可以按照term进行排序，用一个二分查找就可以定为这个term所在的地址，但这样的复杂度是logN，在term很多，内存放不下的时候，效率还是需要进一步提升。于是就有了term index。

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

*  A开头的term ……………. 1页
 *  C开头的term ……………. 445页
 *  E开头的term ……………. 566页

如果所有的term都是英文字符的话，可能这个term index就真的是26个英文字符表构成的了（A->Z）。但是实际的情况是，term未必都是英文字符，term可以是任意的byte数组。而且26个英文字符也未必是每一个字符都有均等的term，比如x字符开头的term可能一个都没有，而s开头的term又特别多。

所以实际的term index是一棵trie 树：  
![在这里插入图片描述][20201216215847234.png]  
上图中例子是一个包含 “A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, 和 “inn” 几个单词的 trie 树。这棵树不会包含所有的term，它包含的是term的一些前缀。通过term index可以快速地定位到term dictionary的某个offset，然后从这个位置再往后顺序查找。

再加上一些压缩技术（搜索 Lucene Finite State Transducers） term index 的尺寸可以只有所有term的尺寸的几十分之一，使得用内存缓存整个term index变成可能。

### 3.2.2 FST ###

#### 3.2.2.1 FSM ####

FST是一种类TRIE树，使用FSM(Finite State Machines)作为数据结构：

*  FSM(Finite State Machines)有限状态机: 表示有限个状态（State）集合以及这些状态之间转移和动作的数学模型。其中一个状态被标记为开始状态，0个或更多的状态被标记为final状态。一个FSM同一时间只处于1个状态。
    
    FSM很通用，可以用来表示多种处理过程，下面的FSM描述了《小猫咪的一天》。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 5]  
    其中“睡觉”或者“吃饭”代表的是状态,而“提供食物”或者“东西移动”则代表了转移。图中这个FSM是对小猫活动的一个抽象（这里并没有刻意写开始状态或者final状态），小猫咪不能同时的即处于“玩耍”又处于“睡觉”状态，并且从一个状态到下一个状态的转换只有一个输入。“睡觉”状态并不知道是从什么状态转换过来的，可能是“玩耍”，也可能是”猫砂窝”。
    
    如果《小猫咪的一天》从睡觉状态开始，这个FSM接收以下的输入:
    
     *  提供食物
     *  有大声音
     *  安静
     *  消化食物
    
    那么我们会明确的知道，小猫咪会这样依次变化状态： 睡觉->吃饭->躲藏->吃饭->猫砂窝.

以上只是一个现实中的例子，下面我们来看如何实现一个Ordered Sets,和Map结构。

#### 3.2.2.2 Ordered Sets ####

Ordered Sets是一个有序集合。通常一个有序集合可以用二叉树、B树实现。无序的集合使用hash table来实现. 这里，我们用一个确定无环有限状态接收机（Deterministric acyclic finite state acceptor, FSA）来实现。

FSA是一个FSM(有限状态机)的一种，特性如下:

*  确定：意味着指定任何一个状态，只可能最多有一个转移可以访问到。
 *  无环： 不可能重复遍历同一个状态
 *  接收机：有限状态机只“接受”特定的输入序列，并终止于final状态。

下面来看，我们如何来表示只有一个key：”jul“ 的集合。FSA是这样的：  
![在这里插入图片描述][20201220154240552.png]  
当查询这个FSA是否包含“jul”的时候，按字符依序输入。

*  输入j，FSA从0->1
 *  输入u, FSA从1->2
 *  输入l，FSA从2->3

设想一下

*  如果输入“jun”，在状态2的时候无法移动了，就知道不在这个集合里了。
 *  如何输入“ju”, 在状态2的时候，已经没有输入了。而状态2并不是final状态，所以也不在这个集合里。
 *  值得指出的是，查找这个key是否在集合内的时间复杂度，取决于key的长度，而不是集合的大小。

现在往FSA里再加一个key `mar`  
![在这里插入图片描述][2020122015440616.png]  
start状态0此时有了2个转移：j和m。因此，输入key:”mar”,首先会跟随m来转移。 final状态是“jul”和“mar”共享的。这使得我们能用更少的空间来表示更多的信息。

当我们再在这个FSA里加入“jun”，那么它和“jul”有共同的前缀“ju”:  
![在这里插入图片描述][20201220154455557.png]  
这里变化很小，没有增加新的状态，只是多了一个转移而已。

下面再来看一下由“october”，“november”,”december”构成的FSA.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 6]  
它们有共同的后缀“ber”，所以在FSA只出现了1次。 其中2个有共同的后缀”ember”，也只出现了1次。

那么我们如何来遍历一个FSA表示的所有key呢，我们以前面的”jul”，“jun”,”mar”为例：  
![在这里插入图片描述][20201220155645160.png]  
遍历算法是这样的：  
![在这里插入图片描述][2020122015565759.png]  
这个遍历算法时间复杂度O(n),n是集合里所有的key的大小, 空间复杂度O(k),k是结合内最长的key字段length。

#### 3.2.2.3 Ordered maps ####

Ordered maps就像一个普通的map，只不过它的key是有序的。我们来看一下如何使用确定无环状态转换器（Deterministic acyclic finite state transducer， FST）来实现它。

FST是也一个有限状态机（FSM）,具有这样的特性：

*  确定：意味着指定任何一个状态，只可能最多有一个转移可以遍历到。
 *  无环： 不可能重复遍历同一个状态
 *  transducer：接收特定的序列，终止于final状态，**同时会输出一个值。**

FST和FSA很像，给定一个key除了能回答是否存在，还能输出一个关联的值。

下面来看这样的一个输入：“jul:7”, 7是jul关联的值，就像是一个map的entry.  
![在这里插入图片描述][2020122016224075.png]  
这和对应的有序集合基本一样，除了第一个0->1的转换j关联了一个值7. 其他的转换u和l,默认关联的值是0,这里不予展现。那么当我们查找key:”jul”的时候，大概流程如下：

*  初始状态0
 *  输入j, FST从0->1， value=7
 *  输入u, FST从1->2， value=7+0
 *  输入l，FST从2->3, value=7+0+0

此时，FST处于final状态3，所以存在jul，并且给出output是7.

我们再看一下，加入mar:3之后，FST变成什么样：  
![在这里插入图片描述][20201220162434687.png]  
同样的很简单，需要注意的是mar自带的值3放在了第1个转移上。这只是为了算法更简单而已，事实上，可以放在其他转移上。

如果共享前缀，FST会发生什么呢？这里我们继续加入jun:6。  
![在这里插入图片描述][20201220162453653.png]  
和sets一样，jun和jul共享状态3， 但是有一些变化。

*  0->1转移，输出从7变成了6
 *  2->3转移，输入l，输出值变成了1。

这样就可以共用 值6，还能分别找到各自正确的值。也就是说FST保证了不同的转移有唯一的值，但同时也复用了大部分的数据结构。实现共享状态的关键点是：每一个key,都在FST中对应一个唯一的路径。因此，对于任何一个特定的key，总会有一些value的转移组合使得路径是唯一的。我们需要做的就是如何来在转移中分配这些组合。

key输出的共享机制同样适用于共同前缀和共同后缀。比如我们有tuesday:3和thursday:5这样的FST:  
![在这里插入图片描述][20201220162923465.png]  
上面的这个例子，其实有点简单化，并且局限。假如这些关联的value并不是int呢？ 实际上，FST对于关联value(outputs)的类型是要求必须有以下操作（method）的。

*  加（Addition）
 *  减 (Subtraction)
 *  取前缀 (对于整数来说，就是min)

#### 3.2.2.4 Trie与FSM ####

构建相对于遍历来说，还是有些复杂的。为了简单化，我们假设set或者map里的数据是按字典序加入的。这个假设是很沉重的限制，不过我们会讲如何来缓解它。

为了构建FSM，我们先来看看TRIE树是如何构建的。TRIE可以看做是一个FSA,唯一的一个不同是TRIE只共享前缀，而FSA不仅共享前缀还共享后缀。

假设我们有一个这样的Set: mon,tues,thurs。FSA是这样的：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 7]  
相应的TRIE则是这样的，只共享了前缀。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 8]  
TRIE有重复的3个final状态3，8，11. 而8，11都是s转移，是可以合并的。

构建一个TRIE树是相当简单的。插入1个key，只需要做简单的查找就可以了。如果输入先结束，那么当前状态设置为final；如果无法转移了，那么就直接创建新的转移和状态。**不要忘了最后一个创建的状态设置为final。**

#### 3.2.2.5 FST的构建 ####

构建FST在很大程度上和构建FSA是一样的，主要的不同点是，怎么样在转移上放置和共享outputs。

仍旧使用前面提到的例子，mon,tues和thurs，并给他们关联相应的星期数值2，3和5.

从第1个key, mon:2开始：  
![在这里插入图片描述][20201220164051716.png]  
这里虚线代表在后续的insert过程中，FST可能有变化。

需要关注的是，这里只是把2放在了第1个转移上。技术上说，下面这样分配也是正确的。  
![在这里插入图片描述][2020122016413160.png]  
下面继续把thurs:5插入：  
![在这里插入图片描述][20201220164139795.png]  
就像FSA的insert一样，插入thurs之后，我们可以知道FST的mon部分（蓝色）就不会再变了。

由于mon和thurs没有共同的前缀，只是简单的2个map中的key. 所以他们的output value可以直接放置在start状态的第1个转移上。

下面，继续插入tues:3，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 9]  
这引起了新的变化。有一部分被冻住了，并且知道以后不会再修改了。output value也出现了重新的分配。因为tues的output是3，并且tues和thurs有共同的前缀t, 所以5和3的prefix操作得出的结果就是3. 状态0->状态4的value被分配为3，状态4->状态5设置为2。

我们再插入更多的key, 这次插入tye:99看发生什么情况：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 10]  
插入tye，导致”es”部分被冻住，同时由于共享前缀t, 状态4->状态9的输出是99-3=96。

最后一步，结束了，再执行一次冻住操作。

最终的FST长这样：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 11]

#### 3.2.2.6 FST小结 ####

除了在Term词典这块有应用，FST在整个lucene内部使用的也是很广泛的，基本把hashmap进行了替换。  
场景大概有以下：

*  自动联想：suggester
 *  charFilter: mappingcharFilter
 *  同义词过滤器
 *  hunspell拼写检查词典

FST，不但能共享前缀还能共享后缀。不但能判断查找的key是否存在，还能给出响应的输入output。 它在时间复杂度和空间复杂度上都做了最大程度的优化，使得Lucene能够将Term Dictionary完全加载到内存，快速的定位Term找到响应的output（posting倒排列表）。

从lucene4开始，为了方便实现rangequery或者前缀，后缀等复杂的查询语句，lucene使用FST数据结构来存储term字典，下面就详细介绍下FST的存储结构。

我们就用Alice和Alan这两个单词为例，来看下FST的构造过程。首先对所有的单词做一下排序为“Alice”，“Alan”：

1.  插入“Alan”  
    ![在这里插入图片描述][20201220125228607.png]
2.  插入“Alice”  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 12]  
    这样你就得到了一个有向无环图（类似于Trie树），有这样一个数据结构，就可以很快查找某个人名是否存在。

*  缺点  
    FST在单term查询上可能相比hashmap并没有明显优势，甚至会慢一些。
 *  优点  
    但是在范围，前缀搜索以及压缩率上都有明显的优势。

# 4 小结 #

## 4.1 如何联合索引查询？ ##

### 4.1.1 概述 ###

1.  所以给定查询过滤条件`age=18`的过程就是先从term index找到18在term dictionary的大概位置，然后再从term dictionary里精确地找到18这个term，然后得到一个posting list或者一个指向posting list位置的指针。
2.  然后再查询`gender=女` 的过程也是类似的。
3.  最后得出 age=18 AND gender=女 就是把两个 posting list 做一个“与”的合并。

这个理论上的“与”合并的操作可不容易。对于mysql来说，如果你给age和gender两个字段都建立了索引，查询的时候只会选择其中最selective的来用，然后另外一个条件是在遍历行的过程中在内存中计算之后过滤掉。

那么要如何才能联合使用两个索引呢？有两种办法：

*  使用skip list数据结构。同时遍历gender和age的posting list，互相skip；
 *  使用bitset数据结构，对gender和age两个filter分别求出bitset，对两个bitset做AN操作。

PostgreSQL 从 8.4 版本开始支持通过bitmap联合使用两个索引，就是利用了bitset数据结构来做到的。当然一些商业的关系型数据库也支持类似的联合索引的功能。

而Elasticsearch支持以上两种的联合索引方式:

*  如果查询的filter缓存到了内存中（以bitset的形式），那么合并就是两个bitset的AND。
 *  如果查询的filter没有缓存，那么就用skip list的方式去遍历两个on disk的posting list。

### 4.1.2 利用 Skip List 合并Posting List ###

为了能够快速查找docid，lucene采用了SkipList这一数据结构。SkipList有以下几个特征：

*  元素排序的，对应到我们的倒排链，lucene是按照docid进行排序，从小到大。
 *  跳跃有一个固定的间隔，这个是需要建立SkipList的时候指定好，例如下图以间隔是3
 *  SkipList的层次，这个是指整个SkipList有几层  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 13]  
    有了这个SkipList以后比如我们要查找docid=12，原来可能需要一个个扫原始链表，1，2，3，5，7，8，10，12。有了SkipList以后：

1.  先访问第一层看到是然后大于12，
2.  进入第0层走到3，8，发现15大于12，
3.  然后进入原链表的8继续向下经过10和12。

有了FST和SkipList的介绍以后，我们大体上可以画一个下面的图来说明lucene是如何实现整个倒排结构的：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 14]  
有了这张图，我们可以理解为什么基于lucene可以快速进行倒排链的查找和docId查找，下面就来看一下有了这些后如何进行倒排链合并返回最后的结果。

假如我们的查询条件是`name = “Alice”`，那么按照之前的介绍，首先在term字典中定位是否存在这个term，如果存在的话进入这个term的倒排链，并根据参数设定返回分页返回结果即可。这类查询，在数据库中使用二级索引也是可以满足，那lucene的优势在哪呢。假如我们有多个条件，例如我们需要按名字或者年龄单独查询，也需要进行组合 `name = "Alice"` and `age = "18"`的查询，那么使用传统二级索引方案，你可能需要建立两张索引表，然后分别查询结果后进行合并，这样如果`age = 18`的结果过多的话，查询合并会很耗时。

那么在lucene这两个倒排链是怎么合并呢？假如我们有下面三个倒排链需要进行合并。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 15]  
在lucene中会采用下列顺序进行合并：

1.  在termA开始遍历，得到第一个元素docId=1
2.  Set currentDocId=1
3.  在termB中 search(currentDocId) = 1 (返回大于等于currentDocId的一个doc，这一步搜索时就会进行SkipList数据跳过),
    
    1.  因为currentDocId ==search结果1，继续
    2.  如果currentDocId 和search返回的不相等，则执行2，然后继续
4.  到termC后搜索结果依然符合，返回结果
5.  Set currentDocId = termC.nextItem = 2
6.  然后继续步骤3 依次循环。直到某个倒排链到末尾。

整个合并步骤我可以发现，如果某个链很短，会大幅减少比对次数，并且由于SkipList结构的存在，在某个倒排中定位某个docid的速度会比较快不需要一个个遍历（该例子所需的时间比完整遍历三个posting list要快得多，但是前提是每个list需要使用SkipList独有的Advance操作）。可以很快的返回最终的结果。从倒排的定位，查询，合并整个流程组成了lucene的查询过程，和传统数据库的索引相比，lucene合并过程中的优化减少了读取数据的IO，倒排合并的灵活性也解决了传统索引较难支持多条件查询的问题。  
![在这里插入图片描述][20201216224701218.png]  
以上是三个posting list。我们现在需要把它们用AND的关系合并，得出posting list的交集。首先选择最短的posting list，然后从小到大遍历。遍历的过程可以跳过一些元素，比如我们遍历到绿色的13的时候，就可以跳过蓝色的3了，因为3比13要小。

整个过程如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 16]  
最后得出的交集是\[13,98\]，所需的时间比完整遍历三个posting list要快得多。但是前提是每个list需要指出Advance这个操作，快速移动指向的位置。什么样的list可以这样Advance往前做蛙跳？skip list：  
![在这里插入图片描述][20201216225120135.png]

从概念上来说，对于一个很长的posting list，比如：

\[1,3,13,101,105,108,255,256,257\]

可以把这个list分成三个block：

`[1,3,13] [101,105,108] [255,256,257]`

可利用三个Block开头的数字构建出skip list的上一层：

\[1,101,255\]

其中 `1,101,255`分别指向自己对应的block。这样就可以很快地跨block的移动指向位置了。

### 4.1.3 利用bitset合并 ###

这两种合并使用索引的方式都有其用途。

Elasticsearch对其性能有详细的对比（https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps）。简单的结论是：因为Frame of Reference编码是如此 高效，对于简单的相等条件的过滤缓存成纯内存的bitset还不如需要访问磁盘的skip list的方式要快。

## 4.2 BKDTree-应对数值类型 ##

在lucene中如果想做范围查找，根据上面的FST模型可以看出来，需要遍历FST找到包含这个range的一个点然后进入对应的倒排链，然后进行求并集操作。但是如果是数值类型，比如是浮点数，那么潜在的term可能会非常多，这样查询起来效率会很低。所以为了支持高效的数值类或者多维度查询，lucene引入类BKDTree。

BKDTree是基于KDTree，对数据进行按照维度划分建立一棵二叉树确保树两边节点数目平衡。

在一维的场景下，KDTree就会退化成一个二叉搜索树，在二叉搜索树中如果我们想查找一个区间，logN的复杂度就可以访问到叶子结点得到对应的倒排链。如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 17]  
如果是多维，kdtree的建立流程会发生一些变化。  
比如我们以二维为例，建立过程如下：

1.  确定切分维度，这里维度的选取顺序是数据在这个维度方法最大的维度优先。一个直接的理解就是，数据分散越开的维度，我们优先切分。
2.  切分点的选这个维度最中间的点。
3.  递归进行步骤1，2，我们可以设置一个阈值，点的数目少于多少后就不再切分，直到所有的点都切分好停止。

下图是一个建立例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 18]  
BKDTree是KDTree的变种，因为可以看出来，KDTree如果有新的节点加入，或者节点修改起来，消耗还是比较大。类似于LSM的merge思路，BKD也是多个KDTREE，然后持续merge最终合并成一个。

不过我们可以看到如果你某个term类型使用了BKDTree的索引类型，那么在和普通倒排链merge的时候就没那么高效了所以这里要做一个平衡，一种思路是把另一类term也作为一个维度加入BKDTree索引中。

## 4.3 为什么Elasticsearch/Lucene检索可以比mysql快 ##

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

## 4.4 为什么使用RoaringBitmap做filter cache? ##

### 4.4.1 概述 ###

以下性能测试中，

*  `for`是指在基准测试时，Lucene在索引建立时在操作系统缓存中创建的基于磁盘的posting list。
 *  测试以使用BitMap作为参考系，即蓝色横线。
 *  y轴使用以2为底的对数刻度：值0表示它与BitMap一样快，1表示快2倍。
 *  x轴使用以10为底的对数刻度，代表DocId集合数据的稠密程度。例如，值-2表示该DocId集中包含`10^-2 = 1％`的文档。也就是说左边更稀疏，右边代表数据更稠密。

### 4.4.2 迭代性能对比 ###

![在这里插入图片描述][20201218225546715.png]  
主要是在constant-score中使用filter时。

当数据稀疏时，BitMap性能最差，意味着此时用BitMap缓存Filter还不如直接再次从磁盘读取DocId。

### 4.4.3 跳过文档性能对比 ###

交叉一个Filter和其他查询时需要跳过跳过文档。下图括号中的数字是我们试图在每次迭代中跳过的文档数（无论它们是否匹配）  
![在这里插入图片描述][20201218232817458.png]  
![在这里插入图片描述][2020121823282459.png]  
与所有文档的大约1 / N匹配的查询相交时，基本上会跳过N个文档。可以看到数据稠密时BitMap最快，同时RoaringBitMap随密度增加的性能下降幅度较小。

各个数据结构使用的跳过文档的技术如下：

*  FOR  
    使用跳表
 *  BitMap  
    直接按位找
 *  RoaringBitMap  
    先从Block找出目标DocId，然后如果docId存在于数组就用二分查找，BitMap就直接查找。
    
    当数据很稠密时，就转而存储未命中的记录，目的是节约内存，但跳跃速度下降，如上图最靠右。
 *  int\[\]  
    [exponential search][]

### 4.4.4 内存占用对比 ###

![在这里插入图片描述][20201219000142199.png]

### 4.4.5 构建缓存时间对比 ###

![在这里插入图片描述][20201219000158762.png]  
注意Y轴值越大，缓存构建时间越短。所以这里在密度在0.01％到1％之间时RoaringBitMap构建速度最快。

### 4.4.6 结论 ###

*  没有一种技术适用所有场景
 *  BitMap在稀疏场景表现糟糕
 *  int\[\]数组很快，但在数据稠密时内存占用极高
 *  RoaringBitMap是速度和开销均衡的选择
 *  尽管来自倒排索引的PostingList存在磁盘而不是内存上，仍然速度很快。所以Filter Cache只应该在运行缓慢的Filter上开启以提升效率，而在一些如TermFilter之类的Filter上不应该开启。
 *  未来也许会根据文档密度而采取不同的Filter缓存实现

## 4.5 如何减少文档数？ ##

一种常见的压缩存储时间序列的方式是把多个数据点合并成一行。Opentsdb支持海量数据的一个绝招就是定期把很多行数据合并成一行，这个过程叫compaction。类似的vivdcortext使用mysql存储的时候，也把一分钟的很多数据点合并存储到mysql的一行里以减少行数。

这个过程可以示例如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 19]  
可以看到，行变成了列了。每一列可以代表这一分钟内一秒的数据。

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,value:17}
    ]
    }

这样可以把数据点公共的维度字段上移到父文档里（如这里的`idc:sz`），而不用在每个子文档里重复存储，从而减少索引的尺寸。  
![在这里插入图片描述][20201216232103741.png]

在存储的时候，无论父文档还是子文档，对于Lucene来说都是文档，都会有文档Id。但是对于嵌套文档来说，可以保存起子文档和父文档的文档id是连续的，而且父文档总是最后一个。有这样一个排序性作为保障，那么有一个所有父文档的posting list就可以跟踪所有的父子关系。也可以很容易地在父子文档id之间做转换。把父子关系也理解为一个filter，那么查询时检索的时候不过是又AND了另外一个filter而已。前面我们已经看到了Elasticsearch可以非常高效地处理多filter的情况，充分利用底层的索引。

使用了嵌套文档之后，对于term的posting list只需要保存父文档的doc id就可以了，可以比保存所有的数据点的doc id要少很多。如果我们可以在一个父文档里塞入50个嵌套文档，那么posting list可以变成之前的1/50。

# 参考文档 #

*  [Frame of Reference and Roaring Bitmaps][]

[2]: https://www.infoq.cn/article/database-timestamp-02
[Elasticsearch - Lucene]: https://learnku.com/articles/40398
[Lucene]: https://blog.csdn.net/yunqiinsight/article/details/80008394
[Lucene_FST]: https://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]: /images/20221120/634744c8ff454017bb13797577fd804c.png
[20201216214050149.png]: /images/20221120/a252e9e494944c448934f56f3d53090e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 1]: /images/20221120/1e361cf5fb204813b088cc417deb6ad6.png
[20201216213938862.png]: /images/20221120/aea918b9b4284523bc359ea592d1a820.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 2]: /images/20221120/eb23b04e75964f53a31430c51240745d.png
[-BitSet_RoaringBitmap]: https://blog.csdn.net/baichoufei90/article/details/106210233
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 3]: /images/20221120/42b3e0f2293d4e3b8f8783629ce233a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 4]: /images/20221120/3f0a3db8be304319b927479525094d03.png
[20201216215847234.png]: /images/20221120/1670c556022644d49d82952dba7b6658.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 5]: /images/20221120/c484c5a210c445e5b500b8a9cebec27e.png
[20201220154240552.png]: /images/20221120/2a58a417020746eeb1c838e5836f6941.png
[2020122015440616.png]: /images/20221120/87bf85bca40249bcb67edd05d6807e74.png
[20201220154455557.png]: /images/20221120/3befafc3eae44053913503d965085aec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 6]: /images/20221120/95164f28471345e7b1f925c0ba9fe68b.png
[20201220155645160.png]: /images/20221120/9c9ba2a41c5545e6b64e97d6860c50d7.png
[2020122015565759.png]: /images/20221120/379ece411e484615aed740475db9eea2.png
[2020122016224075.png]: /images/20221120/8842edb505c84577adc8fbaaf797cd97.png
[20201220162434687.png]: /images/20221120/73e9b87d67234b508847a597c7b0b701.png
[20201220162453653.png]: /images/20221120/b49ecab4baf0456bbd22b9dd8947efcd.png
[20201220162923465.png]: /images/20221120/65084e1951744673bf7a08d58c33c000.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 7]: /images/20221120/1cc2de7937594a2589fb2a36841193e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 8]: /images/20221120/b48518ab86174344831739ad291e8960.png
[20201220164051716.png]: /images/20221120/17a1e0c28ec94a149a4610b9feddd92d.png
[2020122016413160.png]: /images/20221120/f9341b29b9bf4c6ea70462bdebe1e446.png
[20201220164139795.png]: /images/20221120/1e40c1172ca54bf6a839c063dd5ddf66.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 9]: /images/20221120/41e02b64aadf4a728e164ef2e2d97abc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 10]: /images/20221120/7cadf24cc3c54a5dbf791e1a7f2a975f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 11]: /images/20221120/e787f5e7ae444860adee92db34979f10.png
[20201220125228607.png]: /images/20221120/457ebeff2771438cbfcd39237ae2a5e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 12]: /images/20221120/a5f3ea3fbe6f4e189a2249373f0709e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 13]: /images/20221120/7a3f08487fd04fb6bb57363900cd176e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 14]: /images/20221120/072549279ba5411090ac155c57409271.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 15]: /images/20221120/35cc3959c8284f7494966ced3a0badb8.png
[20201216224701218.png]: /images/20221120/53f4744c579a4737958f044c47ba6377.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 16]: /images/20221120/cd5d2992723f40c78c2057e304538ebc.png
[20201216225120135.png]: /images/20221120/ffe6a413ee2645b3839f0edcb2be34b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 17]: /images/20221120/5454c57ec301407dbfbcef7bbc7f5663.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 18]: /images/20221120/9e7184e222e645fb9de44f03f79b647d.png
[20201218225546715.png]: /images/20221120/e363722b0b8f4fc19dce7cf47c2260c2.png
[20201218232817458.png]: /images/20221120/7b878f7edcad4270a195f63ee1c49657.png
[2020121823282459.png]: /images/20221120/08f04cba8faa4b9ab2f0d7bf28746f52.png
[exponential search]: http://en.wikipedia.org/wiki/Exponential_search
[20201219000142199.png]: /images/20221120/44454b05b1aa43e082ef9ad92730de94.png
[20201219000158762.png]: /images/20221120/d06ae19627144a9fa7f83321318f65b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 19]: /images/20221120/a62c207665444416ba90f9e43a191e30.png
[20201216232103741.png]: /images/20221120/92bd03fd02c84000b96d04e13fccfe16.png
[Frame of Reference and Roaring Bitmaps]: https://www.elastic.co/cn/blog/frame-of-reference-and-roaring-bitmaps