postgresql -- 索引Blink-Tree并发原理

driftingman

221人浏览 · 2026-07-12 21:09:24

driftingman · 2026-07-12 21:09:24 发布

B-Tree作为一种低扇入、高扇出的数据结构，在很长一段时间内都是磁盘数据库实现索引的首选数据结构，即使到了现代，B-Tree也是实现数据库索引的最常用结构之一。

PostgreSQL在实现索引的时候并没有采用B-Tree或者B+Tree，而是采样并发度更好的Blink-Tree。

B树用阶（order）定义
Every node has at most m children.
Every non-leaf node (except root) has at least ⌈m/2⌉ child nodes.
The root has at least two children if it is not a leaf node.
A non-leaf node with k children contains k − 1 keys.
All leaves appear in the same level and carry no information.
B树除叶子和跟节点，其余节点的孩子数在[ceil(m / 2), m]之间。
所有节点都保存key，叶子节点存在并且也会保存key。
B树要求每个节点至少半满（算法导论：bstar-tree要求2/3满）。
有n棵子树的结点中含有n-1个key。
注意：n阶B树主要限制了孩子的数量，key的数量通过第五条来限制，例如5阶B树某个节点最多有5个孩子，那么该节点只能保存4个key

https://en.wikipedia.org/wiki/B-tree

3阶B树的生长过程：A B Tree insertion example with each iteration. The nodes of this B tree have at most 3 children .

B树高度
高度等于=log┌m┐(N+1/2)

N：B树中key的数量。
m：阶，表示每个节点至少有m/2个孩子，至多有m个孩子。
树的阶越高，每层存的key数量越多，树的高度约低。

m阶B+树在B树基础上增加要求：

所有非叶子节点都是索引，不保存数据，只保存每个孩子节点的最大值或最小值。
所有叶子节点保存全部key，并形成linkedlist。
B+的优点：

非叶子不保存数据，可以保存大量索引数据，只需要IO叶子，IO次数降低。
遍历、区间查询效率大幅度提高。
查询稳定，每次查询经历的节点树相同。

B*-tree

m阶B*树在B+树的基础上增加要求：

~~非根和非叶子结点增加指向兄弟的指针。~~（这是B-linked-tree）
非叶子结点关键字个数至少为floor ((2m-1)/3)，即块的最低使用率为2/3（代替B+树的1/2）。

B* 树平衡更多相邻的内部节点，以保持内部节点更密集。

【优点】[2]此变体确保非根节点至少 2/3 满而不是 1/2。 [13]由于在 B-tree 中插入节点的操作成本最高的部分是拆分节点，因此创建 B*-trees 以尽可能推迟拆分操作。 [14]为了保持这一点，不是在节点满时立即拆分节点，而是与旁边的节点共享key（把自己的key挪到右兄弟）。这种溢出操作比拆分成本更低，因为它只需要在现有节点之间移动键，而不是为新节点分配内存。
【未满】 [14]对于插入，首先检查节点中是否有一些空闲空间，如果有，则将新key插入节点中。但是，如果节点已满（它有 m - 1 个键，其中 m 是树的order（阶），作为从一个节点指向子树的最大指针数，就是最大孩子数），则需要检查右兄弟是否存在并且有一些空闲空间。
【满了】如果右兄弟节点有 j < m - 1 个键，则键在两个兄弟节点之间尽可能均匀地重新分配。为此，来自当前节点的 m - 1 个键、插入的新键、来自父节点的一个键和来自兄弟节点的 j 个键被视为 m + j + 1 个键的有序数组。数组被分成两半，因此 ⌊(m + j + 1)/2⌋ 最低的键留在当前节点中，下一个（中间）键插入父节点，其余的进入右兄弟节点。 [14 ] （新插入的key可能最终出现在三个位置中的任何一个。）右兄弟已满而左兄弟未满的情况类似。 [14]当两个兄弟节点都已满时，这两个节点（当前节点和一个兄弟节点）被分成三个，另外一个键沿树向上移动到父节点。 [14]如果父节点已满，则溢出/拆分操作向根节点传播。 [14]然而，删除节点比插入要复杂一些。
B* 和 B+相比更饱满了：
B+树分裂、B*树分裂

B+树的分裂
当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。

B*树的分裂
（总结一）使用 B* 树优于 B+称为“二到三”拆分，拆分后每个节点中的最小key数不是1/2（B+），而是2/3，使数据更加紧凑。缺点是删除操作复杂。
（总结二）当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。
所以，B*树分配新结点的概率比B+树要低，空间使用率更高。

情况一：当前节点满了，右sibling满了

节点{1,2,4}、节点{7,8,9}都已经满了。现在需要插入5。

将{1,2,4}, 5 , {6}, {7,8,9}进行排序
新建三个新的node：p、q、r
p：前(2m – 2)/3个的key保存在p中， (2m – 2)/3位置的key保存在parent1中
q：接着(2m – 1)/3个key保存在q中，(2m – 1)/3位置的key保存在parent2中
r：剩下(2m)/3个key保存在r中
p、q的parent指针更新为parent1，r的parent指针更新为parent2
parent中新增parent2
parent1、parent2维护child指针指向p、q、r

情况二：当前节点满了，右sibling有空间

节点{1,2,4}、节点{7,8}都已经满了。现在需要插入3。

将当前节点的最后一个元素移动到父节点。
将右兄弟节点中的所有键向右移动，并插入前一个父节点。
将3插入当前节点合适的位置。

Blink-Tree的结构

在B*的基础上增加了指向右兄弟。

增加link pointer的目的：提供到达节点的另一种方法。当一个节点因为数据溢出被分裂时，单个节点被两个新的节点&替换。第一个新节点的链接指针指向第二个节点；第二个节点的链接指针包含第一个节点的链接指针字段的旧内容。通常新旧节点在磁盘上占用相同的物理页面。
该方案的目的：两个节点因为它们通过链接指针连接，在功能上基本上与单个节点相同，直到可以添加来自其父节点的正确指针。
新增的指针可以在分裂的时候添加，这是他的优点。因此，链接指针可以充当对btree的临时修复，允许正确的并发操作，甚至在所有常用树指针都更改为新（拆分）节点之前。如果搜索关键字超过了节点中的最大值（如高关键字所示），则表明树结构已更改，应使用链接指针访问孪生节点。虽然这效率稍低（我们需要执行额外的磁盘读取以跟随链接指针），但它仍然是到达叶节点的正确方法。链接指针应该相对不经常使用，因为节点的分裂是一种例外情况。

Blink-Tree 查询

为了在树中搜索值 u，搜索过程从根开始，然后通过将 u 与树下路径中每个节点中的值进行比较来进行。在每个节点中，比较产生一个从该节点跟随的指针，到下一级或叶（记录）节点。

如果搜索过程检查一个节点并发现该节点给出的最大值小于 u，那么它推断在当前节点中发生了一些变化（父节点不知道）。当前节点一定已经拆分了，拆分为两个（或更多）新节点。搜索必须通过遵循新拆分节点的链接指针而不是像通常那样搜索子指针来纠正其在树中位置的错误。

差异点：如果扫描过程中，根据父节点的指针拿到一个子节点，然后发现当前节点的high_key<u，说明这个节点已经分裂过了，但是没有维护父指针，这时候需要沿着链接指针找到右兄弟继续查询。这就是B-linked-tree上面定义中提到的功能，分裂时可以延迟维护父指针。直到扫描到了在维护。

Blink-Tree 插入

要在树中插入一个值 u，需要执行搜索操作。从根开始向下扫描树到应该包含值 u 的叶节点。我们还跟踪在树的递归过程中每个级别检查的最右边的节点。通过树的这种下降搜索拿到 u 的适当位置（例如，节点 a）。

将值 u 插入叶节点可能需要拆分节点（在不安全的情况下）。在这种情况下，我们拆分节点（如图 8 所示），将节点 a 替换为节点 a’（写入同一磁盘页面的 a 的新版本）和 b’。节点 a’ 和 b’ 与 a 具有相同的内容，但增加了值 u。

然后我们继续返回树（使用我们搜索过的“记忆”节点列表）在叶节点的父节点中插入新节点 (b’) 和 a’ 的新HIGHKEY的条目。

该节点也可能需要拆分。如果是这样，我们回溯树，分裂节点并将新指针插入它们的父节点，当我们到达一个不需要分裂的安全节点时停止。在所有情况下，我们都会在修改节点之前锁定它。

为了提高B-Tree的并发性，在B-Tree的非叶子引入了左右向指针，除了叶子节点是双向链表之外，中间节点也是双向链表，这便是link的含义。

在页面引入high key用于表示页面存储元组的最大值，这样在查找时如果待查找的数据大于页面的high key，那么可以直接跳过该页面。

因此Blink-Tree的两大特点：

内部节点也有前后向指针，也是双向链表；
high key机制标识页面的最大值，最右节点没有high key。

关于high key的取值，PostgreSQL中有一条规定“一个节点的high key必须等于其右节点的最小值”，这是PostgreSQL的铁律，索引相关的操作都需要遵守这个规则。

传统B-Tree的加锁方式叫蟹行协议（carbbing step），加锁放锁成对出现，B-Tree加锁流程如下：

给当前节点加锁；
给下级节点加锁，释放当前节点的锁；
重复步骤1、步骤2，直到叶子节点。

可见，蟹行协议在加锁时是按照加当前锁->拿下级锁->放当前锁的形式来的，也就是说任何时候，至少持一把锁。

蟹行协议加锁方式在SMO（Structure Modification Operation结构修改操作），即页面发生分裂时很容易引起死锁。

比如：进程1执行查询时拿了上级页面锁而加下级页面锁；而进程2在插入数据后触发页面分裂，导致拿下级锁而加上级锁，如此便会死锁。

图2 蟹行协议引起死锁(图片来自网络)

当然这并不是B-Tree索引就无法使用了，事实上MySQL也使用了B-Tree来构建索引的，幸运的是SMO只会发生在索引的插入、合并操作中，而且并不是所有的插入、合并都会触发SMO。因此MySQL在插入时对于拿到锁的每个页面，首先做一个预判，假如插入不会引起分裂，即不需要向上加锁，说明安全，可以继续向下加锁；否则说明会触发SMO，需要从根节点开始加写锁一直到叶子节点。

正是这种SMO，导致了MySQL在大数据量场景下并发不及PostgreSQL。