Lucene 查询原理及解析

前言

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

在数据中因为有索引的存在，也可以支持很多有效的查询操作。不过对比Lucene，数据的查询能力还是会弱很多，本文就将探索下Lucene支持支持哪些查询，并会分析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进行搜索查询。

Lucene中的文件操作都是通过这Directory来实现的，Directory的实现类分为文件目录、内存目录和目录的代理类及工具类。

目录类型	说明
FSDirectory	文件系统目录操作的父类，基本实现的文件目录操作
SimpleFSDirectory	FSDirectory的简单实现,并发能力有限，遇到多线程读同一个文件时会遇到瓶颈，通常用NIOFSDirectory或MMapDirectory代替
NIOFSDirectory	通过java.nio’s FileChannel实行定位读取，支持多线程读（默认情况下是线程安全的）。该类仅使用FileChannel进行读操作，写操作则是通过FSIndexOutput实现。注意：NIOFSDirectory 不适用于Windows系统，另外如果一个访问该类的线程，在IO阻塞时被interrupt或cancel，将会导致底层的文件描述符被关闭，后续的线程再次访问NIOFSDirectory时将会出现ClosedChannelException异常，此种情况应用SimpleFSDirectory代替。
MMapDirectory	通过内存映射进行读，通过FSIndexOutput进行写的FSDirectory实现类。使用该类时要保证用足够的虚拟地址空间。另外当通过IndexInput的close方法进行关闭时并不会立即关闭底层的文件句柄，只有GC进行资源回收时才会关闭

具体代码如下：

<dependency>
 <groupId>org.apache.lucene</groupId>
 <artifactId>lucene-core</artifactId>
 <version>7.7.2</version>
</dependency>
<dependency>
 <groupId>org.apache.lucene</groupId>
 <artifactId>lucene-queryparser</artifactId>
 <version>7.7.2</version>
</dependency>
<dependency>
 <groupId>org.apache.lucene</groupId>
 <artifactId>lucene-analyzers-common</artifactId>
 <version>7.7.2</version>
</dependency>

Analyzer analyzer = new StandardAnalyzer();
//索引存储在内存中；
File file = new File("/Users/data/lucene/test");
Path path = file.toPath();
Directory directory = new MMapDirectory(path);
//也可以将索引存储在硬盘上
//Directory directory = FSDirectory.open("/tmp/testindex");
IndexWriterConfig config = new IndexWriterConfig(analyzer);
IndexWriter iwriter = new IndexWriter(directory, config);
Document doc = new Document();
String text = "这是文本索引测试";
doc.add(new Field("fieldname", text, TextField.TYPE_STORED));
iwriter.aDDDocument(doc);
iwriter.close();

//现在开始搜索刚才创建的索引。
DirectoryReader ireader = DirectoryReader.open(directory);
IndexSearcher isearcher = new IndexSearcher(ireader);
QueryParser parse = new QueryParser("fieldname", analyzer);
Query query = parser.parse("文本");
ScoreDoc[] hits = isearcher.search(query, 100).scoreDocs;
for(Document hitDoc : hits){
  System.out.println(hitDoc.get("fieldname"));
}
ireader.close();
directory.close();

在使用IndexSearcher类的时候，需要一个DirectoryReader和QueryParser，其中DIrectoryReader需要对应写入时候的Directory实现。QueryParser主要来解析你的查询语句，例如你想查询 “A and B”，Lucene内部会有机制解析出term A和term B的交集查询。

Lucene 查询过程分析

在Lucene中查询基于segment，每个segment可以看成是一个独立的sub index。在建立索引的过程中，Lucene会不断flush内存中的数据持久化形成新的segment。多个segment也会不断的被merge成一个大的segment，在老的segment还有查询在读取时，不会被删除，没有被读取且被merge的会被删除。这个过程类似LSM数据库的merge过程。

docid	name	Age
1	Alice	18
2	Alan	20
3	Tony	18

在Lucene中为了查询条件age=18，会建立基于age的倒排链，如下：

age	Docid
18	[1,3]
20	[2]

所以倒排本质上就是基于term的方向列表。

如果term非常多，如何快速拿到这个倒排链呢？在Lucene就引入term dictionary的概念，也就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”。

插入“Alan”

插入“Alice”

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

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

SkipList

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

元素排序的，对应到我们的倒排链，lucene是按照docid进行排序，从小到大。
跳跃有一个固定的间隔，这个是需要建立SkipList的时候指定好，例如下图间隔是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中会采用下列顺序进行合并：

在termA开始遍历，得到第一个元素docId=1
Set currentDocId=1
在termB中 search(currentDocId) = 1 (返回大于等于currentDocId的一个doc),

因为currentDocId ==1，继续
如果currentDocId 和返回的不相等，执行2，然后继续

到termC后依然符合，返回结果
currentDocId = termC的nextItem
然后继续步骤3 依次循环。直到某个倒排链到末尾。

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

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

通过之前介绍可以看出Lucene通过倒排的存储模型实现term的搜索，那对于有时候我们需要拿到另一个属性的值进行聚合，或者希望返回结果按照另一个属性进行排序。

在Lucene4之前需要把结果全部拿到再读取原文进行排序，这样效率较低，还比较占用内存，为了加速Lucene实现了fieldcache，把读过的field放进内存中。这样可以减少重复的IO，但是也会带来新的问题，就是占用较多内存。

新版本的Lucene中引入了DocValues，DocValues是一个基于docid的列式存储。当我们拿到一系列的docid后，进行排序就可以使用这个列式存储，结合一个堆排序进行。当然额外的列式存储会占用额外的空间，Lucene在建索引的时候可以自行选择是否需要DocValue存储和哪些字段需要存储。

Lucene的代码目录结构

简单介绍了lucene中几个主要的数据结构和查找原理后，我们再来看下Lucene的代码结构目录：

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

最后

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