从名称可以看出，DirectMonotonicWriter 这个类主要是针对单调递增或者递减（即有序）数据集的编码。本文将结合源码分析其编码原理。

无序数组压缩

在 Lucene 中，有很多地方都需要存储无序整型序列，如数值型 DocValues 的值、ords 等等。对于这种类型的序列值如何才能做到较好的压缩编码呢？最简单的做法就是减去序列中的最小值，缩小值域范围，比如下面一组值：[35, 40, 30, 45]，值域范围[30, 45]，采用 DirectWriter 编码，bitPerValue 为 8 ；减去最小值后为 [5, 10, 0, 15]，值域为[0, 15]，bitPerValue 为 4，因此相比原始数据可以减少一半的存储开销。

那还能不能取得更进一步的压缩率呢？答案是有的。我们观察上面差值后的数据集，发现它们都能被 5 整除，即最大公约数（gcd）为 5，因此可以再将上述数据集中的数除以 5 得到 [1, 2, 0, 3]。很明显，数据集的范围降低了数倍，此时 bitPerValue 为 2，相比原始数据，可以有 4 倍的压缩比。

综上，对于无序数据集的压缩方式可以命名为差值&最大公约数压缩。bitPerValue 的计算方式为 (max -min)/gcd。

有序数组压缩

上一节讲了无序数据集编码原理，那么对于有序数据集是否可以采用同样的编码方式来达到最佳的编码效果呢？假如有如下数据集 [0, 2, 5, 7, 8]，要达到压缩的效果就是要缩小数据集的值域，对于有序数组，很容易想到可以直接求相邻元数的差值得到 [0, 2, 3, 2, 1]，完了以后再将该数据集按照无序数组的压缩方式压缩即可。

假如有数组 [0, 100, 300, 700, 801]，它们的差值为 [0, 100, 200, 400, 101]，最大差值为 400 依旧较大，bitPerValue 得取 12，范围压缩不够明显。那有没有更好的办法将数组的值域变得更小呢？这就是 DirectMonotonicWriter 需要解决的问题，我们结合源码来看看 DirectMonotonicWriter 是怎么做的。

  private void flush() throws IOException {
    assert bufferSize != 0;

    // 求 avgInc
    final float avgInc =
        (float) ((double) (buffer[bufferSize - 1] - buffer[0]) / Math.max(1, bufferSize - 1));
    // 按位置减去 i*avgInc
    for (int i = 0; i < bufferSize; ++i) {
      final long expected = (long) (avgInc * (long) i);
      buffer[i] -= expected;
    }

    long min = buffer[0];
    for (int i = 1; i < bufferSize; ++i) {
      min = Math.min(buffer[i], min);
    }

    long maxDelta = 0;
    // 减去最小值
    for (int i = 0; i < bufferSize; ++i) {
      buffer[i] -= min;
      // use | will change nothing when it comes to computing required bits
      // but has the benefit of working fine with negative values too
      // (in case of overflow)
      maxDelta |= buffer[i];
    }

    meta.writeLong(min);
    meta.writeInt(Float.floatToIntBits(avgInc));
    meta.writeLong(data.getFilePointer() - baseDataPointer);
    if (maxDelta == 0) {
      meta.writeByte((byte) 0);
    } else {
      final int bitsRequired = DirectWriter.unsignedBitsRequired(maxDelta);
      DirectWriter writer = DirectWriter.getInstance(data, bufferSize, bitsRequired);
      for (int i = 0; i < bufferSize; ++i) {
        writer.add(buffer[i]);
      }
      writer.finish();
      meta.writeByte((byte) bitsRequired);
    }
    bufferSize = 0;
  }

我们主要关注前面几步，第一步算出数组的平均增长值 avgInc，第二步根据元素所处位置减去 iavgInc。还是以上面的数组 [0, 100, 300, 700, 801] 为例，算出 avgInc = (801-0)/(5-1) = 200，各元数减去 iavgInc 后得到差值数组 [0, -100, -100, 100, 1]；第三步差值数组减去最小值（当前最小值 -100）得到数组 [100, 0, 0, 200, 101]，最大差值（maxDelta）为 200，bitsRequired 为 8。

DirectMonotonicWriter 尽可能让处理后的数组最大元数更小，从而减小编码所需位数。

总结

本文结合例子讲解了无序数组和有序数组的编码原理 ，并着重通过源码讲解了 DirectMonotonicWriter 如何对有序数组进行编码。总的来说，编码方式很容易理解，在 lucene 中多处地方会用到本文讲的编码算法，后面涉及相关内容时会更容易理解。