数据结构 查找 动态查找表二

（3）B-树

from：http://student.zjzk.cn/course_ware/data_structure/web/chazhao/chazhao9.3.2.1.htm

　当查找的文件较大，且存放在磁盘等直接存取设备中时，为了减少查找过程中对磁盘的读写次数，提高查找效率，基于直接存取设备的读写操作以"页"为单位的特征。
1972年R.Bayer和E.M.McCreight提出了一种称之为B-树的多路平衡查找树。它适合在磁盘等直接存取设备上组织动态的查找表。

1.定义

一棵m(m≥3)阶的B-树是满足如下性质的m叉树：
(1)每个结点至少包含下列数据域：
(j，P₀，K_l，P₁，K₂，…，K_i，P_i)
　　其中：
j为关键字总数
K_i(1≤i≤j)是关键字，关键字序列递增有序：K₁ <K₂<…<K_i。
P_i(0≤i≤j)是孩子指针。对于叶结点，每个P_i为空指针。
(2)所有叶子是在同一层上，叶子的层数为树的高度h。
(3)每个非根结点中所包含的关键字个数j满足： 。即每个非根结点至少应有 个关键字，至多有m-1个关键字。
(4)若树非空，则根至少有1个关键字，故若根不是叶子，则它至少有2棵子树。根至多有m-1个关键字，故至多有m棵子树。

注意：

(1) 每个节点的结构是n个指向子节点的指针和n个key，其中的n在节点中有记录。

(2) 对于磁盘上一棵较大的B-树，通常每个结点拥有的孩子数目(即结点的度数)m为50至2000不等。

(3) 一棵度为m的B-树称为m阶B-树。

(4) 选取较大的结点度数可降低树的高度，以及减少查找任意关键字所需的磁盘访问次数。

B-树的查找：有两个基本步骤：

①在B-树中查找结点，该查找涉及读盘DiskRead操作，属外查找；（在B-树中找节点，要求高度越小越好）

②在结点内查找，该查找属内查找。（在节点中找关键字，顺序查找或者折半查找）

查找操作的时间为：

①外查找的读盘次数不超过树高h，故其时间是O(h)；

②内查找中，每个结点内的关键字数目keynum<m(m是B-树的阶数)，故其时间为O(nh)。

注意：

①实际上外查找时间可能远远大于内查找时间。

②B-树作为数据库文件时，打开文件之后就必须将根结点读人内存，而直至文件关闭之前，此根一直驻留在内存中，故查找时可以不计读入根结点的时间。

程序略。

（4）B+树

应文件系统的需要对B-树的变形。

与B-树的差异在于：

a. 有n棵子树的节点中包含n个关键字。

b. 所有的叶子节点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序连接。

c. 所有的非终端节点可以看成是索引部分，节点中仅含有其子树（根结点）中的最大（或最小）关键字。