全文索引数据库Elasticsearch底层Lucene

Lucene

全文检索的心，天才的想法。

1. 一个高效的，可扩展的，全文检索库。
2. 全部用 Java 实现，无须配置。
3. 仅支持纯文本文件的索引(Indexing)和搜索(Search)。
4. 不负责由其他格式的文件抽取纯文本文件，或从网络中抓取文件的过程。

基于《Lucene 原理与代码分析 觉先 (forfuture1978)》

核心就是将进来的数据，创建进行倒排索引。以及将搜索的内容根据倒排索引来搜索，避免了遍历搜索的速度消耗。

一种牺牲空间，换取时间的手段。

索引的创建

将简单的文本数据，处理成易于根据单词查询的格式。便于全文检索。

数据查询

对于搜索的条件也会进行同样的分词手法，

1. 把数据进行分割，去除is are那种无意义的词。
2. 动名词变词根之类的操作。
3. 然后去查询存储了这些词的文档链表，进行搜索条件中的与或非操作。
4. 最后得到的文档进行权重分析，排序。
5. 最后得到数据。

权重计算

计算权重(Termweight)的过程。 影响一个词(Term)在一篇文档中的重要性主要有两个因素:

1. Term Frequency (tf):即此 Term 在此文档中出现了多少次。tf 越大说明越重要。
2. Document Frequency (df):即有多少文档包􏰀次 Term。df 越大说明越不重要。

这只是权重计算的一部分，完整的要复杂得多。考虑到不同单词的重要性，和搜索内容的在不同场景下会有特殊意义，权重自然都不相同。

向量空间模型的算法(VSM)

大致思路就是，将每一个文档通过计算每个词的权重，然后组成一个向量。然后用户搜索的条件也变成一个搜索的向量（因为搜索条件可能会有must，也可能有must not这种，所以会分布在坐标系的各个象限），最后对比哪个向量的夹角较小，就符合搜索条件。

相关计算过程：

参考 http://www.lucene.com.cn/about.htm 中文章《开放源代码的全文检索引擎 Lucene》

Lucene架构

save: Document->IndexWriter->index

search: Query->IndexSearch->index->TopDocsController

1. 被索引的文档用Document对象表示。
2. IndexWriter通过函数addDocument将文档添加到索引中，实现创建索引的过程。
3. Lucene的索引是应用反向索引。
4. 当用户有请求时，Query代表用户的查询语句。
5. IndexSearcher通过函数search搜索LuceneIndex。
6. IndexSearcher计算termweight和score并且将结果返回给用户。
7. 返回给用户的文档集合用TopDocsCollector表示。

Create

Flie f = ? 
//需要写入的文档  
Document doc = new Document();
doc.add(new Field("path",f.getPath(),Field.Store.Yes,Field.Index.NOT_ANALYZED);//数据字段写入doc        
doc.add(new Field("contents", new FlieReader(f))://创建writer写 一个INDEX_DIR存储文件的位置
IndexWriter writer = new IndexWrte(//源文件地址FSDirectory.open(INDEX_DIR),//分词器new StandardAnalyzer(Version.LOCENE_CURRENT),true,IndexWriter,MaxFeildLenth.LIMITED);
writer addDocument(doc);
writer optimize();
writer.close();

Search

//根据索引创建一个search
Searcher searcher = new IndexSearcher(reader);//分词器
Analyzer analyzer = new StanardAnalyzer（xxx）;//分词器分词 查询语句分析
QueryParser parser = new QueryParser(field,analyzer) ;
Query query = parser.parse(queryString)//查询
searcher.search(query,collecor)  

代码结构

1. Lucene的analysis模块主要负责词法分析及语言处理而形成Term。 ! Lucene的index模块主要负责索引的创建，里面有IndexWriter。
2. Lucene的store模块主要负责索引的读写。
3. Lucene的QueryParser主要负责语法分析。
4. Lucene的search模块主要负责对索引的搜索。
5. Lucene的similarity模块主要负责对相关性打分的实现。

索引文件结构

Lucene 的索引过程，就是按照全文检索的基本过程，将倒排表写成此文件格式的过程。

Lucene 的搜索过程，就是按照此文件格式将索引进去的信息读出来，然后计算每篇文档打分(score)的过程。

具体文件保存逻辑，更新太频繁，推荐官网阅读。

参考：

Home - Apache Lucene (Java) - Apache Software Foundation

http://lucene.apache.org/java/2_9_0/fileformats.html

1. Lucene

一个lucene索引放在一个文件夹里面。

2. Segment

   1. Segment分段是包裹某一堆数据的集合。一个索引将会有多个段，新增一个文档就会放到个新的段里面，段之间会合并。
   2. 图中—1—2就是两个不同的段，lucene中留有两个segments.gen和segments—5来防止元数据。

3. Doc

   1. doc中就保存的是每一个完整的文件数据。比如是新闻就包括他的标题，内容，创建时间，点击量等等
   2. 新增一个文档就会放到个新的段里面，段之间会合并。

4. Field

   1. field则是精确到字段，每个字段都在不同的field里面
   2. 不同类型的字段，建立倒排索引的方式不同，比如long,text,date等

5. Term

   1. 经过分词器分词出来得到的词，一句话中提取出核心的单词用来建立倒排的根本。
   2. Xxx.tis存储的是term dictionary，即此段包含的所有词按字典顺序的排序（"book",2）（词找分段）
   3. xxx.frq保存了倒排表，即每个词包含的文档id（词找文档）
   4. xxx.prx保存了每个词在文档的位置。（词在文档的位置(高亮功能)）

底层保存规则

1. 前缀后缀优化

2. 数值改为差值优化

3. 跳表操作

   很多数据库都使用了类似的跳表，原理与B+树类似。

索引过程分析

Lucene 的索引过程，很多的博客，文章都有介绍，推荐大家上网搜一篇文章:《Annotated Lucene》，好像中文名称叫《Lucene 源码剖析》是很不错的。

段合并过程分析

概述

由IndexWriter的代码中与段合并有关的成员变量有：

//保存正在合并  的段，以防止合并期间再次选中被合并。
HashSet<Segmentlnfo:>mergingSegments=new HashSet<Segmentlnfo>();//合并策略，也即选取哪些段  来进行合并。
MergePolicy mergePolicy=new LogByteSizeMergePolicy(this);  //段合并器，背后有  一个线程负责合并。   
MergeScheduler mergeScheduler=new ConcurrentMergeScheduler(); //等待被合并的任务  
LinkedList<MergePolicy.OneMerge> =LinkedList<MergePolicy.OneMerge:();//正在被合并的任务
Set<MergePolicy.OneMerge>runningMerges new HashSet<MergePolicy.OneMerge>():

我们可以得出：

一个是选择哪些段应该参与合并，这一步由MergePolicy来决定。

一个是将选择出的段合并成新段的过程，这一步由MergeScheduler来执行。

段的合并也主要 包括：
1. 对正向信息的合并，如存储域，词向量，标准化因子等。
1. 对反向信息的合并，如词典，倒排表。

段合并代码分析

1. 将缓存写入新的段

   //DocumentsWriter添加文档，最 后返回是否进行向硬盘写入
   doFlush=docWriter.addDocument(doc,analyzer);//这取决于当使用的内存大于 ramBufferSize 的时候，则由内存向硬盘写入。
   return state.doFlushAfter || timeToFlushDeletes();//当缓存写入硬盘，形成了新的段后，就有可能触发一次段合并，所以调用 maybeMerge()
   IndexWriter.maybeMerge()//主要负责 找到可以合并的段，并生产段合并任务对象，并向段合并器注册这个任务。 
   IndexWriter.updatePendingMerges(int maxNumSegmentsOptimize, boolean optimize)//主要负责进行段的合并。
   ConcurrentMergeScheduler.merge(IndexWriter)
   

2. 选择合并段，生成合并任务

   //生成合并任务
   IndexWriter.updatePendingMerges(int maxNumSegmentsOptimize, boolean optimize)//两部分:
   //选择能够合并段:
   MergePolicy.MergeSpecificationspec= mergePolicy.findMerges(segmentInfos);//向段合并器注册合并任务，将任务加到pendingMerges中: " 
   for(int i=0;i<spec.merges.size();i++)
   registerMerge(spec.merges.get(i));//选择合并逻辑 
   

   段合并逻辑

   在LogMergePolicy中，选择可以合并的段的基本逻辑是这样的：

   1. 选择的可以合并的段都是在硬盘上的，不再存在内存中的段，也不是像早期的版本一样 每添加一个Document就生成一个段，然后进行内存中的段合并，然后再合并到硬盘中。

   2. 由于从内存中flush到硬盘上是按照设置的内存大小来DocumentsWriter.ramBufferSize 触发的，所以每个刚flush到硬盘上的段大小差不多，当然不排除中途改变内存设置， 接下来的算法可以解决这个问题。
      （通过1，2解决了早起磁盘上段大小差距大的问题）

   3. 合并的过程是尽量按照合并几乎相同大小的段这一原则，只有大小相当的mergeFacetor 个段出现的时候，才合并成一个新的段。 在硬盘上的段基本应该是大段在前，小段在后，因为大段总是由小段合并而成的，当小 段凑够mergeFactor个的时候，就合并成一个大段，小段就被删除了，然后新来的一定 是新的小段。
      （可以理解为一个自动整理文件的手法，毕竟写入的时候是多线程，写入多个小段速度最快，然后在一个同步程序来把写入的文件好好整理成册）

   4. 比如mergeFactor:3,开始来的段大小为10M,当凑够3个10M的时候，0.cfs,1.cfs,2.cfs 则合并成一个新的段3.cfs,大小为30M,然后再来4.cfs,5.cfs,6.cfs,合并成7.cfs,大 小为30M,然后再来8.cfs,9.cfs,a.cfs合并成b.cfs,大小为30M,这时候又凑够了3个 30M的，合并成90M的c.cfs,然后又来d.cfs,e.cfs,f.cfs合并成10.cfs,大小为30M,然 后11.cfs大小为10M,这时候硬盘上的段为：c.cfs(90M)10.cfs(30M),11.cfs(10M)。

在段合并的时候，会将所有的段按照生成的顺序,将段的大小以 merge Factor为底取对数,放入数组中,作 为选择的标准。然后再对段进行判定然后执行段的合并逻辑。

![](https://myalipapa-for-live.oss-cn-chengdu.aliyuncs.com/pic-mac/image-20220105141839569.png" alt="image-20220105141839569" style="zoom: 50%;" />

3. 段合并器执行段合并

   // 得到下一个合并任务:
   MergePolicy.OneMergemerge=writer.getNextMerge();
   // 初始化合并任务:
   writer.mergeInit(merge);
   // 将删除文档写入硬盘:
   applyDeletes();
   //是否合并存储域:
   mergeDocStores=false//按照Lucene的索引文件格式(2)中段的元数据信息(segments_N)中提到的，IndexWriter.flush(boolean triggerMerge, boolean flushDocStores, boolean flushDeletes)中第二个参数 flushDocStores 会影 响到是否单独或是共享存储。其实最终影响的是 DocumentsWriter.closeDocStore()。 每当 flushDocStores 为 false 时，closeDocStore 不被调用，说明下次添加到索引文件 中的域和词向量信息是同此次共享一个段的。直到 flushDocStores 为 true 的时候， closeDocStore 被调用，从而下次添加到索引文件中的域和词向量信息将被保存在一个新 的段中，不同此次共享一个段。如 2.1 节中说的那样，在 addDocument 中，如果内存中 缓存满了，则写入硬盘，调用的是 flush(true, false, false)，也即所有的存储域都存储在 共享的域中(_0.fdt)，因而不需要合并存储域。
   //生成新的段:
   merge.info=newSegmentInfo(newSegmentName(),...)
   for(int i=0;i<count;i++) mergingSegments.add(merge.segments.info(i));//将新的段加入mergingSegments
   //如果已经有足够多的段合并线程，则等待while(mergeThreadCount()>=
   maxThreadCount) wait();//生成新的段合并线程:
   merger = getMergeThread(writer, merge);
   mergeThreads.add(merger);//启动段合并线程:
   merger.start();//循环执行合并
   while(true){
   // 合并当前的任务:
   doMerge(merge);
   // 得到下一个段合并任务:
   merge = writer.getNextMerge();
   }
   

4. 合并存储域/元数据

    for (IndexReader reader : readers) {SegmentReader segmentReader = (SegmentReader) reader; FieldInfos readerFieldInfos = segmentReader.fieldInfos();       int numReaderFieldInfos = readerFieldInfos.size();for (int j = 0; j < numReaderFieldInfos; j++) {FieldInfo fi = readerFieldInfos.fieldInfo(j);//这里有两种情况，如果两个doc的元数据相同，也就是字段都一样，那么就是快速的合并add//如果是有数据字段的变化，那么就需要一个个doc挨个更新元数据，会导致速度变慢//所以在使用lucene时，最好一个索引定死那些字段，那样能得到最优的速度fieldInfos.add(fi.name, fi.isIndexed, fi.storeTermVector,fi.storePositionWithTermVector,          fi.storeOffsetWithTermVector, !reader.hasNorms(fi.name), fi.storePayloads, fi.omitTermFreqAndPositions);}}

5. 合并标准化因子（标准化因子：用于影响文档打分）

   合并标准化因子的过程比较简单，基本就是对每一个域，用指向合并段的 reader 读出标准 化因子，然后再写入新生成的段。（重新打分）

6. 合并词向量（词向量：表示词出现的多少，位置，和数量的向量）

   与存储域差不多

7. 合并词典和倒排表

   倒排索引合并

   1. 对词典的合并需要找出两个段中相同的词，Lucene是通过一个称为match的 SegmentMergelnfo类型的数组以及称为queue的SegmentMergeQueue（图画起来更像一个栈）实现的。

   2. SegmentMergeQueue是继承于PriorityQueue<SegmentMergelnfo>,是一个优先级队列，是按照字典顺序排序的。SegmentMergelnfo保存要合并的段的词典及倒排表信息，在 SegmentMergeQueue中用来排序的key是它代表的段中的第一个Term。 我们来举一个例子来说明合并词典的过程，以便后面解析代码的时候能够很好的理解：

   3. 对字典的合并，词典中的Term是按照字典顺序排序的，需要对词典中的Term进行重新排序对于相同的Term,对包含此Term的文档号列表进行合并，需要对文档号重新编号。

   4. 假设要合并五个段，每个段包含的em也是按照字典顺序排序的，如下图所示。 首先把五个段全部放入优先级队列中，段在其中也是按照第一个em的字典顺序排序 的，如下图。

   

   image

打分公式的数学推导

整体打分思路：

核心参数标准化因子：

所以我们可以在改动权重，来改变搜索和写入词的比重，以搜索到更有价值的信息。

搜索过程解析

<img src="https://myalipapa-for-live.oss-cn-chengdu.aliyuncs.com/pic-mac/image-20220105170125590.png" alt="image-20220105170125590" style="zoom:67%;" />

总共包括以下几个过程:

1. IndexReader 打开索引文件，读取并打开指向索引文件的流。
2. 用户输入查询语句
3. 将查询语句转换为查询对象 Query 对象树
4. 构造 Weight 对象树，用于计算词的权重 Term Weight，也即计算打分公式中与仅与搜索
   语句相关与文档无关的部分(红色部分)。
5. 构造 Scorer 对象树，用于计算打分(TermScorer.score())。
6. 在构造 Scorer 对象树的过程中，其叶子节点的 TermScorer 会将词典和倒排表从索引中读出来。
   （同时读取词典和倒排表，此时只有doc id）
7. 构造 SumScorer 对象树，其是为了方便合并倒排表对 Scorer 对象树的从新组织，它的叶子节点仍为 TermScorer，包词典和倒排表。此步将倒排表合并后得到结果文档集，并 对结果文档计算打分公式中的蓝色部分。打分公式中的求和符合，并非简单的相加，而 是根据子查询倒排表的合并方式(与或非)来对子查询的打分求和，计算出父查询的打分。
   （打分同时拿到文档）
8. 将收集的结果集合及打分返回给用户。

查询语法，JavaCC 及 QueryParser

场景lucene语法

Luecene 3.0.1

SIP-9 Advanced Query Parser - SOLR

查询语法

1. 语法关键字

   +- && || ! ( ) { } [ ] ^ " ~ * ? : \ 如果所要查询的查询词中本身包含关键字，则需要用\进行转义

2. 查询词(Term)

   Lucene 支持两种查询词，一种是单一查询词，如"hello"，一种是词组(phrase)，如"hello world"。

3. 查询域(Field)

   在查询语句中，可以指定从哪个域中寻找查询词，如果不指定，则从默认域中查找。 查询域和查询词之间用:分隔，如 title:"Do it right"。 :仅对紧跟其后的查询词起作用，如果 title:Do it right，则仅表示在 title 中查询 Do，而 it right 要在默认域中查询。

4. 通配符查询(Wildcard)
   支持两种通配符:?表示一个字符，＊表示多个字符。 通配符可以出现在查询词的中间或者末尾，如 te?t，test＊，te＊t，但决不能出现在开始， 如＊test，?test。

5. 模糊查询(Fuzzy)
   模糊查询的算法是基于 Levenshtein Distance，也即当两个词的差􏰁小于某个比例的时 候，就算匹配，如 roam~0.8，即表示差距小于 0.2，相似度大于 0.8 才算匹配。

6. 临近查询(Proximity)
   在词组后面跟随~10，表示词组中的多个词之间的距离之和不超过 10，则满足查询。

   所谓词之间的距离，即查询词组中词为满足和目标词组相同的最小移动次数。 如索引中有词组"apple boy cat"。
   如果查询词为"apple boy cat"~0，则匹配。
   如果查询词为"boy apple cat"~2，距离设为 2 方能匹配，设为 1 则不能匹配。

7. 区间查询(Range)

   区间查询包括两种，一种是包含边界，用[A TO B]指定，一种是不包含边界，用{A TO B} 指定。
   如 date:[20020101 TO 20030101]，当然区间查询不仅仅用于时间，如 title:{Aida TO Carmen}

8. 增加一个查询词的权重(Boost)
   可以在查询词后面加^N 来设定此查询词的权重，默认是 1，如果 N 大于 1，则说明此查询 词更重要，如果 N 小于 1，则说明此查询词更不重要。
   如 jakarta^4 apache，"jakarta apache"^4 "Apache Lucene"

9. 布尔操作符
   布尔操作符包括连接符，如 AND，OR，和修饰符，如 NOT，+，-。 默认状态下，空格被认为是 OR 的关系， QueryParser.setDefaultOperator(Operator.AND)设置为空格为 AND。 +表示一个查询语句是必须满足的(required)，NOT 和-表示一个查询语句是不能满足的 (prohibited)。

10. 组合
    可以用括号，将查询语句进行组合，从而设定优先级。
    如(jakarta OR apache) AND website

JavaCC

JavaCC 本身既不是一个词法分析器，也不是一个语法分析器，而是根据指定的规则生成两者的生成器。

javacc.com

Lucene 的查询语法是由 QueryParser 来进行解析，从而生成查询对象的。 通过编译原理我们知道，解析一个语法表达式，需要经过词法分析和语法分析的过程，也即 需要词法分析器和语法分析器。
QueryParser 是通过 JavaCC 来生成词法分析器和语法分析器的。

//词法分析器编写
SKIP : { " " }
SKIP : { "\n" | "\r" | "\r\n" }
TOKEN : { < PLUS : "+" > }
TOKEN : { < NUMBER : (["0"-"9"])+ > }//语法分析器编写
void Start() :
{} {
<NUMBER> (
<PLUS>
<NUMBER> )*
<EOF> }//编译后就可以变成一个能够解析器 输入正确 就能输出结果

QueryParser

用javacc实现，能够把易懂的lucene语法变为java语法。

查询对象

和es的查询差不了太多，但是也提供了一些很有趣的。

常用的就不写了，写一些有趣的。

BoostingQuery

/*** match 必须满足* context 不影响结果，可选，会将打分 X boost* boost 权重分*/public BoostingQuery(Query match, Query context, float boost) 

CustomScoreQuery

//自定义打分规则//子查询和其他的信息源来共同决定最后的打分public float customScore(int doc, float subQueryScore, float valSrcScores[]) 

MoreLikeThisQuery

在分析 MoreLikeThisQuery 之前，首先介绍一下 MoreLikeThis。

在实现搜索应用的时候，时常会遇到"更多相似文章"，"更多相关问题"之类的需求，也即根 据当前文档的文本内容，在索引库中查询相类似的文章。我们可以使用 MoreLikeThis 实现此功能:

IndexReader reader = IndexReader.open(......);IndexSearcher searcher = new IndexSearcher(reader);MoreLikeThis mlt = new MoreLikeThis(reader);Reader target = ... //此是一个 io reader，指向当前文档的文本内容。Query query = mlt.like( target); //根据当前的文本内容，生成查询对象。 Hits hits = searcher.search(query); //查询得到相似文档的结果。

SpanQuery

//所谓 SpanQuery 也即在查询过程中需要考虑进 Term 的位置信息的查询对象。//SpanQuery 中最基本的是 SpanTermQuery，其只包􏰀一个 Term，与 TermQuery 所不同的是， 其提供一个函数来得到位置信息:public Spans getSpans(final IndexReader reader) throws IOException { return new TermSpans(reader.termPositions(term), term);}//Spans 有以下方法://next() 得到下一篇文档号，不同的 SpanQuery 此方法实现不同 ! skipTo(int) 跳到指定的文档//doc() 得到当前的文档号//start() 得到起始位置，不同的 SpanQuery 此方法实现不同//end() 得到结束位置，不同的 SpanQuery 此方法实现不同//isPayloadAvailable() 是否有 payload//getPayload() 得到 payload

在这个基础上，我们可以开发出搜索词高亮的功能。

SpanFirstQuery

搜索以xx开头的文档。

SpanNearQuery

搜索词必须满足x间隔。

FieldCacheRangeFilter<T>及 FieldCacheTermsFilter

FieldCacheRangeFilter 同 NumericRangeFilter 或者 TermRangeFilter 功能类似，只不过后两者 取得 docid 的 bitset 都是从索引中取出，而前者是缓存了的，加快了速度。
同样 FieldCacheTermsFilter 同 TermFilter 功能类似，也是前者进行了缓存，加快了速度。

分词器 Analyzer

Analyzer

public final class SimpleAnalyzer extends Analyzer {  @Overridepublic TokenStream tokenStream(String fieldName, Reader reader) {//返回的是将字符串最小化，并且按照空格分隔的 Tokenreturn new LowerCaseTokenizer(reader); }  @Overridepublic TokenStream reusableTokenStream(String fieldName, Reader reader) throws IOException {// 得 到 上 一 次 使 用 的 TokenStream ， 如 果 没 有 则 生 成 新 的 ， 并 且 用 setPreviousTokenStream 放入成员变量，使得下一个可用。Tokenizer tokenizer = (Tokenizer) getPreviousTokenStream(); if (tokenizer == null) {tokenizer = new LowerCaseTokenizer(reader);setPreviousTokenStream(tokenizer); } else//如果上一次生成过 TokenStream，则 reset。tokenizer.reset(reader); return tokenizer;} }

TokenStream

TokenStream是一个由分词后的 Token 结果组成的流，能够不断的 得到下一个分成的 Token。

TokenStream 主要以下几个方法://用于得到下一个 Tokenboolean incrementToken()//使得此 TokenStrean 可以重新开始返回各个分词。public void reset() 

例：NumericTokenStream.class

public static int intToPrefixCoded(final int val, final int shift, final char[] buffer) { if (shift>31 || shift<0)throw new IllegalArgumentException("Illegal shift value, must be 0..31"); int nChars = (31-shift)/7 + 1, len = nChars+1;buffer[0] = (char)(SHIFT_START_INT + shift);int sortableBits = val ^ 0x80000000;sortableBits >>>= shift; while (nChars>=1) {//int 按照每七位组成一个 utf-8 的编码，并且字符串大小比较的顺序同 int 大小比较 的顺序完全相同。buffer[nChars--] = (char)(sortableBits & 0x7f);sortableBits >>>= 7; }return len; }

存储方面使用了各种优化方式，做到最高效的存储。

具体存储优化方式使用<索引文件结构.底层保存规则>小节中的部分方式。