手机网站建设流程网上做广告推广

B-tree

目前支撑着数据库产业的半壁江山。

50 年来不变而且人们还没有改变它的意向

鉴定一个算法的优劣，有一个学派叫 IO复杂度分析 ，简单推演真假便知。

下面就用此法分析下 B-tree(traditional b-tree) 的 IO 复杂度，对读、写 IO 一目了然，真正明白读为什么快，写为什么慢，如何优化。

为了可以愉快的阅读，本文不会做任何公式推导，复杂度分析怎么可能没有公式呢！

读IO分析

这里有一个 3-level 的 B-tree，每个方块代表一个 page，数字代表 page ID。

上图 B-tree 结构是 内存 的一个表现形式，如果我们要读取的记录在 leaf-8上，read-path 如蓝色箭头所示:

root-9 –> branch-6 –> leaf-8 根-9 ->分支-6 ->叶-8

下图是 B-tree 在 磁盘 上的存储形式，meta page 是起点:

这样读取的随机 IO (假设内存里没有 page 缓存且 page 存储是随机的)总数就是(蓝色箭头):

1(meta-10)IO + 1(root-9)IO + 1(branch-6)IO + 1(leaf-8)IO = 4次 IO，这里忽略一直缓存的 meta 和 root，就是 2  次随机 IO。

如果磁盘 seek 是 1ms，读取延迟就是 2ms 。

通过推演就会发现，B-tree 是一种读优化(Read-Optimized)的数据结构，无论 LSM-tree 还是 Fractal-tree 等在读上只能比它慢，因为读放大(Read Amplification)问题。

存储引擎算法可谓日新月异，但是大部分都是在跟写优化(Write-Optimized)做斗争，那怕是一个常数项的优化那就是突破，自从 Fractal-tree 突破后再无来者了！

写IO分析

现在写一条记录到 leaf-8。

可以发现，每次写都需要先读取一遍，如上图蓝色路径所示。

假设这次写入导致 root, branch 都发生了变化，这种 in-place 的更新反映到磁盘上就是：

基本是 2  次读 IO和写 2  次写 IO+WAL fsync，粗略为 4  次随机 IO。

通过分析发现，B-tree 对写操作不太友好，随机 IO 次数较多，而且 in-place 更新必须增加一个 page 级的 WAL 保证失败回滚，简直是要命。

Write-Optimized B-tree 写优化B树

说到写优化，在机械盘的年代，大家的方向基本是把随机 IO 转换为顺序 IO，充分发挥磁盘的机械优势，于是出现一种 Append-only B-tree：

更新生成新的 page(蓝色)

page 回写磁盘时 append only 到文件末尾

无需 page WAL，数据不 overwrite，有写放大(Write Amplification)问题，需要做空洞重利用机制

Append-only B-tree 节省了回写时的 2 次随机 IO，转换为常数级(constant)的1次顺序 IO，写性能大幅提升，总结起来就是：

随机变顺序，空间换时间

LSM-tree, Fractal-tree 等写优化算法的核心思想也是这个，只不过其实现机制不同。

LSM-trees lsm树

随着 LevelDB 的问世，LSM-tree 逐渐被大家所熟知。

LSM-tree 更像一种思想，模糊了 B-tree 里 tree 的严肃性，通过文件组织成一个更加松散的 tree。

rockdb应用：

写入

先写入内存的 C0

后台线程根据规则(Leveled/Sized)进行 merge，C0 –> C1, C1 –> C2 … CL

写入 C0 即可返回，IO 放到后台的 Merge 过程

每次 Merge 是硬伤，动作大就抖，动作小性能不好，每次 Merge 的数据流向不明确

写放大问题

读取

读取 C0

读取 C1 .. CL 读取 C1 . CL

合并记录返回

读放大问题

Fractal-tree 分形树

终于发展到了“终极”优化(目前最先进的索引算法，本篇文章参考的是T okuDB 的 Contributor的文章，可能有点武断，个人想法没有最好的算法，只有最适合的算法，有时遍历也是最好的方案 )，Fractal-tree。

它是在 Append-only B-tree 的基础上，对每个 branch 节点增加了一个 message buffer 作为缓冲，可以看做是 LSM-tree 和 Append-only B-tree 完美合体。

相对于 LSM-tree 它的优势非常明显:

Merge 更加有序，数据流向非常分明，消除了 Merge 的抖动问题，大家一直寻找的 compaction 防抖方案一直存在的！

这个高科技目前只有 TokuDB  在使用，这个算法可以开篇新介，这里不做累述，感兴趣的可以参考原型实现 nessDB 。