B-Tree作为一种低扇入、高扇出的数据结构在很长一段时间内都是磁盘数据库实现索引的首选数据结构即使到了现代B-Tree也是实现数据库索引的最常用结构之一。PostgreSQL在实现索引的时候并没有采用B-Tree或者BTree而是采样并发度更好的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个keyhttps://en.wikipedia.org/wiki/B-tree3阶B树的生长过程A B Tree insertion example with each iteration. The nodes of this B tree have at most 3 children .B树高度高度等于log┌m┐(N1/2)NB树中key的数量。m阶表示每个节点至少有m/2个孩子至多有m个孩子。树的阶越高每层存的key数量越多树的高度约低。m阶B树在B树基础上增加要求所有非叶子节点都是索引不保存数据只保存每个孩子节点的最大值或最小值。所有叶子节点保存全部key并形成linkedlist。B的优点非叶子不保存数据可以保存大量索引数据只需要IO叶子IO次数降低。遍历、区间查询效率大幅度提高。查询稳定每次查询经历的节点树相同。B*-treem阶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/2B而是2/3使数据更加紧凑。缺点是删除操作复杂。总结二当一个结点满时如果它的下一个兄弟结点未满那么将一部分数据移到兄弟结点中再在原结点插入关键字最后修改父结点中兄弟结点的关键字因为兄弟结点的关键字范围改变了如果兄弟也满了则在原结点与兄弟结点之间增加新结点并各复制1/3的数据到新结点最后在父结点增加新结点的指针。所以B*树分配新结点的概率比B树要低空间使用率更高。情况一当前节点满了右sibling满了节点{1,2,4}、节点{7,8,9}都已经满了。现在需要插入5。将{1,2,4}, 5 , {6}, {7,8,9}进行排序新建三个新的nodep、q、rp前(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指针更新为parent1r的parent指针更新为parent2parent中新增parent2parent1、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_keyu说明这个节点已经分裂过了但是没有维护父指针这时候需要沿着链接指针找到右兄弟继续查询。这就是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直到叶子节点。可见蟹行协议在加锁时是按照加当前锁-拿下级锁-放当前锁的形式来的也就是说任何时候至少持一把锁。蟹行协议加锁方式在SMOStructure Modification Operation结构修改操作即页面发生分裂时很容易引起死锁。比如进程1执行查询时拿了上级页面锁而加下级页面锁而进程2在插入数据后触发页面分裂导致拿下级锁而加上级锁如此便会死锁。图2 蟹行协议引起死锁(图片来自网络)当然这并不是B-Tree索引就无法使用了事实上MySQL也使用了B-Tree来构建索引的幸运的是SMO只会发生在索引的插入、合并操作中而且并不是所有的插入、合并都会触发SMO。因此MySQL在插入时对于拿到锁的每个页面首先做一个预判假如插入不会引起分裂即不需要向上加锁说明安全可以继续向下加锁否则说明会触发SMO需要从根节点开始加写锁一直到叶子节点。正是这种SMO导致了MySQL在大数据量场景下并发不及PostgreSQL。Blink-Tree的并发相比B-Tree的并发Blink-Tree的并发会高效些但也复杂Blink-Tree的加锁流程如下给当前节点加锁获取下级节点的页号释放当前节点的锁给下级节点加锁重复步骤1、步骤2直到叶子节点。可见Blink-Tree加锁流程和蟹行协议的区别在于步骤2即加下级锁时是否需要释放当前锁。蟹行协议拿的是下级页面的锁而Blink-Tree拿的是下级页面的页号。如此在Blink-Tree加锁过程中同一时刻只会持有一个页面锁这也就不会出现死锁。在PostgreSQL中加锁必须是从左往右顺序或者从上到下顺序否则可能会出现死锁。索引是数据库系统最重要也是最复杂的模块之一 简单介绍了PostgeSQL中索引与B-Tree的差异并明确了Blink-Tree的加锁机制和规则。