动态查找表_图文.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1 35 1 18 1 11 1 27 1 39 3 47 64 F 58 1 99 2 43 78 F F F F F F F F F F F B-树的查找类似于二叉树的查找 二、B-树的查找 查找47 1 35 1 18 1 11 1 27 1 39 3 47 64 F 58 1 99 2 43 78 F F F F F F F F F F F B-树的查找类似于二叉树的查找 二、B-树的查找 查找30 B-树查找算法 result srch_mbtree(mblink t; keytp k){ //在B-树中查找k p=t; q=NULL; i=0; //初始化 while ( p ) { i=Search(p,k); //在p-key[1..n]中进行查找, //直至p-key[i] = k p-key[i+1] 止, 0=i=n if ( (i0)(p-key[i]==K)) return(p,i,1)；//查找成功 else { q=p; p=p-ptr[i]; } } return(q,i,0)//查找不成功, 返回插入位置信息 } //srch_mbtree 三、B-树查找分析 B-树主要用作文件的索引，因此，它的查找涉及到外存的存取。 B-树通常存储在磁盘上。 从上述算法可知：在B-树上进行查找包含两种基本操作：(1)在B-树中找结点；(2)在结点中找关键字。 因此，第(1)步查找操作是在磁盘上进行的。第(2)是在内存中进行的。即在磁盘上找到指针p所指结点后，先将结点中的信息读入内存，然后再利用顺序查找或折半查找查询等于K的关键字。 显然，在磁盘上进行一次查找比在内存中进行一次查找耗费时间多得多，因此，在磁盘上进行查找的次数、即待查关键字所在结点在B-树上的层次数，是决定B-树查找效率的首要因素。 考虑最坏情况，即待查结点在B-树上的最大层次数，即含N个关键字的m阶B-树的最大深度是多少？ 三、B-树查找分析 设关键字的总数为 N ，求 m阶 B-树的最大层次 L。 层次 结点数 1 1 2 2 3 2（ m/2 ） 4 2（ m/2 ） 2 ……... ……... ……... ……... L 2（ m/2 ）L-2 L+1 2（ m/2 ）L-1 （这一层是叶子层，若m阶B-树中有N个关键字，则查找不成功的结点为N+1) 所以，N+1≥2 *( m/2 L-1 ) (N=1＋ 2 ＋ 2（ m/2 -1） +……...+ 2（ m/2 ）L-2 = 2 m/2 L-1 -1 故：L＝log m/2 （（N+1）/2 + 1） 设 N ＝1000000 且 m＝256 ，则 L = 3； 最多 3 次访问外存可找到所有的记录。 四、B-树的插入 1 35 1 18 1 11 2 27 1 39 3 47 64 F 58 1 99 2 43 78 F F F F F F F F F F F F 30 注意：叶子要在同一层上。 插入 插入30 四、B-树的插入 1 35 1 18 1 11 2 27 1 39 3 47 64 F 58 1 99 2 43 78 F F F F F F F F F F F F F 30 问题：若插入一元素时，使得某一结点m叉？ 例如插入60。 解决方法：分裂！将一个结点分成两个结点。 B-树插入举例：2-3树（3阶B-树）及插入。 （1）插入14； B-树插入举例：2-3树（3阶B-树）及插入。 （2）插入55； （3）插入19 例：2-3 树的删除操作。 3 24 45 53 90 37 100 50 61，70 删50 3 24 45 61 90 37 100 53 70 再删除53 3 24 45 90 37 100 61，70 再删除37 3，24 45 90 100 61，70 3，24 45 90 100 61，70 合并 合并 合并 五、B-树的删除 8.2.4 B+树 B+树是 B-树的变形树。在实现文件索引结构方法比B-树使用得更