1、倒排索引原理
倒排索引，简单来说是通过分词策略，形成了词和文章的映射关系表，这种词典+映射表即为倒排索引。有了倒排索引，就能实现O(1)时间复杂度的效率检索文章了，极大的提高了检索效率。
Lucene在查询过程中是基于segment。每个segment可以看做是一个独立的subindex，在建立索引的过程中，lucene会不断的flush内存中的数据持久化形成新的segment。多个segment也会不断的被merge成一个大的segment，在老的segment还有查询在读取的时候，不会被删除，没有被读取且被merge的segement会被删除。这个过程类似于LSM数据库的merge过程（这里涉及es分片，详见【ES分片原理与规划】）。下面我们主要看在一个segment内部如何实现高效的查询。
Lucene的倒排索引为一个term词典表+倒排表。它从词出发，记载了这个词在哪些文档中出现过，如下是一个详细的倒排索引表，每一个单词，后面对应着它的文档频率，文档ID、该文档中的词频率以及出现的位置。
倒排索引表
2、Term字典设计——假如term非常多，如何快速拿到这个倒排链呢？
在lucene里面就引入了term dictonary的概念。term字典里我们可以按照term进行排序，假如用一个二分查找就可以定为这个term所在的地址。这样的复杂度是logN，在term很多，内存放不下的时候，效率还是需要进一步提升。可以用一个hashmap，当有一个term进入，hash继续查找倒排链。这里hashmap的方式可以看做是term dictionary的一个index。 从lucene4开始，为了方便实现rangequery或者前缀，后缀等复杂的查询语句，lucene使用FST数据结构来存储term字典，下面就详细介绍下FST的存储结构。
倒排索引的底层实现是基于：FST（Finite State Transducer）数据结构。
常见词典的优缺点
FST(有限状态转换器)是一个有向无环图，有这样一个数据结构，就可以很快查找某个人名是否存在。FST在单term查询上可能相比hashmap并没有明显优势，甚至会慢一些。但是在范围，前缀搜索以及压缩率上都有明显的优势。
3、SkipList跳表——如何快速查找文档docId
为了能够快速查找docid，lucene采用了SkipList这一数据结构。
- 元素排序的，对应到我们的倒排链，lucene是按照docid进行排序，从小到大。
- 跳跃有一个固定的间隔，这个是需要建立SkipList的时候指定好，例如下图以间隔是3
- SkipList的层次，这个是指整个SkipList有几层
skipList
有了这个SkipList以后比如我们要查找docid=12，原来可能需要一个个扫原始链表，1，2，3，5，7，8，10，12。有了SkipList以后先访问第一层看到是然后大于12，进入第0层走到3，8，发现15大于12，然后进入原链表的8继续向下经过10和12。
source：【Lucene 查询原理】
网友评论