怎样解析Lucene查询原理

16次阅读
没有评论

这篇文章将为大家详细讲解有关怎样解析 Lucene 查询原理,文章内容质量较高,因此丸趣 TV 小编分享给大家做个参考,希望大家阅读完这篇文章后对相关知识有一定的了解。

前言

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

在数据库中因为有索引的存在,也可以支持很多高效的查询操作。不过对比 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 进行搜索查询。

 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 内部如何实现高效的查询。

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

docidnameageid1Alice181012Alice201023Alice211034Alan211045Alan18105

在 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”。

插入“Alan”
怎样解析 Lucene 查询原理

插入“Alice”
怎样解析 Lucene 查询原理

有了这个 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 查询原理

在 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,倒排合并的灵活性也解决了传统索引较难支持多条件查询的问题。

BKDTree

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

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 查询原理就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。