简介： # 前言 Lucene 是一个基于 Java 的全文信息检索工具包，目前主流的搜索系统Elasticsearch和solr都是基于lucene的索引和搜索能力进行。想要理解搜索系统的实现原理，就需要深入lucene这一层，看看lucene是如何存储需要检索的数据，以及如何完成高效的数据检索。

前言

Lucene 是一个基于 Java 的全文信息检索工具包，目前主流的搜索系统Elasticsearch和solr都是基于lucene的索引和搜索能力进行。想要理解搜索系统的实现原理，就需要深入lucene这一层，看看lucene是如何存储需要检索的数据，以及如何完成高效的数据检索。

在数据库中因为有索引的存在，也可以支持很多高效的查询操作。不过对比lucene，数据库的查询能力还是会弱很多，本文就将探索下lucene支持哪些查询，并会重点选取几类查询分析lucene内部是如何实现的。为了方便大家理解，我们会先简单介绍下lucene里面的一些基本概念，然后展开lucene中的几种数据存储结构，理解了他们的存储原理后就可以方便知道如何基于这些存储结构来实现高效的搜索。本文重点关注是lucene如何做到传统数据库较难做到的查询，对于分词，打分等功能不会展开介绍。

本文具体会分以下几部分：

1. 介绍lucene的数据模型，细节可以参阅lucene数据模型一文。
2. 介绍lucene中如何存储需要搜索的term。
3. 介绍lucene的倒排链的如何存储以及如何实现docid的快速查找。
4. 介绍lucene如何实现倒排链合并。
5. 介绍lucene如何做范围查询和前缀匹配。

6. 介绍lucene如何优化数值类范围查询。

Lucene数据模型

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

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

在lucene中，读写路径是分离的。写入的时候创建一个IndexWriter，而读的时候会创建一个IndexSearcher，
下面是一个简单的代码示例，如何使用lucene的IndexWriter建索引以及如何使用indexSearch进行搜索查询。

    Analyzer analyzer = new StandardAnalyzer();

    // Store the index in memory:

    Directory directory = new RAMDirectory();

    // To store an index on disk, use this instead:

    //Directory directory = FSDirectory.open("/tmp/testindex");

    IndexWriterConfig config = new IndexWriterConfig(analyzer);

    IndexWriter iwriter = new IndexWriter(directory, config);

    Document doc = new Document();

    String text = "This is the text to be indexed.";

    doc.add(new Field("fieldname", text, TextField.TYPE_STORED));

    iwriter.addDocument(doc);

    iwriter.close();

    // Now search the index:

    DirectoryReader ireader = DirectoryReader.open(directory);

    IndexSearcher isearcher = new IndexSearcher(ireader);

    // Parse a simple query that searches for "text":

    QueryParser parser = new QueryParser("fieldname", analyzer);

    Query query = parser.parse("text");

    ScoreDoc[] hits = isearcher.search(query, 1000).scoreDocs;

    //assertEquals(1, hits.length);

    // Iterate through the results:

    for (int i = 0; i < hits.length; i++) {

         Document hitDoc = isearcher.doc(hits[i].doc);

         System.out.println(hitDoc.get("fieldname"));

    }

    ireader.close();

    directory.close();

从这个示例中可以看出，lucene的读写有各自的操作类。本文重点关注读逻辑，在使用IndexSearcher类的时候，需要一个DirectoryReader和QueryParser，其中DirectoryReader需要对应写入时候的Directory实现。QueryParser主要用来解析你的查询语句，例如你想查 “A and B"，lucene内部会有机制解析出是term A和term B的交集查询。在具体执行Search的时候指定一个最大返回的文档数目，因为可能会有过多命中，我们可以限制单词返回的最大文档数，以及做分页返回。

下面会详细介绍一个索引查询会经过几步，每一步lucene分别做了哪些优化实现。

Lucene 查询过程

在lucene中查询是基于segment。每个segment可以看做是一个独立的subindex，在建立索引的过程中，lucene会不断的flush内存中的数据持久化形成新的segment。多个segment也会不断的被merge成一个大的segment，在老的segment还有查询在读取的时候，不会被删除，没有被读取且被merge的segement会被删除。这个过程类似于LSM数据库的merge过程。下面我们主要看在一个segment内部如何实现高效的查询。

为了方便大家理解，我们以人名字，年龄，学号为例，如何实现查某个名字（有重名）的列表。

docid	name	age	id
1	Alice	18	101
2	Alice	20	102
3	Alice	21	103
4	Alan	21	104
5	Alan	18	105

在lucene中为了查询name=XXX的这样一个条件，会建立基于name的倒排链。以上面的数据为例，倒排链如下：
姓名

Alice | [1,2,3]
---- | --- | 
Alan | [4,5]
如果我们还希望按照年龄查询，例如想查年龄=18的列表，我们还可以建立另一个倒排链：

18 | [1,5]
---| --- | 
20 | [2]
21 | [3,4]

在这里，Alice，Alan，18，这些都是term。所以倒排本质上就是基于term的反向列表，方便进行属性查找。到这里我们有个很自然的问题，如果term非常多，如何快速拿到这个倒排链呢？在lucene里面就引入了term dictonary的概念，也就是term的字典。term字典里我们可以按照term进行排序，那么用一个二分查找就可以定为这个term所在的地址。这样的复杂度是logN，在term很多，内存放不下的时候，效率还是需要进一步提升。可以用一个hashmap，当有一个term进入，hash继续查找倒排链。这里hashmap的方式可以看做是term dictionary的一个index。 从lucene4开始，为了方便实现rangequery或者前缀，后缀等复杂的查询语句，lucene使用FST数据结构来存储term字典，下面就详细介绍下FST的存储结构。

FST

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

1. 插入“Alan”
   

2. 插入“Alice”
   

这样你就得到了一个有向无环图，有这样一个数据结构，就可以很快查找某个人名是否存在。FST在单term查询上可能相比hashmap并没有明显优势，甚至会慢一些。但是在范围，前缀搜索以及压缩率上都有明显的优势。

在通过FST定位到倒排链后，有一件事情需要做，就是倒排链的合并。因为查询条件可能不止一个，例如上面我们想找name="alan" and age="18"的列表。lucene是如何实现倒排链的合并呢。这里就需要看一下倒排链存储的数据结构

SkipList

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

1. 元素排序的，对应到我们的倒排链，lucene是按照docid进行排序，从小到大。
2. 跳跃有一个固定的间隔，这个是需要建立SkipList的时候指定好，例如下图以间隔是3
3. SkipList的层次，这个是指整个SkipList有几层
   

有了这个SkipList以后比如我们要查找docid=12，原来可能需要一个个扫原始链表，1，2，3，5，7，8，10，12。有了SkipList以后先访问第一层看到是然后大于12，进入第0层走到3，8，发现15大于12，然后进入原链表的8继续向下经过10和12。
有了FST和SkipList的介绍以后，我们大体上可以画一个下面的图来说明lucene是如何实现整个倒排结构的：

有了这张图，我们可以理解为什么基于lucene可以快速进行倒排链的查找和docid查找，下面就来看一下有了这些后如何进行倒排链合并返回最后的结果。

倒排合并

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

在lucene中会采用下列顺序进行合并：

1. 在termA开始遍历，得到第一个元素docId=1
2. Set currentDocId=1

3. 在termB中 search(currentDocId) = 1 (返回大于等于currentDocId的一个doc),

   1. 因为currentDocId ==1，继续
   2. 如果currentDocId 和返回的不相等，执行2，然后继续
4. 到termC后依然符合，返回结果
5. currentDocId = termC的nextItem
6. 然后继续步骤3 依次循环。直到某个倒排链到末尾。

整个合并步骤我可以发现，如果某个链很短，会大幅减少比对次数，并且由于SkipList结构的存在，在某个倒排中定位某个docid的速度会比较快不需要一个个遍历。可以很快的返回最终的结果。从倒排的定位，查询，合并整个流程组成了lucene的查询过程，和传统数据库的索引相比，lucene合并过程中的优化减少了读取数据的IO，倒排合并的灵活性也解决了传统索引较难支持多条件查询的问题。

BKDTree

在lucene中如果想做范围查找，根据上面的FST模型可以看出来，需要遍历FST找到包含这个range的一个点然后进入对应的倒排链，然后进行求并集操作。但是如果是数值类型，比如是浮点数，那么潜在的term可能会非常多，这样查询起来效率会很低。所以为了支持高效的数值类或者多维度查询，lucene引入类BKDTree。BKDTree是基于KDTree，对数据进行按照维度划分建立一棵二叉树确保树两边节点数目平衡。在一维的场景下，KDTree就会退化成一个二叉搜索树，在二叉搜索树中如果我们想查找一个区间，logN的复杂度就会访问到叶子结点得到对应的倒排链。如下图所示：

如果是多维，kdtree的建立流程会发生一些变化。
比如我们以二维为例，建立过程如下：

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

下图是一个建立例子：

BKDTree是KDTree的变种，因为可以看出来，KDTree如果有新的节点加入，或者节点修改起来，消耗还是比较大。类似于LSM的merge思路，BKD也是多个KDTREE，然后持续merge最终合并成一个。不过我们可以看到如果你某个term类型使用了BKDTree的索引类型，那么在和普通倒排链merge的时候就没那么高效了所以这里要做一个平衡，一种思路是把另一类term也作为一个维度加入BKDTree索引中。

如何实现返回结果进行排序聚合

通过之前介绍可以看出lucene通过倒排的存储模型实现term的搜索，那对于有时候我们需要拿到另一个属性的值进行聚合，或者希望返回结果按照另一个属性进行排序。在lucene4之前需要把结果全部拿到再读取原文进行排序，这样效率较低，还比较占用内存，为了加速lucene实现了fieldcache，把读过的field放进内存中。这样可以减少重复的IO，但是也会带来新的问题，就是占用较多内存。新版本的lucene中引入了DocValues，DocValues是一个基于docid的列式存储。当我们拿到一系列的docid后，进行排序就可以使用这个列式存储，结合一个堆排序进行。当然额外的列式存储会占用额外的空间，lucene在建索引的时候可以自行选择是否需要DocValue存储和哪些字段需要存储。

Lucene的代码目录结构

介绍了lucene中几个主要的数据结构和查找原理后，我们在来看下lucene的代码结构，后续可以深入代码理解细节。lucene的主要有下面几个目录：

1. analysis模块主要负责词法分析及语言处理而形成Term。
2. codecs模块主要负责之前提到的一些数据结构的实现，和一些编码压缩算法。包括skiplist，docvalue等。
3. document模块主要包括了lucene各类数据类型的定义实现。
4. index模块主要负责索引的创建，里面有IndexWriter。
5. store模块主要负责索引的读写。
6. search模块主要负责对索引的搜索。
7. geo模块主要为geo查询相关的类实现
8. util模块是bkd，fst等数据结构实现。

最后

本文介绍了lucene中的一些主要数据结构，以及如何利用这些数据结构实现高效的查找。我们希望通过这些介绍可以加深理解倒排索引和传统数据库索引的区别，数据库有时候也可以借助于搜索引擎实现更丰富的查询语意。除此之外，做为一个搜索库，如何进行打分，query语句如何进行parse这些我们没有展开介绍，有兴趣的同学可以深入lucene的源码进一步了解。

 

时间序列数据库的秘密(2)——索引 - InfoQ https://www.infoq.cn/article/database-timestamp-02/

如何快速检索？

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

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

Term Index --> Term Dictionary --> Posting List

这里有好几个概念。我们来看一个实际的例子，假设有如下的数据：

docid

年龄

性别

1

18

女

2

20

女

3

18

男

这里每一行是一个 document。每个 document 都有一个 docid。那么给这些 document 建立的倒排索引就是：

年龄

性别

可以看到，倒排索引是 per field 的，一个字段由一个自己的倒排索引。18,20 这些叫做 term，而 [1,3] 就是 posting list。Posting list 就是一个 int 的数组，存储了所有符合某个 term 的文档 id。那么什么是 term dictionary 和 term index？

假设我们有很多个 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 的时间）。所以尽量少的读磁盘，有必要把一些数据缓存到内存里。但是整个 term dictionary 本身又太大了，无法完整地放到内存里。于是就有了 term index。term index 有点像一本字典的大的章节表。比如：

A 开头的 term ……………. Xxx 页

C 开头的 term ……………. Xxx 页

E 开头的 term ……………. Xxx 页

如果所有的 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 树。这棵树不会包含所有的 term，它包含的是 term 的一些前缀。通过 term index 可以快速地定位到 term dictionary 的某个 offset，然后从这个位置再往后顺序查找。再加上一些压缩技术（搜索 Lucene Finite State Transducers） term index 的尺寸可以只有所有 term 的尺寸的几十分之一，使得用内存缓存整个 term index 变成可能。整体上来说就是这样的效果。

现在我们可以回答“为什么 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 更节约磁盘空间。

如何联合索引查询？

所以给定查询过滤条件 age=18 的过程就是先从 term index 找到 18 在 term dictionary 的大概位置，然后再从 term dictionary 里精确地找到 18 这个 term，然后得到一个 posting list 或者一个指向 posting list 位置的指针。然后再查询 gender= 女 的过程也是类似的。最后得出 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。

利用 Skip List 合并

以上是三个 posting list。我们现在需要把它们用 AND 的关系合并，得出 posting list 的交集。首先选择最短的 posting list，然后从小到大遍历。遍历的过程可以跳过一些元素，比如我们遍历到绿色的 13 的时候，就可以跳过蓝色的 3 了，因为 3 比 13 要小。

整个过程如下

	Next -> 2
	Advance(2) -> 13
	Advance(13) -> 13
	Already on 13
	Advance(13) -> 13 MATCH!!!
	Next -> 17
	Advance(17) -> 22
	Advance(22) -> 98
	Advance(98) -> 98
	Advance(98) -> 98 MATCH!!!

最后得出的交集是 [13,98]，所需的时间比完整遍历三个 posting list 要快得多。但是前提是每个 list 需要指出 Advance 这个操作，快速移动指向的位置。什么样的 list 可以这样 Advance 往前做蛙跳？skip list：

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

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

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

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

然后可以构建出 skip list 的第二层：

[1,101,255]

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

Lucene 自然会对这个 block 再次进行压缩。其压缩方式叫做 Frame Of Reference 编码。示例如下：

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

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

利用 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 遍。

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

如何减少文档数？

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

这个过程可以示例如下：

12:05:00

10

12:05:01

15

12:05:02

14

12:05:03

16

合并之后就变成了：

可以看到，行变成了列了。每一列可以代表这一分钟内一秒的数据。

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}
	]
	}

这样可以把数据点公共的维度字段上移到父文档里，而不用在每个子文档里重复存储，从而减少索引的尺寸。

（图片来源：https://www.youtube.com/watch?v=Su5SHc_uJw8，Faceting with Lucene Block Join Query）

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

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

作者简介

陶文，曾就职于腾讯 IEG 的蓝鲸产品中心，负责过告警平台的架构设计与实现。2006 年从 ThoughtWorks 开始职业生涯，在大型遗留系统的重构，持续交付能力建设，高可用分布式系统构建方面积累了丰富的经验