lucene索引结构整理

一、基础信息

1、索引结构：

索引信息元数据：segment_N.
段信息元数据：.si
正排信息：.fnm .fdx .fdt
倒排信息：.tim .tip 与 .doc .pos .pay
norm信息：.nvm .nvd
doc_value信息：.dvm .dvd
term_vector信息：.tvx .tvd

lucene索引结构整理

2、存储类型

Int8： Byte
Int32：4 Byte 无符号int值
Int64：8 Byte 无符号int值
VInt: 长度在1 到4 Byte之间，支持负数但不建议使用，8 bit中，首位代表是否还有后续Byte 。0111 1111=127 ，1000 0000 0000 0001=128 ，lucene中的或然跟随规则
Long : 8 Byte 数值（也有时候叫 UInt64）
VLong: 1到9 Byte之间，规则等同VInt
String：utf8编码，前面是一个VInt代表值长度，后面是byte[]
Set：首位是一个Int32，代表长度
Map：一个Vint，代表长度
Packed Array：压缩数组，值域为 0到N ，根据值域计算一个保存每个值必须的最小长度位数L。一般前面会有一个Vint保存最小长度位数L

二、索引文件结构

1）segment_N：索引信息元数据，主要包含当前索引（目录）中lucene版本信息、段个数、各个段的元数据信息

lucene_version （类型VInt）
mingSeg_version （类型VInt）
version：修改次数（类型Int64）
NameCounter：下一个段的名字（类型Int32）
SegCount：段个数（类型Int32）
SegInfo[SegCount]
- SegName （类型String）
- SegID （类型String）
- SegCodec （类型String）
- DelGen：修改次数（类型Int64）
- DelCount：修改数量（类型Int64）
- FieldInfoGen：修改次数（类型Int64）
- DocValueGen：修改次数（类型Int64）

2）.si：段元数据信息，主要包含应段的lucene版本信息、段内文档数量、是否存为复合文件、以及段的一些动态属性

SegVersion： lucene版本号（类型String）
SegSize：段内文档数（类型Int32）
Files：段相关索引文件（类型Set<String>）
IsCompoundFile：是否是聚合索引（类型Int8）
Attribute：（类型Map<String,String>）

3）正排信息

.fnm : 域的元数据信息，包括：字段ID、字段名称、字段的IndexOption、Norms选项、DovValue选项、TermVector选项

FieldsCount：域的数量（类型VInt）
FieldInfo[FieldsCount]
- FieldName：字段名（类型byte）
- FieldNumber：字段编号（类型byte）
- FieldBits: （类型byte）
  - -1：启用TermVector
  - -2：禁用norm
  - -3：启用Payload信息
- DocValueBits / norms：（类型byte）
  - 0：No
  - 1：Numeric
  - 2：Binary
  - 3：Sorted
- IndexOption：（类型byte）
  - 0：Not Index
  - 1：Docs_Only
  - 2：Docs_And_Freqs
  - 3：Docs_And_Freqs_And_Poisition
  - 4：Docs_And_Freqs_And_Poisition_And_Offsets
- DocValueGen：当前字段的doc_value修改次数

FieldBits相关信息：

lucene索引结构整理

.fdx：正排数据的索引，用于快速找到指定doc

Block [BlockCount]
- BlockChunks： Block中chunk的数量（类型VInt）
DocBases： DocID信息
- DocBase : Block中第一个doc的ID （类型VInt）
- AvgChunkDoc: fdt文件中每个chunk中doc数量的均值（类型VInt）
- BitsPerDocBaseDelta：Packed Array中DocBaseDelta的编码长度,单位bit （类型VInt）
- DocBaseDelta[BlockChunks]：每个Chunk的docBase和预测docBase的偏移量（类型Packed Array）
StartPointers： Doc指针信息
- StartPointerBase：Block中第一个doc在fdt数据文件中的指针
- AvgChunkSize：fdt文件中每个chunk数据长度的均值（类型VInt）
- BitsPertartPointerDelta
- StartPointerDelta[BlockChunks]：（类型Packed Array）

.fdt：正排数据，包括各文档长度、文档字段数量、文档各字段类型和字段值

Chunk[ChunkCount]： 16kb
- DocBase：chunk中第一个doc的ID （类型VInt）
- ChunkDocs：chunk中doc数量（类型VInt）
- DocFieldCount：文档域的数量
  - if chunkDocs=1，VInt=N
  - else
    - 当所有文档的域数相同 bitsRequired=0 VInt=域数量
    - else bitsRequired + packed array 记录每篇文档的域数量
- DocLengths：文档域的长度
  - 类同DocFieldCount的存储方式
- Doc[ChunkDocs*字段数]
  - FieldNumAndType （类型VLong）
    - Type （后三个bit）
      - 0-5：String、Binary、Int、Float、Long、Double
  - FieldNum：字段ID
- Value ：根据Type信息选用不同的数据类型存储
- ChunkCount ：文件中chunk的个数（类型VInt）

#fdx到fdt示意：

lucene索引结构整理

Block中chunk的个数
DocBase信息：
- Block的第一个BlocalBaseDocId
- Block中平均每个chunk中保存多少doc: AvgChunkDocs
- 一个数组，保存第n个chunk的第一个docId (ChunkBaseDocId)同BlocalBaseDocId+n*AvgChunkDocs的偏移量
StartPointer信息
- 基本类似DocBase的存储方式
- 根据DocBase信息找到doc所在的chunk，然后从StartPointer信息里找到对应chunk在.fdt文件中的指针信息

4）倒排信息

.tip：倒排词典的前缀索引，会加载在存中，用于快速找到对应词条

FSTIndex[NumFields]：FST索引结构，指向文件中对应词的倒排信息位置
IndexStartFP[NumFields]：指向对应field的FSTIndex的指针
DirOffset：指向IndexStartFP数组起点的指针

.tim：主要包括词条到倒排、倒排跳表、positon、payload/offset信息的映射，以及各个域的基本统计信息

NodeBlocks：词和倒排指针信息
- ( InnerNode ) OuterNode
  - EntryCount：term的数量
  - SuffixLength+Suffix：term 前缀信息（类型VInt +byte[]）
  - StatsLength：TermStats数据长度（类型VInt）
  - TermStats[EntryCount]
    - DocFreq：词的DF信息（类型VInt）
    - TotalTermFreq：词在所有doc中的TF信息（类型VLong）
  - MetaLength （类型VInt）
  - TermMetadata[EntryCount]
    - DocFilePoint：term在doc文件中的指针（类型VLong）
    - PosFilePoint： term在pos文件中的位置（类型VLong）
    - PosVIntBlockFPDelta： .pos文件中，VintBlock的起始位置。判定block是packed array还是VInt （类型VLong）
    - PayFilePoint：term在payload文件中的位置（类型VLong）
    - SkipFilePoint：term的跳变信息在pos文件中的位置（类型VLong）
FieldSummarys ：各个域的基本统计信息
- FieldSummary [NumFields]
  - FieldNum：字段ID （类型VInt）
  - NumTerms：域中term的数量（类型VLong）
  - RootCodeLength +RootCode：指向该field的根block （类型VInt+byte[]）
  - SumTotalTermFreq：总TF （类型VLong）
  - SumDocFreq：总DF（不排重，倒排中没出现一次计算一次）（类型VLong）
  - DocCount：总DF （排重，一个DocID计算一次）（类型VInt）
  - LongsSize：记录每个词条需要的平均长度（类型VInt）
  - MinTerm：该域中最小的词条（字典序）（类型VInt+byte[]）
  - MaxTerm：该域中最大的词条（字典序）（类型VInt+byte[]）

.doc ：真正的倒排表信息，倒排表中存储着DocID和对应词条的TF信息，并为每个词条保存了跳表结构用于做快速Doc合并。

TermInfo[TermCount]
- PackedBlock[BlockNum]
  - PackedDocDeltaBlock：（类型packed int array ）
  - PackeeTermFreqBlock：（类型packed int array ）
- VIntBlock
  - DocDelta：（类型VInt）
  - TermFreq ：（类型VInt）
- SkipData：跳表数据
  - SkipLevel （类型VInt）
  - SkipDatum[DF/BlockSize ^ (SkipLevel+1)] :
    - DocSkip：doc id （类型VInt）
    - DocFilePointSkip：doc tf信息指针（类型VLong）
    - PosFpSkip：term的pos信息所在block，在.pos文件中的指针
    - PosBlockOffset：term的pos信息在指定block中偏移
    - PayLength：payload数据长度
    - PayFpSkip：payload数据文件指针
    - SkipChildLevelPoint：下一层、下一级跳表指针

.pos ：存储了词的位置信息。

PositionInfo[TermCount]
- PackedPosDeltaBlock[BlockNum]
- VintBlock：
  - PosDelta：position信息
  - PayloadLength：payload长度
  - PayloadData：payload数据
  - OffsetDelta：offset起始信息
  - OffsetLength：offset长度信息

这里做了一个策略，PackedPosBlockNum = floor(totalTermFreq/PackedBlockSize)。

剩下的position信息会使用一个VIntBlock进行存储。并且这部分词的payload和offset信息会一起存在这个VIntBlock中。

.pay：存储词的payload信息和offset信息

<Pay,Offset>[TermCount]
- TermPayloadBlock[BlockNum]
  - PayLengthBlock：（类型packed int array ）
  - SumPayLength : block中数据总长度（类型VInt）
  - PayData：（类型byte）
- TermOffsetBlock[BlockNum]
  - PackedOffsetStartDeltaBlock：（类型packed int array ）
  - PackedOffsetLengthDeltaBlock：（类型packed int array）

# tim到倒排数据：

lucene索引结构整理

5）字段长度规约

.nvm：

Entry[NumFields]
- FieldNumber：字段编号（类型VInt）
- BytesPerValue：指定字段压缩后每个值得长度（类型Int8）
- offset：指定字段数据偏移

.nvd：

Data：（类型byte[]）

6）doc_value数据

.dvm .dvd （TODO）

7）文档向量数据

.tvx：文档词向量数据的索引，用于快速找到指定doc

Block [BlockCount]
- BlockChunks
- DocBases： DocID信息
  - DocBase
  - AvgChunkDoc
  - BitsPerDocBaseDelta
  - DocBaseDelta
- StartPointers： Doc指针信息
  - StartPointerBase
  - AvgChunkSize
  - BitsPertartPointerDelta
  - StartPointerDelta

.tvd：存储了各个doc的域的数量、各个域的term_vector策略信息，以及从存储各个doc的词列表，及每个词的position、offset、payload信息

Chunk[ChunkCount] ： 16kb
- DocBase
- ChunkDocs
- DocNumFields [ChunkDocs]：每个doc的字段数量（类型Packed Array）
- FieldNumDelta [TotalDistinctFieldNums]：chunk中字段的unique count值（排重总数）（类型Packed Array）
- FieleNumOffset [TotalFieldNums]：chunk中字段的count值（不排重总数） = sum (DocNumFields [ChunkDocs]) （类型Packed Array）
- Flags
  - Bit ：值为1时说明所有文档中，相同字段的term_vector选项是相同的。否则，说明不同文档中相同字段的term_vector选项不同。（类型bit）
  - if Bit=1 则 Flag[TotalDistinctFieldNums]
  - if Bit=1 则 Flag[TotalFieldNums]
    - Flag：3个bit
      - 第1个bit：是否存position
      - 第2个bit：是否存offset
      - 第3个bit：是否存payload
- FieldTermNums [TotalFieldNums]： TotalTerms=sum of FieldTermNums [TotalFieldNums]
- TermLengths
  - PrefixLength [TotalTerms]
  - SuffixLength [TotalTerms]
- TermFreqsMinus1 [TotalTerms]：（类型Packed Array）
PositionDelta [TotalPosition] : TotalPosition=sum of TermFreqs[TotalTerms] （类型Packed Array）
StartOffsets [TotalPosition] : 假设所有字段都存offset （类型Packed Array）
PayloadLentgh [TotalPosition]: 假设所有字段都存Payload （类型Packed Array）
FieldTermsAndPayLoads [TotalFieldNums]
- Term [TotalPosition] ：（类型byte[]）
- Payload [TotalPosition]：（类型byte[]）
ChunkCount

8）文档删除数据

.liv：存储了被删除doc的id，使用位图形式，并以D-Gaps方式压缩

三、压缩/加速

1）fdx 估值偏移: Block/Chunk压缩

lucene索引结构整理

#fdx到fdt示意图：

lucene索引结构整理

Block中chunk的个数
DocBase信息：
- Block的第一个BlocalBaseDocId
- Block中平均每个chunk中保存多少doc: AvgChunkDocs
- 一个数组，保存第n个chunk的第一个docId (ChunkBaseDocId)同BlocalBaseDocId+n*AvgChunkDocs的偏移量
StartPointer信息
- 基本类似DocBase的存储方式
- 根据DocBase信息找到doc所在的chunk，然后从StartPointer信息里找到对应chunk在.fdt文件中的指针信息

2）倒排表的数据格式（差值压缩）

若设置不存储TF，只需要存储文档号，则每个block第一个doc存储真实dodId，后续doc存储同前一个docId之间的差值
当设置存放TF时，规则为，当TF=1，则DocDelta=2* DocDelta+1，TF不再单独存储。若TF!=1，则存放方式为<DocDelta差值*2，TF>

示例：

docId=5的文档中词出现1次，doc=8的文档中，词出现3次

若设置不存储TF：

则存放方式为： 5，3

若设置存储TF:

则存放方式为： 11，6，3。（或然跟随规则）

奇数代表TF=1,DocId=（DocDelta-1）/2

偶数代表DocId=DocDelta/2+ lastDocId ，TF 随后存储

3）倒排表快速查找（跳表）

lucene中跳变的interval等于BlockSize=128

#跳表到数据示意图：

lucene索引结构整理

4）.liv 文件的DGaps结构

lucene索引结构整理

.tvd 词频 blocks of 64 packed ints：

MinValue
Ints：解压时要加上MinValue

5）数值型及日期型数据

原始的数值型存储方式，字典树--区间倒排加速

lucene索引结构整理

默认情况下int、double、float等数字类型precisionstep为4，就是按4位二进制进行分割

k-d tree

lucene索引结构整理

四、索引拓展

1）索引数据抛弃：减少召回非精确的topN召回

idf过滤：可以理解一种停用词过滤
胜者表：对每个词保留k个胜者文档（超过k的文档，我们认为它对总分的影响可以忽略）
层次型索引：高端表（全局胜者表） + 低端表（其他文档）

按idf值分层，第一层idf>30%(或分>20等)，第二层idf>60%(或分>10)

2）前缀后缀索引

正向字典树+反向字典树取交集
轮排索引
- hello
  - hello$-》1
  - ello$h—》1
  - llo$he
  - lo$hel
  - o$hell->1
  - $hello
- he*o
  - he*o$
  - o$he*
- *llo
  - *llo$
  - llo$*