前言
正文
一, B树
1, B树的基本性质
B树,又称多路平衡查找树,B树中所有结点的孩子结点数的最大值称为B树的阶,通常用m表示。一棵m阶B树或为空树,或为满足如下特性的m叉树;
- 树中每个结点至多有m颗子树(即至多含有m-1个关键字)。
- 若根结点不是终端结点,则至少有两颗子树。
- 除根结点外的所有非叶结点至少有[m/2]颗子树(即至少含有[m/2] - 1个关键字)。
2, B树的高度(磁盘存取次数)
若n>=1, 则对任意一棵包含n个关键字,高度为h,阶数为m的B树:
- 因为B树中每个结点最多有m颗子树,m-1个关键字,所以在一棵高度为h的m阶B树中关键字的个数字的个数应满足:
n <= (m-1)(1 + m + m^2 +...+ m^(h-1))= m^h -1
即： h>= logm^(n+1)
- 若让每个结点中的关键字个数达到最少,则容纳同样多关键字的B树的高度达到最大。由B树的定义:第一层至少有1个结点,第二层至少有2个结点;除根结点外的所有非终端结点至少有[m/2]个结点… ,第h+1层至少有2(m/2)^(h-1)个结点,注意到第h+1层是包含任何信息的节点。对于关键字个数为n的B树,叶结点即查找不成功的结点为n+1,由此有n+1 >= 2(m/2)^(h-1),即h<= log[m/2]^((n+1)/2)+1。
例如:
假设一棵3阶B树共有8个关键字,则其高度范围为 2<= h <= 3.17。
3,B树的查找
在B树上进行查找与二叉树查找树很相似,只是每个结点都是多个关键字的有序表,在每个结点上所做的不是两路分支决定,而是根据该结点的子树所做的多路分支决定。
B树的查找包含两个基本操作:①在B树中找结点;②在结点内找关键字。由于B树常储存在磁盘上,因此前一个查找查找是在磁盘上进行的,而后一个查找操作是在内存中进行的,即在找到目标结点后,先将结点中的信息读入内存,然后采用顺序查找法或者折半查找法查找等于K的关键字。
在B树上查找到每个结点后,先在有序表中进行查找,若找到则查找成功,否则按照对应的指针信息到所指的子树中去查找.查找到叶结点时,则说明树中没有对应的关键字,查找上班。
4. B树的插入
与二叉查找树的插入操作相比,B树的插入操作要复杂得多。在二叉查找树中,仅需查找到需插入的终端结点的位置。但是,在B树中找到插入的位置后,并不能简单地将其添加到终端结点中,因为此时可能会导致整颗树不再满足B树定义的要求。将关键字key插入B树的过程如下:
- 定位。利用前术的B树查找算法,找出插入该关键字的最底层中的某个非叶结点(注意,B树中的插入关键字一定插入在最底层中某个非叶结点内)。
- 插入。在B树中,每个非失败结点的关键字个数都在区间[(m/2)-1, m-1]内,插入后的结点关键字个数小于m,可以直接插入;插入后检查被插入结点内关键字的个数,当插入后的关键字个数大于m-1时,必须对结点进行分裂。
分裂的方法是: 取一个新结点,在插入key后的原结点,从中间位置将其中的关键字分为两部分,左部分包含的关键字放在原结点中,右部分包含的关键字放到新结点中,中间位置(m/2)的结点插入原结点的父结点。若此时导致其父结点的关键字个数也超过了上限,则继续继续这种分裂操作,直至这个过程传到根结点为止。进而导致B树高度增1.
对于m=3的B树,所有结点中最多有m-1=2个关键字,若某结点中已有两个关键字,则结点已满, 下图。插入一个关键字60后,结点内的关键字个数超过了m-1.
5, B树的删除
B树中的删除操作与插入操作类似,但要稍微复杂一些,
