第9章 查找 - 2.ppt

第9章 查找 9.1 静态查找表 9.2 动态查找表 9.3 哈希表 9.2.2 B-树和B+树 1. B-树及其查找 2. B-树查找分析 3. B-树的插入和删除 4. B+树 9.2.2 B-树和B+树 前面介绍的平衡二叉树在需要查找的数据（紫癜）足够小（可以整个装载在内存中）时，可以有效地进行查找。 对于更大量的数据，如何有效地实现查找？ 1. B-树及其查找 B-树是一种平衡的多路查找树，在文件系统中很有用。 定义：m 阶 B-树或为空树，或为满足下列性质的m叉树： A、根结点如果不是叶结点，至少有两个儿子 B、除根结点和叶结点之外，每个结点的儿子个数 n 为: m/2 = n = m C、有 n+1 个儿子的结点具有 n 个关键字。 这些结点的数据信息为： （n, P0, K1, D1, P1, K2, D2, P2, ……… Kn, Dn, Pn） 这里：n: 关键字的个数 P0： key K1 的结点的地址（指在该 B-树中） K1：关键字 D1：关键字 = K1 的数据记录的信息 P1： K1 且 K2 的结点的地址（指在该 B-树中） 余类推 ……… Pn： Kn 的结点的地址（指在该 B-树中） 注意：K1 K2 …... Kn D、所有的叶子结点都出现在同一层上。 1. B-树及其查找 例如：m = 4 阶 B-树。除根结点和失败结点之外，每个结点的儿子个数至少为m/2 = 2 个；结点的关键字个数至少为 1 。 1. B-树及其查找 #define m 3 Typedef struct BTNode{ int keynum; struct BTNode *parent; KeyType key[m+1]; struct BTNode *ptr[m+1]; Record *recptr[m+1]; } BTNode, *BTree; typedef struct{ BTNode *pt; int i; int tag; }Result; 1. B-树及其查找 查找过程，类似于二叉树的查找。如查找关键字为 KEY 的记录。 从根开始查找，如果 Ki = KEY 则查找成功，Di 为关键字为 KEY 的记录的地址。 若 Ki KEY Ki+1; 查找 Pi指向的结点 若 KEY K1; 查找 P0 指向的结点 若 KEY Kn; 查找 Pn指向的结点 若 找到叶子，则查找失败。 注意：每次查找将去掉 （s-1）/s 个分支，比仅仅丢掉一半分支还要快。 1. B-树及其查找 Result SearchBTree( BTree T, KeyType K){ p = T; q = NULL; found = FALSE; i=0; while( p!found){ i = Search( p, K); // 在p-key[1…keynum]中查找 // i 使得p-key[i]=Kp-key[i+1] if( i0p-key[i] == K) found = TRUE; else{ q = p; p = p-ptr[i];} } if( found) return( p, i, 1); // 查找成功 else return( q, i, 0); // 不成功，返回插入点 } 2. B-树查找分析 在B-树上进行查找包含两种基本操作： 在B-树中找节点； 在节点中找关键字 通常B-树存储在磁盘上，操作1需要在磁盘上进行，操作2在内存中进行。 提高效率的关键是减少磁盘读写的次数，即B-树的高度应该尽可能小。 2. B-树查找分析 设关键字的总数为 N ，求 m 阶 B-树的最大层次 h+1。 层次 结点数（最少） 关键字的个数（最少） 1 1 1 2 2 2(ceil(m/2) -1) 3 2ceil(m/2) 2ceil(m/2)ceil(m/2-1) 4 2ceil(m/2)2 2ceil(m/2)2ceil(m/2 -1) h 2ceil(m/2)h-2 2ceil(m/2)h-2ceil(m/2 -1) h+1 2ceil(m/2)h-1 所以，N =1＋ 2(ceil(m/2) -1) +……...+ 2ceil(m/2)h-2ceil(m/2 -1) = 2ceil(m/2)