B+ 树的基本概念

B+ 树是 B 树的一种变体，专为数据库和文件系统等应用进行了优化，其核心思想是提高范围查询和顺序访问的性能。

结点结构区分：
- 内部结点 (非叶子结点)：不存储数据，只存储用于索引的关键字。其结构为 $(P_{0}, K_{1}, P_{1}, ..., K_{n}, P_{n})$ ，其中 $K_{i}$ 是其子树中的最大（或最小）关键字，仅作为导航。
- 叶子结点：存储了所有的关键字以及指向这些关键字对应的数据记录的指针。
- m 个分支的节点就有 m 个元素
数据存储位置：所有数据记录的指针都只存在于叶子结点中。内部结点不包含指向具体数据记录的指针。
关键字冗余：内部结点中的关键字是其子树中叶子结点关键字的副本（索引）。因此，在 B+ 树中，某些关键字会同时出现在内部结点和叶子结点中。
顺序访问：所有叶子结点通过指针相互链接，形成一个有序的链表（通常是双向链表）。这极大地提高了范围查询和顺序遍历的效率。
固定的查找路径：任何关键字的查找都必须从根结点走到相应的叶子结点才能完成，所以查找操作的 I/O 次数是稳定的。

B+ 树和 B 树在很多方面相似，但其关键差异导致了它们在不同应用场景下的性能表现不同。

特性	B+ 树	B 树
数据存储	所有数据都存储在叶子结点。	数据存储在所有结点中（内部结点和叶子结点）。
结点内容	内部结点仅存储关键字 (索引)，不存储数据。	内部结点存储关键字和数据指针。
关键字冗余	内部结点的关键字是叶子结点关键字的冗余副本。	所有关键字在树中唯一出现。
叶子结点链接	所有叶子结点通过指针链接成一个有序链表。	叶子结点之间没有链接。
查找性能	查找任何关键字都必须走到叶子结点，路径长度固定，性能稳定。	查找可能在内部结点命中而提前结束，性能不稳定（最好情况更快）。
范围查询	效率极高。定位到范围起点后，沿叶子链表顺序遍历即可。	效率较低。需要对树进行复杂的中序遍历。
空间利用率与 I/O	内部结点更小（无数据），分叉数 (fan-out) 更大，树的高度更低，I/O 次数更少。	内部结点较大，分叉数相对较小，树的高度可能更高。

Okay, three, two, one, let's jam