数据结构-B+树

MySQL 的索引采用这种数据结构。一棵 $m$ 阶的B+树需满足下列条件：

1. 每个分支结点最多有 $m$ 棵子树。
2. 非叶根结点至少有两棵子树，其他每个分支结点至少有 $\lceil \frac{m}{2} \rceil$ 棵子树。
3. 每个结点的子树个数与关键字个数相等。
4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字从小到大排序，并且相邻叶结点从小到大相互链接起来。
5. 所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向其子结点的指针。

查找

B+树的查找、插入和删除操作和B树的基本类似。只是在查找过程中，非叶结点上的关键字值等于给定值时并不终止，而是继续向下查找，直到叶结点上的该关键字为止。所以，在B+树中查找时，无论查找成功与否，每次查找都是一条从根结点到叶结点的路径。

B+树与B树的差异

1. 在B+树中，具有n个关键字的结点含有n棵子树；而在B树中，具有n个关键字的结点含有n+1棵子树。
2. 在B+树中，每个结点的关键字个数n的范围是 $\lceil \frac{m}{2} \rceil \le n \le m$（根结点：$1 \le n \le m$）；在B树中，每个结点的关键字个数n的范围是 $\lceil \frac{m}{2} \rceil-1 \le n \le m-1$（根结点：$1 \le n \le m-1$)。
3. 在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
4. 在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在B树中，叶结点（最外层内部结点）包含的关键字和其他结点包含的关键字是不重复的。