什么是B-树
B-树可以看作二叉搜索树的推广，不同之处在于B-树的结点可以有很多孩子，也就是相同的结点数，B-树比起一般的二叉树深度会小很多。
为什么要B-树
B-树是为磁盘或者其他直接存取的辅助存储设备而设计的一种平衡搜索树。B-数在降低磁盘I/O操作数方面要好一些，所以许多数据库系统使用B-树或者B-树的变种来存储信息。
在典型的B-树应用中，所处理的数据量非常大，无法全部装入主存中，又因为磁盘的操作要远远慢于主存的操作，所以，B-树的运行时间主要是DISK-READ和DISK-WRITE的次数决定的。
为了让这些操作能读或者写尽可能多的信息，所以一个B-树结点通常和一个完整磁盘页一样大。
B-树的性质
一般来说，B-树为每个关键字存放一个指针，这个指针指向存放这个关键字对应的卫星数据的磁盘页。
每个结点x有一下属性：
a. x.n代表存储的关键字的个数
b. x.n个关键字x.key1…x.keyn，非降序存放
c. x.leaf指示x是否为叶结点
每个内部结点x包含x.n+1个指向孩子的指针x.c1…x.c(n+1)，叶子结点没有孩子
所有叶结点都是相同高度的
每个结点包含的关键字个数存在一个上界和下界，用B-树的最小度数整数t（>=2）表示
a. 除根结点外，每个结点至少要有t-1个关键字
b. 每个结点至多有2t-1个关键字
###B-树的高度
对于任意一棵包含n个关键字、高度为h，最小度数>=2的B-树，有
$$h \le \log_t \frac{n+1}{2}$$