题外话：在博客园看了几篇关于B树的博文确实很有帮助，但是也看到有一些Funny的博文- -比如拿二叉树堂（BinaryTree）而皇之写上B树的帽子。
好了题归正传，B树（Balanced-Tree）与红黑树的主要不同在于，B树的节点可以有许多子女，从几个到几千个。这就是说，B树的分支因子可能会非常的大，这一分支因子往往又是由磁盘所决定的，B树与红黑树的相似之处在于，每棵含N个节点的B树的高度为O（lgn），但可能要比一棵红黑树的高度小很多，也就是意味着递归向下访问时的地址堆栈段可以节省一定的空间，因其分支因子比较大，所以B树也可以用来在O（logN）时间内，实现许多动态集合操作。
B树的几个必要的属性定义如下：
（1）首先是最重要的B树的度数，每一个B树的节点的关键字的个数不允许少于t-1个，也不允许大于2t-1个。个人讲不得不说设计B树的人实在是功夫高深，t-1和2t-1这一对神奇的数字正好构成了B树的完美分裂和合并过程。
（2）从数据结构的角度来讲，每一个B树节点的数据存储域在于一个保存关键字的个数n和一个保存子节点指针数组c[]，另外一个重要的域是布尔值leaf用于表示该节点是否是一个内节点/根节点/叶结点。
一.B树的创建为以下几个步骤：
（a）在内存/进程堆中寻找一段空闲的空间来创建一个新的B树
（b）将该节点的leaf域置为true（该节点既是根节点也是叶结点），并且将n域置为0说明这是一个空的根节点，内部并没有关键字
（c）写入磁盘储存
二.B树的搜索过程（简单的递归过程，这里不多赘述）
三.B树的插入关键字过程分支步骤如下：不妨假设访问某一个个节点的函数为（r，k）k为需要新加入的关键字
首先需要判断当前访问到的节点的关键字个数是否满足2t-1个
Y：对当前访问到的节点及进行一次分裂的操作，即将该满节点的中间序关键字提升，如果并没有父节点的话新创建一个父节点并且将其加入至新的节点，如果有父节点 的话即将该中间序关键字提升一个高度
N：直接进行遍历的向下递归访问插入操作，每向下访问一级都需要检查该节点是否为叶结点和关键字个数是否已经满，如果满节点的话再进行一次分裂中间序关键字提 升高度的操作，因为之前访问到的每一个节点都是经过了处理所以不会出现提升高度的关键字被插入关键字个数已经等于2t-1的父节点之中的情况。
//////////////////////////////////////////////////////
//图书馆要关门撵人了 回寝室继续更新
/////////////////////////////////////////////////////////
---恢复内容结束---
<算法导论>高级数据结构--以我的角度看B树（Balanced-Tree）的建增删查
原文：http://www.cnblogs.com/guguli/p/4364133.html