点击查看【processon】
    目前以 4字节 的int整数分析,它的总位数为 32位,可以拆分成 2^16 * 2^16,所以我们对它分成两个部分:

    1. 通过对PostingList每个值除以65535,获取整除个数N
    2. 通过对PostingList每个值对65535取余,获取余数R

      取这个整数的高16就是 可以被整除的个数,取这个整数的低16位就是 余数

    然后将整除个数作为Key,形成一个Map<N, Container<R>>的集合。

    这里的N为short类型,这里的R也为short类型

    这里的Container是一个容器,它有三种类型:

    1. ArrayContainer:直接保存余数R,没有花里胡哨的操作。
    2. BitmapContainer:同过 65535个Bit位来保存是否存在某一个值,比如下标为 64230 的Bit位为 1,那么说明 64230 这个Bit位存在
    3. RunContainer:如果余数都是连续的,比如直接是 1,2,3,4...3000 这样一串连续的值,那么RunContainer就会保存两个数——一个是1,一个是3000。共占用2个Short整型。

    image.png
    红色线是ArrayContainer,蓝色线是BitmapContainer。Y轴是内存使用,X轴是节点数量。
    我们可以看到,如果使用ArrayContainer,那么随着节点数量越来越多,占用的空间越来越多(因为每个数据都是Short类型,占用2个字节。如果有4096个数据,那么就会占用 4096 * 2Byte = 8KB),最大占用128KB内存。如果使用BitmapContainer,只要节点数量再65535以内,那么都只占用8KB的内存。