区块分段方案能够满足我们设定的4个目标。不过,除了处理区块标记的麻烦外,这个办法对于列存也不是非常适合。
创新互联公司专业为企业提供海阳网站建设、海阳做网站、海阳网站设计、海阳网站制作等企业网站建设、网页设计与制作、海阳企业网站模板建站服务,10多年海阳做网站经验,不只是建网站,更提供有价值的思路和整体网络服务。
数据按列分别存储后,分段时必须保证各列同步,即各列的分段点对应的是同一条记录的列,否则就会出错数据错位。而各个列的宽度是不同的,同样大小的区块在存储不同列的值时,能装下的个数是不同的,继续按区块分段就无法保证同步了。
各列要同步分段,就需要按记录数分段,但这样就不能采用固定大小的区块了,而要有个区块索引。如果数据不再追加,那可以建立固定长度的索引,但数据不断追加时,索引也会动态增长。这时候,要么每次追加数据时把所有数据重写一遍保证索引的连续性,要么用有某种复杂机制能处理不连续的索引,都是成本不低的手段。
当前业界常用的列存分段也就是分块方案:把数据分成若干块,块内是列存,分段以块为单位。分块数要足够多才能保证平均分段,而分块又要足够大才能让列存产生效果,这两者就是个矛盾,要数据量很大时才合适。而且,这个分块是按记录数划分的,不能固定大小,就需要我们上面说的分块索引,当数据不断追加时,索引也会动态变大,连续性就无法保证了。
为解决这些问题,我们再设计一种倍增分段方案。
预留一个固定长度的索引区,可以保存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。而且,在遍历过程也不象固定区块方案那样需要处理标记,只是连续地从分段起始位置读到结束位置就可以,动作非常简单。
倍增分段方案是以记录数为基础的,所以对于列存也是适合的。各个列都采用这种方式追加数据后,分段点对于各列总是落在同一条记录上,不会发生错位的情况,而且,每个列的数据都是一直连续的,没有中断点,不象分块式方式在只能在分块内连续,也不会面对分块大小与数量的矛盾。