备忘，记述一篇关于B树的介绍。
####简要说明####
根据各种资料的说明，因为B树的整体高度比较低，使得其在文件系统中应用较为普遍，因为树的高度低，有助于减少 IO 访问的次数。从而提高性能。
####相关特性####
1、 对于每个节点的键值个数有限制，如果键值个数的下限为 t - 1, 那么其上限为 2 * t - 1 ，根节点除外，根节点键值最少为 1。其中对于内部节点，其子节点的个数比键值个数多一。
这里为什么要设置上限和下限，我个人片面的认为，目的可能是可以更好的使所有数据均匀的分布到各个节点之中， 首先不设置下限，就有可能某些节点数据很少，某些节点数据很多，而设置上限，也是为了限制这种情况的出现。原则上来说，上限和下限的区间越小，数据的分布越均匀，但选取 2 * t - 1 作为上限，主要是为了维护上的方便，上限可以设的更大，但性能也会随之下降。
接下来会介绍，在节点的插入和删除过程中，某些情况下会伴随有节点的分割和合并，分割就是当一个节点满了，比如根据算法导论中介绍的方法，在节点的插入过程中，如果碰到满的节点，就对其进行分割操作，分割就是将当前节点的中间值上移，然后左半部分作为左子节点，右半部分作为右子节点，使得当前节点被分割为两个键值个数都为t - 1 的子节点。
同时在节点的删除过程中，可能伴随有节点的合并，还是根据算法导论中提供的算法，这里为什么说根据算法导论中的算法，因为实际中，在B树的具体实现上，有一些不同的算法，当然思想是一样的，有的算法需要回溯，但算法导论中的算法不涉及回溯。该算法在删除过程中如果碰到一个待删除的节点的左右兄弟都只有最少的键值，即 t - 1 ，则选取其中一个兄弟节点，再加上父节点，与当前节点，合并为一个节点。合并之后的节点的键值个数就为 2 * t - 1。
所以对于B树键值个数的上限和下限设置还是有其合理之处的，不是想当然的胡乱设置一个值。
2、所有的叶子节点都在同一层， 这似乎看起来是一条比较难以实现的性质，或者说难以维护的性质。但比较巧妙的地方就在于其树的高度是向上生长的，也就是当一个节点满了之后，对当前节点进行分割，分割后其父节点上移，当前节点与其兄弟节点仍然处于同一层。
3、假设当前节点有 n 个键值分别为 key1 , key2 … , keyn 那么就一共有 n + 1 个子节点，设分别为 child1 , child2 , … , childn childn+1 。其中以 childi 为根的子树上的节点都大于 keyi-1 小于 keyi ，但对于 child1 和 childn+1 稍微特殊，一个没有下限，一个没有上限。
####具体实现####
B树的性质比较好描述，主要难点在对B树的维护上，维护主要涉及到插入和删除两个操作，这里分别进行记述。主要结合自己在实现过程中的产生的想法和遇到的问题进行描述，同时算法主要间接或者直接参考至算法导论。
####键值插入####
这里不考虑相同键值的插入，就是默认拟待插入的键值都是当前树上不存在的键值。
同时对于所有的键值插入都是在叶节点上进行，就是所有的键值最终都会被插入到某一个叶节点中。
可能很自然的就能联想到，如果插入新的键值之后，被插入的节点键值个数超过了上限怎么办。然后很自然的联想到，将当前节点中的键值移一个到父节点，但简单的移动肯定不行，因为父节点中增加一个键值，那就意味中需要增加一个子节点，因为根据前面的介绍，子节点的个数是刚好比键值个数多 1 的。
所以实际的操作就是要对当前节点进行分割，分割为两个节点，然后将原先节点的中间值上移到父节点中。这就是通常的回溯，如果情况糟糕，这种回溯可能会一直进行到根节点，并且如果根节点也满了，就需要对根节点进行分割，产生一个新的根节点。这也就是我们前面所说的树的高度是向上生长的。
这里介绍一种主动式的方法，就是对待插入的节点再多一点限制，对于每一个潜在的待插入节点 （也就是遍历路径上的所有节点），我们都要保证其键值的个数不满，这样如果再插入一个新节点，就不需要回溯。
这里根据实现的步骤进行说明
#####第一步#####
判断根节点是否为空，或者根节点已满（因为根节点也是一个潜在的待插入节点，所以如果根节点已满，则进行分割）。这两种情况都需要会产生新的根节点。同时更新根节点。并从根节点开始进行遍历。
#####第二步#####
判断当前节点是否为叶节点，如果为叶节点则将节点插入到合适的位置。（根据第一步，当前节点不可能已满，因为如果已满会被事先分割），然后插入过程结束。
#####第三步#####
如果当前节点为内部节点，找到合适的子节点 childi 使得待插入的键值 k 满足 keyi-1 < k < keyi 。
然后查看 childi 的键值是否已满，如果已满，则对该子节点进行分割。(这里我们能保证父节点的键值不满，否则他在之前会被分割。) 如果键值 k 比 childi的中间值大，则进入分割后的右子节点，否则进入分割后的左子节点，再跳转到第二步。
以上是插入过程的大致思想。
####键值删除####
键值的删除对比键值插入需要考虑的情况更多，因为被删除的键值可能在任何位置，可能在内部节点也可能在叶节点，如果待删除的键值在内部节点，那么我们可以删除子树上的某个合适的键值，然后用被子树上被删除的键值替换当前节点上原本需要被删除的键值。
和前面插入过程类似，这里也采用一种主动式的方法，即限制所有潜在的待删除节点的键值个数比下限至少多一，这样保证如果该节点上的某个键值被删除之后仍然符合条件，不需要额外的回溯。
下面根据具体的实现，对算法进行简要的描述。
这里假设待删除的节点都在树上。
#####第一步#####
找到合适的键值 keyi ，假设待删除的键值为 k ，使得 keyi-1 < k <= keyi ，那么可以知道 键值 k 要么就在当前节点，要么在子节点 childi 上（如果当前节点不为叶节点）
#####第二步#####
如果当前节点为叶节点，则删除待删除的键值。(这里需要考虑当前节点是否为根节点，如果为根节点，且键值个数为 1, 则删除之后，根节点为空。) 删除过程结束。
#####第三步#####
如果当前节点不为叶节点，且待删除的键值在当前节点，即待删除的键值 k = keyi 。
首先判断 childi的节点的键值个数是否比下限大，如果是，则递归的删除 childi上的最后一个键值，并将当前节点的 keyi 更新为 childi的最后一个键值，这样达到删除 keyi的目的。
如果 childi 的键值个数不比下限大，则查看 childi+1的键值个数是否比上限大，如果是，递归的删除 childi+1 的第 1 个键值，并将当前节点的 keyi 更新为 childi+1 的第一个键值。
如果 childi 和 childi+1 的键值个数都刚好为下限。则将 keyi下移，与 childi 和 childi+1 合并为一个节点，再递归的删除合并后的节点上的键值 k (即原先节点的键值 keyi)。(这里可能当前节点为树的根节点，如果根节点原先只有一个键值，合并之后根节点要下移一层）
#####第四步#####
如果当前节点为内部节点，且待删除的键值 k 不在当前节点内，根据第一步即 k < keyi ，则待删除的节点肯定在 childi上。
首先判断 childi 的键值个数是否比下限大，如果是，递归的删除以 childi 为根的子树上的键值 k。
如果 childi 的键值个数为下限， 查看 childi-1的节点是否比下限大，如果是，将 childi-1的最后一个节点移到 keyi-1 ，将原先 keyi-1的值移到childi的键值之首 (注意这里移动键值的同时子节点要一并移动）。然后递归的删除以 childi 为根的子树上的键值 k 。
如果 childi-1的键值个数也为下限值。查看 childi+1 的键值个数是否比下限大，如果是，将 childi+1的第一个键值移动到 keyi 。然后将键值 keyi 移动到 childi 之尾 （同样要注意移动子节点）。再递归的删除以 childi 为根的子树上的键值 k 。
如果 childi-1 和 childi+1 上的键值个数都刚好为下限，则将 childi-1 与 childi合并 （或者 childi 与 childi+1 合并）。然后递归的删除以合并后的节点为根的子树上的键值 k。(这里可能当前节点为树的根节点，如果根节点原先只有一个键值，合并之后根节点要下移一层）
####总结####
以上是针对B树的简要记述，感觉需要考虑的情况比较多，导致实现起来也比较繁琐。这里是简要的源码实现
####引用####
算法导论上B树介绍
从B树、B+树、B*树谈到R 树