B+ 树

B+ 树

B+ 树是一种多叉排序树，即每个节点通常有多个孩子。一棵 B+ 树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。

B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入，这与二叉树恰好相反。
结构示例：

定义方式采取和 wikipedia 上保持一致。一颗 b 阶的 B+ 树，其中 b 表示树的每个节点最多可以拥有的子节点个数，特性有：

• B+ 树的阶或分支因子 b 定义为：内部节点允许的最大的子树节点数量/指针的数量；
• 内部节点的实际子树节点/指针的数量 m 限制：$\lceil \frac{b}{2} \rceil \le m \le b$ ；根节点子树节点的数量为：$2 \le m \le b$
• 如果内部节点包含 m 个子树节点/指针，那么该节点包含 m-1 个关键字 key (不同定义此处有差别)
• 叶子节点都在同一高度上

特别的，当初始只有一个节点时，根节点本身就是叶子节点，其记录的个数：$0\le n \le b-1$

所有叶子节点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接；
B+树的查找操作，无论查找成功与否，每次查找操作都是走了一条从根结点到叶子结点的路径。

查找插入删除操作

参考链接：https://zhuanlan.zhihu.com/p/149287061

用途

B+树 主要适用于索引操作。为什么说 B+树 比 B-树 更适合实际应用于操作系统的文件索引和数据库索引？

• B+树的内部节点只存储索引信息，而不存储实际数据，因此可以存储更多的索引信息，提高查询效率。
• B+树的叶子节点形成一个有序链表，可以方便地进行范围查询和排序操作。
• B+树的查询效率更加稳定: 由于非终节点并不是最终指向文件内容的节点，而只是叶子节点中关键字的索引。所以任何关键字的查找必须走一条从根节点到叶子节点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

MySQL 中的应用

为了查询更加高效，采用 B+树 作为数据库索引。在 MySQL 中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的。我们接下来讨论两个引擎：MyISAM 和 InnoDB 这两种引擎。

MyISAM

MyISAM 中有两种索引，分别是主索引和辅助索引，在这里面的主索引使用具有唯一性的键值进行创建，而辅助索引中键值可以是相同的。MyISAM 分别会存在一个索引文件和数据文件，它的主索引是非聚集索引。当我们查询的时候，我们找到叶子节点中保存的地址，然后通过地址我们找到对应的信息。

InnoDB

InnoDB 索引和 MyISAM 的最大区别是它只有一个数据文件。在 InnoDB 存储引擎中，表数据文件本身就是按 B+树 组织的一个索引结构，这棵树的叶节点数据保存了完整的数据记录，所以我们把它的主索引叫做聚集索引。而它的辅助索引和 MyISAM 也会有所不同，它的辅助索引都是将主键作为数据域，所以这样当我们查找的时候通过辅助索引先找到主键，然后通过主索引找到对应的主键，从而得到相应的数据信息。

链接

说明：不同的版本在定义上可能有差别。

• https://oi-wiki.org/ds/bplus-tree/
• https://www.cnblogs.com/nullzx/p/8729425.html
• https://zhuanlan.zhihu.com/p/149287061
• B+树及插入和删除操作详解(注: key数量等于指针数量)
• C++简单实现