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