引言

这也许是你全网你能找到的最详细的倒排索引的底层解读。博主把倒排索引的讲解划分为以下七个部分，理解难度递增，可根据自身需要选择依次阅读或者针对性阅读。

通常来说，应付一般的面试，理解第一部分即可。如果需要面试搜索相关业务的岗位，需要深层次理解倒排索引，可根据自身情况选择阅读。

本文花费了作者大量的精力来论证和整理，如果你喜欢作者的文章，请帮忙点个赞和关注吧 O(∩_∩)O ~。谢谢大家的支持。

1、倒排索引核心原理

提到ES，大多数爱好者想到的都是搜索引擎，尽管这是个误区，但是也不得不提。大数据搜索最重要的三个要素分别是 “快”、“准”、“高”。

所谓快，即搜索速度要快，搜索引擎级别的要求要达到PB级数据的秒内搜索；

所谓“准”，即搜索结果要尽量符合正常人类的预期值，在ES里我们用相关度这个概念来描述搜索结果的准确性。ES里计算相关性采用“打分机制”，ES在旧版本中使用一种叫TF/IDF的评分算法作为默认的评分算法，从 7.x 之后，默认改为BM25评分算法。

天下武功，唯快不破。本节内容，我将围绕“ES是如何支撑大数据近实时搜索”这一话题展开，这一点非常重要。聪明的人类在探索快速检索这一技术领域已经发挥了令人难以想象的智慧，后人不必重复造轮子，要学会如何站在巨人的肩膀上。这一点，前人已经帮助我们总结很多经验。概括的说，一个优秀的搜索引擎的设计，至少应该具备以下几点要求：

• 高效的压缩算法
• 快速的编码和解码算法
• 合理的数据结构
• 通用最小化算法

结合以上几点，后面我将通过一个案例来讲解，倒排索引的基本原理是什么。在了解“倒排索引”之前，我们先来看一下何为“索引”。

一本汉语字典，如果我们想要从中找到某个字，通常我们会通过字典最前面的拼音检索或者是部首检索来查找。其实汉语字典的正文本身就是一个索引，比如我们要查找“吴”字，很自然的就想到了“吴”的拼音是“wu”，w在26个字母中在很靠后的位置，基本上就可以确定“吴”字的大致位置，然后按照字典序可以在w字母的汉字里精确的找到这个字，因为汉字本身就是按照字典序排列的，这种按照一定规则排序的目录在关系型数据库中一般叫做“聚集索引”。

除了这种索引，通常我们还了解一种类似于“偏旁部首”的检索方式称之为“非聚集索引”，我们这里不展开来讨论什么是聚集索引和非聚集索引。但是我们可以确定的是，不管是什么索引，它的目的都是帮助我们快速检索数据的。

在数据库领域里，索引可以概括为一种帮助我们快速检索数据的以文件形式落地的数据结构。

以MySQL为例，如图1-1所示：

左侧是MySql安装文件的data目录，右侧使我们使用数据库客户端打开数据库后的样式，左侧文件分别对应了右侧数据库中的数据库名，我们以“mysql”这个数据库为例，文件夹中每个文件都有若干个不同后缀的同名文件，分别对应右侧某个数据表，不同的后缀代表不同的数据类型，其中.frm文件代表当前文件存储的是数据表的表结构，.MYD和.MYI文件则代表了当前文件是myisam存储引擎下的数据文件和索引文件，.ibd则代表当前文件是innodb存储引擎下的索引文件，只不过innodb的数据和索引使用了同一个文件。

不管是元数据还是索引数据，他们最终都是以“文件”的形式存储在磁盘中的，只不过不同的文件内部使用的数据结构各不相同。而MySql使用的数据结构是B+Trees。但是这种数据结构并不适用于倒排索引，原因我们会在后面的文章中提到。

理解了索引的定义，我们来看一下索引在生活场景中的实际应用。如图1-2所示：

我们假设右侧表格是某个商城软件的商品表，当我们有通过关键字搜索商品列表的需求的时候，我们会执行图中左侧的SQL语句进行模糊查询，但是当数据量达到一定量的时候，搜索速度会很慢，原因是当前语句会造成“扫表”，产生大量的IO，MySql每次IO的大小默认为16KB，所以这样的查询是不被允许的，通常情况下解决的办法是在product字段上创建索引，但是这样做会产生很多问题。

首先，MySql使用的B+Trees的数据结构来存储索引数据，这种数据结构当数据量达到千万级的时候，那么每个单个节点会树的深度就已经达到甚至超过4层了，当数据量再大，查询的性能就达不到要求了，况且搜索引擎级别的数据量级动辄亿级或者十亿级，如果按照搜索引擎的要求，那这种数据结构是难以支撑的。

其次，因为每个树的每个节点大小固定为16KB，一般来说每个索引的占用的空间越大，那么单个节点所容纳的索引数量就越少。虽然B+Trees的非叶子节点不存放data，只存放索引数据，但是由于关键字搜索的需求就是在文本字段上去创建索引，所以通常我们的索引Key也都是文本类型，这就造成了单个索引占用的空间较大，B+Trees非叶子节点不存放数据这种设计相较于B-Trees（B Trees）本身就是为了减轻非叶子节点的负重，从而降低树的深度，但是显然我们这样做就违背了这一B+Trees的设计初衷，显然在文本上创建索引并不是很明智的选择，当索引字段为长文本的时候，树的深度会成指数级加大。

而且通常情况下我们有模糊查询的需求，需要在搜索的时候前后加上“%”，但由于“最左匹配原则”，左like查询会导致索引的失效，导致SQL查询性能指数级下降。况且即便索引不会失效，目标字段的关键词中往往掺杂着一些无用字符，比如我们要查找的商品叫做“小米NFC旗舰手机”，但是我们搜索的关键词是“小米NFC手机”或者“小米手机NFC”，这种由于词序颠倒或者有干扰字符的情况就会导致我们的搜索结构不准确。

综上所述，B+Trees支撑的索引并不适合做“关键词搜索”这种需求。

那么，Lucene中的倒排索引是如何解决这类问题呢？同样我们以上文提到的场景为例，如图1-3所示：

Lucene首先会把目标域（field）的所有行进行分词操作，就是把product字段对应的短语切分成若干个词项（Term），这里其实英文有天然的优势，因为每个词项都是以空格切分的，如果是中文就要用到中文分词器，不同的分词策略的分词结果大相径庭。关于分词器，笔者会在后面内容中详细介绍。这里我们按照正常人类的思维暂且以图中空格作为切分依据，如“新款小米至尊纪念版手机”我们暂且认为分词后包含了“新款”、“小米”、“至尊”、“纪念版”、“手机”这么几个词项，以此类推，Lucene会在Index time把索引字段的所有词项切分计算出来，并且按照字典序生成一个词项字典（Term Dictionary），此项字段存储的是去重之后的所有词项。我们假设上图左侧的表格中term dictionary字段就是最终生成的词项字典，那么右侧的倒排表（Posting List）保存的就是所有包含当前词项的元数据的id的有序int数组。当然实际存储的这两种数据结构真正的情况远比我们目前看到的复杂的多，但是它们实际的样子并不便于我们理解什么是倒排索引，因此我们暂且以这种“二维表格”的形式来展示这两种数据结构。至于Term Index，我们暂时不必理会，只需要知道，这张表格里包含的三种数据结构便组成了我们经常提到的“倒排索引”。

当我们按照上述所说进行一定的分词策略创建倒排索引之后，假如最终的结果就如上面图中所示。此时加入用户搜索的关键词为“小米NFC手机”，按照相同的分词策略，用户的搜索词会被分成“小米”、“NFC”、“手机”三个词项，我们分别对三个词项在左侧表格也就是我们暂时理解的“倒排索引”文件中进行检索。此时的查询由原本的模糊查询编程了精准查询，比如“小米”这个关键词，匹配到了就是匹配到了，如果匹配到了也没必要继续检索下去了，因为后面不可能再有相同的词项了。这种查询会大大加快查询的速度，比如“小米”这个关键词，最好的情况可能只匹配了第一次就命中了索引，假如元数据有10亿条，并且在这10亿数据中可能包含“小米”这个关键词的数据超过了100W行，那么本次查询只检索了一次就找到了元数据中包含“小米”这个关键词的一百万+条数据，不可谓不高效！当然了，检索也不可能次次都是一次命中，不过ES底层对倒排索引的检索做了大量的优化，大大提高了倒排索引的检索效率，比如Term Index就是词项字典索引，可以大大加快倒排索引的查询效率，关于词项索引（词项索引）我会在后面的内容中详细介绍，此处不再赘述。

回过头来继续看当前的案例，假设每个词项在倒排索引中命中之后，我们都做一个“命中”标记，那么当前搜索的三个词项都命中了对应的Term，我们计算一下此次命中的倒排表中的id分别命中了多少次。假如此次搜索倒排表中包含了元数据中id为1，2，3，4这几条数据，我们分别计算一下每个id被命中的次数，并且把对应的结果抽象出一个字段放在元数据表格的右侧，那么这个结果就可以暂时理解为一个简单的“相关度”。我们按照这个“相关度”倒序排列元数据，就会发现，当前这个顺序基本就是符合我们正常人类对搜索结果的一个预期排序。最符合预期的结果会被排在最上面，最不符合的结果排在最下面。

到此为止，上图左侧的表格就可以看成是“倒排索引”，那么整个这个检索的过程就叫做“全文检索”。

2、倒排索引的存储结构

2.1 倒排表（Posting List）

索引文件中分别存储了不同的数据

其中倒排表包含某个词项的所有id的数据存储了在.doc文件中；

2.2 词项字典（Term Dictionary）

词项字典包含了index field的所有经过normalization token filters处理之后的词项数据，最终存储在.tim文件中。

所谓normalization其实是一个如去重、时态统一、大小写统一、近义词处理等类似的相关操作；词项索引就是为了加速词项字典检索的一种数据结构，落地文件为.tip。.tip文件和.tim文件的数据结构

如下图2-2所示：

2.3 词项索引（Term Index）

Lucene中通过FST Index信息来读取当前域在索引文件.tim的具体信息，而同一个索引所有域的FSTIndex都被连续的写入在同一个.tip文件中，所以就需要indexStartFP 来索引 FSTIndex。

FSTIndex底层是一个字节数组，存储了每个Block在.tim中的起始位置，如上图2-2所示，Block f 和Block g 对应的 Block 分别被保存在了.tim文件的 Block 0 和 Block 1 的位置。

每个Block内部又保存了Block Header、Suffix和Stats信息以及Metadatas信息，其中Block Header中存储了当前Block中的Pending Block和Pending Term的总计数，也就是EntryCount，Sufix则是保存了当前Block后缀的个数以及分别是什么，如block b的SufixLength=2，为f、g。Stats则保存了当前Term的词频和文档频率，参见：org.apache.lucene.index.TermsEnum.TermStats。

其中docFreq为包含当前Term的doc数量，totalTermFreq为当前term在所有文档中的当前字段中出现的总次数，但实际保存的是和docFreq的差值，这也是遵循通用最小化算法的法则表现。需要注意的是，两者均是指在同一个域内的计数。Metadatas这里不着重介绍。

关于倒排表的文件结构，我们仅需知道其内部存储了包含Term的id数组、词频、postion、payload、offset等信息，需要重点注意的是ES内部采用怎样的压缩算法。这一点在下一节内容展开来讲。

3、倒排表的压缩算法

既然全文检索经常被用在“大数据检索”这一应用领域，搜索引擎级别的数据量级通常通常在亿级甚至十亿级上，那么也就说如果我们对其建立倒排索引，每个字段被拆分成了若干Term，结果就有可能导致倒排索引的数据量甚至超过了source data，即便我们对倒排索引的检索不必全表扫描，但是太多的数据不管是存储成本还是查询性能可能都不是我们想要的，解决办法就是采用高效的压缩算法和快速的编码和解码算法。

3.1 FOR（Frame Of Reference）

以第一节中的场景为例，假设我们的商品有10亿个，某个Term如“小米”，包含当前词项的docs假如有100万条，每个docid为int类型，占用4个Bytes，也就是32个bit，换算成MB，就是400万字节总占用大小为3200万个bit≈3.8MB。粗略的看，也许你并不觉得3.8MB有多大，但是需要注意的是，倒排索引的数量级很有可能也是亿级甚至更多，这样算来，数据的压缩就是我们不得不考虑的事情。

我们还是以“小米”这个Term为例，加入其对应的倒排表中的id为“[1,2,3…100W]”，我这里有字母W代表万。通常一个数值类型占用的bit数取决于其值的大小，这是数值存储的计算方式决定的，一个bit所能存储的数字个数是21，能存储的最大值就是21-1，也就是[0,1]，同理2个bit的取值范围就是[0,22）或[0,22-1]，其计算公式为n个bit能存储数值的区间为[0,2n)，比如int使用32个bit存储，最大值就是231-1，这里之所以是31次方是因为int是有符号整型，其中一个bit用来存储符号位了，但是由于docId只有正整型，因此在倒排索引的常经理不必考虑负数的情况。那么当前数组中最大值只有100W，我们就可以使用更少的bit来存储，而不是32个bit，那么具体用多少个呢，原则上是2n只要大于100W，n取最小值就可以了，此时n=20。但此时数组中每个数值都需要使用20个bit来存储，这显然是极大的浪费，因为数组前段的数值都非常小，仅用很少的bit就可以存储，这时我们就考虑是否可以用差值存储（dealta list），即不存储原本的数值，而是存储每个数值与前一个数字的差值，这时原本的数字组就变成了[1,1,1…1]，数组中共包含100W个1，如果存储数字1，那么用1个bit就足够存储，也就是我们存储一百万个数字，只需要用100万个bit，虽然看上去还是很多，但是原本存储这些数据需要使用3200W个bit，现在数据压缩了32倍，这也是采用差值存储的理论最该的压缩倍率。如图3-1：

此时或许你已经有了疑惑，实际场景中不可能有这么巧合的情况。没错，那我们以图3-1中的数组[73，300，302，332，343，372]为例，此数组占用的空间大小为4Bytes*6=24Bytes，计算差值列表，结果为[73，227，2，30，11，29]，取差值的目的就是压缩整个数组的取值范围。经过计算后，最大值为227，使用8个bit来存储。但是细心思考可以发现，除了227意外，其他数字都很小，如果都是用8个bit来存储，那么显然浪费了不少存储空间。于是我们尝试将数组进行拆分，将原本一个数组拆分成[73，227]和[2,30,11,29]两个数组，这样做的好处就是第二个数组的数值区间进一步减小了，最大值由227变为了30，这时只需要5个bit就可以存储任意一个数字。而第一个数组还是使用8个bit存储每一个数字。然而问题又来了，为什么我们不对每一个数字单独使用其最合适的bit数来存储，这样岂不是更节省空间么？这就要再次提到关于数据存储的法则“快速的编码和解码”，我们不仅需要把数据尽可能的压缩使其占用更小的空间，还需要对齐进行解码，因为我们最终需要的还是source data，我们deltas list进行拆分的目的是对每个数组使用不同的bit进行合理的空间分配，在这个过程中我们需要对每个数组数组元素使用的bit数进行记录，比如[73，227]这个数组每个数字使用8个bit来存储，这个数字“8”是需要一段空间来记录的，笔者暂且把这块记录空间叫Record Space，这块空间的大小是1个Byte。如果我们把每个数字单独拆分出来，那么也就是我们需要对每个数字单独再开辟出这个1个Byte的空间，得不偿失。所以在计算数组的拆分长度的时候就要权衡得失，尽量把数组保留的足够长，数组越长Record Space所占用的空间越可以忽略不计，但同时数组越扁平越好，取值区间越小越好。比如这个数组：[22, 43, 21, 34, 55, 64, 4322, 345]，就可以吧4322和345拆分出来，因为4322加大了每个数字的bit占用，造成了空间浪费。

最后我们来计算一下经过压缩后的磁盘占用。数组经过拆分，分为了两个数组，第一个数组每个数字占用1个Byte，共两个数字，总占用为2Bytes，记录数组单位大小的Record Space大小为1Byte，第二个数组每个数字占用5个bit，一共四个数字，共计20bit，但是计算空间的最小单位是Byte，所以实际占用的大小为3Bytes，第二个数组的Record Space大小也是1Byte，因此压缩后的数据总大小为1B+2x1B+3B+1B=7Bytes，相比压缩之前，大小不到原先的三分之一。

3.2 RBM（RoaringBitmap）

如果你足够细心，你也许会发现其实上述例子中的数组仍然具有一定的特殊性。没错，他是一个稠密数组，可以理解为是一个取值区间波动不大的数组。如果倒排表中出现这样的情况：[1000W, 2001W, 3003W, 5248W, 9548W, 10212W, … , 21Y]，情况将会特别糟糕，因为我们如果还按照FOR的压缩算法对这个数组进行压缩，我们对其计算dealta list，可以发现其每个项与前一个数字的差值仍然是一个很大的数值，也就意味着dealta list的每个元素仍然是需要很多bit来存储的。于是Lucene对于这种稀疏数组采用了另一种压缩算法：RBM（Roaring Bitmaps）

我们以图3-2中的数组 [1000，62101，131385，132052，191173，196658] 为例，这是一个典型的稀疏型数组。在进行数据压缩的时候，其实不管何种方法，我们的最终目的都是把原来的数字转换成足够小的数字以便于我们存储，同时又必须保证压缩后的数据是可以快速解码的。“减法”不好用，这次我们尝试使用“除法”。由于无符号int类型的最大值不超过232，因此RBM的策略就是把一个int型拆成两个short型的乘机，具体做法是把数组中的每个元素对216取模，因为被除数是232除数是216，因此商和余数均小于216。其实这种想法是国内开发者强行转化的逻辑，RBM算法本身的设计思路是将原数字的的32个bit分为了高16位和低16位。以原数组中的196658这个id为例，将其转化为二进制结果为 110000000000110010，我们看到其实结果是不足32bits的，但因为每个int型都是有32个bit组成的，不足32bit会在其前面补0，实际其占用的空间大小仍然为32bits，如果这一点不理解，打个比方，公交车有32个座位，无论是否坐满，都是使用了32个座位。最终196658转换成二进制就是0000 0000 0000 0011 0000 0000 0011 0010，前16位就是高16位，转换成十进制就是3，后16位也就是低16位，转换成十进制就是50，3和50分别正好是196658除以63326（216）的得数和余数，换句话说，int类型的高16位和低16位分别就是其本身对216的商和模。

对数组中每个数字进行相同的操作，会得到以下结果：（0,1000）（0,62101）（2,313）（2,980）（2,60101）（3,50），其含义就是每个数字都由一个很大的数字变为了两个很小的数字，并且这两个数字都不超过65536，更重要的是，当前结果是非常适合压缩的，因为不难看出，出现了很多重复的数字，比如前两个数字的得数都是0，以及第2、3、4个数字的得数都是2。RBM使用了非常适合存储当前结果的数据结构。这种数据结构是一种类似于哈希的结构，只不过Key值是一个short有序不重复数组，用于保存每个商值，value是一个容器，保存了当前Key值对应的所有模，这些模式不重复的，因为同一个商值的余数是不会重复的。这里的容器官方称之为Container，如图3-3：RBM中包含三种Container，分别是ArrayContainer、BitmapContainer和RunContainer，下面我将对这三种Container展开来逐一讲解。

首先是ArrayContainer，顾名思义，Container中实际就是一个short类型的数组，其空间占用的曲线如图3-4中的红色线段，注意这里是线段，因为docs的数量最大不会超过65536，其函数为 y（空间占用）=x（docs 长度） x 2Bytes，当长度达到65536极限值的时候，其占用的大小就是16bit * 65536 / 8 /1024 = 128KB，乘以65536是总bit数，除以8是换算成Byte，除以1024是换算成KB。

第二种是BitmapContainer，理解BitmapContainer之前首先要了解什么是bitmap。以往最常见的数据存储方式都是二进制进位存储，比如我们使用8个bit存储数字，如果存十进制0，那二进制就是 0 0 0 0 0 0 0 0，如果存十进制1，那就是 0 0 0 0 0 0 0 1，如果存十进制2，那就是 0 0 0 0 0 0 1 1，用到了第二个bit。这种做法在当前场景下存储效率显然不高，如果我们现在不用bit来存储数据，而是用来作为“标记”，即标记当前bit位置商是否存储了数字，出的数字值就是bit的下标，如下图3-5所示，就表示存储了2、3、5、7四个数字，第一行数字的bit仅代表当前index位置上是否存储了数字，如果存储了就记作1，否则记为0，存储的数字值就是其index，并且存储这四个数字只使用了一个字节。

不过这种存储方式的问题就是，存储的数字不能包含重复数字，并且Bitmap的大小是固定的，不管是否存储了数值，不管存储了几个值，占用的空间都是恒定的，只和bit的长度有关系。但是我们刚才已经说过，同一个Container中的数字是不会重复的，因此这种数据类型正好适合用这种数据结构作为载体，而因为我们Container的最大容量是65536，因此Bitmap的长度固定为65536，也就是65536个bit，换算成千字节就是8KB，如图3-4中的蓝色线段所示，即Lucene的RBM中BitmapContainer固定占用8KB大小的空间，通过对比可以发现，当doc的数量小于4096的时候，使用ArrayContainer更加节省空间，当doc数量大于4096的时候，使用BitmapContainer更加节省空间。

第三种Container叫RunContainer，这种类型是Lucene 5之后新增的类型，主要应用在连续数字的存储商，比如倒排表中存储的数组为 [1,2,3…100W] 这样的连续数组，如果使用RunContainer，只需存储开头和结尾两个数字：1和100W，即占用8个字节。这种存储方式的优缺点都很明显，它严重收到数字连续性的影响，连续的数字越多，它存储的效率就越高。