图解数据结构和算法： B-tree

B-tree

B-tree是平衡搜索树，一般理解为多路径平衡搜索树，也称为B树、B_tree。它是一种自平衡树形数据结构，可以以 O(log n) 的时间复杂度搜索、插入和删除存储的数据。 B树通常用于存储系统，例如数据库或文件系统。

B 树特性

• B 树可以将 m 值定义为预定范围，即 m 路（顺序）B 树。
• 每个节点最多有 m 个子节点。
• 每个节点至少有 ceil(m/2) 个子节点，根节点和叶节点除外。
• 对于根节点来说，子树的个数范围是[2,m]，节点内的值的个数范围是[1,m-1]。
• 对于非根节点，节点内取值个数的范围为[ceil(m/2)-1,m-1]。
• 根节点（非叶节点）至少有两个子节点。
• 具有 k 个子节点的非叶节点包含 k-1 个值。
• 所有叶子节点都在同一层。节点
• 中的值按从小到大的顺序排列。
• 父节点的不同值作为分隔符值被分成多个子树。 左子树小于对应的分离值，对应的分离值小于右子树。

下面是一个四阶B树。

插入

假设您现在构建一棵四阶B树并开始直接插入'A'作为根节点。

放置比“A”大的“B”，放在右侧，

放置“C”，依次排列到最后，

继续“D”，直接相加的结果如下图，此时已经超出了节点的存储容量，对于每棵四阶B树，一个节点最多可以存储3个值，此时必须进行分裂操作在

分裂操作中，首先选择要分裂的节点的中值，这里是'B'，然后将中值'B'放在父节点中。这里的父节点无论如何都是立即创建一个新的父节点来存储“B”，而原本小于“B”的值被认为是左子树，大于“B”的值被认为是右子树

继续插入“E”，“E”比“B”大，走到右子节点，

分别与“C”和“D”比较，如果比这个大，就一直放下去向右，

插入“F”，“F”大于“B”，转到右子树，

“F”分别与“C”、“D”和“E”进行比较。如果它比它们大，则将其放置在最右侧。此时触发分裂操作，

选择要分裂的节点的中值“D”，然后将中值“D”放入父节点中。父节点中的'B'小于'D'，因此将其放置在'B'的右侧，并且原始值小于'D'。 '这些值被认为是左子树，那些大于“D”的值被认为是正确的子树。

继续插入“M”，结果是：

插入“L”，它比“B”和“D”大，并转到右子树，

“L”大于“ E”和“F”小于“M”，因此将其置于第三位置，此时激活分割操作。

选择要分裂的节点的中值“F”，然后将中值“F”放入父节点中，父节点D”中的“B”都小于“F”，所以它们被放在最右边，那些原本小于“F”的值被认为是左子树，大于“F”的值被认为是右子树。

插入“K” ，结果为：

在右子树中插入大于“B”、“D”、“F”的“J”，

“J”小于“K”、“L”和“M”，使其放在第一个位置。当激活分裂操作时，选择

要分裂的节点的中位数“K”，然后将中位数“K”放置在父节点中。父节点中的“B”、“D”、“F”都小于“K”，所以放在最右边，原本小于“K”的值都被认为是左子树，而那些大于“K”的值被认为是正确的子树。此时父节点也触发分裂操作。

选择要分割的节点的中心值为“D”，然后将中值“D”放置在父节点中。由于还没有父节点，所以可以直接创建一个新的父节点来存储“D”，小于“D”的值被认为是左子树。事实证明，那些大于“D”的值被用作正确的子树。

插入“I”，比“D”大，走到右子树，

右子树不是叶子节点，继续往下，此时“I”比“F”小则“K”，所以转到第二个分支，

“I”比“J”小，所以放在左边，

同理插入“H”，结果如下，

插入“G”，前往左子树，

分支到中心，

激活分裂操作，

选择要分裂的节点的中位数“H”，然后放置中位数“H”在父节点中，“H”比父节点中的“F”大，但比“K”小，所以放在中间，而原来小于“H”的值都被认为是左子树，而那些最初大于“H”的值被认为是正确的子树。

总结如上所述，插入操作的核心是拆分操作。不分裂的情况比较简单：直接合并即可；如果插入后超出节点容量，可以提前调整该容量，然后进行分裂操作。需要注意的是，分裂可能需要父节点继续分裂。

搜索

搜索B树相对容易。搜索过程有点像二叉搜索树。从根节点开始查找，根据比较值找到对应的分支，并继续查找子树。搜索。

比如搜索'I'，'I'大于'D'，走到右子树，

'I'与节点中的值进行比较，大于“F”、“H”且小于“K”，转到第三个分支，

将节点中的值一一比较，找到“I”。

作者：超人王小健
链接：https://juejin.im/post/5b873a1af265da43741e2328
来源：掘金
版权归作者所有。商业转载请联系作者获得许可。非商业转载请注明出处。