Lucene 查询原理

数据库

发布日期: 2021-02-25

作者: 锦泉

文章字数: 2.7k

阅读时长: 10 分

阅读次数:

前言

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

转载至阿里云：https://zhuanlan.zhihu.com/p/35814539 | https://blog.csdn.net/baichoufei90/article/details/111303223

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的交集查询。

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

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

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

Lucene 查询过程

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

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

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

如果我们还希望按照年龄查询，例如想查年龄=18 的列表，我们还可以建立另一个倒排链：

在这里，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”。

插入“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。

SkipList本质上是在有序的链表上实现实现二分查找，它能有效的提升链表的查找效率，其时间复杂度为O(logn)（其中n为链表长度）。简单说SkipList优化了Postings的随机查找的性能问题。

SkipList的节点存储了三部分数据：

当前节点指向Block的信息，是关于Block本身的信息；
指向下层的索引；
存储freq和norm的信息，它被封装在Impact里面。

Impact结构仅是 <freq, norm> 的键值对，与文档无关，在SkipList的索引节点中。Impacts表示一系列Impact结构，用有序的TreeSet存储。这里强调的是Impact并没有与具体文档关联，其次按freq和norm作为主键去重。也就是Impacts代表了该索引节点指向数据点以及之前所有数据节点所包含的文档得分的分布。

如果此索引节点中最大的Impact都小于Scorer的水位线，那么此节点的范围内的所有节点都不需要再进入Scorer评分程序，在TOP_SCORE模式下。

实际上SkipList的性能提升是通过在链表上加上多级索引获得的，所以说它属于空间换时间的做法，在索引时牺牲小量空间换取在搜索时的性能提升。而层级越高，索引的步长越短，构建索引的空间代价也会越高。这也解释了Lucene为什么要采用8个Block作为步长，虽然它的查询性能相比会差一些，但是需要的空间也缩减少n/8，是一种存储空间和性能的折中方案。

倒排结构图解

有了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，这一步搜索时就会进行SkipList数据跳过）,
1. 因为currentDocId ==search结果1，继续
2. 如果currentDocId 和search返回的不相等，则执行2，然后继续（执行2是什么意思。。。）
到termC后搜索结果依然符合，返回结果
Set currentDocId = termC.nextItem = 2
然后继续步骤3 依次循环。直到某个倒排链到末尾。

这里有点看不明白，留个坑

整个合并步骤我可以发现，如果某个链很短，会大幅减少比对次数，并且由于SkipList结构的存在，在某个倒排中定位某个docid的速度会比较快不需要一个个遍历（该例子所需的时间比完整遍历三个posting list要快得多，但是前提是每个list需要使用SkipList独有的Advance操作）。可以很快的返回最终的结果。从倒排的定位，查询，合并整个流程组成了lucene的查询过程，和传统数据库的索引相比，lucene合并过程中的优化减少了读取数据的IO，倒排合并的灵活性也解决了传统索引较难支持多条件查询的问题。

转载规则