B树

在B-树中查找给定关键字的方法是，首先把根结点取来，在根结点所包含的关键字K1,…,Kn查找给定的关键字（可用顺序查找或二分查找法），若找到等于给定值的关键字，则查找成功；否则，一定可以确定要查找的关键字在Ki与Ki+1之间，Pi为指向子树根节点的指针，此时取指针Pi所指的结点继续查找，直至找到，或指针Pi为空时查找失败。

定义

1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树（或B-树、B_树）。

一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：

1、根结点至少有两个子女；

2、每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；

3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：┌m/2┐ <= k <= m ；

4、所有的叶子结点都位于同一层。

在B-树中，每个结点中关键字从小到大排列，并且当该结点的孩子是非叶子结点时，该k-1个关键字正好是k个孩子包含的关键字的值域的分划。

因为叶子结点不包含关键字，所以可以把叶子结点看成在树里实际上并不存在外部结点，指向这些外部结点的指针为空，叶子结点的数目正好等于树中所包含的关键字总个数加1。

B-树中的一个包含n个关键字，n+1个指针的结点的一般形式为：（n,P0,K1,P1,K2,P2,…,Kn,Pn）

其中，Ki为关键字，K1

性能分析

设B-树包含N个关键字，因此有N+1个叶子结点，叶子都在第I层。因为根至少有两个孩子，因此第二层至少有两个结点。除根和叶子外，其它结点至少有┌m/2┐个孩子，因此在第三层至少有2*┌m/2┐个结点，在第四层至少有2*(┌m/2┐^2)个结点，．．．，在第I层至少有2*(┌m/2┐^(l-2) )个结点，于是有：

N+1 ≥ 2*┌m/2┐I-2

考虑第L层的结点个数为N+1，那么2*(┌m/2┐^(l-2)）≤N+1，也就是L层的最少结点数刚好达到N+1个

即： I≤ log┌m/2┐((N+1)/2 )+2

所以，当B-树包含N个关键关键字时，B-树的最大高度为l-1（因为计算B-树高度时，叶结点所在层不计算在内）

即：log┌m/2┐((N+1)/2 )+1。

这个公式保证了B-树的查找效率是相当高的。

示例

当在叶子结点处于第L+1层的B树中插入关键字时，被插入的关键字总是进入第L层的结点。

若在一个包含j

插入算法演示：插入之前如图1：

插入之后如图2：

4. B-树的删除:

当从B-树中删除一个关键字Ki时，总的分为以下两种情况：

如果该关键字所在的结点不是最下层的非叶子结点，则先需要把此关键字与它在B-树中后继对换位置，即以指针Pi所指子树中的最小关键字Y代替Ki，然后在相应的结点中删除Y。

如果该关键字所在的结点正好是最下层的非叶子结点，这种情况下，会有以下两种可能：

① 若该关键字Ki所在结点中的关键字个数不小于┌m/2┐，则可以直接从该结点中删除该关键字和相应指针即可。

② 若该关键字Ki所在结点中的关键字个数小于┌m/2┐，则直接从结点中删除关键字会导致此结点中所含关键字个数小于┌m/2┐-1 。这种情况下，需考察该结点在B树中的左或右兄弟结点，从兄弟结点中移若干个关键字到该结点中来（这也涉及它们的双亲结点中的一个关键字要作相应变化），使两个结点中所含关键字个数基本相同；但如果其兄弟结点的关键字个数也很少，刚好等于┌m/2┐-1 ，这种移动则不能进行，这种情形下，需要把删除了关键字Ki的结点、它的兄弟结点及它们双亲结点中的一个关键字合并为一个结点。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省