7.3.2 B+树

B+ 树的阶（又称扇出），指一个页（节点）能存放多少个子指针。

下文中 $[\ ]$ 表示向下取整。

（P250 11.3.1）若一个 B+ 树的扇出为 $n$：

• 每个叶节点最多存放 $n$ 个指针、$n-1$ 个数据，最少存放 $[n / 2]$ 个指针、$[(n - 1) / 2]$ 个数据。

插入数据时：

1. 若当前节点数据个数少于扇出，则直接插入。
2. 若当前节点已满，则需要分裂，将当前节点中第 $[n / 2] + 1$ 个数据提拔为上一级节点指针，并将节点按此位置分为左右两部分。

可视化模拟：

原始地址：https://bplustree.app/，这个网站插入是对的可以参考，删除与教材行为不一致，且教材认为非叶节点和叶节点存放的指针数量一致。