知识卡片
B*树用高键和右兄弟指针,解决恢复原子性与并发热点问题
PostgreSQL/Greenplum用的B+树不是教科书里最简单的版本,而是加了 两个额外结构(双向指向左右兄弟节点的指针、每个节点里记录本节点 最大键值的”高键”)的变体(Blink树,书中称为B*树),这两个结构 分别是为了解决两个具体的工程问题。第一个问题是故障恢复的原子性: B+树插入或删除数据时,叶子节点或非叶子节点可能会分裂,而分裂 往往不只改动本页,还会牵连相邻节点甚至父节点,这些改动必须 被当作一个整体来恢复——如果数据库在分裂过程中崩溃,而预写式 日志(WAL)只记录了分裂涉及的一部分页面,恢复时就会出现不一致。 高键和右兄弟指针的引入,让分裂操作可以被拆解成一系列更小、 各自独立可恢复的原子步骤,而不必要求”整个分裂”必须被当成一个 不可分割的大动作来记录和恢复。第二个问题是高并发下的热点竞争: 普通B+树无论读还是写都得从根节点逐层往下加锁再释放,读的时候 要一路加访问共享锁,写的时候要一路加排他锁,节点越靠近根、 被并发路径经过的次数就越多,锁竞争自然集中在这些”热点”节点上。 B*树换了一种”从左到右、从底向上”的加锁策略:查询下沉时只加 共享锁,找到叶子节点才加排他锁;如果确实要分裂,就向右侧分裂、 对新节点加排他锁完成插入,再回头去给父节点加锁增加索引项—— 这套顺序既减少了逐层加锁造成的竞争,也顺带避免了传统”自顶向下 锁全程占用”策略容易引发的死锁。两个改动看似只是多加了两个 指针字段,实际分别对应”如何把大操作拆成可恢复的小步骤”和 “如何把加锁范围从整条路径压缩到局部”这两个完全不同性质的问题。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《深入浅出Greenplum分布式数据库:原理、架构和代码分析》
第3章"并发控制"3.10节"B*树和LSM树"(源文件:
_epub-src/EPUB/xhtml/chapter8.xhtml)
- 结论依据:原文明确"B*树和B+树的区别在于,B*树使用双向指针
指向节点的左右兄弟节点,并在叶子节点和非叶子节点上引入了
高键……第一,在数据库里使用B+树进行索引,需要有故障恢复的
功能……这样的改变必须按照原子操作来实现……第二,B*树增加了
B+树的并发能力……B*树使用'从左到右,从底向上'的加锁策略……
这样的策略能提高并发效率,也能避免死锁发生",分别对应故障
恢复原子性与并发热点这两个动机。
- 原始内容:B*树增加了B+树的并发能力。如果没有B*树的高键,
对值进行查找的工作效率比较低下;如果没有B*树指向兄弟节点
(右节点)指针的功能,在加锁、解锁方面效率会很低下,并发
能力不高……B*树使用"从左到右,从底向上"的加锁策略。