从B树到B+树：姐妹节点丰富还是不丰富？

B+树的特点

B+树与B树一样，都是乘法平衡树，也称为多树。两者的属性基本相同。在看细节之前，我们先看一下B+树的特点，有个大概的印象。

个人认为B+树的大部分特征与B-树相同。唯一的区别是以下几点：

1. 所有数据都存储在叶子节点中，中间节点不存储数据
2. 中间节点的元素个数对应子树的个数，叶子节点中的子树个数B树比元素个数多1
3. 叶子节点是一个链表，可以通过指针顺序查找

我发个照片，大家应该能直观感受一下。

从上图中我们可以看到，所有出现在中间节点的元素都在叶子节点中找到，这对应了刚才提到的所有数据都存储在叶子节点中。那么我们还可以发现，中间节点的元素个数和子树的个数是一致的，这也对应了区间分布。父节点的每个元素对应于子树中的最大元素。

至于最终的链表，应该很容易理解。只是树形视图中出现了链表，看起来有点新奇。

看到上面的照片我最大的感受就是太像B树了。他们就像两个双胞胎兄弟。乍一看它们几乎一模一样。只有通过细致的分析，你才能发现细微的差别。那么对于这样一棵众所周知却又不为人知的树，我们该如何增删改查呢？

我们继续往下看。在此之前先说一下，尽管B+树是B树的改进版本，但实现难度实际上有所降低。也就是说，通常比 B 树 更容易实现 。

B+树搜索

由于B+树中的所有数据都存储在叶子节点中，所以搜索时我们必须一直搜索到叶子节点。也就是说，不会再出现中途停下来的情况，这简化了我们的判断，几乎不需要暂时停下来。

还有一个特点是B+树的元素个数与子树个数相同，每个元素代表一个子树的最大值。这个限制使我们能够轻松确定我们要查找的元素位于哪个子树中。 B 型繁荣可能会出界，我们需要特殊的判断。

举个例子，这是一棵B树：

假设我们要找的元素是12，我们在根节点求值，首先通过二分查找找到9，发现12>9，所以我们去到侧面子树之间最右边的检查。

如果是B+树，那就这样吧。为了便于绘制，我省略了叶节点中的水平指针。

可以看到，我们将其分为两部分，就能准确找到对应的子树。我们可以直接向下重复。如果越线了，就说明它肯定不在树上，你可以早点回来。

所以这是一个非常简单的树搜索。不得不说，只要了解了树的形状和递归思想，应该不难。然而，需要注意的一件事是，我们的搜索界面不仅仅提供给外界。插入的时候，我们还需要找到对应的位置（节点），然后再进行插入。显然我们要插入的元素可能不存在于树中（否则就称为插入）。这个时候我们不能空返回。我们需要返回一个真实的节点。

因此我们可以传递一个标志来指示这是否是我们内部调用的插入阶段。该标志默认设置为 False，因此对远程调用没有影响。

如果flag是真的，如果我们半路找不到，我们就不能早点离开，只能继续寻找。我们还可以更新最右边元素的值。

我们以上图为例：

如果我们插入元素15，整棵树就变成：

看，的根节点中的12被替换为15，这也是与之前所说的一致。节点中的每个元素对应于子树中的最大值。当然我们可以先插入父级然后更新它，但我们也可以在搜索过程中直接更新。当我们发现要插入的元素大于当前节点的最大元素时，我们可以直接替换它，这样可以节省时间。一个代码。

我们看一下代码：

def _query(self, node, key, flag=False):
"""
:param node: 当前节点
:param key: te find Key
:param flag: 是否是插入阶段
:return: True/False 是否找到对应的节点，key在节点中的下标
"""
# 如果是叶子节点，表示没有子节点
if node.is_leaf:
# 检查当前值是否为空
if node.length == 0:
return False, node, 0
# 二分查找
pos = bisect_left(node.keys, key)
# 如果没有找到，返回False
if pos == node.length of node.keys[pos] ! = key:
返回 False, 节点, 0
else:
返回 True, 节点, pos
else:
pos = bisect_left(node.keys, key)
# 递归
if pos == len(node.childs ):
if not flag:
return False, node, 0
else:
# 如果是插入阶段，则插入的元素是大于所有元素
# 立即替换最后一个元素
node.keys[-1] = key
pos -= 1
return self._query(node.childs[pos], key, flag ）

大家应该都注意到了，B+树的叶子节点是一个链表，每个节点都有一个next指针指向它的右兄弟。所以我们也可以通过链表来查找元素。这段代码并不难写。这是一个简单的链表演练。没有涉及太多细节。我们直接看代码：

def seq_query( self, key):
node = self.head
# 循环链表
while node is not None:
# 二分查找查看当前节点是否
pos = bisect_left(node.keys, key)
# 如果大于当前所有元素
if pos == node.length:
# 如果不存在一个延续，这意味着如果node.next为None，则找不到
：
return False, None
node = node.next
continue
# 如果找到，判断是否是我们想要
if node.keys[pos] == key:
return True, node.values[ pos]
else:
return False, None

B+的第二种加法树

是添加元素。添加元素的逻辑与B树基本相同，但有一些细微的变化。

与 B 树一样，B+ 树中的所有插入也 发生在叶节点 上。所以我们使用搜索操作来找到适合插入的节点并插入这个元素。因为B+树限制了一个节点上的元素数量，所以最大不能超过M，这意味着插入操作可能会造成非法，所以我们需要评估这种情况。如果插入造成非法，我们必须采取行动予以维护。数据结构的本质。

的措施非常简单。与B树类似，如果节点元素数量超过限制，将会分裂。

但是分裂操作会略有不同，让我们看看：

如果这是一个4阶B+树，如果我们插入一个元素，它就会分裂。例如，如果我们插入5，我们得到：

你有没有注意到，由于分裂会产生两个子树，所以分裂后的顶部节点将有两个元素，而B树只会有一个元素。

但是如果不是在根节点进行分裂，那么只会上传一个元素，就像B树一样。

再看一个例子：

如果此时添加元素12，第三个子树的元素数量就会超出限制，因此会发生分裂：

分裂发生在我们最后一个节点之后已插入一个元素，但只上传了 10 个元素到父节点。由于15已经在父节点中，所以不需要上传。

当然，这个图并不是最终的形式。根节点明显超出了限制，需要进一步分裂。最终结果是这样的：

当然，这只是一般逻辑。在我们的实施过程中，有很多细节需要考虑。 。比如当前节点是不是叶子节点？如果是叶子节点，它没有子树可以分裂，但它确实有值可以分裂。如果它不是叶子节点，那么它分裂后，我们仍然需要保留子节点和底层链表。虽然细节很多，但是实现的时候只要把所有的细节弄清楚，逻辑并不复杂。

这里重点关注分割过程中next指针的处理。假设当前bt_node是叶子节点。当它分裂时，会产生两个新节点，我们称之为lnode和rnode。 。然后我们需要将bt_node提升为父节点，并合并父节点。此时我们如何保留下一个指针呢？

我们很容易认为lnode中的下一个应该指向rnode，rnode中的下一个应该指向node中的下一个，但是如何确保bt_node之前的下一个指向lnode点？

一种方法是我们也可以将节点的左兄弟传递到函数中，但这需要大量操作。例如，我们需要先找到左边的兄弟。这个查找其实并不容易，因为左兄弟可能不在同一个子树中，我们还需要判断左兄弟是否不存在。所以还是很棘手的，或者我们可以多保留一个指向左边的指针，这样我们就可以轻松找到左边的兄弟了。我想出的一种方法是使用 Python 中的引用存储技巧来避免这些复杂的操作。

我们假设sibling的左节点是brother，bt_node的引用存储在brother的下一个节点中，也就是该节点在内存中的地址。技巧是让lnode等于bt_node，即使用lnode引用指向bt_node，然后手动将lnode中的值更新为我们需要的值。这样一来，这个问题就被巧妙的方法规避了。我们看一下代码：

bt_node_next = bt_node.next
lnode = bt_node
# 手动更新lnode
lnode.update()
rnode = BTree.BT reeNode(key s= rkeys,children=rchilds,is_leaf=bt_node.is_leaf,father=node,pos_in_father=1,values=rvals)
lnode.next = rnode
rnode.next = bt_node_next

这段代码并不难，但是这一招并不容易。想一想，你需要对Python的引用机制有一些了解。这只是一个实现技巧，与算法关系不大。不懂的同学可以忽略。

明白了这一点后，我们最后看看删除B+树。

B+树的删除

B+树的删除逻辑与B树完全相同，但具体操作细节略有不同。

与B树一样，所有删除都发生在叶节点，但由于B+树的所有元素都有叶节点，因此我们不需要考虑删除中间节点并用后继节点替换它们案件。我们可以直接找到叶子节点进行移除和维护。我必须说这要容易得多。

立即删除

与B树一样，如果叶子节点元素数量足够，则立即删除。

例如，我们要删除上图中的13。由于叶子节点比较丰富，我们可以直接删除，得到如下：

这个没什么好说的，但是如果删除15个，即使也直接删除，也会有一些问题。我想大家应该都发现了，15不仅是叶子节点之一，而且还出现在中间节点上。如果我们删除 15，我们显然需要 更新 上的这个链接节点。

我们需要一路回溯，将它们的值改为去掉15后的最大值。这里的这个细节和B树不同，所以需要注意。更新后的结果应该是这样的：

当我们回去的时候，我们还要评估后面要改变的节点只要在父节点中具有最大值就需要回去，因为在父节点中的最大值父节点也是父节点的父节点。如果不需要只改变节点，也不需要返回，我们看一下代码：

def upload(self, bt_node,father, key):
iffather is None:
return
# 更改父节点中的值
father.keys[bt_node.pos_in_father] = key
grand_fa =father.father
# 如果更改父节点中的最大值，继续跟进
# 因为父节点中的最大值也在爷爷节点中
if bt_node.pos_in_father ==father.length-1 并且 grand_fa 不为 None:
self.upload(father , grand_fa, key)

这里很有趣的一点是，当我第一次实现的时候，我忘记了需要进一步回溯。我考虑只更新父节点并且没有继续回去。但我用大量的数据进行测试，发现还是成立的。

后来想了很多，得出的结论是，实在没有必要一路走回去。因为在搜索时我们无法判断该元素是否存在于顶节点中。例如，在上面的示例中，如果我只返回一级，则不会返回顶层。树看起来是这样的：

也就是说，15 仍然存储在根节点中，但是此时 15 已经被删除了。其实并不影响我们的搜索，因为树中没有大于15的元素。如果我们用15将顶层分成两半，用13除，结果是相同的，即在右侧。子树递归。当我们向下返回后，数据是正确的，所以我们只需要更新叶子节点即可向上移动一级。但这只是我的意见。我还没有想到什么反例。有想法的同学可以留言。

兄弟节点丰富

兄弟节点丰富。这很容易。我们只是从姐妹节点借用。与B树不同，由于所有节点都在叶子上，我们可以直接从姐妹节点借用元素，但这需要更新父节点中的值。

比如我们要去掉下图中的4，我们发现它的左兄弟元素丰富。我们不再需要通过父节点转账，可以直接借用。

但是借用之后，会有一个小问题，就是父节点中的3会失效，因为它不再是左子树中的最大元素，最大元素会变成2。所以我们需要在父节点中更新这个值。我们同样借用了右边这位兄弟的元素，只是方向不同，就不赘述了。

兄弟节点不丰富

最后我们考虑一下兄弟节点也不丰富的情况。这与B树类似，但略有不同。当前场景中，我们不再强制从父节点借用元素。想一想就可以明白，父节点中的数据都是在叶子上的。还有什么可以借的？所以我们不借用元素，直接将它们与姐妹节点合并。

例如，在下图中，如果我们要删除元素 12，则会导致约束违规。此时我们直接合并红框中的两个节点。

合并后，子树的数量会减少，所以我们需要删除父节点中的一个元素。如果我们将其与上图进行比较，我们可以看到我们想要从父节点中删除 10。这里我们需要判断左兄弟是否会和当前节点合并，我们要移除的是左兄弟的最大值，否则就是右兄弟的最小值。删除后，保留父节点，我们发现父节点不再合规，需要维护。

显然没有丰富的姐妹节点，所以继续合并：

同样操作后，我们发现当前节点的父节点，也就是根节点，只有一个元素left about，这是非法的，所以我们需要扔掉它并更新主节点。

后记

至此我们的B+树就完成了引入、删除、修改、查找。听起来是一个非常可怕的数据结构，但是只有几张图片来展示它。我完整写的代码不超过500行，这并不是一个很可怕的数字。常常我们害怕数据结构中的变形、旋转等操作，但其实我们可以从容地画出所有的变化，而且只有几个来回。 当我们反抗、退缩的时候，打败我们的不是数据结构，也不是问题，而是我们放弃了。

最后我们思考一个问题：为什么将所有元素都放在B+树的叶子节点中是一种优化呢？这不是增加了寻找的负担吗？我们可能已经找到了一半的元素，但现在我们必须找到它的最后。这怎么能算是优化呢？

同样，要回答这个问题，仅仅了解数据结构是不够的。我们还需要结合用例。我们都知道B+树的场景，数据库的底层实现结构。我们都知道数据库中的数据非常大，我们不可能将所有数据都存储在内存中。随机读写磁盘非常耗时。我们将所有数据放置在叶节点上。对于大量的增删改查，我们可以获得连续数据进行批量操作，可以大量使用，节省时间。而且，B+树对于批量读取比B-树效率更高。比如我们要读取一个范围，可以先找到一个节点，然后通过next指针批量获取。我们通过指针的移动是顺序读写，读写速度比随机读写要快很多。