这篇文章上次修改于 361 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

用途

B+树的主要目的之一就是存储所有键值对，并确保键的有序性，以便于高效的查找操作。B+树是一种树状数据结构，其中所有的键值对都存储在叶子节点上，而内部节点仅包含用于导航的关键字。

内部节点就是除了叶子节点的节点

特征

B+树拥有一个阶数m，这个阶数是根据特定应用场景和系统需求进行权衡的结果。

B+树全称(Balanced Plus tree)，它与B树的区别就是每个节点可以包含多个子节点，数量由阶数决定。

确定了阶数m，m阶的B+数将会有以下特征：

  • 对于每个内部节点，它最多包含m个关键字，拥有m + 1个指针，每个指针指向它的子节点
  • 对于每个叶子节点，它最多包含m个数据的索引，它们是有序的。

B+树的本身特征：

  • 在内部节点中出现的每个值也作为子树叶级中最右边的值出现（由于已排序，最右边即最大）
  • 根节点只有树节点指针，叶节点只有数据指针
  • 在插入和删除的过程中，节点会动态变化，移动关键字和调整指针，

B+树的查找

精确查找

对于B+树，刚进入查找时从根节点开始，根节点有m个索引值和m + 1个指针，由于索引值是有序的，每两个索引值之间都有一个指针，代表索引值位于这两者之间值的下一层节点。若查找值小于等于最小值，则进入第一个指针，若大于所有值则进入。直至最后一层叶子节点，找到对应的索引值，叶子节点的索引值会带有数据的指针。

p1.png

对于以上例子，当我查找7的时候，7 > 5，故查看最右边的节点，然后找到7。

范围查找

对B+树的观察可以发现，叶子节点之间都有指针相连，这是为了便于范围查找，当找到范围的左边和右边，便可通过遍历获取范围内的值。

B+树的插入

分裂

分裂是B+树插入的重要行为，当插入到叶子节点有空位时，便可直接插入，当要插入的叶子节点没有空位，例如上图插入2，此时该叶子节点就会有三个值，B+树就会采用分裂的行为。

该叶子节点分裂， 建立一个新的叶子节点插入，将一半的关键字移动到一个新的叶子节点中，然后由于下面叶子节点的变化，上面也跟着发生变化，当一个非叶子节点中的关键字数量达到阶数的上限时，该节点中的关键字按照中间的关键字分成两组，然后分别放入两个新的节点中，并在父节点中添加一个指向新节点的指针。这样可以保持B+树的平衡。

为了更好理解，可以尝试对一颗空的B+树添加元素8,5,1,7,3,12,9,6

B+树的删除

通过查找找到要删除的关键字，如果删除关键字后，叶子节点的关键字数量低于下限(没有关键字了或者低于设置的下限)，就需要进行重配或者合并

重配(借关键字)

如果相邻的兄弟节点关键字数量足够多，可以从兄弟节点借一个关键字过来，这样就可以放置低于最低值

合并(合并节点)

如果相邻的兄弟节点关键字数量都较小，可以选择合并两个节点，并将一个关键字提升到父节点中。

B+树应用场景

B+树主要用在磁盘文件组织、数据索引和数据库索引。

  • B+tree的磁盘读写代价更低，B+tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

  • B+tree的查询效率更加稳定，由于非叶子结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

  • B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。