掌握它才说明你真正懂 Elasticsearch - Lucene (一)

Lucene 简介

Lucene 是一种高性能、可伸缩的信息搜索(IR)库,在 2000 年开源,最初由鼎鼎大名的 Doug Cutting 开发,是基于 Java 实现的高性能的开源项目。

Lucene 采用了基于倒排表的设计原理,可以非常高效地实现文本查找,在底层采用了分段的存储模式,使它在读写时几乎完全避免了锁的出现,大大提升了读写性能。

核心模块

Lucene 的写流程和读流程如下图所示:

其中,虚线箭头(a、b、c、d)表示写索引的主要过程,实线箭头(1-9)表示查询的主要过程。

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

  • analysis:主要负责词法分析及语言处理,也就是我们常说的分词,通过该模块可最终形成存储或者搜索的最小单元 Term。

  • index 模块:主要负责索引的创建工作。

  • store 模块:主要负责索引的读写,主要是对文件的一些操作,其主要目的是抽象出和平台文件系统无关的存储。

  • queryParser 模块:主要负责语法分析,把我们的查询语句生成 Lucene 底层可以识别的条件。

  • search 模块:主要负责对索引的搜索工作。

  • similarity 模块:主要负责相关性打分和排序的实现

核心术语

下面介绍 Lucene 中的核心术语:

  • Term:是索引里最小的存储和查询单元,对于英文来说一般是指一个单词,对于中文来说一般是指一个分词后的词。

  • 词典(Term Dictionary,也叫作字典):是 Term 的集合。词典的数据结构可以有很多种,每种都有自己的优缺点。

    比如:排序数组通过二分查找来检索数据:HashMap(哈希表)比排序数组的检索速度更快,但是会浪费存储空间。

    FST(finite-state transducer)有更高的数据压缩率和查询效率,因为词典是常驻内存的,而 FST 有很好的压缩率,所以 FST 在 Lucene 的最新版本中有非常多的使用场景,也是默认的词典数据结构。

  • 倒排序(Posting List):一篇文章通常由多个词组成,倒排表记录的是某个词在哪些文章中出现过。

  • 正向信息:原始的文档信息,可以用来做排序、聚合、展示等。

  • 段(Segment):索引中最小的独立存储单元。一个索引文件由一个或者多个段组成。在 Luence 中的段有不变性,也就是说段一旦生成,在其上只能有读操作,不能有写操作。

Lucene 的底层存储格式如下图所示,由词典和倒排序两部分组成,其中的词典就是 Term 的集合:

词典中的 Term 指向的文档链表的集合,叫做倒排表。词典和倒排表是 Lucene 中很重要的两种数据结构,是实现快速检索的重要基石。

词典和倒排表是分两部分存储的,在倒排序中不但存储了文档编号,还存储了词频等信息。

在上图所示的词典部分包含三个词条(Term):Elasticsearch、Lucene 和 Solr。词典数据是查询的入口,所以这部分数据是以 FST 的形式存储在内存中的。

在倒排表中,“Lucene”指向有序链表 3,7,15,30,35,67,表示字符串“Lucene”在文档编号为3、7、15、30、35、67的文章中出现过,Elasticsearch 和 Solr 同理。
检索方式

在 Lucene 的查询过程中的主要检索方式有以下四种:

①单个词查询

指对一个 Term 进行查询。比如,若要查找包含字符串“Lucene”的文档,则只需在词典中找到 Term“Lucene”,再获得在倒排表中对应的文档链表即可。

②AND

指对多个集合求交集。比如,若要查找既包含字符串“Lucene”又包含字符串“Solr”的文档,则查找步骤如下:

  • 在词典中找到 Term “Lucene”,得到“Lucene”对应的文档链表。

  • 在词典中找到 Term “Solr”,得到“Solr”对应的文档链表。

  • 合并链表,对两个文档链表做交集运算,合并后的结果既包含“Lucene”也包含“Solr”。

③OR

指多个集合求并集。比如,若要查找包含字符串“Luence”或者包含字符串“Solr”的文档,则查找步骤如下:

  • 在词典中找到 Term “Lucene”,得到“Lucene”对应的文档链表。

  • 在词典中找到 Term “Solr”,得到“Solr”对应的文档链表。

  • 合并链表,对两个文档链表做并集运算,合并后的结果包含“Lucene”或者包含“Solr”。

④NOT

指对多个集合求差集。比如,若要查找包含字符串“Solr”但不包含字符串“Lucene”的文档,则查找步骤如下:

  • 在词典中找到 Term “Lucene”,得到“Lucene”对应的文档链表。

  • 在词典中找到 Term “Solr”,得到“Solr”对应的文档链表。

  • 合并链表,对两个文档链表做差集运算,用包含“Solr”的文档集减去包含“Lucene”的文档集,运算后的结果就是包含“Solr”但不包含“Lucene”。

通过上述四种查询方式,我们不难发现,由于 Lucene 是以倒排表的形式存储的。

所以在 Lucene 的查找过程中只需在词典中找到这些 Term,根据 Term 获得文档链表,然后根据具体的查询条件对链表进行交、并、差等操作,就可以准确地查到我们想要的结果。

相对于在关系型数据库中的“Like”查找要做全表扫描来说,这种思路是非常高效的。

虽然在索引创建时要做很多工作,但这种一次生成、多次使用的思路也是非常高明的。

摘抄 石杉的架构笔记 钱丁君

本作品采用《CC 协议》,转载必须注明作者和本文链接

快乐就是解决一个又一个的问题!

讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!