RecType *recptr[M+1] ; /* 记录指针向量，recptr[0]未用 */
struct BTNode *parent ; /* 指向父结点的指针 */
struct BTNode *ptr[M+1] ; /* 子树指针向量 */
} BTNode;
数据结构
5
B-树的查找过程
例：查找26 查找100
插入53
插入75
插入139
75
插入49,145
75
53
53 75
53 139 49 53 139 145
插入36
49 75 36 53 139 145
数据结构
插入101
49
75 139
36 53 101 145
12
B-树的删除操作
• 在B-树上删除一个关键字，首先应找到该关键字所在结点， 并从中删除之：
• 若该结点为最下层的非终端结点，且其中的关键字数目不少 于m/2，则删除完成，否则要进行“合并”结点的操作；
• 若所删关键字为非终端结点中的Ki，则可以指针Ai所指子树 中的最小关键字Y代替Ki ，然后在相应结点中删去Y。
• 讨论删除最下删层除5非5
B-树的结点类型定义
• 根据m阶B-树的定义，结点类型定义如下：
#define M 5 /* 根据实际需要定义B_树的阶数 */
typedef struct BTNode {
int keynum ;
/* 结点中关键字的个数 */
KeyType key[M+1] ;
/* 关键字向量,key[0]未用 */
第12讲 多路查找树、哈希表
• B-树和B+树
• 哈希表
数据结构
1
树形索引表
• 平衡二叉排序树便于动态查找，因此用平衡二叉排序树来 组织索引表是一种可行的选择。当用于大型数据库时，所 有数据及索引都存储在外存，因此，涉及到内、外存之间 频繁的数据交换，这种交换速度的快慢成为制约动态查找 的瓶颈。
• 若以二叉树的结点作为内、外存之间数据交换单位，则查 找给定关键字时对磁盘平均进行(㏒2n)次访问是不能容忍 的，因此，必须选择一种能尽可能降低磁盘I/O次数的索引 组织方式。树结点的大小尽可能地接近页的大小。
• 如果双亲结点原来也是满的，则需要继续分裂和提升。最坏 的情况一直到根，若根也要分裂，由于它没有双亲，就要另 外建立一个新的根结点，整个B-树增加一层。
• 比较：二叉排序树插入的结点可在任何层。
数据结构
9
B-树的插入操作
数据结构
10
11
3阶B-树的生成
• B-树的生成也是从空树起，逐个插入关键字而得。
7
B-树查找分析
结论：在含有N个关键字的B-树上进行查找时，从 根结点到关键字所在结点的路径上涉及的结点数不 超过 logm/2 ((N+1)/2)+ 1
• 考虑最坏的情况，即待查结点在B-树的最大层次上。
• 含N个关键字的m阶B-树的最大深度是多少？
根据B-树的定义：
• 第一层至少有1个结点；第二层至少有2个结点；
• 条件(4) 结点中关键字递增排列，使B-树具有某种“中序”递增性， 可看成二叉排序树的扩充，是一种平衡多叉排序树；而子树数比关 键字个数多1，使得最终叶子数比树中所含关键字数多1。
• 条件(5) 叶子都在同一层，使B-树高度上平衡；而叶子不含关键字， 表示叶子实际上是树中并不存在的外部结点，且指向这些外部结点 的指针为空；
• 由于除根之外的每个非终端结点至少有m/2棵子树，则第三层 至少有2(m/2)个结点；… ；
• 依次类推，第l+1层至少有2(m/2) l−1个结点，而l+1层的结点为 叶子结点。
• 若m阶B-树中具有N个关键字，则叶子结点即查找不成功的结点 为N+1，由此有： N+l ≥ 2*(m/2 ) l−1
⑤ 所有的叶子结点都出现在同一层次上，并且不带信息。
数据结构
3
B-树的结构
5阶B树
30
12 25
40 62 70 85
05 10 15 19 22 26 28
35 39
43 47 55 59
65 68
73 77 81
88 93
• 条件(1)和(3)使每个结点至少半满；
• 条件(2) 使B-树不至于一开始就偏向一边；
• R.Bayer和E.Mc Creight在1972年提出了一种多路平衡查 找树，称为B-树(其变型体是B+树)。
数据结构
2
B-树的概念
• 一棵m阶的B-树，或为空树，或为满足下列特性的m叉树：
① 树中每个结点至多有m棵子树； ② 若根结点不是叶子结点，则至少有两棵子树；
③ 除根之外的所有非终端结点至少有m/2棵子树； ④ 所有的非终端结点中包含下列信息数据
② 在结点中找关键字
• 在磁盘上找到指针p所指结点后，先将结点中的信息读入内 存，因此，第2步查找操作在内存中进行；然后再利用顺序 查找或折半查找查询等于给定值的关键字。
• 由于访外（磁盘）耗时，在磁盘上进行查找的次数，即待 查关键字所在结点在B-树上的层次数，是决定B-树查找效 率的首要因素。
数据结构
反之
l ≤ log m/2 ((N+1)/2) + 1
数据结构
8
B-树的插入操作
• 每插入一个关键字不是在树中添加一个叶子结点，而 是首先在最低层的非终端结点中添加一个关键字。
• 若该结点的关键字个数不超过m−1，则插入完成；否则要产 生结点“分裂”，将位于中间的关键字提升到双亲结点，使 分裂后的两个结点大小相当，都约半满；
(n, A0, K1 , A1 , K2 , A2 , … , Kn , An)
其中：Ki (1≤i≤n)为关键字，且Ki<Ki+1 (1≤i≤n-1)；Ai(i=0, 1, … , n)为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关 键字均小于Ki (1≤i≤n)，An所指子树中所有结点的关键字均大于Kn； n( m/2 -1≤n≤m-1)为关键字的个数（或n+1为子树个数）。
root
50
类似二叉排序树的查找
15
71 84
3 8 20 26 43 56 62 78 89 96
• 在B-树上进行查找的过程是一个顺指针查找结点和在结 点的关键字中进行查找交叉进行的过程。
数据结构
6
B-树查找分析
• 两种基本操作
① 在B-树中找结点
• B-树通常存储在磁盘上，第1步查找操作在磁盘上进行。