B+树
B+树是一种树数据结构，通常用于数据库和操作系统的文件系统中。
B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。
B+树元素自底向上插入，这与二叉树恰好相反。
简介
B+树在节点访问时间远远超过节点内部访问时间的时候，比可作为替代的实现有着实在的优势。
这通常在多数节点在次级存储比如硬盘中的时候出现。
通过最大化在每个内部节点内的子节点的数目减少树的高度，平衡操作不经常发生，而且效率增加了。
这种价值得以确立通常需要每个节点在次级存储中占据完整的磁盘块或近似的大小。
B+背后的想法是内部节点可以有在预定范围内的可变数目的子节点。
因此，B+树不需要象其他自平衡二叉查找树那样经常的重新平衡。对于特定的实现在子节点数目上的低和高边界是固定的。
B+ 树的创造者Rudolf Bayer没有解释B代表什么。最常见的观点是B代表平衡(balanced)，因为所有的叶子节点在树中都在相同的级别上。
节点结构
在 B+ 树中的节点通常被表示为一组有序的元素和子指针。如果此B+树的序数（order）是m ，
则除了根之外的每个节点都包含最少 个元素最多 m-1 个元素，对于任意的节点有最多 m 个子指针。
对于所有内部节点，子指针的数目总是比元素的数目多一个。
因为所有叶子都在相同的高度上，节点通常不包含确定它们是叶子还是内部节点的方式。
每个内部节点的元素充当分开它的子树的分离值。
例如，如果内部节点有三个子节点（或子树）则它必须有两个分离值或元素a1和a2。
在最左子树中所有的值都小于等于a1，在中间子树中所有的值都在a1和a2之间((a1，a2]），而在最右子树中所有的值都大于a2。
特征
B+树是B树的一种变形，比B树具有更广泛的应用，m阶 B+树有如下特征:
- 每个结点的关键字个数与孩子个数相等，所有非最下层的内层结点的关键字是对应子树上的最大关键字，最下层内部结点包含了全部关键字。
- 除根结点以外，每个内部结点有 到m个孩子。
- 所有叶结点在树结构的同一层，并且不含任何信息(可看成是外部结点或查找失败的结点)，因此，树结构总是树高平衡的。