610
“寫優化”的數據結構(2)：buffered tree
作者：一工
這一小節談談buffered tree吧。
buffered tree有幾種設計方法吧。
一種是buffered b-tree，就是整個tree的結構還是類b-tree的，包括節點分裂都一樣，每個pivot都有一個子節點，但是與b-tree的區別就是寫的時候，先寫到root節點，然後根據節點的飽和度進行往下刷數據操作。數據的表現行為完全不一樣。
這個很像數據在一個“外力”的作用下，不停的被往下推，直到葉節點。
另一種就是類似 2–3 tree(https://en.wikipedia.org/wiki/2%E2%80%933_tree)的數據結構，不過這裏不是2或者3，而是一個更大的數字，比如 10–16 tree，就是每個節點不是每個pivot有一個子節點，而是每個節點最多16個子節點，最少10個，如果大於16就分裂，小於10就合並。
這裏不談buffered b-tree 或 10–16 tree的具體設計，而是從工程的角度來簡單講講buffered tree。
write
——-
1) 數據寫的時候不會產生disk seek，因為一條記錄總是先被寫到root節點，由於經常被操作，可認為總在page cache裏，root的子節點們也基本在page cache裏，這樣緩存的管理可以讓linux kernel來做。但是最熱的節點總是在page cache裏，從而大大減少disk seek。
2) 如果給幾十MB內存，那更爽了！最新操作的節點都放這幾十MB內存裏，後台線程並行的把這些節點刷到磁盤。
3) 同一節點裏的數據基本都算“緊湊”的，leaf節點的數據更“緊湊”，4MB的節點壓縮起來也很占優勢。
4) 如果想做事務，一個row的記錄在buffered tree裏有可能打散的。事務的樣子基本是<key, txid, val…, uncommit>，跟插入一條普通的記錄沒什麼區別，隻是這條message有些額外的信息來標識這是個事務，是否提交。沒有row的概念，更沒有row locking。
當一條沒有提交的事務message被刷到leaf的時候，就可以玩玩MVCC。
在buffered tree裏做事務，會有天然優勢。
read
——
對於一個4MB的node，如果查詢一條記錄，總不能都讀吧？所以這個大node裏還可以分段，比如每256KB記一個pivot，當然這裏的技巧很多，發揮的餘地也很大。
要想磁盤寫的快，數據結構要設計成：寫是lazy式的，偶爾批量flush下。
其實還有一些比較好玩的“寫優化“數據結構。
最後更新：2017-04-03 07:57:05