【对线面试官】B 树与 B + 树：原理、区别及优劣势分析

在数据库领域，索引是提升查询效率的关键，而 B 树和 B + 树作为常用的索引数据结构，分别被 MongoDB 和 MySQL 广泛采用。本文将深入解析 B 树和 B + 树的定义、底层原理、优缺点，以及两种数据库选择不同树结构的原因，并补充关键架构图及图示辅助理解。

一、B 树和 B + 树的定义

（一）B 树

B 树是一种多路平衡查找树，它的每个节点包含多个关键字和对应的指向子树的指针。这些关键字在节点内部按照升序排列，且每个关键字左边子树中的所有关键字均小于该关键字，右边子树中的所有关键字均大于该关键字。B 树的阶数（即每个节点最多包含的关键字数量）通常根据实际情况确定，一般来说，阶数越大，树的高度越低。

B 树结构图示：

（注：上图为一个 3 阶 B 树示例，根节点包含 2 个关键字 K1、K2，分别指向三个子树，左子树关键字均小于 K1，中子树关键字介于 K1 和 K2 之间，右子树关键字均大于 K2）

（二）B + 树

B + 树是 B 树的一种变体，它与 B 树的主要区别在于：所有关键字都出现在叶子节点上，非叶子节点仅起到索引作用，不存储实际数据；叶子节点之间通过指针连接形成一个有序链表，便于进行范围查询。B + 树的非叶子节点中的关键字是叶子节点中关键字的副本，用于引导查询。

B + 树结构图示：

（注：上图为 B + 树示例，非叶子节点仅作索引，叶子节点 E 包含所有关键字，B、C、D 通过虚线表示指针形成有序链表）

二、B 树和 B + 树的底层原理

（一）B 树的底层原理

1. 查询过程：在 B 树中进行查询时，从根节点开始，将目标关键字与节点中的关键字进行比较。如果找到相等的关键字，则查询成功；如果目标关键字小于某个关键字，则进入该关键字左边的子树继续查询；如果目标关键字大于某个关键字，则进入该关键字右边的子树继续查询，直到找到目标关键字或确定不存在该关键字。
   B 树查询过程图示：

2. 插入过程：插入一个新的关键字时，首先找到合适的插入位置。如果插入后节点的关键字数量不超过阶数减一，则直接插入；否则，需要将节点分裂成两个节点，将中间的关键字向上移动到父节点中。如果父节点也因此超过阶数限制，则需要继续分裂，直到树的结构保持平衡。
   B 树插入分裂图示：

3. 删除过程：删除关键字时，首先找到要删除的关键字所在的节点。如果该节点是叶子节点，直接删除关键字即可；如果是非叶子节点，则需要用其前驱或后继关键字替换该关键字，然后删除前驱或后继关键字所在的叶子节点中的对应关键字。删除后，如果节点的关键字数量小于规定的最小值，则需要进行合并操作，即将该节点与相邻的兄弟节点合并，并调整父节点中的关键字。
   B 树删除合并图示：

（二）B + 树的底层原理

1. 查询过程：B + 树的查询过程与 B 树类似，从根节点开始逐层向下查找。由于非叶子节点不存储实际数据，所以必须一直查询到叶子节点才能确定是否找到目标关键字。
   B + 树查询过程图示：

2. 插入过程：插入操作首先在叶子节点中进行。如果插入后叶子节点的关键字数量超过阶数限制，则需要进行分裂。分裂后的中间关键字向上移动到父节点，若父节点也超过限制，则继续分裂，直到树保持平衡。
   B + 树插入分裂图示：

3. 删除过程：删除操作同样在叶子节点进行。删除后，如果叶子节点的关键字数量小于规定的最小值，则需要从相邻的兄弟节点借调关键字或进行合并操作，并相应地调整父节点中的关键字。
   B + 树删除合并图示：

三、B 树和 B + 树的优缺点

（一）B 树的优缺点

1. 优点：查询速度快，在非叶子节点找到目标值就可以结束查询，减少了磁盘 I/O 操作；对于随机访问的情况，性能较好。

2. 缺点：插入和删除操作复杂，需要频繁地进行节点分裂和合并来维护树的平衡性；不便于进行范围查询，因为需要遍历多个子树。

（二）B + 树的优缺点

1. 优点：查询效率稳定，所有查询都要到叶子节点，避免了在不同层级查询效率差异较大的问题；便于范围查询，通过叶子节点之间的指针可以快速遍历一个范围内的所有关键字；由于非叶子节点只存储索引信息，相同阶数下，B + 树能够存储更多的关键字，减少了树的高度，降低了磁盘 I/O 次数。

2. 缺点：占用空间较大，因为叶子节点存储了所有关键字；对于单个关键字的查询，可能需要比 B 树更多的磁盘 I/O 操作，因为必须到达叶子节点。

四、MongoDB 为什么用 B 树，MySQL 为什么用 B + 树

（一）MongoDB 选择 B 树的原因

MongoDB 是文档型数据库，其数据的访问模式更倾向于随机访问。B 树在随机访问时性能较好，能够快速定位到目标文档。此外，MongoDB 的文档通常是一个完整的实体，查询时往往需要获取整个文档，B 树可以在找到对应的关键字后直接获取数据，减少了查询的步骤。

（二）MySQL 选择 B + 树的原因

MySQL 是关系型数据库，经常需要进行范围查询，如查询某个区间内的数据。B + 树的叶子节点形成有序链表，能够高效地完成范围查询操作。同时，MySQL 的数据通常按照表的形式组织，数据量较大，B + 树在相同阶数下能够存储更多的索引信息，降低了树的高度，减少了磁盘 I/O 次数，提高了查询效率。而且，B + 树查询效率稳定的特点也符合关系型数据库对查询准确性和一致性的要求。

综上所述，B 树和 B + 树各有其特点和适用场景，MongoDB 和 MySQL 根据自身的数据库类型和数据访问模式选择了合适的索引结构，以达到最佳的性能表现。