原文链接： https://www.amazingkoala.com.cn/Lucene/yasuocunchu/2019/0213/31.html

  BulkOperation 类的子类 BulkOperationPacked，提供了很多对整数(integers)的压缩存储方法，其压缩存储过程其实就是对数据进行编码，将每一个整数（long 或者 int）编码为固定大小进行存储，大小取决于最大的那个值所需要的 bit 位个数。优点是减少了存储空间，并且对编码后的数据能够提供随机访问的功能。

例如有以下的数据{1，1，1，0，2，2, 0, 0}，二进制的表示为{01, 01, 01, 0, 10, 10, 0, 0}，存储需要 32 个字节大小的空间。数据中最大的值是 2，需要 2 个 bit 位即可表示，所以其他数据统一用 2 个 bit 位固定大小来表示，编码后需要的空间如下图：图 1：

  如上图所示，编码后只需要 2 个字节的空间大小。

encode 源码解析

  https://github.com/luxugang/Lucene-7.5.0/blob/master/solr-7.5.0/lucene/core/src/java/org/apache/lucene/util/packed/BulkOperationPacked.java 中给出了详细的注释，根据不同的 bitsPerValue(最大值需要的 bit 位个数)，BulkOperationPacked 有几十个子类，但是编码操作都是调用了父类 BulkOperationPacked 的 encode 方法，仅仅是部分 BulkOperationPacked 子类的 decode 方法不同一共有四种 encode 方法：

• long[]数组编码至 byte[]数组
• int[]数组编码至 byte[]数组
• long[]数组编码至 long[]数组
• int[]数组编码至 long[]数组

  在下面的代码中，挑选了其中一种 encode 方法，即将 long[]数组编码至 byte[]数组，出于仅仅对 encode 逻辑的介绍，所以简化了部分代码，比如 iterations，byteValueCount 变量。这些变量不影响对 encode 过程的理解。下面的代码大家可以直接运行测试。

public class Encode {
  public static byte[] encode(long[] values,int bitsPerValue) {
    byte[] blocks = new byte[2];
    int blocksOffset = 0;
    int nextBlock = 0;
    int bitsLeft = 8;
    int valuesOffset = 0;
    for (int i = 0; i < values.length; ++i) {
      final long v = values[valuesOffset++];
      // bitsPerValue指的是每一个元素需要占用的bit位数，这个值取决于数据中最大元素需要的bit位
      // 也就是每一个元素不管大小，占用的bit位数都是一致的
      if (bitsPerValue < bitsLeft) {
        // 将当前处理的数值写到nextBlock中
        nextBlock |= v << (bitsLeft - bitsPerValue);
        bitsLeft -= bitsPerValue;
      } else {
        // flush as many blocks as possible
        int bits = bitsPerValue - bitsLeft;
        // nextBlock | (v >>> bits)的操作将v值存储到nextBlock中
        // 然后将nextBlock的值存储到blocks[]数组中，完成一个字节的压缩
        blocks[blocksOffset++] = (byte) (nextBlock | (v >>> bits));
        while (bits >= 8) {
          bits -= 8;
          // 将一个数组分成多块(按照一个8个bit大小划分)存储
          blocks[blocksOffset++] = (byte) (v >>> bits);
        }
        // then buffer
        bitsLeft = 8 - bits;
        // 把v的值的剩余部分存放到下一个nextBlock中,也就是当前的v值的部分值会跟下一个v值的数据(可能是部分数据)混合存储到同一个字节中
        // 这里说明了数据是连续存储，可能分布在不同的block中
        nextBlock = (int) ((v & ((1L << bits) - 1)) << bitsLeft);
      }
    }
    return blocks;
  }

  public static void main(String[] args) {
    long[] array = {1, 1, 1, 0, 2, 2, 0, 0};
    byte[] result = Encode.encode(array, 2);
    for (int a: result
    ) {
      System.out.println(a);
    }
  }
}

  输出的结果是 84, -96。

decode 源码解析

全解码

  不同的 BulkOperationPacked 子类有着不同的 decode 方法，解码的方法不尽相同，在 Lucene7.5.0 版本中，共有 14 种解码方法，尽管有这么多，但是逻辑都是大同小异。由于在上文中我们设置的 bitPerValue 的值为 2，所以我们就介绍对应的 decode 方法。

public class Decode {
  public static void decode(byte[] blocks, int blocksOffset, long[] values, int valuesOffset, int iterations) {
    for (int j = 0; j < iterations; ++j) {
      final byte block = blocks[blocksOffset++];
      // 因为 bitPerValues 的值为 2，所以每次取 2 个 bit 位的数据即可
      values[valuesOffset++] = (block >>> 6) & 3;
      values[valuesOffset++] = (block >>> 4) & 3;
      values[valuesOffset++] = (block >>> 2) & 3;
      values[valuesOffset++] = block & 3;
      // 至此，我们取出了 1 个字节的所有数据，这些数据包含了 4 个编码前的数据
    }
  }
    
  public static void main(String[] args) {
    long[] array = {1, 1, 1, 0, 2, 2, 0, 0};
    byte[] result = Encode.encode(array, 2);
    System.out.println("Encode");
    for (long a: result
    ) {
      System.out.println(a);
    }
    long [] arrayDecode = new long[8];
    // 每次解码都是对一个字节操作，而编码后的 byte[]数组有 2 个字节，所以 iterations 参数为 2
    Decode.decode(result, 0, arrayDecode, 0, 2);
    System.out.println("Decode");
    for (long a : arrayDecode
         ) {
      System.out.println(a);
    }
  }
}

随机解码(随机访问)

  上面的 decode()方法对所有的数据，按照在 byte[]数组中的顺序依次解码，下面介绍的就是这种编码带有的随机访问(随机解码)的功能。

  下面的 get()方法在 DirectReader 类中实现。根据 bitsPerValue 的值(encode 阶段，固定大小的 bit 位数)，本篇博客中仅列出 bitsPerValue 值为 2 的解码方法，对应上文的 encode 方法。更具体的注释请查看 GitHub：https://github.com/luxugang/Lucene-7.5.0/blob/master/solr-7.5.0/lucene/core/src/java/org/apache/lucene/util/packed/DirectReader.java 。

1. public long get(long index) {
2.     try {
3.       // 在 encode 阶段，每一个值用 2 个 bit 位进行存储，所以每一个 block(一个字节大小)中起始位置只会有 4 种  可能，即第 1 位，第 3 位，第 5 位，第 7 位(计数从 0 开始)
4.      // 即 shift 的值只可能是 0, 2，4，6
5.      int shift = (3 - (int)(index & 3)) << 1;
6.      // 每一个数组元素都用 2 个 bit 位表示，所以跟 0x3 执行与操作
7.      return (in.readByte(offset + (index >>> 2)) >>> shift) & 0x3;
8.    } catch (IOException e) {
9.      throw new RuntimeException(e);
10.    }
11.  }

例子（随机访问）

  编码后的值如下图所示：

图 1：

取出原数组中下标值(index)为 2 的数组元素

  根据 decode 中第 5 行代码，我们先求出 shift 的值为 2。截取上图中部分字节数据，大小为 index >> 2, 即截取 8 个 bit 位，然后根据 shift 的值执行无符号右移操作(第 7 行代码)，如下图：

图 2：

  接着根据第 7 行代码与 0x3 执行与操作，如下图：

图 3：

  从上面的解码过程可以看出，这种编码方式可以实现随机访问功能。

在 Lucene 中的应用

  在 DocValues 中，有着广泛的应用，例如在 SortDocValue 中，用来存放 ordMap[]数组的元素值，ordMap[]的概念会在后面介绍 SortedDocValuesWriter 类时候介绍。

结语

  本篇博客介绍了使用 BulkOperationPacked 类实现对整数(long 或者 int)进行压缩存储，与去重编码相比，优点在于在解码时性能更高，并且能实现随机访问，在去重编码中，由于使用了差值存储，所以做不到随机访问。缺点在于当数据中出现较大的值时，压缩比就不如去重编码了。