ElasticSearch/Lucene分布式存储

[转]Lucene的索引文件格式

2018-05-07  本文已影响298人  囧雪啥都不知道

原文链接Lucene学习总结之三：Lucene的索引文件格式(1)、Lucene的索引文件格式(2)、Lucene的索引文件格式(3)，这里做一些摘要并收藏。

Lucene的索引里面存了些什么，如何存放的，也即Lucene的索引文件格式，是读懂Lucene源代码的一把钥匙。

当我们真正进入到Lucene源码之中的时候，我们会发现：

本文详细解读了Apache Lucene - Index File Formats(http://lucene.apache.org/java/2_9_0/fileformats.html)这篇文章。

摘录本文时，Apache Lucene的最新版本为7.3.0，对应的Index File Formats(http://lucene.apache.org/core/7_3_0/core/org/apache/lucene/codecs/lucene70/package-summary.html)

一、基本概念

下图就是Lucene生成的索引的一个实例：

Lucene生成索引实例

Lucene的索引结构是有层次结构的，主要分以下几个层次：

Lucene的索引结构中，即保存了正向信息，也保存了反向信息。

所谓正向信息：

所谓反向信息：

Apache Lucene 2.9.0 - Index File Formats中对文件的名称和扩展名的总结：

Name Extension Brief Description
Segments File segments.gen, segments_N Stores information about segments
Lock File write.lock The Write lock prevents multiple IndexWriters from writing to the same file.
Compound File .cfs An optional "virtual" file consisting of all the other index files for systems that frequently run out of file handles.
Fields .fnm Stores information about the fields
Field Index .fdx Contains pointers to field data
Field Data .fdt The stored fields for documents
Term Infos .tis Part of the term dictionary, stores term info
Term Info Index .tii The index into the Term Infos file
Frequencies .frq Contains the list of docs which contain each term along with frequency
Positions .prx Stores position information about where a term occurs in the index
Norms .nrm Encodes length and boost factors for docs and fields
Term Vector Index .tvx Stores offset into the document data file
Term Vector Documents .tvd Contains information about each document that has term vectors
Term Vector Fields .tvf The field level info about term vectors
Deleted Documents .del Info about what files are deleted

Apache Lucene 7.3.0 - Index File Formats中对文件的名称和扩展名的总结：

Name Extension Brief Description
Segments File segments_N Stores information about a commit point
Lock File write.lock The Write lock prevents multiple IndexWriters from writing to the same file.
Segment Info .si Stores metadata about a segment
Compound File .cfs, .cfe An optional "virtual" file consisting of all the other index files for systems that frequently run out of file handles.
Fields .fnm Stores information about the fields
Field Index .fdx Contains pointers to field data
Field Data .fdt The stored fields for documents
Term Dictionary .tim The term dictionary, stores term info
Term Index .tip The index into the Term Dictionary
Frequencies .doc Contains the list of docs which contain each term along with frequency
Positions .pos Stores position information about where a term occurs in the index
Payloads .pay Stores additional per-position metadata information such as character offsets and user payloads
Norms .nvd, .nvm Encodes length and boost factors for docs and fields
Per-Document Values .dvd, .dvm Encodes additional scoring factors or other per-document information.
Term Vector Index .tvx Stores offset into the document data file
Term Vector Data .tvd Contains term vector data.
Live Documents .liv Info about what documents are live
Point values .dii, .dim Holds indexed points, if any

在了解Lucene索引的详细结构之前，先看看Lucene索引中的基本数据类型。

二、基本类型

Lucene索引文件中，用以下基本类型来保存信息：

Value First byte Second byte Third byte
0 0
1 1
2 10
...
127 1111111
128 10000000 1
129 10000001 1
130 10000010 1
...
16383 11111111 1111111
16384 10000000 10000000 1
16385 10000001 10000000 1

三、基本规则

Lucene为了使的信息的存储占用空间更小，访问速度更快，采取了一些特殊的技巧，然而在看Lucene文件格式的时候，这些技巧却容易让我们感到困惑，所以有必要把这些特殊的技巧规则提取出来介绍一下。

原作者给这些规则起了一些名字，以方便后面应用这些规则的时候能够简单。

1. 前缀后缀规则(Prefix+Suffix)

Lucene在反向索引中，要保存词典(Term Dictionary)的信息，所有的词(Term)在词典中是按照字典顺序进行排序的，然而词典中包含了文档中文档中几乎所有的词，并且有的词还是非常的长的，这样索引文件会非常的大，所谓前缀后缀规则，即当某个词和前一个词有共同的前缀的时候，后面的词仅仅保存前缀在词中的偏移(offset)，以及除前缀以外的字符串(称为后缀)。

前缀后缀规则

比如要存储如下词：term，termagancy，termagant，terminal，如果按照正常方式来存储，需要空间如下：

[VInt = 4][t][e][r][m]，[VInt = 10][t][e][r][m][a][g][a][n][c][y]，[VInt = 9][t][e][r][m][a][g][a][n][t]，[VInt = 8][t][e][r][m][i][n][a][l]

共需要35个Byte。

如果应用前缀后缀规则，需要的空间如下：

[VInt = 4][t][e][r][m]，[VInt = 4 (offset)][VInt = 6][a][g][a][n][c][y]，[VInt = 8 (offset)][VInt = 1][t][VInt = 4 (offset)][VInt = 4][i][n][a][l]

共需要22个Byte。
(一个Chars 1个Byte，共15个；一个VInt一个Byte，4个字符串长度，3个offset，共7个；总计22个)

大大缩小了存储空间，尤其是在按字典顺序排序的情况下，前缀重合率大大提高。

2. 差值规则(Delta)

在Lucene的反向索引中，需要保存很多的整型数字的信息，比如文档ID号，比如词(Term)在文档中的位置等等。

由上面的介绍，我们知道，整型数字是以VInt的格式存储的。随着数值的增大，每个数字占用的Byte的个数也逐渐的增多。所谓差值规则(Delta)就是先后保存两个整数的时候，后边的整数仅仅保存和前面整数的差即可。

以差值规则存储排序的数列

比如要存储如下整数：16386，16387，16388，16389

如果按照正常的方式来存储，需要的空间如下：
[(1)000 0010][(1)000 0000][(0)000 0001]，[(1) 000, 0011][(1) 000, 0000][(0) 000, 0001]，[(1) 000, 0100][(1) 000, 0000][(0) 000, 0001]，[(1) 000, 0101][(1) 000, 0000][(0) 000, 0001]

共需12个Byte。

如果应用差值规则来存储，需要的空间如下：
[(1)000 0010][(1)000 0000][(0)000 0001]，[(0)000 0001]，[(0)000 0001]，[(0)000 0001]

共需6个Byte。

大大缩小了存储空间，而且无论是文档ID，还是词在文档中的位置，都是按从小到大的顺序，逐渐增大的。(这里要注意是对排序过的整型才可用)

3. 或然跟随规则(A, B?)

Lucene的索引结构中存在这样的情况，某个值A后边可能存在某个值B，也可能不存在，需要一个标志来表示后面是否跟随着B。

一般的情况下，在A后面放置一个Byte，为0则后面不存在B，为1则后面存在B；或者为0后面存在B，为1后面不存在B。

但这样要浪费一个Byte的空间，其实一个bit就可以了。

在Lucene中，采取以下的方式：A的值左移一位，空出最后一位，作为标志位，来表示后面是否跟随B，所以在这种情况下，A/2是真正的A原来的值。

空出最后一位作为标志位

如果去读Apache Lucene - Index File Formats这篇文章，会发现很多符合这种规则的：

当然还有一些带?的但不属于此规则的：

为什么会存在以上两种情况，其实是可以理解的：

文章中对如下格式的描述令人困惑：

Positions --> <PositionDelta，Payload?> Freq
Payload --> <PayloadLength?，PayloadData>

PositionDelta和Payload是否使用或然跟随规则呢？如何标识PayloadLength是否存在呢?

其实PostionDelta和Payload并不符合或然跟随规则，Payload是否存在，是由.fnm文件中对于每个域的配置中有关Payload的配置决定的(FieldOption.STORES_PAYLOADS)。

当Payload不存在时，PayloadDelta本身不遵循或然跟随规则。

当Payload存在时，格式应该变成如下：Positions --> <PositionDelta，PayloadLength?，PayloadData> Freq
从而PositionDelta和PayloadLength一起适用或然跟随规则。

4. 跳跃表规则(Skip list)

为了提高查找性能，Lucene在很多地方采取了跳跃表数据结构。

跳跃表(Skip List)是如图的一种数据结构，有以下几个基本特征：

跳跃表

需要注意的一点是，在很多数据结构或算法书中都会有跳跃表的描述，原理都是大致相同的，但是定义稍有差别：

跳跃表比顺序查找，大大提高了查询速度，如查询元素72，原来要访问2，3，7，12，23，37，39，44，50，72总共10个元素，应用跳跃表后，只要首先访问第1层的50，发现72大于50，而第一层无下一个节点，然后访问第2层的94，发现94大于72，然后访问原链表的72，找到元素，共需访问3个元素即可。

然而Lucene在具体实现上，与理论又有所不同，在具体的格式中，会有详细说明。

四、具体格式

上面曾交代过，Lucene保存了从Index到Segment到Document到Feild一直到Term的正向信息，也包括了从Term到Document映射的反向信息，还有后其他一些Lucene特有的信息。下面对这三种信息一一介绍。

4.1 正向信息

Index -> Segments(segments.gen，segments_N) -> Field(fnm，fdx，fdt) -> Term(tvx，tvd，tvf)

4.1.1 段的元数据信息(segments_N)

一个索引(Index)可以同时存在多个segments_N(至于如何存在多个segments_N，在描述完详细信息之后会举例说明)，然而当我们要打开一个索引的时候，我们必须要选择一个来打开，那么如何选择打开哪个segments_N呢？

Lucene采取以下过程：

IndexInput genInput = directory.openInput(IndexFileNames.SEGMENTS_GEN);//"segments.gen" 
int version = genInput.readInt();//读出版本号 
if (version == FORMAT_LOCKLESS) {//如果版本号正确 
    long gen0 = genInput.readLong();//读出第一个N 
    long gen1 = genInput.readLong();//读出第二个N 
    if (gen0 == gen1) {//如果两者相等则为genB 
        genB = gen0; 
    } 
}

if (genA > genB) 
    gen = genA; 
else 
    gen = genB;

如下图是segments_N的具体格式：

segments_N的具体格式 
// 在DirectoryReader中有一个函数

public boolean isCurrent() throws CorruptIndexException, IOException { 
    return SegmentInfos.readCurrentVersion(directory) == segmentInfos.getVersion(); 
}
Index下的文件 
IndexWriter writer = new IndexWriter(FSDirectory.open(INDEX_DIR), new StandardAnalyzer(Version.LUCENE_CURRENT), true, IndexWriter.MaxFieldLength.LIMITED); 
writer.setUseCompoundFile(false); 
indexDocs(writer, docDir);//docDir中只有两篇文档

//文档一为：Students should be allowed to go out with their friends, but not allowed to drink beer.

//文档二为：My friend Jerry went to school to see his students but found them drunk which is not allowed.

writer.commit();//提交两篇文档，形成_0段。

writer.deleteDocuments(new Term("contents", "school"));//删除文档二 
writer.commit();//提交删除，形成_0_1.del 
indexDocs(writer, docDir);//再次索引两篇文档，Lucene不能判别文档与文档的不同，因而算两篇新的文档。 
writer.commit();//提交两篇文档，形成_1段 
writer.deleteDocuments(new Term("contents", "school"));//删除第二次添加的文档二 
writer.close();//提交删除，形成_1_1.del


IndexWriter.applyDeletes()

-> DocumentsWriter.applyDeletes(SegmentInfos)

     -> reader.deleteDocument(doc);

IndexWriter.commit()

-> IndexWriter.applyDeletes()

    -> IndexWriter$ReaderPool.release(SegmentReader)

         -> SegmentReader(IndexReader).commit()

             -> SegmentReader.doCommit(Map)

                  -> SegmentInfo.advanceDelGen()

                       -> if (delGen == NO) { 
                              delGen = YES; 
                           } else { 
                              delGen++; 
                           }

IndexWriter writer = new IndexWriter(FSDirectory.open(INDEX_DIR), new StandardAnalyzer(Version.LUCENE_CURRENT), true, IndexWriter.MaxFieldLength.LIMITED); 
writer.setUseCompoundFile(false);

indexDocs(writer, docDir);//索引两篇文档，一篇包含"school"，另一篇包含"beer" 
writer.commit();//提交两篇文档到索引文件，形成段(Segment) "_0" 
writer.deleteDocuments(new Term("contents", "school"));//删除包含"school"的文档，其实是删除了两篇文档中的一篇。 
writer.commit();//提交删除到索引文件，形成"_0_1.del" 
writer.deleteDocuments(new Term("contents", "beer"));//删除包含"beer"的文档，其实是删除了两篇文档中的另一篇。 
writer.commit();//提交删除到索引文件，形成"_0_2.del" 
indexDocs(writer, docDir);//索引两篇文档，和上次的文档相同，但是Lucene无法区分，认为是另外两篇文档。 
writer.commit();//提交两篇文档到索引文件，形成段"_1" 
writer.deleteDocuments(new Term("contents", "beer"));//删除包含"beer"的文档，其中段"_0"已经无可删除，段"_1"被删除一篇。 
writer.close();//提交删除到索引文件，形成"_1_1.del"

形成的索引文件如下：

      IndexWriter writer = new IndexWriter(FSDirectory.open(INDEX_DIR), new StandardAnalyzer(Version.LUCENE_CURRENT), true, IndexWriter.MaxFieldLength.LIMITED); 
      writer.setUseCompoundFile(false);

    
      indexDocs(writer, docDir); 
      writer.flush();

//flush生成segment "_0"，并且flush函数中，flushDocStores设为false，也即下个段将同本段共享域和词向量信息，这时DocumentsWriter中的docStoreSegment= "_0"。

      indexDocs(writer, docDir); 
      writer.commit();

//commit生成segment "_1"，由于上次flushDocStores设为false，于是段"_1"的域以及词向量信息是保存在"_0"中的，在这个时刻，段"_1"并不生成自己的"_1.fdx"和"_1.fdt"。
//然而在commit函数中，flushDocStores设为true，也即下个段将单独使用新的段来存储域和词向量信息。
//然而这时，DocumentsWriter中的docStoreSegment= "_1"，也即当段"_2"存储其域和词向量信息的时候，是存在"_1.fdx"和"_1.fdt"中的，而段"_1"的域和词向量信息却是存在"_0.fdt"和"_0.fdx"中的，这一点非常令人困惑。 
//如图writer.commit的时候，_1.fdt和_1.fdx并没有形成。
段"_1"形成 
      indexDocs(writer, docDir); 
      writer.flush();

//段"_2"形成，由于上次flushDocStores设为true，其域和词向量信息是新创建一个段保存的，却是保存在_1.fdt和_1.fdx中的，这时候才产生了此二文件。
段"_2"形成 
      indexDocs(writer, docDir); 
      writer.flush();

//段"_3"形成，由于上次flushDocStores设为false，其域和词向量信息是共享一个段保存的，也是是保存在_1.fdt和_1.fdx中的

      indexDocs(writer, docDir); 
      writer.commit();

//段"_4"形成，由于上次flushDocStores设为false，其域和词向量信息是共享一个段保存的，也是是保存在_1.fdt和_1.fdx中的。
//然而函数commit中flushDocStores设为true，也意味着下一个段将新创建一个段保存域和词向量信息，此时DocumentsWriter中docStoreSegment= "_4"，也表明了虽然段"_4"的域和词向量信息保存在了段"_1"中，将来的域和词向量信息却要保存在段"_4"中。
//此时"_4.fdx"和"_4.fdt"尚未产生。
段"_4"形成 
      indexDocs(writer, docDir); 
      writer.flush();

//段"_5"形成，由于上次flushDocStores设为true，其域和词向量信息是新创建一个段保存的，却是保存在_4.fdt和_4.fdx中的，这时候才产生了此二文件。
段"_5"形成 
      indexDocs(writer, docDir); 
      writer.commit(); 
      writer.close();

//段"_6"形成，由于上次flushDocStores设为false，其域和词向量信息是共享一个段保存的，也是是保存在_4.fdt和_4.fdx中的
段"_6"形成
非复合文件 复合文件 
读取此文件格式参考SegmentInfos.read(Directory directory, String segmentFileName):

int format = input.readInt();
version = input.readLong(); // read version
counter = input.readInt(); // read counter
for (int i = input.readInt(); i > 0; i--) // read segmentInfos
    add(new SegmentInfo(directory, format, input));
        name = input.readString();
        docCount = input.readInt();
        delGen = input.readLong();
        docStoreOffset = input.readInt();
        docStoreSegment = input.readString();
        docStoreIsCompoundFile = (1 == input.readByte());
        hasSingleNormFile = (1 == input.readByte());
        int numNormGen = input.readInt();
        normGen = new long[numNormGen];
        for(int j=0;j
        normGen[j] = input.readLong();
    isCompoundFile = input.readByte();
    delCount = input.readInt();
    hasProx = input.readByte() == 1;
    diagnostics = input.readStringStringMap();
    userData = input.readStringStringMap();
final long checksumNow = input.getChecksum();
final long checksumThen = input.readLong();
4.1.2 域(Field)的元数据信息(.fnm)

一个段(Segment)包含多个域，每个域都有一些元数据信息，保存在.fnm文件中，.fnm文件的格式如下：

.fnm文件格式

要了解域的元数据信息，还要了解以下几点：

Position and offset Payload的存储方式 
//声明一个特殊的域和特殊的词 
public static final String ID_PAYLOAD_FIELD = "_ID";

public static final String ID_PAYLOAD_TERM = "_ID";

public static final Term ID_TERM = new Term(ID_PAYLOAD_TERM, ID_PAYLOAD_FIELD);

//声明一个特殊的TokenStream，它只生成一个词(Term)，就是那个特殊的词，在特殊的域里面。

static class SinglePayloadTokenStream extends TokenStream { 
    private Token token; 
    private boolean returnToken = false;

    SinglePayloadTokenStream(String idPayloadTerm) { 
        char[] term = idPayloadTerm.toCharArray(); 
        token = new Token(term, 0, term.length, 0, term.length); 
    }

    void setPayloadValue(byte[] value) { 
        token.setPayload(new Payload(value)); 
        returnToken = true; 
    }

    public Token next() throws IOException { 
        if (returnToken) { 
            returnToken = false; 
            return token; 
        } else { 
            return null; 
        } 
    } 
}

//对于每一篇文档，都让它包含这个特殊的词，在特殊的域里面

SinglePayloadTokenStream singlePayloadTokenStream = new SinglePayloadTokenStream(ID_PAYLOAD_TERM); 
singlePayloadTokenStream.setPayloadValue(long2bytes(id)); 
doc.add(new Field(ID_PAYLOAD_FIELD, singlePayloadTokenStream));

//每当得到一个Lucene的文档号时，通过以下的方式得到payload里面的文档号 
long id = 0; 
TermPositions tp = reader.termPositions(ID_PAYLOAD_TERM); 
boolean ret = tp.skipTo(docID); 
tp.nextPosition(); 
int payloadlength = tp.getPayloadLength(); 
byte[] payloadBuffer = new byte[payloadlength]; 
tp.getPayload(payloadBuffer, 0); 
id = bytes2long(payloadBuffer); 
tp.close();

FieldInfos.read(IndexInput, String)

int firstInt = input.readVInt();
size = input.readVInt();
for (int i = 0; i < size; i++)
String name = input.readString();
byte bits = input.readByte();
boolean isIndexed = (bits & IS_INDEXED) != 0;
boolean storeTermVector = (bits & STORE_TERMVECTOR) != 0;
boolean storePositionsWithTermVector = (bits & STORE_POSITIONS_WITH_TERMVECTOR) != 0;
boolean storeOffsetWithTermVector = (bits & STORE_OFFSET_WITH_TERMVECTOR) != 0;
boolean omitNorms = (bits & OMIT_NORMS) != 0;
boolean storePayloads = (bits & STORE_PAYLOADS) != 0;
boolean omitTermFreqAndPositions = (bits & OMIT_TERM_FREQ_AND_POSITIONS) != 0;
4.1.3 域(Field)的数据信息(.fdt，.fdx)
Field 
Document FieldsReader.doc(int n, FieldSelector fieldSelector);

long position = indexStream.readLong();//indexStream points to ".fdx"
fieldsStream.seek(position);//fieldsStream points to "fdt"
int numFields = fieldsStream.readVInt();
for (int i = 0; i < numFields; i++){
    int fieldNumber = fieldsStream.readVInt();
    byte bits = fieldsStream.readByte();
    boolean compressed = (bits & FieldsWriter.FIELD_IS_COMPRESSED) != 0;
    boolean tokenize = (bits & FieldsWriter.FIELD_IS_TOKENIZED) != 0;
    boolean binary = (bits & FieldsWriter.FIELD_IS_BINARY) != 0;
    if (binary){
    int toRead = fieldsStream.readVInt();
        final byte[] b = new byte[toRead];
        fieldsStream.readBytes(b, 0, b.length);
        if (compressed)
        int toRead = fieldsStream.readVInt();
        final byte[] b = new byte[toRead];
        fieldsStream.readBytes(b, 0, b.length);
        uncompress(b);
    }
    else{
        fieldsStream.readString();
    }
}
4.1.4 词向量(Term Vector)的数据信息(.tvx，.tvd，.tvf)
Term Vector

词向量信息是从索引 (index)到文档(document)到域(field)到(term)的正向信息，有了词向量信息，我们就可以得到一篇文档包含了哪些词的信息。

TermVectorsReader.get(int docNum, String field, TermVectorMapper)

int fieldNumber = fieldInfos.fieldNumber(field);//通过field名字得到field号

seekTvx(docNum);//在tvx文件中按docNum文档号找到相应文档的项

long tvdPosition = tvx.readLong();//找到tvd文件中相应文档的偏移量

tvd.seek(tvdPosition);//在tvd文件中按偏移量找到相应文档的项

int fieldCount = tvd.readVInt();//此文档包含的域的个数。

for (int i = 0; i < fieldCount; i++) //按域号查找域
    number = tvd.readVInt();
    if (number == fieldNumber)
        found = i;

position = tvx.readLong();//在tvx中读出此文档的第一个域在tvf中的偏移量

for (int i = 1; i <= found; i++)
    position += tvd.readVLong();//加上所要找的域在tvf中的偏移量

tvf.seek(position);

int numTerms = tvf.readVInt();

byte bits = tvf.readByte();

storePositions = (bits & STORE_POSITIONS_WITH_TERMVECTOR) != 0;

storeOffsets = (bits & STORE_OFFSET_WITH_TERMVECTOR) != 0;

for (int i = 0; i < numTerms; i++)
    
    start = tvf.readVInt();
    deltaLength = tvf.readVInt();
    totalLength = start + deltaLength;
    tvf.readBytes(byteBuffer, start, deltaLength);
    term = new String(byteBuffer, 0, totalLength, "UTF-8");
    
    if (storePositions)
        
        positions = new int[freq];
        int prevPosition = 0;
        
        for (int j = 0; j < freq; j++)
            positions[j] = prevPosition + tvf.readVInt();
            prevPosition = positions[j];
            
    if (storeOffsets)
        
        offsets = new TermVectorOffsetInfo[freq];
        int prevOffset = 0;
        for (int j = 0; j < freq; j++)
        int startOffset = prevOffset + tvf.readVInt();
        int endOffset = startOffset + tvf.readVInt();
        offsets[j] = new TermVectorOffsetInfo(startOffset, endOffset);
        prevOffset = endOffset;
4.2 反向信息

反向信息是索引文件的核心，也即反向索引。

反向索引包括两部分，左面是词典(Term Dictionary)，右边是倒排表(Posting List)。

在Lucene中，这两部分是分文件存储的，词典是存储在.tii，.tis中的，倒排表又包括两部分，一部分是文档号及词频，保存在.frq中，一部分是词的位置信息，保存在.prx中。

4.2.1 词典(.tis)及词典索引 (.tii)信息
Term Dictionary

在词典中，所有的词都是按照字典顺序排序的。

origEnum = new SegmentTermEnum(directory.openInput(segment + "." + IndexFileNames.TERMS_EXTENSION,readBufferSize), fieldInfos, false);//用于读取tis文件

    int firstInt = input.readInt();
    size = input.readLong();
    indexInterval = input.readInt();
    skipInterval = input.readInt();
    maxSkipLevels = input.readInt();

SegmentTermEnum indexEnum = new SegmentTermEnum(directory.openInput(segment + "." + IndexFileNames.TERMS_INDEX_EXTENSION, readBufferSize), fieldInfos, true);//用于读取tii文件

    indexTerms = new Term[indexSize];
    indexInfos = new TermInfo[indexSize];
    indexPointers = new long[indexSize];
    for (int i = 0; indexEnum.next(); i++)
        indexTerms[i] = indexEnum.term();
        indexInfos[i] = indexEnum.termInfo();
        indexPointers[i] = indexEnum.indexPointer;
4.2.2 文档号及词频(.frq)信息
文档号及词频

文档号及词频文件里面保存的是倒排表，是以跳跃表形式存在的。

For example, the TermFreqs for a term which occurs once in document seven and three times in document eleven, with omitTf false, would be the following sequence of VInts:

15, 8, 3

If omitTf were true it would be this sequence of VInts instead:

7,4

首先我们看omitTf=false的情况，也即我们在索引中会存储一个文档中term出现的次数。

例子中说了，表示在文档7中出现1次，并且又在文档11中出现3次的文档用以下序列表示：15，8，3.

那这三个数字是怎么计算出来的呢？

首先，根据定义TermFreq --> DocDelta[, Freq?]，一个TermFreq结构是由一个DocDelta后面或许跟着Freq组成，也即上面我们说的A+B？结构。

DocDelta自然是想存储包含此Term的文档的ID号了，Freq是在此文档中出现的次数。

所以根据例子，应该存储的完整信息为[DocID = 7, Freq = 1] DocID = 11, Freq = 3。

然而为了节省空间，Lucene对编号此类的数据都是用差值来表示的，也即上面说的规则2，Delta规则，于是文档ID就不能按完整信息存了，就应该存放如下：

[DocIDDelta = 7, Freq = 1][DocIDDelta = 4 (11-7), Freq = 3]

然而Lucene对于A+B?这种或然跟随的结果，有其特殊的存储方式，见规则3，即A+B?规则，如果DocDelta后面跟随的Freq为1，则用DocDelta最后一位置1表示。

如果DocDelta后面跟随的Freq大于1，则DocDelta得最后一位置0，然后后面跟随真正的值，从而对于第一个Term，由于Freq为1，于是放在DocDelta的最后一位表示，DocIDDelta = 7的二进制是000 0111，必须要左移一位，且最后一位置一，000 1111 = 15，对于第二个Term，由于Freq大于一，于是放在DocDelta的最后一位置零，DocIDDelta = 4的二进制是0000 0100，必须要左移一位，且最后一位置零，0000 1000 = 8，然后后面跟随真正的Freq = 3。

于是得到序列：[DocDleta = 15][DocDelta = 8, Freq = 3]，也即序列，15，8，3。

如果omitTf=true，也即我们不在索引中存储一个文档中Term出现的次数，则只存DocID就可以了，因而不存在A+B?规则的应用。

[DocID = 7][DocID = 11]，然后应用规则2，Delta规则，于是得到序列[DocDelta = 7][DocDelta = 4 (11 - 7)]，也即序列，7，4.

Example: SkipInterval = 4, MaxSkipLevels = 2, DocFreq = 35. Then skip level 0 has 8 SkipData entries, containing the 3rd, 7th, 11th, 15th, 19th, 23rd, 27th, and 31st document numbers in TermFreqs. Skip level 1 has 2 SkipData entries, containing the 15th and 31st document numbers in TermFreqs.

按照描述，当SkipInterval为4，且有35篇文档的时候，Skip level = 0应该包括第3，第7，第11，第15，第19，第23，第27，第31篇文档，Skip level = 1应该包括第15，第31篇文档。

然而真正的实现中，跳跃表节点的时候，却向前偏移了，偏移的原因在于下面的代码：

FormatPostingsDocsWriter.addDoc(int docID, int termDocFreq)
   final int delta = docID - lastDocID;
   if ((++df % skipInterval) == 0)
       skipListWriter.setSkipData(lastDocID, storePayloads, posWriter.lastPayloadLength);
       skipListWriter.bufferSkip(df);

从代码中，我们可以看出，当SkipInterval为4的时候，当docID = 0时，++df为1，1%4不为0，不是跳跃节点，当docID = 3时，++df=4，4%4为0，为跳跃节点，然而skipData里面保存的却是lastDocID为2。

所以真正的倒排表和跳跃表中保存以下的信息：

倒排表与跳跃表
4.2.3 词位置(prx)信息
词位置信息

词位置信息也是倒排表，也是以跳跃表形式存在的。

4.3 其他信息
4.3.1 标准化因子文件(nrm)

为什么会有标准化因子呢？从第一章中的描述，我们知道，在搜索的过程中，搜索出的文档要按与查询语句的相关性排序，相关性大的打分(score)高，从而排在前面。相关性打分(score)使用向量空间模型(Vector Space Model)，在计算相关性之前，要计算Term Weight，也即某Term相对于莫Document的重要性。在计算Term Weight时，主要有两个影响因素，一个是此Term在此文档中出现的次数，一个是此Term的普通程度。显然此Term在文档中出现的次数越多，此Term在此文档中越重要。

这种Term Weight的计算方法时最普通的，然而存在以下几个问题：

由于上述原因，Lucene在计算Term Weight时，都会乘上一个保准话因子(Normalization Factor)，来减少上面三个问题的影响。

标准化因子(Normalization Factor)是会影响随后打分(score)的计算的，Lucene的打分计算一部分发生在索引过程中，一般是与查询语句无关的参数如标准化因子，大部分发生在搜索过程中，会在搜索过程的代码分析中详述。

标准化因子(Normalization Factor)在索引过程总的计算如下：

计算标准化因子

它包含三个参数：

从上面的公式，我们知道，一个词(Term)出现在不同的文档或不同的域中，标准化因子不同。比如有两个文档，每个文档有两个域，如果不考虑文档长度，就有四种排列组合，在重要文档的重要域中，在重要文档的非重要域中，在非重要文档的重要域中，在非重要文档的非重要域中，四种组合，每种有不同的标准化因子。

于是在Lucene中，标准化因子共保存了(文档数目乘以域数目)个，格式如下：

标准化因子
4.3.2 删除文档文件(.del)
删除文档文件

五、总体结构

总体结构

大家可以通过看源代码，相应的Reader和Writer来了解文件结构，将更为透彻。

上一篇下一篇

猜你喜欢

热点阅读