Inverted Index in the Luence

假设有一本书,前面有目录,中间是正文,最后会有附录。有这样一种附录,它会把正文中出现的关键名词列出来,并附上正文中出现的页码。当我们想找某个术语的相关信息时,去附录里查正文出现的页码显然方便些。目录类似于我们常规的索引,一个章节/文件里有什么内容;附录保存的信息和它相反,这个信息出现在哪些章节/文件里。我们称附录这种数据的索引方式叫做“Inverted Index”,中文一般翻译为“倒排索引”。

这种数据结构是搜索程序的核心数据结构,它本身并不复杂,很容易理解,网上的解释也很多,具体可以参考维基百科。因为最近接触ElasticSearch,比较好奇它的倒排索引是怎么实现的。

ElasticSearch是一个基于Lucene的全文搜索引擎。Lucene提供了搜索的核心功能,维护倒排索引是其中的功能之一。

Luence的倒排索引是由许多子片段组成的。每一个子片段是一个完整的能独立工作的子索引,由几个二进制文件组成。当有新的文档需要被索引时,会新建子索引,当有文档被删除时,并不会删除对应的索引数据,而是做标记,记录这些数据已经失效了。子索引数据的合并和删除会在某一时间统一执行。

Luence里对数据的基本定义是这样的:

The fundamental concepts in Lucene are index, document, field and term.

An index contains a sequence of documents.

  • A document is a sequence of fields.

  • A field is a named sequence of terms.

  • A term is a sequence of bytes.

The same sequence of bytes in two different fields is considered a different term. Thus terms are represented as a pair: the string naming the field, and the bytes within the field.

所有这些信息都被保存到几个二进制文件里。Lucene为了减少数据的大小,对数据采用了bit packing的压缩方法。举个例子,一个字节可以表示0~127的无符号数,但是如果我们的数据确定最大不会超过63,那就可以只用4位来表示,这样就省去了一半的空间。类似的方法还有ZigZag编码。这部分实现对应代码org.apache.lucene.util.packed。

为了提高搜索效率,Lucene底层查找Term Dictionary(记录了term在文档中的位置信息)时使用了跳跃链表的数据结构。它相对于平衡二叉树简单,但是也有不错的性能,Redies中也有用到。

Ref