索引文件的读取（五）（Lucene 8.4.0）
本篇文章开始介绍索引文件.dvm&&dvd的读取，阅读本系列文章建议先看下文章索引文件的生成（十八）之dvm&&dvd、索引文件的生成（十九）之dvm&&dvd、IndexedDISI（一）、IndexedDISI（二），了解写入的过程能快的理解读取的逻辑。
DocValues的其中一个用途用于对查询结果的进行排序，在搜索阶段，当获取了满足查询条件的文档号之后，它会交给Collector实现收集功能，并且在收集过程中实现文档的排序。本文先介绍在使用SortedDocValues或者SortedSetDocValues的情况下，如何获取文档之间的排序关系，而通过读取索引文件.dvm&&dvd的过程即获取排序关系的过程：
通过索引文件.dvd、.dvm之SortedDocValues、SortedSetDocValues获取排序关系的流程图
图1：
文档号
图2：
流程图的准备数据为一个文档号，Collector收集器只接受满足查询条件的文档号。
DocIdData中是否包含该文档号？
图3：
DocIdData中存储了所有包含用于排序的DocValues的文档的文档号，如下红框所示所示：
图4：
图4中，通过读取索引文件.dvm的DocIdIndex字段，根据字段中的offset跟length来确定DocIdData在索引文件.dvd中的数据区间，而对于索引文件.dvm中的DocIdIndex以及其他字段的信息，则是根据索引文件.dvm的固定的数据结构依次轮流读取，如下所示：
图5：
图5中，meta.readLong()描述的是读取一个long类型大小的字节数量，另外readTermDict的方法的逻辑也是类似的，即读取TermsDictMeta、TermsIndexMeta的信息。不详细展示了。
在获取了DocIdData的信息之后就可以判断是否包含图2提供的文档号，包含意味着这篇文档中包含正在用于排序的DocValues信息。
如何判断DocIdData中是否包含该文档号
在文章IndexedDISI（一）、IndexedDISI（二）中我们介绍了详细的读取过程，这里不赘述。
DocIdData中包含该文档号
如果包含，那么返回一个段内编号index，index的概念在文章IndexedDISI（一）中已经介绍过了，我们这里再次说明下：
xxxxxxxxxx11段内编号index：index是一个从0开始递增的值，index的值描述的是在生成索引文件.dvd阶段，依次处理的第index个文档号。index实际上跟currentValue[ ]数组的下标值是同一个意思，见文章索引文件的生成（十八）之dvm&&dvd的介绍。
DocIdData中不包含该文档号
如果不包含，那么返回的missingOrd值可以为 -1 或者 Integer.MAX_VALUE，至于missingOrd值的用途在下文中我们再介绍。
根据index从Ords中获取ord值
图6：
Ords即图4中索引文件.dvd的Ords字段的信息，Ords的写入过程见文章索引文件的生成（十九）之dvm&&dvd，这里可以简单的将Ords理解为一个数组，其中数组下标为上文中的index、数组元素为ord值（具有相同用于排序的DocValues域值的文档对应的ord值是相同的），其中ord描述了文档之间的排序关系，如果是递增排序，那么ord越小，文档排序越靠前，如果某篇文档不包含当前用于排序的DocValues，那么上文中的missingOrd就作为这篇文档的ord值参与排序。至于为什么ord值描述了文档文档之间的排序关系，相信在读完文章索引文件的生成（十八）之dvm&&dvd之后能明白。
从上文的内容可以看出，如果用SortedValues/SortedSetValues来排序， 并不是比较SortedValues/SortedSetValues对应的域值的字典序，而是在生成索引文件.dvd阶段将域值映射为一个ord值，通过比较int类型的ord值就能得出排序关系，性能上明显是大于字典序的比较方式，特别是较长的域值。当然ord值的用途不仅仅如此，下文中我们会继续介绍其他的用途。
到此流程，我们已经获得了文档之间的关系，如果还要取出每篇文档中参与排序的域值，即DocValues的域值，那么可以根据ord获得。
根据ord值从TermsDict中获取域值
图7：
在生成索引文件.dvm&&.dvd阶段，会将有序的并且去重的域值依次写入，并且每处理16个域值就生成一个block、同时生成一个address用来描述这个block在索引文件.dvd中的起始位置，随后在block中找到对应的域值：
图8：
当获得了ord值后，需要三步才能找到对应的域值：
- 步骤一：计算出在BlockIndex的哪一个块中，计算方式为 ord >> 16，获取块中的address的值
- 步骤二：根据address的值，找到Block在索引文件.dvd中的起始位置
- 步骤三：依次读取Block中的每一个域值，并且判断该域值对应的ord值是否为我们期望的ord，如果不是，那么读取下一个域值，直到找到我们期望的ord
在步骤三中，相邻term的前缀存储，即如果需要读取第n个域值的完整值，需要知道第n-1个域值的完整值，故Block中第一个域值存储的是完整的域值（见文章SortedDocValues的介绍）。
至此流程点介绍完毕，可以看出，根据文档号我们能获得用于排序的DocValues的域值以及文档的排序关系，注意到的是索引文件.dvd中的TermsIndex在上文中没有涉及，我们接下来介绍该字段的用途。
读取TermsIndex
通过TermsIndex字段，可以用来判断为DocValues中是否包含某个域值，其中一个应用场景为利用DocValues来实现范围查询，demo如下：
图9：
图9的demo完整代码见：https://github.com/LuXugang/Lucene-7.5.0/blob/master/LuceneDemo8.4.0/src/main/java/io/lucene/DcoValues/SortedDocValuesTest4Test.java 。
图9中，使用了SortedDocValuesField.newSlowRangeQuery(...)方法执行范围查询，查询条件为包含域名为"level"、域值范围为[b, c]的SortedDocValues的文档，可见文档3、文档4满足查询条件，故代码第88行的查询结果数量为2。
我们先给出TermsIndex的数据结构，然后介绍如何通过实现图9的范围查询。
同图4一样，要读取索引文件.dvd中的TermsIndex字段数据，需要通过索引文件.dvm中的TermsIndexMeta，如下所示：
图10：
接着我们看索引文件.dvd中TermsIndex字段的数据结构：
图11：
在生成索引文件.dvd的TermsIndex期间，每处理1024个域值，就生成一个PrefixValue，它描述的是在区间[0, 1023]的ord值对应的域值都小于PrefixValue（字典序，详细的介绍见文章索引文件的生成（二十）之dvm&&dvd）。
如果判断SortedDocValues是否包含某个域值，分为以下的步骤：
- 步骤一：获取域值的数量termsDictSize，然后执行 termsDictSize - 1 >>> 10获得一个ordHigh，这个操作计算的是TermsIndex中PrefixValue的数量，可见ordHigh是一个1024的倍数，例如0、1024、2048等，另外termsDictSize的值通过索引文件.dvm中TermsDict字段的TermsDictSize，下图红框标注：
图12：
- 步骤二：根据ordLow == 0跟ordHigh做二分查询，实际就是对图11中的TermsIndex中的PrefixValue进行二分查询，最后获得PrefixValue对应的blockLo跟blockHi，即找到一个ord区间
- 步骤三：随后根据上个步骤计算出的ord区间，对区间内的ord继续做二分查找，实际就是对图8中TermsDict的Block中的第一个term进行二分查找（Block中的第一个term是一个完整的域值），最后确定待查找的域值所属的block
- 步骤四：遍历block中的每一个域值，跟待查找的域值进行字节比较，如果相同说明DocValues中包含待查找的域值，并且返回该域值对应的ord值
对于图9中的范围查找，实际的过程为尝试找到第78行域值"b"、"c"分别对应的ord值，注意的是：如果没有找到域值"b"对应的ord值，那么ord值为下一个block的第一个term对应的ord值，如果没有找到域值"c"对应的ord值，那么ord值为当前block的最后一个term，最后遍历域名为"level"中包含的所有文档号（DocIdData字段），并且找出文档号对应的ord值（上文中已经介绍如何通过文档号找到对应的ord值），如果ord值在"b"、"c"对应的ord值区间，那么就认为该文档是满足查询条件的。
上述的内容查找"b"、"c"对应的ord只是介绍了部分的情况，其他一些边界的情况就不展开，相信你已经能了解如何通过DocValues实现范围查找。
结语
尽管本文中没有对SortedSetDocValues进行额外的介绍，实际上原理跟SortDocValue是一致的，故不赘述。
点击下载附件