B_树的插入、删除、查找的算法(C语言描述).doc
5星 · 超过95%的资源 需积分: 11 185 浏览量
2013-05-19
20:00:24
上传
评论
收藏 442KB DOC 举报 
B-树的插入、查找、删除算法（C 语言描述）
前面讨论的查找都是内查询算法，被查询的数据都在内存。当查询的数据
放在外存，用平衡二叉树作磁盘文件的索引组织时，若以结点为内外存交换的
单位，则找到需要的关键字之前，平均要进行 lgn 次磁盘读操作，而磁盘、光
盘的读写时间要比随机存取的内存代价大得多。其二，外存的存取是以“页”为
单位的，一页的大小通常是 1024 字节或 2048 字节。
针对上述特点，1972 年 R.Bayer 和 E.M.Cright 提出了一种 B-树的多路
平衡查找树，以适合磁盘等直接存取设备上组织动态查找表。B-树上算法的执
行时间主要由读、写磁盘的次数来决定，故一次 I/O 操作应读写尽可能多的信
息。因此 B-树的结点规模一般以一个磁盘页为单位。一个结点包含的关键字及
其孩子个数取决于磁盘页的大小。
一、基本概念
B-树又称为多路平衡查找树。
一棵度为 m 的 B-树称为 m 阶 B_树。一个结点有 k 个孩子时，必有 k-1 个关键
字才能将子树中所有关键字划分为 k 个子集。B-树中所有结点的孩子结点最大
值称为 B-树的阶，通常用 m 表示。从查找效率考虑，一般要求 m≥3。一棵 m
阶的 B-树或者是一棵空树，或者是满足下列要求的 m 叉树：
（1）根结点或者为叶子，或者至少有两棵子树，至多有 m 棵子树。
（2）除根结点外，所有非终端结点至少有 ceil(m/2)棵子树，至多有 m 棵子
树。
（3）所有叶子结点都在树的同一层上。
（4）每个结点的结构为：
（n，A0，K1，A1，K2，A2，…，Kn，An）
其中，Ki(1≤i≤n)为关键字，且 Ki<Ki+1(1≤i≤n-1)。
Ai(0≤i≤n)为指向子树根结点的指针。且 A
i
所指子树所有结点中的关键字均小
于 K
i+1
。An 所指子树中所有结点的关键字均大于 Kn。
n 为结点中关键字的个数，满足 ceil(m/2)-1≤n≤m-1。
比如，一棵 3 阶 B-树，m=3。它满足：
（1）每个结点的孩子个数小于等于 3。
（2）除根结点外，其他结点至少有=2 个孩子。
（3）根结点有两个孩子结点。
（4）除根结点外的所有结点的 n 大于等于=1，小于等于 2。
剩余12页未读，继续阅读
资源评论
ymyymh2014-01-14代码风格不错，讲的很详细
向前向后2013-10-28很详细，讲的简单易懂。- qq_289936792015-06-13很不错，程序对我很有帮助。。。讲的 清楚明了，很容易理解。。
- only_AU2013-07-03很有参考价值很好
