源码系列
原文： https://www.amazingkoala.com.cn/Lucene/2019/1205/115.html
阅读本篇文章需要前置内容： BulkOperationPacked，下文中会列出在文章 BulkOperationPacked 中涉及的代码，但是不会展开介绍。
DirectWriter&&DirectReader 两个类用来处理 long 类型的数据集（数组类型），其中 DirectWriter 用来在写数据时使用 BulkOperationPacked 将 long 类型的数据转换成 byte 类型，而 DirectReader 则是将 byte 类型的数据恢复成 long 类型。使用 byte 类型数据存储的组件都可以使用 DirectWriter&&DirectReader 实现压缩存储，比如以字节为单位存储索引文件内容的 Directory。
压缩实现
在 BulkOperation 中，根据 bitPerValue 的值，对应的压缩实现不尽相同，但是 DirectWriter 只支持下列的 bitPerValue：
|
|
bitPerValue 是什么：
使用 BulkOperation 提供的压缩实现，要求数据集中的所有数据按照固定位数存储，固定位数即 bitPerValue。
bitPerValue 怎么计算：
选取数据集中的最大值，它的有效数据占用的 bit 位个数为 bitPerValue。
例如有下面的数据集：
数组一：
|
|
数组一中的元素对应的二进制表示如下所示：
表一：
数组元素二进制200000000_00000000_00000000_00000000_00000000_00000000_00000000_0000001027800000000_00000000_00000000_00000000_00000000_00000000_00000001_000101102300000000_00000000_00000000_00000000_00000000_00000000_00000000_00010111
数组一中的最大值为 278，它的有效数据占用的 bit 位个数如表一中红色标注所示，共 9 位，故 bitPerValue 的值为 9，并且数值 2、23 都使用 9 个 bit 来存储。
待处理的数据集的 bitPerValue 不是 SUPPORTED_BITS_PER_VALUE 中的一员怎么办：
如果待处理的数据集的 bitPerValue 不属于 SUPPORTED_BITS_PER_VALUE 数组中的数组元素之一，那么另下一个比 bitPerValue 大的数组元素作为新的 bitPerValue。例如表一中，bitPerValue 的值为 9，那么重新另 bitPerValue 为 12，即，数值 2、278、23 都使用 12 个 bit 位存储。
为什么只支持 SUPPORTED_BITS_PER_VALUE 中的 bitPerValue：
因为这些 bitPerValue 对应的压缩实现是读写性能最佳的， 衡量读写性能的指标如下：
- 写性能：写入一个数值需要涉及的 block 个数，越少性能越高
- 读性能：读取一个数值对应的 block 的个数，越少性能越高，另外字节对齐的数据读取性能越高，否则需要额外计算字节首地址
例如我们有以下的数据集：
数组二：
|
|
数组一中的元素对应的二进制表示如下所示：
表二：
数组元素二进制12000000000_00000000_00000000_00000000_00000000_00000000_00000000_011110006900000000_00000000_00000000_00000000_00000000_00000000_00000000_010001012300000000_00000000_00000000_00000000_00000000_00000000_00000000_000101112500000000_00000000_00000000_00000000_00000000_00000000_00000000_00011001
表二中，数组二的 bitPerValue 为 7，如果我们使用该 bitPerValue，即每个数值使用 7 个 bit 位存储，那么处理结束后如下所示，同时给出 bitPerValue 为 8 时的结果：
图 1：
从图 1 可以看出，在读取阶段，如果 bitPerValue 为 7，那么需要两个字节才能读取到 69、23、25 的值，另外需要计算首地址跟偏移才能找到在字节中的起始位置，而如果 bitPerValue 为 8，那么只需要一个字节即可，并且不需要计算偏移地址。很同时也可以看出，这是空间换时间的设计。
我们再看下写阶段的情况，从图 1 同样能明显看出 bitPerValue 为 7 时，写入一个数值需要跨越 2 个 block，我们从代码中也可以看出其性能差异的原因：
图 2：
图 2 截取自 BulkOperationPacked，bitPerValue 为 7 时，相比较 bitPerValue 为 8 时需要执行额外的位移操作，如第 31 行代码所示。 更重要的是当处理相同数量的数值时，需要更多的遍历次数，在文章 BulkOperationPacked 中，为了简化介绍 BulkOperationPacked 的原理，我们并没有介绍如何计算遍历次数，只是简单的将待处理的数据集数量作为遍历次数，即图 8 中第 31 行的 values.length，在源码中，图 1 中的第 8 行代码应该是这样的：
图 3：
遍历次数是如何计算的：
在后续介绍 PackedWriter 的文章中我们再讲述这个问题，本篇文章中我们只要知道 bitPerValue 为 7 时，相比较 bitPerValue 为 8 在处理相同数量的数据集时，需要更多的遍历次数。
如何选择 bitPerValue 的值作为 SUPPORTED_BITS_PER_VALUE 中的一员：
我们再次列出 SUPPORTED_BITS_PER_VALUE 中的成员：
|
|
我们先看下 bitPerValue 大于等于 8 的情况，当 bitPerValue 为 8、16、24、32、40、48、56 时，这几个值总能保证待处理的数值能按照字节对齐（8 的倍数）处理，故读写性能是很快的，我们想要了解的是，bitPerValue 的值不是 8 的倍数的情况下，为何还将 12、20、28、48 作为 SUPPORTED_BITS_PER_VALUE 的成员。
这是一种出于空间使用率与读写性能的折中处理，例如 bitPerValue 的值为 9 时，如果只能选择 16，那么每一个数值的额外空间开销为（16 - 9）/ 16 = 0.4375，故我们需要在(8，16)的区间内找出一个空间开销与读写性能兼顾的 bitPerValue，那么 12 是最好的选择，因为它的读写性能在这个区间内是最佳的，同时额外空间开销降低到 （12 - 9）/ 12 = 0.25。
为什么在区间(8，16)中选取 bitPerValue 的值是 12:
首先在这个区间内 bitPerValue 的写性能是差不多的，因为它们的值不是 8（一个字节）的倍数，都需要跨 block 存储，所以我们看它们在读性能的差异性，同样地，由于不能保证每个数值都是按照字节对齐存储，故我们只能通过平均读取一个数值需要计算首地址的次数来判断读的性能：
我们有如下的数据集数组三：
数组三：
|
|
数组三中的元素对应的二进制表示如下所示：
表三：
数组元素二进制6900000000_00000000_00000000_00000000_00000000_00000000_00000000_010001012500000000_00000000_00000000_00000000_00000000_00000000_00000000_0001100126100000000_00000000_00000000_00000000_00000000_00000000_00000001_000001012300000000_00000000_00000000_00000000_00000000_00000000_00000000_00010111
数组三中，最大值为 261，故此时的 bitPerValue 为 9，我们用 bitPerValue 为 9 以及 bitPerValue 为 12 来处理数组三的数据，如下所示：
图 4：
从图 4 可见，如果需要读取 261 的数值，在
- 原文作者：知识铺
- 原文链接：https://geek.zshipu.com/post/%E4%BA%92%E8%81%94%E7%BD%91/%E6%BA%90%E7%A0%81%E7%B3%BB%E5%88%97/
- 版权声明：本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可，非商业转载请注明出处（作者，原文链接），商业转载请联系作者获得授权。
- 免责声明：本页面内容均来源于站内编辑发布，部分信息来源互联网，并不意味着本站赞同其观点或者证实其内容的真实性，如涉及版权等问题，请立即联系客服进行更改或删除，保证您的合法权益。转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。也可以邮件至 sblig@126.com
