B+ Tree
B+树，是应数据库所需而出现的一种B树的变型树。
严格来说，它已经不是“树”了。
Definition
m阶B+树的定义：
- 每个分支结点最多有m棵子树（最多有m个孩子结点）；
- 非叶根结点至少有两颗子树，其他每个分支结点至少有
ceil(m/2)棵子树； - 结点的子树个数与关键字个数相等；
- 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来；
- 所有分支结点（可视为索引的索引）中仅包含它各个子结点（即下一级的索引块）中关键字的最大值即指向其子结构的指针。
Comparison
| B+ Tree | B Tree |
|---|---|
| 具有n个关键字只含有n棵子树（每个关键字对应一棵子树） | 具有n个关键字的结点含有n+1棵子树 |
| 每个结点（非根内部结点）的关键字个数n范围上下界为 |
对应左边，两个范围分别为 |
| 叶结点包含信息，所有非叶结点仅仅起索引作用；非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址. | 无对应 |
| 叶结点包含了全部的关键字，即在非叶结点中出现过的关键字也会出现在叶结点中. | 叶结点包含的关键字和其他结点包含的关键字是不重复的. |
Search
对B+树可以进行两种查找方式：
- 从最小关键字开始的顺序查找；
- 从根结点开始的多路查找。
原因
在一棵B+树中，分支结点的某个关键字是其子树中最大关键字的副本。通常在B+树中有两个头指针：一个指向根结点，一个指向关键字最小的叶结点。
Operations
查找
在查找过程中，非叶结点上的关键字值等于给定值时并不终止，而是继续向下查找，直到找到叶结点上的该关键字为止。
由上面叙述，我们可以知道，无论查找成功与否，每次查找都是一条从根结点到叶结点的路径。
如下图：
插入
和B树一样，B+树的插入仅在叶子结点上进行，当结点中的关键字个数大于m时，需要分裂成两个结点，他们所包含的关键字个数分别为和
。并且，他们的最大双亲结点中应同时包含这两个结点中的最大关键字。
删除
B+树的删除也尽在叶子结点进行，当叶子结点中最大的关键字被删除时，其在非终端结点中的值可以作为一个“分界关键字”存在。若因删除而使结点中关键字的个数少于时，其和兄弟结点的结合和B树类似。