我要评论b+树是一种优化的b树结构，适用于数据库索引。它保证所有数据都在叶子节点，且叶子节点间有链接，便于数据检索。
数据结构如下所示：
1、b+树和n叉树
1.1、b+树的基本定义
b+树是一种平衡的多叉搜索树，广泛应用于数据库和文件系统的索引结构（如mysql的innodb存储引擎）。
核心特点
- 每个节点可以包含多个子节点（即n叉树）。
- 所有叶子节点通过指针连接，形成一个有序链表。
- 内部节点仅存储键值，数据（记录指针）仅存在于叶子节点。
1.2、b+树与n叉树的关系
1、n叉树
n叉树是指每个节点最多有nn个子节点的树结构。
- 二叉树：每个节点最多有 2 个子节点（n=2）。
- 三叉树：每个节点最多有 3 个子节点（n=3）。
- b+树：每个节点最多有mm个子节点（n=m，其中mm是 b+树的阶数）。
2、b+树的节点结构
b+树的节点分为内部节点和叶子节点。
1、内部节点（非叶子节点）：
存储键值（key）和子节点指针。每个节点最多有mm个子节点（n=m）。
2、叶子节点：
存储键值和数据指针（或实际数据）。所有叶子节点通过指针双向连接，形成有序链表。
1.3、b+树的n叉特性
1、阶数决定n的值
阶数m是 b+树的核心参数，表示：
- 每个节点最多有m个子节点。
- 每个节点最多存储m−1个键值。
示例：
对于阶数m=5的 b+树：每个节点最多有 5 个子节点（n=5）。每个节点最多存储 4 个键值。
2、b+树的n叉特性
每个节点的子节点数量可变：
- 内部节点的子节点数在⌈m/2⌉到m之间（保持树的平衡）。
- 叶子节点的子节点数为 0（无子节点）。
3、b+树被称为n叉树原因
直接原因：b+树的每个节点最多有mm个子节点（n=m），符合n叉树的定义。
根本原因：
- 多路平衡：b+树通过多路分支（n叉）减少树的高度，提高磁盘io效率。
- 阶数mm：b+树的性能与mm直接相关，mm越大，树越矮，查找路径越短。
示例：阶数m=3 的 b+树
[10, 20] // 内部节点（2个键值，3个子节点）
/ | \
[5, 8] [15] [25, 30] // 叶子节点（存储数据）
- 内部节点：存储键值10、20，指向 3 个子节点。
- 叶子节点：存储数据（如记录指针），并通过指针连接。
4、阶数和性能的影响
1.4、b+树与b树的区别
如下所示：
注意：
- b+树是n叉树的一种，其阶数mm决定了每个节点的最大子节点数（n=m）。
- 这种多叉结构是b+树在数据库和文件系统中广泛应用的核心原因。
2、b+树的查找元素
b+树中的所有数据均保存在叶子结点，且根结点和内部结点均只是充当控制查找记录的媒介，并不代表数据本身，所有的内部结点元素都同时存在于子结点中，是子节点元素中是最大（或最小）元素。
如下图所示：
例如b+树中查找55这个关键字，步骤如下：
1、在根节点中对比55和根节点中的元素[60, 85]，发现55<60，因此应该在第一个结点中继续寻找；
2、比较55和第一个节点中的元素[10, 20, 50, 60]，发现50<55<60，因此55应该存在于第四个结点当中；
3、继续对比55和第四个结点中的元素[55, 60]，找到55，查找成功。当然，也有查找失败的情况，即要查找的元素并不在b+树中。
3、b+树的插入元素
其插入规则如下：
1、插入的操作全部都在叶子结点上进行，且不能破坏关键字自小而大的顺序；
2、当插入关键字后结点的关键字个数大于m，需要进行“分裂”。
b+树的插入有四种情况：
1、若被插入关键字所在的结点，其含有关键字数目小于m，则直接插入；
2、若被插入关键字所在的结点，其含有关键字数目等于m，则需要将这个结点分为左右两部分，中间的结点放到父节点中。假设其双亲结点中包含的关键字个数小于 m，则插入操作完成。
3、在第 2 种情况中，如果上移操作导致其双亲结点中关键字个数大于 m，则应继续分裂其双亲结点。
4、若插入的关键字比当前结点中的最大值还大，破坏了b+树中从根结点到当前结点的所有索引值，此时需要及时根节点、字节点，再做叶子节点插入操作。
举例：
1、插入关键字12，此时第一个叶子节点部分[10, 15]关键字的个数<m，可以直接插入：（紫色代表插入的元素）
2、插入95，需要插入到最后一个叶子节点部分[85, 91, 97]：
此时该节点的关键字个数大于m，需要进行分裂操作，并且父节点需要插入一个新的关键字：
3、插入40，需要插入到第二个叶子节点部分[21, 37, 44]：
此时该节点的关键字个数大于m，需要进行分裂操作，并且父节点需要插入一个新的关键字：
父节点插入新的关键字之后，根结点关键字的个数大于m，也需要进行分裂：
4、插入100，由于其值比最大值 97 还大，插入之后，从根结点到该结点经过的所有结点中的所有值都要由 97 改为 100。（橙色为修改之后的）
修改完最大值之后，在最后一个节点处插入100：
4、实际应用
4.1、innodb引擎
mysql数据表以文件方式存放在磁盘中，默认使用共享表空间（0）存储。
mysql使用共享表空间存储，所有表的数据和索引会存储在一个共享的 ibdata 文件中。表结构以.frm文件的形式存储在与表对应的文件夹中。
如果使用了独立表空间，innodb 会将每个表的结构和数据存储在独立的 .ibd 文件中。每当表的数据或索引被更新时，文件也会随之变化。表的结构仍然以.frm文件存储。
更多知识详细可参考：谈谈mysql的日志的用途
每个页节点段、非页节点段可参考如下：
注意：阶数由页大小（page size）决定（通常为 16kb）。
阶数计算示例：
每个关键字（如主键）为 8 字节，指针为 6 字节。当磁盘块page页大小为 16kb：
实际阶数约为 1170，树高度为 3 时可存储1170^3≈1.6亿条记录。
存储的计算公式：
4.2、文件系统
linux 的 ext4 文件系统：
- 使用 b+树管理目录项。
- 阶数由块大小（4kb）和目录项大小决定。
总结
在数据库中通常不只是查询(select)一条记录，如果是多条记录的话，b树要做中序遍历，可能要跨层访问，而b+树由于所有的数据都在叶子节点，不用跨层，同时由于有链表结构只要找到首尾，就能通过链表把数据都读出来。
以上为个人经验，希望能给大家一个参考，也希望大家多多支持代码网。
发表评论