Lucene
简介
Lucene是用Java语言开发的一款开源检索工具，提供了索引构建以及查询的能力。Lucene目前是Apache基金会jakarta项目组的一个子项目，除了作为SDK集成在业务应用中提供检索功能之外，ElasticSearch、Solr等全文搜索引擎都基于Lucene实现。
Lucene的索引结构可以分为索引，段，文档，域，词等几个层级。
- 索引（Index）：索引是Lucene可以对外提供检索服务的基本单元，一个索引包含的文档通用具有相同的schema，这些文档经过分词建立索引文件之后存储在持久化存储，例如数据库或文件目录。
- 段（Segment）：一个索引可以包含多个彼此独立的段。Lucene进行关键词检索时需要加载所有的段，索引段较多会增加I/O开销，减慢检索速度，Lucene提供了段合并策略定期对段进行合并。
- 文档（Document）：文档是需要建立索引的数据，文档一般有会多个字段，这些字段建立索引之后存储在Index的Segment中。
- 域（Field）：文档一般会包含多种不同的字段，这些字段在建立索引的过程会会有不同的属性，例如是否需要存储，是否需要分词等。
- 词（Item）：Lucene会通过分词器将字段中的字符串拆分成词序列，这些词会以倒排索引的形式存储在索引中。
原理
lucene框架的使用流程一般分为创建索引以及查询检索两部分。
首先建立索引，Lucene采用倒排索引存储词到文档的信息。除了倒排索引之外，Lucene对索引中的词（Item）通过压缩结构建立表字典表，字典表可以定位一个词在倒排索引中的位置。
检索过程首先对输入进行分词，然后分别检索这些词对应的文档，通过一定的合并策略（交集或者并集）再加上加分机制返回结果。
索引结构
lucene最核心的概念是倒排索引的概念。
索引一般是指通过数据的ID可以快速定位数据位置或者数据内容的辅助数据结构，例如Mysql使用的B+树聚簇索引，就是通过主键可以快速查找数据记录，因为检索的过程是通过请求的词查询相关的文档，所以倒排索引存储的是词（数据）到数据ID的记录，通常称为倒排索引。
lucene倒排索引的结构是每个词维护一个文档列表，文档列表中每个元素都记录了文档ID，除了文档ID之后，倒排索引中还可以包含词在文档中的位置，偏移量等信息，这些信息分别存储在不同的文件。
| 内容 | 作用 | 文件 |
|---|---|---|
| 文档ID | 用于检索包含词的文档 | .doc |
| 词频 | 记录term在每篇文档中出现的次数，用于后续相关性的计算 | .doc |
| 位置 | 用于高亮展示 | .pos |
| 偏移 | 用于高亮和相关性排序 | .pay |
| payload | 记录payload信息 | .pay |
除了文档ID是索引中的必要信息，词频，偏移量等信息是否存储取决于创建索引的Document的Schema配置，不同的Field有可以有不同的FieldType决定这些信息是否保存，常用的FieldType有如下几种。
| 文档ID | 词频 | 位置 | 偏移量 | |
|---|---|---|---|---|
| NONE | ❎ | ❎ | ❎ | ❎ |
| DOCS | ✅ | ❎ | ❎ | ❎ |
| DOCS_AND_FREQS | ✅ | ✅ | ❎ | ❎ |
| DOCS_AND_FREQS_AND_POSITIONS | ✅ | ✅ | ✅ | ❎ |
| DOCS_AND_FREQS_AND_POSITIONS_AND_OFFSETS | ✅ | ✅ | ✅ | ✅ |
索引更新
Lucene对同一个文档在索引中的更改拆分为先删除再插入两个过程，所以索引的更新操作可以分为插入删除两种。
对于更新操作而言，最重要的是分词，对于需要分词的字段，Lucene会基于不同的分词组件实现分词功能。常用的分词器有以下几种。
| 分词器 | 实现原理 | 适用范围 |
|---|---|---|
| StopAnalyzer | 通过词汇中特定字符串或单词将句子以及文章分割成词汇。 | 英文分词 |
| StandardAnalyzer | 能够根据数字、字母等进行分词，支持词表过滤替代StopAnalyzer功能，支持中文简单分词。 | 简单场景的中文分词 |
| CJKAnalyzer | 根据中文语言习惯对中文分词提供了比较好的支持。 | 中文分词 |
经过分词以及根据FieldType确定字段需要存储的数据，这些信息会在内存中构建成倒排表等信息。
文档的删除是异步的，首先将要删除的term或者Query添加到删除队列，之后根据Flush策略触发删除操作。
索引存储
当内存中的文档达到一定数量，Lucene会启动索引的Flush操作，将内存在倒排表等信息写入到持久化存储，Lucene每次操作Flush会生成一个Segment。
Lucene的Flush操作目前基于FlushByRamOrCountsPolicy策略。FlushByRamOrCountsPolicy会在以下两类场景执行Flush操作：
- maxBufferedDocs：文档数量达到阈值设定。
- ramBufferSizeMB：内存占用达到阈值设定。
因为lucene的Flush操作需要达到一定的文档数量或者内存空间才能触发，所以不能做到实时的增加文档，ES为了现实更加实时的索引功能，做了一定的优化，可以使索引更新的时效缩短到1秒之内。
索引每次Flush时会单独生成一个segment，当segment过多时进行全文检索需要聚合多个segment的数据，对效能有较大的影响。Lucene提供了多种类型的MergeScheduler对段进行定期的合并操作。
段合并操作也有不同的策略进行选择需要合并的段。
- TieredMergePolicy：通过打分机制对的所有的段进行排序，然后在排序后的段集合中选取部分（可能不连续）段来生成一个待合并段集，即非相邻的段文件。
- LogMergePolicy：定长的合并方式，通过maxLevel、LEVEL_LOG_SPAN、levelBottom参数将连续的段分为不同的层级，再通过mergeFactor从每个层级中选取段进行合并，LogMergePolicy通常合并相邻的段。
索引检索
Lucene的全文检索过程是通过查询索引中所有的Segment，之后通过聚合逻辑以及打分排序之后返回给最优的结果集。
Lucene的检索有不同的Query类型。
| TermQuery | 基本的Query，用来查询指定字段包含指定词项的文档。常用于组合其他更复杂的Query类型。 |
| BooleanQuery | 布尔查询用布尔表达式组合多个自查询。 |
| PhraseQuery | 匹配特定序列的多个词项的查询类型。 |
| MultiPhraseQuery | 短语查询的一种更通用的用法，支持多个词的OR匹配。 |
| SpanNearQuery | 用于更复杂的短语查询，可以指定词间位置的最大间隔跨度。 |
| TermRangeQuery | 用于查询包含某个范围内的词项的文档 |
Lucene的Query经常会对一系列原子检索结果集进行合并操作。对于此类集合合并Lucene会从算法以及数据结构层面进行优化。
算法层面，Lucene会采用跳表或者Hash Join的方式对求交集操作进行优化。
对于文档ID求交集的过程，ID的存储经常采用位图法进行存储，Lucene会优化为Roaring Bitmap。