9.3.2 B-树.pptVIP

§ 9.3.2 B-树 1.概念 B-树是一种完全平衡的多阶查找树，主要是作为磁盘文件的索引组织，用于外部查找。 基本想法是增大结点来降低树高，减少访问外存的次数 一棵m阶B-树，每个结点最多有m个孩子，m一般为50－2000 例如，1棵1001阶B-树，3层即可包含10亿以上的Keys，当根结点置于内存时，查找任一Key至多只要访问2次外存。 § 9.3.2 B-树 定义：一棵m(m≥3)阶的B-树是满足下述性质的m叉树： 性质1：每个结点至少包含下列数据域：(j, P0, K1, P1, K2, … , Kj , Pj ) j：keys总数， Ki：关键字， Pi：指针 keys(P0) K1 keys(P1) K2 … Kj keys(Pj) 性质2：所有叶子在同一层上，叶子层数为树高h，叶子中的指针为空。 性质3：每个非根结点中的关键字数目j满足： 即：每个非根的内部结点的子树数在m和 之间 性质4：非空的B－树中，根至少有1个关键字。 即：根不是叶子时，子树数为：2～m之间 § 9.3.2 B-树 运算 查找 多路查找：先在结点内查找（折半或顺序），后在子结点中查找（读盘） 插入和生成 平衡机制：满时插入分裂结点，从叶子 根，树高可能长 一层 删除 平衡机制：半满时删除，可能要合并结点，从叶子 根， 树高可能减一层 根据m阶B_树的定义，结点的类型定义如下： #define M 5 /* 根据实际需要定义B_树的阶数 */ typedef struct BTNode { int keynum ; /* 结点中关键字的个数 */ struct BTNode *parent ; /* 指向父结点的指针 */ KeyType key[M+1] ; /* 关键字向量,key[0]未用 */ struct BTNode *ptr[M+1] ; /* 子树指针向量 */ RecType *recptr[M+1] ; /* 记录指针向量,recptr[0]未用 */ }BTNode ; 2 B_树的查找 由B_树的定义可知，在其上的查找过程和二叉排序树的查找相似。 ⑴ 算法思想 ① 从树的根结点T开始，在T所指向的结点的关键字向量key[1…keynum]中查找给定值K(用折半查找) ： 若key[i]=K(1≤i≤keynum)，则查找成功，返回结点及关键字位置；否则，转⑵； ② 将K与向量key[1…keynum]中的各个分量的值进行比较，以选定查找的子树： ◆ 若Kkey[1]：T=T-ptr[0]； ◆ 若key[i]Kkey[i+1](i=1, 2, …keynum-1)： T=T-ptr[i]； ◆ 若Kkey[keynum]：T=T-ptr[keynum]； 转①，直到T是叶子结点且未找到相等的关键字，则查找失败。 ⑵ 算法实现 int BT_search(BTNode *T, KeyType K, BTNode *p) /* 在B_树中查找关键字K, 查找成功返回在结点中的位置 */ /* 及结点指针p; 否则返回0及最后一个结点指针 */ { BTNode *q ; int n ; p=q=T ; while (q!=NULL) { p=q ; q-key[0]=K ; /* 设置查找哨兵 */ for (n=q-keynum ; Kq-key[n] ; n--) if (n0EQ(q-key[n], K) ) return n ; q=q-ptr[n] ; } return 0 ; } ⑶ 算法分析 在B_树上的查找有两中基本操作： ◆ 在B_树上查找结点(查找算法中没有体现)； ◆ 在结点中查找关键字：在磁盘上找到指针ptr所指向的结点后，将结点信息读入内存后再查找。因此，磁盘上的查找次数(待查找的记录关键字在B_树上的层次数)是决定B_树查找效率的首要因素。 根据m阶B_树的定义，第一层上至少有1个结点，第二层上至少有2个结点；除根结点外，所有非终端结点至少有?m/2?棵子树，…，第h层上至少有?m/2?h-2个结点。在这些结点中：根结点至少包含1个