“写优化”的数据结构(1)：AOF和b-tree之间

这里谈的“写优化”，是针对HDD(hard disk drive)的，宗旨就是尽量避免disk seek的产生。
首先拿AOF(Append Only File)和b-tree两个“端”谈起。

1) AOF
无论是随机写还是顺序写，在AOF里是没有什么区别，也是最快的。如果搞个坐标图，它的“江湖”地位就是:


                
                

它几乎没有disk seek，但随机读是不可接受的！

2) b-tree
各大存储引擎御用的数据结构，但这里要说的是：它有缺陷，算不上“写优化“的。
假设b-tree的每个node大小为16KB，数据文件大小为160GB，总共会有100万个node。
在随机写的过程中，新node的生成过程就是个布朗运动（一个node的child node在文件里是离散的，可能在它附近，也可能很远），产生了大量的disk seek，此时的page cache利用率也不高。这就是它的一个缺陷。
但是随机读是比较快的(复杂度是O(logN))（即使是100万个node,如果分支因子是1000，一次随机读最多2次disk seek）。
b-tree的江湖地位是：


                
                

从图(2)可以看出，b-tree和AOF占据两个“端”，存在不存在一种数据结构，是二者的合体呢？这样就完美了，可惜是没有 :D，不过可以在这两者之间做平衡。


                
                

图(3)中的蓝色线，就是“随机写”和“随机读“两者做trade off后的一个曲线图，在这条曲线上，有levelDB使用的LSM-Tree，也有Acunu使用的basic-COLA(https://acunu-videos.s3.amazonaws.com/dajs.html) 。
其中红色箭头所指的地方是个“风水宝地”，在这里，随机写和读都还不错，从I/O复杂度上来讲，这里的读接近O(logN)，写则是O(logN / x)，x是个常数项(写优化的数据结构其实就是在b-tree身上做常数项优化)。

接下来要介绍的就是这个“风水宝地”里的一种数据结构：buffered tree(搞这个比较出名的该属Lars Arge, http://www.madalgo.au.dk/~large/ )。
这种数据结构在写的时候，与b-tree最大的区别就是：不会从root查找，找到正确的node再插入，没有root-to-leaf的查找过程。
而是直接插到root节点，如果root节点满了，就把数据刷到它的子节点，如果某个子节点满了，就继续刷到子子节点，一直重复下去。只有当节点满的时候，才有disk seek产生。
且node大小可以设置很大，比如4MB，这样4MB才可能产生一次disk seek，已经很不错了。
如果一个node设置很大，为提高读，就需要对这个node做更细的划分，分成多个小块，随机读I/O复杂度也是O(logN)。

“写优化“的数据结构很多，就是在那条蓝色曲线上躺着很多种数据结构，但是buffered tree是比较出色的。
下一小节会简单谈谈buffered tree ... ...

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

BohuTANG @2013.4