Lu Xugang的小屋
SortedDocValues（Lucene 7.5.0）
Lu Xugang Lv6
  2019-02-19 00:00:00   2024-10-24 14:56:52    2.4k Words  

SortedDocValues同NumericDocValues、SortedNumericDocValues一样，在实际应用中最多的场景用于提供给搜索结果一个排序规则。本篇文章只讲述使用了SortedDocValues后，其在.dvd、.dvm文件中的索引结构。在以后的介绍例如 facet、join、group等功能时，会详细介绍如何根据.dvd、dvm中的索引数据进行查询的过程。

预备知识

下面出现的变量名皆为源码中的同名变量名。

TermId

在索引阶段，根据IndexWriter中添加的document的顺序，有序的处理每一个document中的SortedDocValuesField。并且对每一个SortedDocValuesField的域值赋予一个从0开始递增的termId，相同的域值具有相同的termId。
图1：

域值与termId的对应关系如下：

域值 aa cc bb ff
termId 0 3 2 1

currentValues[]数组

currentValues[]数组中，下标值为文档号docId，数组元素为termId。在索引阶段，由于处理的数据是按照IndexWriter中添加的document的顺序进行的，即按照第一篇文档(document)，文档号为0，文档号递增的顺序。所以在这个过程中，就可以实现通过数组方式来记录 文档号(docId) 跟 termId 的映射关系
图2：

sortedValues[]数组 && ord

sortedValues[]数组中的数组元素是termId，数组下标是ord值。下面的一句话很重要：数组元素是有序的，但是排序规则不是根据termId的值，而是根据termId对应的域值的字典序。
图3：

ordMap[]数组

sortedValues[]数组中实现了 数组下标ord 到 数组元素termId的映射，而ordMap[]数组则是实现了 数组下标termId 到 数组元素 ord的映射。
图4：

数据结构

dvd

图5：

DocIdData

DocIdData中记录包含当前域的文档号。
如果IndexWriter添加的document中不都包含当前域，那么需要将包含当前域的文档号记录到DocIdData中，并且使用IndexedDISI类来存储文档号，IndexedDISI存储文档号后生成的数据结构单独的作为一篇文章介绍，在这里不赘述。

Ords

Ords记录了每一篇文档中SortedDocValuesField的域值对应的ord值。这里的ord值即上文中的预备知识中的ord值。

TermsDict

TermsDict中根据域值大小，并且按块处理，存储所有的SortedDocValuesField域值。
图6：

Block

存储SortedDocValuesField的域值时，按照域值从小到大的顺序，并且按块处理所有的域值，相同的域值不会重复存储。
每16个域值按照一个块（block）处理，在一个块内，只存储第1个域值的完整值，对于剩余的15个域值，只存储与前一个域值不相同后缀的部分值（所以需要按照域值大小顺序存储才能尽可能减少空间占用），即前缀存储。
图7：

FirstTermLength
1
每个block的第1个域值的长度。
FirstTermValue
1
每个block的第1个域值的完整值。
PrefixLength && SuffixLength
1
2
prefixLength是当前域值与前一个域值相同前缀的长度，如果当前当前是第10个域值，那么它跟第9个域值进行prefixLength的计算。
suffixLength是除去相同前缀的剩余部分的长度。
SuffixValue
1
除去相同前缀的剩余部分的域值。

BlockIndex

1
BlockIndex中记录了每一个block相对于第一个block的在.dvd文件中的偏移，在读取阶段，如果需要读取第n个block的数据，那么只要计算 第n个和第n+1个的blockIndex的差值，就可以获得第n个block在.dvd文件中的数据区间，实现随机访问。每一个block的blockIndex采用PackedInts进行压缩存储。

Block与ord的关系

由于域值是从小到大写入到所有Block中， 而在上文中的预备知识中得知，sortedValues[]数组的ord的值正是描述了域值的大小关系，所以写入到block中的第1个域值就是对应ord的值0，第8个域值就是对应ord的值7，ord的值从0开始递增。
下面的例子描述了我们搜索后的结果只要返回Top3，并且比较规则是根据SortedDocValuesField的域值进行比较。
图8：

但是满足搜索要求的文档只会将docId传入到Collector类的collect(int doc)方法中，即我们只能知道文档号的信息，无法获得当前文档中SortedDocValuesField的域值来做排序比较。
这时候我们可以根据文档号docId从IndexedDISI中找到段内编号（见文章IndexedDISI）。段内编号作为currentValues[]数组下标值，取出数组元素，即termId，然后termId作为ordMap[]数组下标值，取出数组元素，即ord值。根据ord值我们就可以找到当前文档中的 SortedDocValuesField的域值在对应的Block中，然后遍历Block中的16个域值，直到找到我们想要的域值。
图9：

TermsIndex

TermsDict中每遍历16个域值就处理为一个block，而在TermsIndex中则是每遍历1024个域值就记录一个域值的前缀值。
图10：

PrefixValue

1
与上一个域值的相同的前缀值 加上 后缀值的第一个字节。

例如第1个域值为 “ab”、第1023个域值为"abcdasdfsaf" 、第1024个域值为"abceftn"、第2047个域值为 “abceftop” 、第2048个域值为 “abceftoqe”，那么存储到TermsIndex的数据如下：
图11：

PrefixValueIndex

1
PrefixValueIndex中记录了每一个prefixValue相对于第一个prefixValue的在.dvd文件中的偏移，在读取阶段，如果需要读取第n个prefixValue的数据，那么只要计算 第n个和第n+1个的PrefixValueIndex的差值，就可以获得第n个prefixValue在.dvd文件中的数据区间，实现随机访问。每一个prefixValue的PrefixValueIndex采用PackedInts进行压缩存储。

PrefixValue有什么用

在TermsDict中，我们可以根据文档号在TermsDict找到对应的SortedDocValuesField的域值，但是通过TermsIndex我们就可以判断 某个域值是不是在SortedDocValuesField中。
例如我们需要判断域值 “abcef” 是否为SortedDocValuesField的一个域值，那么就可以使用二分法遍历PrefixValue，每次跟"abcef"比较，根据上面的例子，我们可以知道 “abcef” 大于““abce”，并且小于"abceftoq”。
图12：

所以我们接着根据两个ord值去TermsDict中继续查找，同样的的使用二分法去遍历Block。

dvm

图13：

FieldNumber

1
域的编号

DocvaluesType

1
Docvalues的类型，本文中，这个值就是 SORTED。

DocIdIndex

DocIdIndex是对.dvd文件的一个索引，用来描述 .dvd文件中DocIdData在.dvd文件中的开始跟结束位置。

情况1：

图14：

如果IndexWriter添加的document中都包含当前域，那么只需要在DocIdIndex中添加标志信息即可。

情况2：

图15：

如果IndexWriter添加的document中不都包含当前域，那么.dvd文件中需要将包含当前的域的文档号信息都记录下来。

offset
1
.dvd文件中存放文档号的DocIdData在文件中的开始位置。
length
1
length为DocIdData在.dvd文件中的数据长度。

在读取阶段，通过offset跟length就可以获得所有的DocIdData数据。

numDocsWithField

1
包含当前域的文档的个数。

OrdsIndex

情况1：

图16：

如果只有一种类型的域值，那么写入固定的标志信息即可。

情况2：

图17：

numberOfBitsPerOrd
1
numberOfBitsPerOrd描述了存储ord值的固定bit位个数。
offset
1
.dvd文件中存放ord的Ords在文件中的开始位置。
length
1
length为Ords在.dvd文件中的数据长度。

TermsDictMeta

图18：

TermsDictSize

1
域值的种类个数(不是域值的个数)

TermsDictBlockShift

1
描述了一个block中有多少个域值。

DIRECT_MONOTONIC_BLOCK_SHIFT

1
DIRECT_MONOTONIC_BLOCK_SHIFT用来在初始化byte buffer[]的大小，buffer数组用来存放BlockIndex。

Min

1
记录一个最小值，在读取阶段用于解码。Min的含义请看我的源码注释。

AvgInc

1
记录一个AvgInc，在读取阶段用于解码。AvgInc的含义请看我的源码注释。

Length

1
BlockIndex的数据总长度

BitsRequired

1
经过DirectMonotonicWriter的数据平缓操作后，每个数据需要的固定bit位个数。

MaxLength

1
域值的最大长度

BlockMeta

图19：

offset
1
Block在.dvd文件中的开始位置。
length
1
length为Block在.dvd文件中的数据长度。

在读取阶段，通过offset跟length就可以获得所有的所有Block数据。

BlockIndexMeta

图20：

offset
1
BlockIndex在.dvd文件中的开始位置。
length
1
length为BlockIndex在.dvd文件中的数据长度。

在读取阶段，通过offset跟length就可以获得所有BlockIndex数据。

TermsIndexMeta

图21：

TERMS_DICT_REVERSE_INDEX_SHIFT

1
描述每遍历多少个域值，保存一次PrefixValue。当前版本为1024。

Min

1
记录一个最小值，在读取阶段用于解码。Min的含义请看我的源码注释。

AvgInc

1
记录一个AvgInc，在读取阶段用于解码。AvgInc的含义请看我的源码注释。

Length

1
PrefixValueIndex的数据总长度

BitsRequired

1
经过DirectMonotonicWriter的数据平缓操作后，每个数据需要的固定bit位个数。

PrefixValueMeta

图22：

offset
1
PrefixValue在.dvd文件中的开始位置。
length
1
length为PrefixValue在.dvd文件中的数据长度。

在读取阶段，通过offset跟length就可以获得所有PrefixValue数据。

PrefixValueIndexMeta

图23：

offset
1
PrefixValueIndex在.dvd文件中的开始位置。
length
1
length为PrefixValueIndex在.dvd文件中的数据长度。

在读取阶段，通过offset跟length就可以获得所有PrefixValueIndex数据。

结语

本文详细介绍了SortedDocValues在.dvd、.dvm文件中的数据结构，并简单介绍了为什么要写入TermsDict、TermsIndex的数据。SortedDocValues跟SortedSetDocValues是在所有DocValues中数据结构最为复杂的。另外在预备知识中提到的几个数组，它们都是在SortedDocValuesWriter类中生成，大家可以可看我的源码注释来加快SortedDocValuesWriter类的理解，源码地址：https://github.com/luxugang/Lucene-7.5.0/blob/master/solr-7.5.0/lucene/core/src/java/org/apache/lucene/index/SortedDocValuesWriter.java

 BUY ME A COFFEE
 Comments
Comment plugin failed to load
Loading comment plugin
  1. 1. 预备知识
    1. 1.1. TermId
    2. 1.2. currentValues[]数组
    3. 1.3. sortedValues[]数组 && ord
    4. 1.4. ordMap[]数组
  2. 2. 数据结构
    1. 2.1. dvd
      1. 2.1.1. DocIdData
      2. 2.1.2. Ords
      3. 2.1.3. TermsDict
        1. 2.1.3.1. Block
          1. 2.1.3.1.1. FirstTermLength
          2. 2.1.3.1.2. FirstTermValue
          3. 2.1.3.1.3. PrefixLength && SuffixLength
          4. 2.1.3.1.4. SuffixValue
        2. 2.1.3.2. BlockIndex
        3. 2.1.3.3. Block与ord的关系
      4. 2.1.4. TermsIndex
        1. 2.1.4.1. PrefixValue
        2. 2.1.4.2. PrefixValueIndex
        3. 2.1.4.3. PrefixValue有什么用
    2. 2.2. dvm
      1. 2.2.1. FieldNumber
      2. 2.2.2. DocvaluesType
      3. 2.2.3. DocIdIndex
        1. 2.2.3.1. 情况1：
        2. 2.2.3.2. 情况2：
          1. 2.2.3.2.1. offset
          2. 2.2.3.2.2. length
      4. 2.2.4. numDocsWithField
      5. 2.2.5. OrdsIndex
        1. 2.2.5.1. 情况1：
        2. 2.2.5.2. 情况2：
          1. 2.2.5.2.1. numberOfBitsPerOrd
          2. 2.2.5.2.2. offset
          3. 2.2.5.2.3. length
      6. 2.2.6. TermsDictMeta
        1. 2.2.6.1. TermsDictSize
        2. 2.2.6.2. TermsDictBlockShift
        3. 2.2.6.3. DIRECT_MONOTONIC_BLOCK_SHIFT
        4. 2.2.6.4. Min
        5. 2.2.6.5. AvgInc
        6. 2.2.6.6. Length
        7. 2.2.6.7. BitsRequired
        8. 2.2.6.8. MaxLength
        9. 2.2.6.9. BlockMeta
          1. 2.2.6.9.1. offset
          2. 2.2.6.9.2. length
        10. 2.2.6.10. BlockIndexMeta
          1. 2.2.6.10.1. offset
          2. 2.2.6.10.2. length
      7. 2.2.7. TermsIndexMeta
        1. 2.2.7.1. TERMS_DICT_REVERSE_INDEX_SHIFT
        2. 2.2.7.2. Min
        3. 2.2.7.3. AvgInc
        4. 2.2.7.4. Length
        5. 2.2.7.5. BitsRequired
        6. 2.2.7.6. PrefixValueMeta
          1. 2.2.7.6.1. offset
          2. 2.2.7.6.2. length
        7. 2.2.7.7. PrefixValueIndexMeta
          1. 2.2.7.7.1. offset
          2. 2.2.7.7.2. length
  3. 3. 结语
  1. 1. 预备知识
    1. 1.1. TermId
    2. 1.2. currentValues[]数组
    3. 1.3. sortedValues[]数组 && ord
    4. 1.4. ordMap[]数组
  2. 2. 数据结构
    1. 2.1. dvd
      1. 2.1.1. DocIdData
      2. 2.1.2. Ords
      3. 2.1.3. TermsDict
        1. 2.1.3.1. Block
          1. 2.1.3.1.1. FirstTermLength
          2. 2.1.3.1.2. FirstTermValue
          3. 2.1.3.1.3. PrefixLength && SuffixLength
          4. 2.1.3.1.4. SuffixValue
        2. 2.1.3.2. BlockIndex
        3. 2.1.3.3. Block与ord的关系
      4. 2.1.4. TermsIndex
        1. 2.1.4.1. PrefixValue
        2. 2.1.4.2. PrefixValueIndex
        3. 2.1.4.3. PrefixValue有什么用
    2. 2.2. dvm
      1. 2.2.1. FieldNumber
      2. 2.2.2. DocvaluesType
      3. 2.2.3. DocIdIndex
        1. 2.2.3.1. 情况1：
        2. 2.2.3.2. 情况2：
          1. 2.2.3.2.1. offset
          2. 2.2.3.2.2. length
      4. 2.2.4. numDocsWithField
      5. 2.2.5. OrdsIndex
        1. 2.2.5.1. 情况1：
        2. 2.2.5.2. 情况2：
          1. 2.2.5.2.1. numberOfBitsPerOrd
          2. 2.2.5.2.2. offset
          3. 2.2.5.2.3. length
      6. 2.2.6. TermsDictMeta
        1. 2.2.6.1. TermsDictSize
        2. 2.2.6.2. TermsDictBlockShift
        3. 2.2.6.3. DIRECT_MONOTONIC_BLOCK_SHIFT
        4. 2.2.6.4. Min
        5. 2.2.6.5. AvgInc
        6. 2.2.6.6. Length
        7. 2.2.6.7. BitsRequired
        8. 2.2.6.8. MaxLength
        9. 2.2.6.9. BlockMeta
          1. 2.2.6.9.1. offset
          2. 2.2.6.9.2. length
        10. 2.2.6.10. BlockIndexMeta
          1. 2.2.6.10.1. offset
          2. 2.2.6.10.2. length
      7. 2.2.7. TermsIndexMeta
        1. 2.2.7.1. TERMS_DICT_REVERSE_INDEX_SHIFT
        2. 2.2.7.2. Min
        3. 2.2.7.3. AvgInc
        4. 2.2.7.4. Length
        5. 2.2.7.5. BitsRequired
        6. 2.2.7.6. PrefixValueMeta
          1. 2.2.7.6.1. offset
          2. 2.2.7.6.2. length
        7. 2.2.7.7. PrefixValueIndexMeta
          1. 2.2.7.7.1. offset
          2. 2.2.7.7.2. length
  3. 3. 结语