Lucene学习图解

lucene基本原理
Lucene学习总结之一：全文检索的基本原理
Lucene底层原理和优化经验分享(1)-Lucene简介和索引原理

lucence组成部分：索引构建，索引搜索，索引管理（优化合并段）

image.png image.png

字典和倒排表

image.png

字典的数据结构

image.png

其中可用的有：B+树、跳跃表、FST
　　B+树：
　　　　　　　　　　　　　　mysql的InnoDB B+数结构

image.png

理论基础：平衡多路查找树
优点：外存索引、可更新
缺点：空间大、速度不够快

跳跃表：

image.png

优点：结构简单、跳跃间隔、级数可控，Lucene3.0之前使用的也是跳跃表结构，后换成了FST，但跳跃表在Lucene其他地方还有应用如倒排表合并和文档号索引。
缺点：模糊查询支持不好

FST
　　Lucene现在使用的索引结构

image.png

理论基础: 《Direct construction of minimal acyclic subsequential transducers》，通过输入有序字符串构建最小有向无环图。
优点：内存占用率低，压缩率一般在3倍~20倍之间、模糊查询支持好、查询快
缺点：结构复杂、输入要求有序、更新不易
Lucene里有个FST的实现，从对外接口上看，它跟Map结构很相似，有查找，有迭代：

Lucene索引实现
（本文对Lucene的原理介绍都是基于4.10.3）
　　Lucene经多年演进优化，现在的一个索引文件结构如图所示，基本可以分为三个部分：词典、倒排表、正向文件、列式存储DocValues。

image.png

倒排表结构

倒排表就是文档号集合，但怎么存，怎么取也有很多讲究，Lucene现使用的倒排表结构叫Frame of reference,它主要有两个特点：
　　1. 数据压缩，可以看下图怎么将6个数字从原先的24bytes压缩到7bytes。

image.png

2. 跳跃表加速合并，因为布尔查询时，and 和or 操作都需要合并倒排表，这时就需要快速定位相同文档号，所以利用跳跃表来进行相同文档号查找。
　　这部分可参考ElasticSearch的一篇博客，里面有一些性能测试：
　　ElasticSearch 倒排表

正向文件

正向文件指的就是原始文档，Lucene对原始文档也提供了存储功能，它存储特点就是分块+压缩，fdt文件就是存放原始文档的文件，它占了索引库90%的磁盘空间，fdx文件为索引文件，通过文档号（自增数字）快速得到文档位置，它们的文件结构如下：

　　 image.png