【数据蒋堂】第40期：倍增分段技术

区块分段方案能够满足我们设定的4个目标。不过，除了处理区块标记的麻烦外，这个办法对于列存也不是非常适合。

数据按列分别存储后，分段时必须保证各列同步，即各列的分段点对应的是同一条记录的列，否则就会出错数据错位。而各个列的宽度是不同的，同样大小的区块在存储不同列的值时，能装下的个数是不同的，继续按区块分段就无法保证同步了。

各列要同步分段，就需要按记录数分段，但这样就不能采用固定大小的区块了，而要有个区块索引。如果数据不再追加，那可以建立固定长度的索引，但数据不断追加时，索引也会动态增长。这时候，要么每次追加数据时把所有数据重写一遍保证索引的连续性，要么用有某种复杂机制能处理不连续的索引，都是成本不低的手段。

当前业界常用的列存分段也就是分块方案：把数据分成若干块，块内是列存，分段以块为单位。分块数要足够多才能保证平均分段，而分块又要足够大才能让列存产生效果，这两者就是个矛盾，要数据量很大时才合适。而且，这个分块是按记录数划分的，不能固定大小，就需要我们上面说的分块索引，当数据不断追加时，索引也会动态变大，连续性就无法保证了。

为解决这些问题，我们再设计一种倍增分段方案。

预留一个固定长度的索引区，可以保存N个位置信息，N是个固定的数，比如是1024。我们用索引区i号位表示其中保存的第i个位置。

初始状态时没有记录。加入第1条记录后，在索引区1号位填入该记录（称为记录1）写入存储（比如文件）时的位置；加入第2条记录后，在索引区2号位填入记录2的位置，…；加入第N条记录后，在索引区位置N填入记录N的位置 。

索引区的i号位可以看成是一个区块，对应由i号位内容指向的那条记录起到第i+1号位内容指向的记录之间的所有记录（含头不含尾）。在这一轮追加叶，相当于每个分段中只有一条记录。

再继续追加记录时，索引区已经没有空位了。这时我们做这样一个操作：1号位保留，2号位填入原3号数的内容，3号位填入原5号位的内容，…，i号位填入原2i-1号位的内容。这样一直到在N/2号位填入原2*N/2-1即N-1号位的信息，然后再把第N/2+1到N号位的内容清空。

这个操作，相当于把区块1和区块2合并成区块1，区块3和区块4合并成区块2，..区块2i-1和区块2i合并成区块i，这些区块就变成由2条记录构成，数据记录本来就是连续写入的，这样合并后的区块仍然是由连续记录构成。

然后，清空的后半部分号位相当于空出一些空区块了，如果继续追加记录时，就每次写2条记录才使用下一个号位，即把记录N+1的位置填入N/2+1号位，记录N+2继续写入，记录N+3的位置填入N/2+2号位，记录N+4继续写入，…。

再追加下去填满所有号位后，再次做合并动作，把每区块记录号再倍增成4条。同时空出后半部分号位，再追加数据时每个号位要增加4条记录才使用下一个号位。…，如此往复下去。

在这个机制下，任何时候都有N/2到N个可用区块，只要N足够大（1024基本上够了），就可以做到平均程度较高的分段。每个分段由连续的区块构成，区块由连续紧凑的记录构成，这样能确保目标3，而上述的算法过程已经解决了目标4。而且，在遍历过程也不象固定区块方案那样需要处理标记，只是连续地从分段起始位置读到结束位置就可以，动作非常简单。

倍增分段方案是以记录数为基础的，所以对于列存也是适合的。各个列都采用这种方式追加数据后，分段点对于各列总是落在同一条记录上，不会发生错位的情况，而且，每个列的数据都是一直连续的，没有中断点，不象分块式方式在只能在分块内连续，也不会面对分块大小与数量的矛盾。