sjjt-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。而且,在遍历过程也不象固定区块方案那样需要处理标记,只是连续地从分段起始位置读到结束位置就可以,动作非常简单。

 

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

润乾科技 暂无个人签名

加关注
喜欢 | 0

登陆后发表文章

  • 0条回应给“【数据蒋堂】第40期:倍增分段技术”的评论