东南大学数据结构-Lec012

第12讲多路查找树、哈希表B-树和B+树哈希表1数据结构树形索引表平衡二叉排序树便于动态查找，因此用平衡二叉排序树来组织索引表是一种可行的选择。当用于大型数据库时，所有数据及索引都存储在外存，因此，涉及到内、外存之间频繁的数据交换，这种交换速度的快慢成为制约动态查找的瓶颈。若以二叉树的结点作为内、外存之间数据交换单位，则查找给定关键字时对磁盘平均进行(㏒2n)次访问是不能容忍的，因此，必须选择一种能尽可能降低磁盘I/O次数的索引组织方式。树结点的大小尽可能地接近页的大小。R.Bayer和E.McCreight在1972年提出了一种多路平衡查找树，称为B-树(其变型体是B+树)。数据结构2B-树的概念一棵m阶的B-树，或为空树，或为满足下列特性的m叉树：树中每个结点至多有m棵子树；若根结点不是叶子结点，则至少有两棵子树；除根之外的所有非终端结点至少有

m/2

棵子树；所有的非终端结点中包含下列信息数据(n,A0,K1,A1,K2,A2,…,Kn,An)

其中：Ki(1≤i≤n)为关键字，且Ki<Ki+1(1≤i≤n-1)；Ai(i=0,1,…,n)为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki

(1≤i≤n)，An所指子树中所有结点的关键字均大于Kn；n(

m/2

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

BTNode{intkeynum; /*结点中关键字的个数*/KeyTypekey[M+1]; /*关键字向量,key[0]未用*/RecType*recptr[M+1];/*记录指针向量，recptr[0]未用*/structBTNode*parent;/*指向父结点的指针*/structBTNode*ptr[M+1];/*子树指针向量*/}BTNode;数据结构5B-树的查找过程数据结构6在B-树上进行查找的过程是一个顺指针查找结点和在结点的关键字中进行查找交叉进行的过程。例：查找26查找100

类似二叉排序树的查找root50157184382026435662788996B-树查找分析两种基本操作在B-树中找结点B-树通常存储在磁盘上，第1步查找操作在磁盘上进行。在结点中找关键字在磁盘上找到指针p所指结点后，先将结点中的信息读入内存，因此，第2步查找操作在内存中进行；然后再利用顺序查找或折半查找查询等于给定值的关键字。由于访外（磁盘）耗时，在磁盘上进行查找的次数，即待查关键字所在结点在B-树上的层次数，是决定B-树查找效率的首要因素。数据结构7B-树查找分析考虑最坏的情况，即待查结点在B-树的最大层次上。含N个关键字的m阶B-树的最大深度是多少？

根据B-树的定义：第一层至少有1个结点；第二层至少有2个结点；由于除根之外的每个非终端结点至少有

m/2

棵子树，则第三层至少有2(

m/2)个结点；…；依次类推，第l+1层至少有2(

m/2)

l−1个结点，而l+1层的结点为叶子结点。若m阶B-树中具有N个关键字，则叶子结点即查找不成功的结点为N+1，由此有：N+l≥2*(

m/2)

l−1

反之

l≤log

m/2

((N+1)/2)+1数据结构8结论：在含有N个关键字的B-树上进行查找时，从根结点到关键字所在结点的路径上涉及的结点数不超过log

m/2

((N+1)/2)+1B-树的插入操作每插入一个关键字不是在树中添加一个叶子结点，而是首先在最低层的非终端结点中添加一个关键字。若该结点的关键字个数不超过m−1，则插入完成；否则要产生结点“分裂”，将位于中间的关键字提升到双亲结点，使分裂后的两个结点大小相当，都约半满；如果双亲结点原来也是满的，则需要继续分裂和提升。最坏的情况一直到根，若根也要分裂，由于它没有双亲，就要另外建立一个新的根结点，整个B-树增加一层。比较：二叉排序树插入的结点可在任何层。数据结构9B-树的插入操作数据结构10113阶B-树的生成B-树的生成也是从空树起，逐个插入关键字而得。数据结构1253插入535375插入757513953插入139751391454953插入49,14549751391455336插入3649533613914510175插入101B-树的删除操作在B-树上删除一个关键字，首先应找到该关键字所在结点，并从中删除之：若该结点为最下层的非终端结点，且其中的关键字数目不少于

m/2

，则删除完成，否则要进行“合并”结点的操作；若所删关键字为非终端结点中的Ki，则可以指针Ai所指子树中的最小关键字Y代替Ki，然后在相应结点中删去Y。讨论删除最下层非终端结点中的关键字的3种情形。数据结构1355587580104065607030acbdefgh删除55用后继替换删后继14587580104060657030acbdefhB-树的删除操作被删关键字所在结点中的关键字数目不小于

m/2

，则只需从该结点中删去该关键字Ki和相应指针Ai，树的其他部分不变。数据结构1555587580m=310406560703050acbdefghad58758010406560703050cbefgh直接删除55B-树的删除操作被删关键字所在结点中的关键字数目等于

m/2-1，而与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于

m/2-1，则需将其兄弟结点中的最小(或最大)的关键字上移至双亲结点中，而将双亲结点中小于(或大于)且紧靠该上移关键字的关键字下移至被删关键字所在结点中。数据结构165558758010406560703050acbdefgh删除6555588010407060753050acbdefgh移动B-树的删除操作被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于

m/2-1。假设该结点有右兄弟(Ai所指)，则在删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲结点中的关键字Ki一起，合并到Ai所指兄弟结点中。数据结构17558010406058753050acbdefgh删除5518合并5860801040753050acbdefhB-树的删除操作双亲拿出关键字后，双亲可能要合并，并可能一直传播到根；如果根只一个关键字，则下移与两孩子合并后，形成新根结点，整个树减少一层。数据结构1958801040606530acbdefh删除1080304060fh5865dbB+树的概念B+树是应文件系统所需而出的一种B-树的变型树。一棵m阶的B+树和m阶的B-树的差异在于：有n棵子树的结点中含有n个关键字；所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；所有的非终端结点可以看成是索引部分，结点中仅含有其子树(根结点)中的最大(或最小)关键字。数据结构20B+树的结构B+树有两个头指针：一个指向根结点，另一个指向关键字最小的叶子结点。因此，可以对B+树进行两种查找运算：从最小关键字开始进行顺序查找；从根结点开始进行随机查找。数据结构21B+树的查找、插入和删除对B+树不仅可以从根结点开始按关键字随机查找，而且可以从最小关键字起，按叶子结点的链接顺序进行顺序查找。在B+树上进行随机查找、插入、删除的过程基本上和B-树类似。查找时，若在非终端结点上找到，并不终止查找，而是继续向下查找直至叶子。在B+树中，不管查找成功与否，每次都是走了一条从根到叶结点的路径。插入仅在叶结点上进行。当结点中的关键字个数大于m时要分裂成两个结点，它们所含关键字的个数分别为

(m+1)/2

和

(m+1)/2

，并且，它们的双亲结点中应同时包含这两个结点的最大关键字。删除也仅在叶结点上进行。当叶子结点中的最大关键字被删除时，其在非终端结点中的值可以作为一个“分界关键字”存在（即不必删除）。若因删除而使结点中关键字的个数少于

m/2

时，要和该结点的兄弟结点进行合并。数据结构22第12讲多路查找树、哈希表B-树和B+树哈希表23数据结构引言记录在线性表、树等结构中的相对位置是随机的，和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上。查找效率依赖于查找过程中进行比较的次数。在顺序查找时，比较的结果为“=”与“≠”两种可能；在折半查找、二叉排序树查找和B-树查找时，比较的结果为“<”、“=”和“>”3种可能。是否可以不作比较就直接得到记录的存储地址，从而找到所要的结点呢？回答是肯定的，这就是散列技术。基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；不经过任何比较，一次存取便能得到所查记录。数据结构24什么是哈希表在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个惟一的存储位置相对应。在查找时，只要根据这个关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。称这个对应关系f为哈希(Hash)函数，按这个思想建立的表为哈希表。对于不同的关键字可能得到同一哈希地址，即key1≠key2，而f(key1)=f(key2)，这种现象称冲突。具有相同函数值的关键字对该哈希函数来说称做同义词。根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集(区间)上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为哈希表，这一映像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。数据结构25一个哈希表的简单例子数据结构2630个地区的各民族人口统计表以编号作关键字；构造哈希函数：H(key)=key

H(1)=1，H(2)=2以地区名称作关键字；取地区名称第1个拼音字母的序号作哈希函数：H(Beijing)=2

H(Shanghai)=19

H(Shenyang)=19编号省、市(区)总人口汉族回族…...1北京2上海…...…...哈希表的建造在一般情况下，哈希函数是一种压缩映象，不可避免产生冲突，只能尽量减少。因此，建造哈希表主要解决两个问题：哈希函数的构造和冲突的处理。设计一个哈希表应包括：哈希表的空间范围，即确定哈希函数的值域；构造合适的哈希函数，使得对于所有可能的元素(记录的关键字)，函数值均在哈希表的地址空间范围内，且出现冲突的可能尽量小；处理冲突的方法，即当冲突出现时如何解决。数据结构27哈希函数的构造方法哈希函数是一个映像，其设定很灵活，只要使得任何关键字由此所得的哈希函数值都落在表长允许范围之内即可。哈希函数“好坏”的主要评价因素：函数的构造简单；能“均匀”地将哈希表中的关键字映射到地址空间。若对于关键字集合中的任一个关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等的，则称此类哈希函数为均匀的哈希函数，有助于减少冲突。数据结构28常用的构造哈希函数的方法直接定址法取关键字或关键字的某个线性函数值为哈希地址。即：

H(key)=key

或H(key)=a·key+b

其中a和b为常数(这种哈希函数叫做自身函数)。特点：直接定址法所得地址集合和关键字集合的大小相同；对于不同的关键字不会发生冲突；实际中能使用这种哈希函数的情况很少。数据结构29常用的构造哈希函数的方法数字分析法对关键字进行分析，取关键字的若干位或组合作为哈希地址。适用于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。数据结构30例：设有80个记录，关键字为8位十进制数，哈希地址为2位十进制数。┇8134653281372242813874228130136781322817813389678136853781419355

分析：

只取8

只取1

只取3、4

只取2、7、5

数字分布近乎随机因此：取

任意两位或两位与另两位的叠加作哈希地址常用的构造哈希函数的方法平方取中法取关键字平方后的中间几位作为哈希地址。

一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。适用于在选定哈希函数时不一定能知道关键字的全部情况，取其中哪几位也不一定合适的情况。数据结构31常用的构造哈希函数的方法折叠法将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，然后取这几部分的叠加和(舍去进位)作为哈希地址。数位叠加有移位叠加和间界叠加两种。移位叠加：将分割后的每一部分的最低位对齐相加；间界叠加：从一端到另一端沿分割界来回折叠，然后对齐相加。适用于关键字位数很多，而且关键字中每一位上数字分布大致均匀的情况。例：设关键字为0442205864，哈希地址位数为4。数据结构32586442200410088H(key)=0088移位叠加5864022404

6092H(key)=6092间界叠加常用的构造哈希函数的方法除留余数法取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址，即：

H(key)=keyMODp，(p

m)一种最简单、也最常用的构造哈希函数的方法，可以对关键字直接取模(MOD)，也可在折叠、平方取中等运算之后取模。p的选择很重要。若p选的不好，容易产生同义词。选取p=2i：运算便于用移位来实现，但等于将关键字的高位忽略而仅留下低位二进制数，则高位不同而低位相同的关键字是同义词。选取p=q

f(q、f都是质因数)：则所有含有q或f因子的关键字的哈希地址均是q或f的倍数。选取p为素数或不包含小于20的质因数的合数：经验；常用的选取方法；能减少冲突出现的可能性。数据结构33常用的构造哈希函数的方法随机数法选择一个随机函数，取关键字的随机函数值为哈希地址，即H(key)=random(key)通常，当关键字长度不等时，采用此法较恰当。视不同的情况采用不同的哈希函数，考虑的因素有：计算哈希函数所需时间；关键字的长度；哈希表的大小（哈希地址范围）；关键字的分布情况；记录的查找频率。数据结构34冲突处理的方法冲突处理：当出现冲突时，为冲突元素找到另一个存储位置。开放定址法基本方法：当冲突发生时，形成某个探测序列；按此序列逐个探测哈希表中的其他地址，直到找到给定关键字或一个空地址(开放的地址)为止，将发生冲突的记录放到该地址中。哈希地址的计算公式是：Hi(key)=(H(key)+di)MODm，i=1,2,…,k(km-1)其中：H(key)为哈希函数；m为哈希表长；

di为第i次探测时的增量序列；

Hi(key)为经第i次探测后得到的哈希地址。数据结构35冲突处理的方法:开放定址法线性探测再散列增量序列为：di=1,2,3,…,m-1将哈希表T[0…m-1]看成循环向量。当发生冲突时，从初次发生冲突的位置依次向后探测其他地址。探测过程终止的情况是：探测到的地址为空：表中没有记录。若是查找则失败；若是插入则将记录写入到该地址；探测到的地址有给定的关键字。若是查找则成功；若是插入则失败；直到T[h]：仍未探测到空地址或给定的关键字，哈希表满。数据结构36冲突处理的方法:开放定址法数据结构37例:(19,13,33,02,06,29,17,05)，取哈希表长12，线性探查。1913330205291706冲突因m＝12，故取p＝1119％11＝813％11＝233％11＝002％11＝206％11＝629％11＝717％11＝605％11＝501234567891011线性探测法的特点◆

优点：只要哈希表未满，总能找到一个不冲突的哈希地址；◆

缺点：每个产生冲突的记录被散列到离冲突最近的空地址上，从而又增加了更多的冲突机会（这种现象称为冲突的“聚集”）。冲突处理的方法:开放定址法二次探测再散列增量序列为：di=1²,-1²,2²,-2²,3²,……±k²(k

m/2)二次探测法的特点◆优点：探测序列跳跃式地散列到整个表中，不易产生冲突的“聚集”现象；◆缺点：不能保证探测到散列表的所有地址。伪随机探测再散列增量序列使用一个伪随机函数来产生一个落在闭区间[1,m-1]的随机序列。数据结构38冲突处理的方法:开放定址法例：表长为11的哈希表中已填有关键字17,60,29的记录，哈希函数为H(key)=keyMOD11。现有第4个记录(关键字为38)，按三种处理冲突的方法，将它填入哈希表中。(1)H(38)=38MOD11=5

冲突

H1=(5+1)MOD11=6冲突

H2=(5+2)MOD11=7冲突

H3=(5+3)MOD11=8不冲突数据结构3901234567891060172938冲突处理的方法:开放定址法(2)H(38)=38MOD11=5冲突

H1=(5+1²)MOD11=6

冲突

H2=(5-1²)MOD11=4

不冲突(3)H(38)=38MOD11=5

冲突设伪随机数序列为9，则H1=(5+9)MOD11=3

不冲突数据结构400123456789106017293838012345678910601729383838冲突处理的方法再哈希法构造若干个哈希函数，在同义词产生地址冲突时，利用不同的哈希函数计算另一个哈希函数地址，直到冲突不再发生。即：

Hi=RHi(key)i=1,2,…,k

其中，RHi

均是不同的哈希函数。第一次发生冲突时，用RH1计算，第二次发生冲突时，用RH2计算，依此类推直到得到的某个Hi不再冲突为止。◆优点：不易产生冲突的“聚集”现象；◆缺点：计算时间增加。数据结构41冲突处理的方法链地址法将所有关键字为同义词(哈希地址相同)的记录存储在同一线性链表中，并用一维数组存放链表的头指针。假设哈希表长为m，设立一个一维指针数组：

ChainChainHash[m];其每个分量的初始状态都是空指针。凡哈希地址为i

的记录都插入到头指针为ChainHash[i]的链表中，插入位置可以在表头或表尾，或按关键字排序插入。优点：不易产生冲突的“聚集”；删除记录也很简单。数据结构42冲突处理的方法:链地址法例：(19,13,33,02,06,29,17,05)，

H(key)=key

%11，

尾插建表数据结构432105438761093319％11＝813％11＝233％11＝002％11＝206％11＝629％11＝717％11＝605％11＝513052919020617^^^^^^^^^^^冲突处理的方法建立一个公共溢出区在基本哈希表之外，另外设立一个溢出表保存与基本表中记录冲突的所有记录。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。例：已知一组关键字(15,4,18,7,37,47)，哈希表长度为7，哈希函数为：H(key)=key

MOD

7，用建立公共溢出区法处理冲突。数据结构44Hashtable表：散列地址

012345

6

关键字71537447OverTable表：溢出地址

0123456

关键字18哈希查找过程哈希表的主要目的是用于快速查找，且插入和删除操作都要用到查找。由于散列表的特殊组织形式，其查找有特殊的方法。设散列为HT[0…m-1]，散列函数为H(key)，解决冲突的方法为R(x,i)，则在散列表上查找给定值K的记录的过程如右图所示。数据结构45给定k值计算H(k)此地址为空?关键字==k?查找失败查找成功按处理冲突方法计算HiNYYN哈希查找分析从哈希查找过程可见：尽管哈希表在关键字与记录的存储地址之间建立了直接映象，但由于“冲突”，查找过程仍是一个给定值与关键字进行比较的过程，评价哈希查找效率仍要用ASL。哈希查找时关键字与给定值比较的次数取决于：哈希函数；处理冲突的方法；哈希表的填满因子

。数据结构46表中填入的记录数哈希表长度

=例：(19,13,33,02,06,29,17,05)，

H(K)＝K％11，线性探测19133302172956找17，17％11＝6不成功11109876543210比较4次成功：1

121

1

1

14不成：21321654321