东南大学数据结构_Lec012汇编

《东南大学数据结构_Lec012汇编》由会员分享，可在线阅读，更多相关《东南大学数据结构_Lec012汇编（50页珍藏版）》请在金锄头文库上搜索。

1、第12讲 多路查找树、哈希表 B-B-树和树和B+B+树树 哈希表 1 数据结构 树形索引表 平衡二叉排序树便于动态查找，因此用平衡二叉排序树来 组织索引表是一种可行的选择。当用于大型数据库时，所 有数据及索引都存储在外存，因此，涉及到内、外存之间 频繁的数据交换，这种交换速度的快慢成为制约动态查找 的瓶颈。 若以二叉树的结点作为内、外存之间数据交换单位，则查 找给定关键字时对磁盘平均进行(2n)次访问是不能容忍 的，因此，必须选择一种能尽可能降低磁盘I/O次数的索引 组织方式。树结点的大小尽可能地接近页的大小。 R.Bayer和E.Mc Creight在1972年提出了一种多路平衡查 找树，

2、称为B-树(其变型体是B+树)。 数据结构 2 B-树的概念 一棵m阶的B-树，或为空树，或为满足下列特性的m叉树 ： 树中每个结点至多有m棵子树； 若根结点不是叶子结点，则至少有两棵子树； 除根之外的所有非终端结点至少有m/2棵子树； 所有的非终端结点中包含下列信息数据 (n, A0, K1 , A1 , K2 , A2 , , Kn , An) 其中：Ki (1in)为关键字，且KiKi+1 (1in-1)；Ai(i=0, 1, , n)为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关 键字均小于Ki (1in)，An所指子树中所有结点的关键字均大于Kn ；n( m/2 -1n

3、m-1)为关键字的个数（或n+1为子树个数）。 所有的叶子结点都出现在同一层次上，并且不带信息。 数据结构 3 B-树的结构 条件(1)和(3)使每个结点至少半满； 条件(2) 使B-树不至于一开始就偏向一边； 条件(4) 结点中关键字递增排列，使B-树具有某种“中序”递增性 ，可看成二叉排序树的扩充，是一种平衡多叉排序树；而子树数比 关键字个数多1，使得最终叶子数比树中所含关键字数多1。 条件(5) 叶子都在同一层，使B-树高度上平衡；而叶子不含关键字 ，表示叶子实际上是树中并不存在的外部结点，且指向这些外部结 点的指针为空； 数据结构 4 B-树的结点类型定义 根据m阶B-树的定义，结点类

4、型定义如下： #define M 5 /* 根据实际需要定义B_树的阶数 */ typedef struct BTNode int keynum ; /* 结点中关键字的个数 */ KeyType keyM+1 ; /* 关键字向量,key0未用 */ RecType *recptrM+1 ; /* 记录指针向量，recptr0未用 */ struct BTNode *parent ; /* 指向父结点的指针 */ struct BTNode *ptrM+1 ; /* 子树指针向量 */ BTNode; 数据结构 5 B-树的查找过程 数据结构 6 在B-树上进行查找的过程是一个顺指针查找结点

5、和在结 点的关键字中进行查找交叉进行的过程。 例：查找26 查找100 类似二叉排序树的查找 rootroot 5050 15 71 84 15 71 84 3 8 20 3 8 20 2626 43 56 62 78 43 56 62 78 89 96 89 96 B-树查找分析 两种基本操作 在B-树中找结点 B-树通常存储在磁盘上，第1步查找操作在磁盘上进行。 在结点中找关键字 在磁盘上找到指针p所指结点后，先将结点中的信息读入内 存，因此，第2步查找操作在内存中进行；然后再利用顺序 查找或折半查找查询等于给定值的关键字。 由于访外（磁盘）耗时，在磁盘上进行查找的次数，即待 查关键字所在

6、结点在B-树上的层次数，是决定B-树查找效 率的首要因素。 数据结构 7 B-树查找分析 考虑最坏的情况，即待查结点在B-树的最大层次上。 含N个关键字的m阶B-树的最大深度是多少？ 根据B-树的定义： 第一层至少有1个结点；第二层至少有2个结点； 由于除根之外的每个非终端结点至少有m/2棵子树，则第三层 至少有2(m/2)个结点； ； 依次类推，第l+1层至少有2(m/2) l1个结点，而l+1层的结点为 叶子结点。 若m阶B-树中具有N个关键字，则叶子结点即查找不成功的结点 为N+1，由此有： N+l 2*(m/2 ) l1 反之 l log m/2 (N+1)/2) + 1 数据结构 8

7、 结论：在含有N个关键字的B-树上进行查找时，从 根结点到关键字所在结点的路径上涉及的结点数不 超过 logm/2 (N+1)/2)+ 1 B-树的插入操作 每插入一个关键字不是在树中添加一个叶子结点，而 是首先在最低层的非终端结点中添加一个关键字。 若该结点的关键字个数不超过m1，则插入完成；否则要产 生结点“分裂”，将位于中间的关键字提升到双亲结点，使 分裂后的两个结点大小相当，都约半满； 如果双亲结点原来也是满的，则需要继续分裂和提升。最坏 的情况一直到根，若根也要分裂，由于它没有双亲，就要另 外建立一个新的根结点，整个B-树增加一层。 比较：二叉排序树插入的结点可在任何层。 数据结构

8、9 B-树的插入操作 数据结构 10 11 3阶B-树的生成 B-树的生成也是从空树起，逐个插入关键字而得。 数据结构 12 53 插入53 53 75 插入75 75 13953 插入139 75 139 14549 53 插入49,145 49 75 139 1455336 插入36 49 5336 139 145101 75 插入101 B-树的删除操作 在B-树上删除一个关键字，首先应找到该关键字所在结点 ，并从中删除之： 若该结点为最下层的非终端结点，且其中的关键字数目不少 于m/2，则删除完成，否则要进行“合并”结点的操作； 若所删关键字为非终端结点中的Ki，则可以指针Ai所指子树

9、 中的最小关键字Y代替Ki ，然后在相应结点中删去Y。 讨论删除最下层非终端结点中的关键字的3种情形。 数据结构 13 55 5875 80104065 60 7030 a cb defgh 删除55 用用后继后继替换替换 删删后继后继 14 58 75 80104060 65 7030 a cb defh B-树的删除操作 被删关键字所在结点中的关键字数目不小于m/2，则只需从该 结点中删去该关键字Ki和相应指针Ai，树的其他部分不变。 数据结构 15 55 5875 80 m = 3 104065 60 7030 50 a cb defgh a d 5875 80104065 60 703

10、0 50 cb efgh 直接删除55 B-树的删除操作 被删关键字所在结点中的关键字数目等于m/2-1，而与该结点相 邻的右兄弟(或左兄弟)结点中的关键字数目大于m/2-1，则需将其 兄弟结点中的最小(或最大)的关键字上移至双亲结点中，而将双亲 结点中小于(或大于)且紧靠该上移关键字的关键字下移至被删关键 字所在结点中。 数据结构 16 55 5875 80104065 60 7030 50 a cb defgh 删除65 55 5880104070 60 7530 50 a cb defgh 移动移动 B-树的删除操作 被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于 m/2-1。

11、假设该结点有右兄弟(Ai所指)，则在删去关键字之后，它 所在结点中剩余的关键字和指针，加上双亲结点中的关键字Ki一 起，合并到Ai所指兄弟结点中。 数据结构 17 5580104060 58 7530 50 a cb defgh 删除55 18 合并合并 58 60801040 7530 50 a cb defh B-树的删除操作 双亲拿出关键字后，双亲可能要合并，并可能一直传播到根；如果根只一 个关键字，则下移与两孩子合并后，形成新根结点，整个树减少一层。 数据结构 19 58 80104060 6530 a cb d efh 删除10 8030 4060 fh 58 65 d b B+树的

12、概念 B+树是应文件系统所需而出的一种B-树的变型树。 一棵m阶的B+树和m阶的B-树的差异在于： 有n棵子树的结点中含有n个关键字； 所有的叶子结点中包含了全部关键字的信息，及指向含这些 关键字记录的指针，且叶子结点本身依关键字的大小自小而 大顺序链接； 所有的非终端结点可以看成是索引部分，结点中仅含有其子 树(根结点)中的最大(或最小)关键字。 数据结构 20 B+树的结构 B+树有两个头指针：一个指向根结点，另一个指向关键字最小的 叶子结点。因此，可以对B+树进行两种查找运算： 从最小关键字开始进行顺序查找； 从根结点开始进行随机查找。 数据结构 21 B+树的查找、插入和删除 对B+树

13、不仅可以从根结点开始按关键字随机查找，而且可以从 最小关键字起，按叶子结点的链接顺序进行顺序查找。在B+树 上进行随机查找、插入、删除的过程基本上和B-树类似。 查找时，若在非终端结点上找到，并不终止查找，而是继续向下查 找直至叶子。在B+树中，不管查找成功与否，每次都是走了一条 从根到叶结点的路径。 插入仅在叶结点上进行。当结点中的关键字个数大于m时要分裂成 两个结点，它们所含关键字的个数分别为(m+1)/2和(m+1)/2 ， 并且，它们的双亲结点中应同时包含这两个结点的最大关键字。 删除也仅在叶结点上进行。当叶子结点中的最大关键字被删除时， 其在非终端结点中的值可以作为一个“分界关键字”

14、存在（即不必删 除）。若因删除而使结点中关键字的个数少于m/2时，要和该结 点的兄弟结点进行合并。 数据结构 22 第12讲 多路查找树、哈希表 B-树和B+树 哈希表哈希表 23 数据结构 引言 记录在线性表、树等结构中的相对位置是随机的，和记录的关 键字之间不存在确定的关系，因此，在结构中查找记录时需进 行一系列和关键字的比较。这一类查找方法建立在“比较”的 基础上。查找效率依赖于查找过程中进行比较的次数。 在顺序查找时，比较的结果为“=”与“”两种可能； 在折半查找、二叉排序树查找和B-树查找时，比较的结果为“”3种可能。 是否可以不作比较就直接得到记录的存储地址，从而找到所要 的结点呢

15、？ 回答是肯定的，这就是散列技术。 基本思想：在记录的存储地址和它的关键字之间建立一个确定 的对应关系；不经过任何比较，一次存取便能得到所查记录。 数据结构 24 什么是哈希表 在记录的存储位置和它的关键字之间建立一个确定的对应关系 f ，使每个关键字和结构中一个惟一的存储位置相对应。在查找 时，只要根据这个关系 f 找到给定值K的像 f(K)。若结构中存在 关键字和 K 相等的记录，则必定在 f(K) 的存储位置上。称这个 对应关系 f 为哈希(Hash)函数，按这个思想建立的表为哈希表。 对于不同的关键字可能得到同一哈希地址，即key1key2，而 f(key1) = f(key2)，这种现象称冲突。 具有相同函数值的关键字对该哈希函数来说称做同义词。 根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像 到一个有限的连续的地址集(区间)上，并以关键字在地址集中的 “像”作为记录在表中的存储位置，这种表便称为哈希表，这一映 像过程称为哈希造表或散列，所得存储位置称哈希地址或散列 地址。 数据结构 25 一个哈