B+树特点及插入、搜索、遍历图解

B+树

B+树是B树的变种，也是平衡多路径搜索树。总体结构与B树相同，包括根节点、内部节点和叶节点。它主要用于数据库和操作系统文件系统。由于B+树的内部节点不存储数据，因此可以在内存中存储更多的索引，提高缓存命中率。另外，由于叶子节点很方便与遍历操作关联，而且数据也是顺序的，所以方便区间搜索。

B+树特点

• B+树可以将m的值定义为预定义的范围，即m路（序）B+树。
• 根节点可以是叶子节点，也可以是包含两个或多个子节点的节点。
• 如果一个内部节点有k个关键字，则它有k+1个子节点。
• 非叶子节点不存储数据，只存储关键字用于索引，所有数据都存储在叶子节点中。
• 没有叶子的节点有多个子树指针。如果非叶节点的键为 k1,k2,...kn，其中 n=m-1，则计算子树的第一个键。条件小于k1，第二个大于等于k1小于k2等，最后一个大于等于kn。总共可以分割m个区间，也就是说可以有m个分支。 （其实，B+树数据能否放置和分区，对判断条件没有严格的要求。有些实现使用m关键字来划分区间，这也是可以接受的）
• 所有叶子节点都通过指针链连接。叶节点本身按关键字大小升序排列。
• 在不进行删除操作的自然插入中，叶子节点的元素个数范围为[floor(m/2),m-1]，内部节点的元素个数范围为[ceil(m/2)- 1，m-1]。
• 另外，B+树通常有两个主指针，一个指向根节点，另一个指向关键字最小的叶子节点。
• 执行删除操作时，会包含索引节点的填充因子和叶子节点的填充因子。一般情况下，可以将叶子节点和索引节点填充因子设置为至少 50%。

以下是一棵4阶B+树，

插入操作

假设现在构建一棵4阶B+树，开始插入“A”，直接作为根节点，

插入“B”，更大比“A”，放在右边，

插入“C”，按顺序排列到最后，

继续插入“D”，直接相加的结果如下图，在此处此时超出了节点的存储容量，对于四阶B+，每个树节点最多可以存储3个元素。此时应进行分割操作。分裂操作

是首先选择要分裂的节点中间的元素。这里，选择“C”，然后将“C”元素放置在父节点中。 ，因为这里还没有父节点，那么直接新建一个父节点来存放“C”，小于“C”的元素作为左子树，大于等于“C”的元素作为左子树右子树。注意，非叶子节点存储关键字并用作索引，因此父节点中存储的项“C”不包含数据，数据仍然存储在右子树中。此外，您需要添加一个从左子树到右子树的指针。

继续插入“M”，“M”大于“C”，转到右子节点，

分别与“C”或“D”比较，如果大于两者，把这个放在最右边。此时，分裂操作开始，

选择要分裂的节点的中心。位置中的元素“L”，然后将元素“L”放入父节点，将“L”按大小顺序放入给定位置，那些原本小于“L”的元素作为左子树，将原来大于或等于“L”的元素作为右子树。父节点中存储的“L”项不包含数据，数据仍存储在右子树中。此外，您需要在左子树中添加一个指向右子树的指针。

继续插入“K”，从根节点开始查找，逐一比较关键词。 “K”大于“C”且小于“L”。转到另一个分支，

逐个比较子节点，“K”最后落到最右边，

继续插入“J”，从根节点开始查找，逐个比较关键字，“J”大于“C”且小于“L”，则转到另一个分支，

在子节点中找到“J”对应的位置。这时候就超出了节点的容量，需要进行分裂操作。

选择要拆分的节点中间的元素“J”，然后将元素“J”放置在父节点上，将“J”按大小顺序放置在某个位置，那些元素原来小于“J”的元素作为左子树，原来大于或等于“J”的元素作为右子树。父节点中存储的“J”项不包含数据，数据仍存储在右子树中。此外，您需要在左子树中添加一个指向右子树的指针。

继续插入“I”，从根节点开始查找，逐个比较关键词。 “I”大于“C”但小于“J”和“L”。到另一个分支，

一一比较找到插入点处的“I”，

继续插入“H”，从根节点开始查找，一一比较关键词，“H”为大于“C”且小于“J”和“L”，转到另一个分支，

“H”与节点中的值一一比较，根据大小放置到某个位置

选择要分割的节点中间的“H”元素，然后将“H”元素放置在父节点中，将“H”放置在指定的位置按大小顺序排列，将原来小于“H”的元素作为左子树，将原来大于等于“H”的元素作为右子树。元素“H”父节点中存储的数据不包含数据，数据仍然存储在右子树中。另外，还需要在左子树中添加指向右子树的指针。

选择要拆分的节点中间的“J”元素，然后将“J”元素放置在尚不存在的父节点中。父节点，必须将其创建为父节点。那些原本小于“J”的元素作为左子树，那些原本大于“J”的元素作为右子树。这是非叶节点的分叉。操作对象是用作索引的关键字，不需要考虑数据存储问题。

插入“G”并从根节点开始查找。 “G”小于“J”。前往第一家分店。

一一比较节点中元素的值。 “G”大于“C”且小于“H”，转到另一个分支，

逐个比较节点中元素的值，找到“G”的位置并将其插入，

插入“F”，从根节点开始查找，“F”小于“J”，走到第一个分支，

逐个比较节点中的元素值，“F”大于“C”且小于“H”，转到第二个分支，

将节点中元素的值一一比较，找到位置值“F”并插入。此时，开始划分操作。

选择要拆分的节点中间的“F”元素，然后将“F”元素放置在父节点中，并将“F”按照大小和原元素的顺序放置在指定位置小于“F”的元素作为左子树，大于或等于“F”的原始元素作为右子树。父节点中存储的“F”项不包含数据，数据仍存储在右子树中。此外，您需要在左子树中添加一个指向右子树的指针。

最后插入“E”，从根节点开始查找，“E”小于“J”，走到第一个分支，

逐个比较节点中的元素值，“E” "大于"C"且小于"F""，转到另一个分支，

逐一比较节点中元素的值，找到对应的位置打“E”并插入。

从上面的插入操作可以看出，插入主要涉及除法运算，需要注意的是，非节点只存储关键字作为索引，数据存储在叶子节点上。此外，必须使用指针来连接叶节点。起床。最后我们可以看到叶子节点的元素是从小到大排列的，因为指针使得遍历数据变得更加容易。

搜索操作

搜索B+树与搜索B树类似，都是从根节点开始，通过比较item的值找到对应的分支，然后继续搜索子树。

比如要找“H”，“H”小于“J”，就走到第一个分支，

逐个比较节点中的元素，发现应该走到第四个分支，

一一比较，找到“H”。

遍历操作

遍历操作首先要找到树的最左边的叶子节点，然后通过指针就可以遍历整棵树了。

从根节点开始，走到第一个分支，

继续到第一个分支，

你发现已经到达了一个叶子节点，这就是你要找的遍历的开始，

一个叶子节点有两个元素，则根据光标跳转到第二个叶子节点，

第二个节点有三个元素，根据光标继续到下一个节点，

该节点有两个元素，根据Cursor继续下一个节点，

相对于指针继续向下，

向下，

完成整棵树的遍历。

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