【數(shù)據(jù)蔣堂】第40期：倍增分段技術

區(qū)塊分段方案能夠滿足我們設定的4個目標。不過，除了處理區(qū)塊標記的麻煩外，這個辦法對于列存也不是非常適合。

數(shù)據(jù)按列分別存儲后，分段時必須保證各列同步，即各列的分段點對應的是同一條記錄的列，否則就會出錯數(shù)據(jù)錯位。而各個列的寬度是不同的，同樣大小的區(qū)塊在存儲不同列的值時，能裝下的個數(shù)是不同的，繼續(xù)按區(qū)塊分段就無法保證同步了。

各列要同步分段，就需要按記錄數(shù)分段，但這樣就不能采用固定大小的區(qū)塊了，而要有個區(qū)塊索引。如果數(shù)據(jù)不再追加，那可以建立固定長度的索引，但數(shù)據(jù)不斷追加時，索引也會動態(tài)增長。這時候，要么每次追加數(shù)據(jù)時把所有數(shù)據(jù)重寫一遍保證索引的連續(xù)性，要么用有某種復雜機制能處理不連續(xù)的索引，都是成本不低的手段。

當前業(yè)界常用的列存分段也就是分塊方案：把數(shù)據(jù)分成若干塊，塊內(nèi)是列存，分段以塊為單位。分塊數(shù)要足夠多才能保證平均分段，而分塊又要足夠大才能讓列存產(chǎn)生效果，這兩者就是個矛盾，要數(shù)據(jù)量很大時才合適。而且，這個分塊是按記錄數(shù)劃分的，不能固定大小，就需要我們上面說的分塊索引，當數(shù)據(jù)不斷追加時，索引也會動態(tài)變大，連續(xù)性就無法保證了。

為解決這些問題，我們再設計一種倍增分段方案。

預留一個固定長度的索引區(qū)，可以保存N個位置信息，N是個固定的數(shù)，比如是1024。我們用索引區(qū)i號位表示其中保存的第i個位置。

初始狀態(tài)時沒有記錄。加入第1條記錄后，在索引區(qū)1號位填入該記錄（稱為記錄1）寫入存儲（比如文件）時的位置；加入第2條記錄后，在索引區(qū)2號位填入記錄2的位置，…；加入第N條記錄后，在索引區(qū)位置N填入記錄N的位置 。

索引區(qū)的i號位可以看成是一個區(qū)塊，對應由i號位內(nèi)容指向的那條記錄起到第i+1號位內(nèi)容指向的記錄之間的所有記錄（含頭不含尾）。在這一輪追加葉，相當于每個分段中只有一條記錄。

再繼續(xù)追加記錄時，索引區(qū)已經(jīng)沒有空位了。這時我們做這樣一個操作：1號位保留，2號位填入原3號數(shù)的內(nèi)容，3號位填入原5號位的內(nèi)容，…，i號位填入原2i-1號位的內(nèi)容。這樣一直到在N/2號位填入原2*N/2-1即N-1號位的信息，然后再把第N/2+1到N號位的內(nèi)容清空。

這個操作，相當于把區(qū)塊1和區(qū)塊2合并成區(qū)塊1，區(qū)塊3和區(qū)塊4合并成區(qū)塊2，..區(qū)塊2i-1和區(qū)塊2i合并成區(qū)塊i，這些區(qū)塊就變成由2條記錄構成，數(shù)據(jù)記錄本來就是連續(xù)寫入的，這樣合并后的區(qū)塊仍然是由連續(xù)記錄構成。

然后，清空的后半部分號位相當于空出一些空區(qū)塊了，如果繼續(xù)追加記錄時，就每次寫2條記錄才使用下一個號位，即把記錄N+1的位置填入N/2+1號位，記錄N+2繼續(xù)寫入，記錄N+3的位置填入N/2+2號位，記錄N+4繼續(xù)寫入，…。

再追加下去填滿所有號位后，再次做合并動作，把每區(qū)塊記錄號再倍增成4條。同時空出后半部分號位，再追加數(shù)據(jù)時每個號位要增加4條記錄才使用下一個號位?！?，如此往復下去。

在這個機制下，任何時候都有N/2到N個可用區(qū)塊，只要N足夠大（1024基本上夠了），就可以做到平均程度較高的分段。每個分段由連續(xù)的區(qū)塊構成，區(qū)塊由連續(xù)緊湊的記錄構成，這樣能確保目標3，而上述的算法過程已經(jīng)解決了目標4。而且，在遍歷過程也不象固定區(qū)塊方案那樣需要處理標記，只是連續(xù)地從分段起始位置讀到結(jié)束位置就可以，動作非常簡單。

倍增分段方案是以記錄數(shù)為基礎的，所以對于列存也是適合的。各個列都采用這種方式追加數(shù)據(jù)后，分段點對于各列總是落在同一條記錄上，不會發(fā)生錯位的情況，而且，每個列的數(shù)據(jù)都是一直連續(xù)的，沒有中斷點，不象分塊式方式在只能在分塊內(nèi)連續(xù)，也不會面對分塊大小與數(shù)量的矛盾。