做瞹瞹小视频网站,河南建筑材料信息网,有什么网站专做买生活污水设备,做网站作品是静态B-tree
目前支撑着数据库产业的半壁江山。
50 年来不变而且人们还没有改变它的意向
鉴定一个算法的优劣#xff0c;有一个学派叫 IO复杂度分析 #xff0c;简单推演真假便知。
下面就用此法分析下 B-tree(traditional b-tree) 的 IO 复杂度#xff0c;对读、写 IO 一目了…
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 次写 IOWAL 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)进行 mergeC0 – 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 。
