“写优化”的数据结构(2)：buffered tree

这一小节谈谈buffered tree吧。
buffered tree有几种设计方法吧。

一种是buffered b-tree，就是整个tree的结构还是类b-tree的，包括节点分裂都一样，每个pivot都有一个子节点，但是与b-tree的区别就是写的时候，先写到root节点，然后根据节点的饱和度进行往下刷数据操作。数据的表现行为完全不一样。
这个很像数据在一个“外力”的作用下，不停的被往下推，直到叶节点。

另一种就是类似 2–3 tree(http://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下。
其实还有一些比较好玩的“写优化“数据结构

“写优化”的数据结构(3)
http://www.douban.com/note/269750379/

BohuTANG @2013.4