论文资料—1b-树的定义 前面介绍的查找法,仅适用于计算机内存中的

1B-树的定义 前面介绍的查找法，仅适用于计算机内存中的文件或表，统称为内查找法，而对外存上文件的查找称为外查找法。 前面介绍的方法也可应用于磁盘文件，例如一个磁盘文件包含n个记录，n=106，且该文件表示成一棵二叉树形，那么欲从该文件中查找包含某一给定关键字的记录平均来说大约要做log2n=log210620次磁盘的存取操作。因为对磁盘存取的速度比内存中的存取速度慢得多，因此当n较大时，用二叉树形来表示文件是行不通的。对于外存上的文件而言，减少查找过程中磁盘存取次数，是很必要的，B-树就是解决此类问题提出的。,三、B-树,B-树是一种平衡的多路查找树，是一类适于外查找的数据结构。m阶的B-树，或为空树，或为满足下列特性的m叉树：(1) 树中每个结点至多有m棵子树；(2) 若根结点不是叶子结点，则至少有两棵子树；(3) 除根之外的所有非终端结点至少有m/2棵子树；(4)所有非终端结点具有n(m/2-1nm-1)个关键字域和n+1个指针项，指向该结点的n+1棵子树；结点包含下列信息数据 (n,A0,K1,A1,K2,A2,Kn,An)其中：Ki为关键字，且Ki Ki+1，Ai为指向子树根结点的指针，且 KAi-1 Ki K Ai ，。(5)所有叶子结点都出现在同一层次上，且不带信息，仅表示查找失败(外部结点)。,三、B-树,下图所示的是一棵4阶的B-树(又称2-4树，非终端结点关键字个数至多为3，至少为1，子树个数最少为2，最多为4),三、B-树,2B-树上的查找 在B-树上的查找过程和二叉排序树的查找类似。首先在根结点所包含的关键字中查找给定的关键字。若找到，则查找成功；否则，确定待查关键字所在的子树并在其上查找，直到查找成功或查找不成功(失配结点F)。,在B-树上进行查找的过程是一个顺指针查找结点和在结点的关键字中进行查找交叉进行的过程 。,三、B-树,3B-树查找分析在B-树上进行查找包含两种基本操作：(1) 在B-树中找结点：在磁盘上进行。(2) 在结点中找关键字：在内存中进行的。 考虑最坏情况，即待查结点在B-树上的最大层次上，确定含有N个关键字的m阶B-树的最大深度，即可判断其查找效率。 在具有N个关键字的B-树上进行查找时，从根结点到关键字K所在结点的路径涉及的结点数目不超过: logm/2(N+1)/2)+1。,深度为l+1的m阶B-树所具有的最少结点数： N2*( m/2)l-1,三、B-树,4B-树的插入和删除 在B-树上进行插入和删除操作较为复杂，要使进行操作后的结点中关键字个数N满足m/2- 1 N m-1，将涉及结点的分裂与合并。,(1)B-树的插入 B-树的生成也是从空树开始，逐个插入关键字而得。由于B-树中关键字个数必须m/2-1，因此，每次插入一个关键字不是在树中添加一个叶子结点，而是首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过m-1，则插入完成，否则要产生结点的“分裂”。,三、B-树,“分裂”的实现： 假设*p结点中已有m-1个关键字，当插入一个关键字之后，结点含有信息为：m,A0，(K1 ，A1)，(Km，Am) 其中 KiKi+1 1im 此时可将*p结点分裂为*p和*p两个结点，以m/2为分裂中心，其前一部分，放在*p结点中，后一部分放在*p结点中。 其中：*p结点中含有信息为 m/2-1，A0，(K1 ，A1)，(Km/2-1,Am/2-1) *p结点中含有信息为 m-m/2，Am/2，(Km/2+1，Am/2+1)，(Km ，Am) 而关键字Km/2 和指向*p的指针一起插入到*p的双亲结点中。,三、B-树,三、B-树,(2)B-树的删除 若在B-树上删除一个关键字，则首先应找到关键字所在结点，并从中删除之，若该结点为最下层的非终端结点，且其中关键字数目不少于m/2，则删除完成，否则要进行“合并”结点的操作。,三、B-树,删除最下层非终端结点中的关键字情况，有下列三种可能：被删除关键字所在结点中的关键字数目不小于m/2，则只需从该结点中删去该关键字Ki和相应的指针Ai，树的其它部分不变。,三、B-树,b)被删关键字所在的结点中的关键字数目等于m/2-1，而与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于m/2-1，则需将其兄弟结点中最小(或最大)的关键字上移至双亲结点中，而将双亲结点中小于(或大于)且紧靠该上移关键字的关键字下移至被删关键字所在结点中。,三、B-树,c)被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于m/2-1。假设该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针Ai所指，则删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲结点中的关键字Ki一起，合并到Ai所指兄弟结点中(若没有右兄弟，则合并到左兄弟结点中)。,三、B-树,一、哈希法的概念 二、哈希函数的构造方法 三、处理冲突的方法 四、哈希表的查找及其分析,8.4 哈希表,1哈希法的引入 哈希英文名称为Hash，散列(杂凑)的意思。因此哈希表又称散列表(杂凑表)。 用哈希表是一种重要的存储方法，也是一种常用的查找方法。前述的查找方法都是以关键字的“比较”为基础的。查找的效率依赖于查找过程中所进行比较的次数。查找效率取决于结点的个数。,一、哈希法的概念,理想的情况是希望不经过任何比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。这就是哈希法的思想。 查找时，只需对结点的关键字进行某种运算，就能直接确定记录在表中的位置。,2. 哈希函数定义 将结点的关键字作为自变量key，通过一个确定的函数关系(关于关键字的某种运算)f，计算出函数值f(key)作为该结点的存储地址。这个确定关系f 就是哈希函数。查找时，用哈希函数确定地址取结点。3. 哈希表的定义 用哈希函数建立起来的存储结构称为哈希表。4. 散列地址法(散列技术) 用哈希函数转换记录关键字得到存储地址，把各记录散列到相应的存储单元里去的方法，称为散列地址法或关键字转换法。,一、哈希法的概念,5冲突 对不同的关键字可能得到同一哈希地址，即key1key2，而f(key1)=f(key2)，这种现象称为冲突。 具有相同函数值的关键字对该哈希函数来说称为同义词。,一、哈希法的概念,6哈希法的两个问题(1)如何构造哈希函数 构造哈希函数也要解决两个问题：哈希函数应是一个压缩映象函数，它应具有较大的压缩性，以节省存储空间。这样就不可避免地产生冲突。哈希函数应具有较好的散列性，尽量减少冲突。(2)如何解决冲突,7综合描述 根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续地址集(区间)上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为哈希表，这一映像过程为哈希造表或散列表，所得存储位置称为哈希地址或散列地址。,一、哈希法的概念,均匀的哈希函数若对于关键字集合中的任一个关键字，经哈希函数映像到地址集中任何一个地址的概率是相等的，则称此类哈希函数为均匀的哈希函数。 换句话说，就是关键字经过哈希函数得到一个“随机的地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。1直接定址法 取关键字或关键字的某个线性函数值为哈希地址。即 H(key)=key或 H(key)=a*key+b 其中a、b为常数。又称H(key)为自身函数。 这种方法，地址集合和关键字集合相同，没有冲突，但若关键字集合大，则地址空间也很大，很少采用。,二、哈希函数的构造方法,2数字分析法 假设关键字是以r为基的数(如以10为基的十进制数)，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。 此方法是通过分析关键字的构成(主要是数字形式)，为了尽量避免冲突，取那些出现的数字随机的位数，作为哈希地址的位数，而那些总出现一种数字或某几种数字的位数，则不取。,二、哈希函数的构造方法,分析关键字看到：前三位都是0，不能取；第3位有2个7，不均匀，不可取；第4位有3个7，不均匀，不可取；第5位有2个6，不均匀，不可取；第1，2，6位数字分布均匀，作为哈希地址 。,二、哈希函数的构造方法,3平方取中法 取关键字平方后的中间几位为哈希地址。 通常在选定的哈希函数时不一定能知道关键字的全部情况，取其中哪几位也不一定合适，而一个数的平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数取由表长决定。,二、哈希函数的构造方法,二、哈希函数的构造方法,4折叠法 如果关键字的位数比地址的位数多，而且各位数分布也比较均匀，将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，其中至少应有一段的位数等于地址码的位数，取这几部分的叠加和作为哈希地址，有进位舍去。5. 随机数法 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key)。,二、哈希函数的构造方法,6. 除留余数法 选择一个适当的正整数p，用p去除关键字，取其余数作为哈希地址。即H(key)=key mod p 可以在平方取中或折叠之后取余。这里关键在于p的选取。 p的选取原则：为了使计算的哈希地址分布均匀，在除留取余法中，p应取小于或等于哈希表长度的最大素数。 例：如果哈希表长为1000，可取997为p。 key H(key)=key mod 997 11052344 599 12051282 543 48765210 943 25341272 523,二、哈希函数的构造方法,无论采用什么样的哈希函数构造哈希表，冲突都是不可避免的，但要求尽量最小。 冲突一旦发生如何解决？是哈希法中的一个重要课题。当不同关键字经过哈希转换，产生了同一哈希地址，就需选择另一地址，直到不冲突为止。,三、处理冲突的方法,1.开放定址法 Hi=(H(key)+di)mod m i=1,2,k(km-1) 其中：H(key)为哈希函数(关键字的哈希地址)，m为哈希表长，di为增量序列，当H(key)重复时，求新的哈希地址Hi值。用开放地址法解决冲突时，要产生一个探测序列。根据di取法的不同，有三种处理冲突的方法，称再散列。(1)线性探测再散列：di=1,2,3 ,m-1(2)二次探测再散列：di=12,-12,22,-22,k2(k m/2)(3)伪随机探测再散列：di=伪随机数序列,三、处理冲突的方法,例1：设在长度为11的哈希表中已填有关键字分别为17、60、29的记录，哈希函数为H(key)=key mod 11，现有第4个记录，其关键字为38，确定其哈希地址。已确定的哈希地址如图： 0 1 2 3 4 5 6 7 8 9 10,由哈希函数求得关键字38的哈希地址为：5与关键字60的哈希地址冲突，用线性探测再散列处理冲突。即H1=(H(key)+1) mod 11=(5+1) mod 11=6，仍存在冲突，继续处理，H2=(H(key)+2) mod 11=(5+2) mod 11=7，仍存在冲突，继续处理，H3=(H(key)+3) mod 11=(5+3) mod 11=8，该位置为“空”处理冲突结束。将38插入8号位置。,三、处理冲突的方法,线性探测产生的哈希地址分布不均匀，而是连在一起，称为堆聚(聚集)现象，这样就增加了探测的次数，且容易产生“二次堆聚”，所谓“二次堆聚”即在线性探测时，不同哈希地址的记录争夺同一后继哈希地址的现象。只有表长足够，即可找到一个不冲突的地址。但当表全满时，则发生溢出，须进行溢出处理。,三、处理冲突的方法,2再哈希法 Hi=RHi(key) i=1,2,k RHi均是不同的哈希函数，产生冲突时，计算另一个哈希函数，直到冲突不再发生。这种方法不易产生“堆聚”现象。,三、处理冲突的方法,3链地址法 在哈希表中的每一个记录增加一个链域，链域中存放下一个具有相同哈希函数值的记录的存储地址。利用链域，就把若干个发生冲突的记录链接在一个链表内。当链域值为NULL时，表示已没有后继记录了。因此，发生冲突时的查找和插入操作就跟线性链表的操作一样。至于删除操作，如果欲删除记录在链表中，则也和线性链表的删除操作一样。,三、处理冲突的方法,例2：已知一组关键字为(19，14，23，01，68，20，84，27，55，11，10，79)，则按哈希函数H(key)=key mod 13和链地址法处理冲突构造所得的哈希表如图所示。,三、处理冲突的方法,4建立一个公共溢出区 设立一个基本表和一个溢出表。基本表存放由哈希函数的值域确定的向量表HashTable0m-1，另一个溢出表用向量OverTable0.v。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。,三、处理冲突的方法,在哈希表上进行查找的过程和哈希造表的过程基本一致。1查找过程 (1)给定K值，根据造表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功； (2)此位置上有记录,比较关键字: 若和给定值相等，则查找成功； 若不相等，则出现了冲突，找“下一地址”，,四、哈希表的查找及其分析,表中记录的关键字等于给定值 找到哈希表中某个位置为“空” 未找到,四、哈希表的查找及其分析,2查找分析 (1)由于“冲突”的产生，使得哈希表的查找过程仍然是一个给定值和关键字进行比较的过程。仍需以平均查找长度作为衡量哈希表的查找效率量度。 (2)查找过程中需和给定值进行比较的关键字的个数取决于下列三个因素：a.哈希函数 哈希函数的“好坏”首先影响出现冲突的频繁程度。通常设定哈希函数是均匀的，产生冲突的可能性相同，则不考虑它对平均查找长度的影响。,b.处理冲突的方法 对同样一组关键字，设定相同的哈希函数，则不同的处理冲突方法得到的哈希表不同，它们的平均查找长度也不同。对上面两例子的哈希表，设定记录的查找概率相等。 链地址法的平均查找长度为： ASL(12)=1/12(1*6+2*4+3+4)=1.75 线性探测再散列的平均查找长度为： ASL(12)=1/12(1*6+2+3*3+4+9)=2.5,四、哈希表的查找及其分析,c.哈希表的装填因子 在处理冲突方法相同的哈希表，其平均查找长度依赖于哈希表的装填因子。设装填因子为，则装填因子定义为,=,表中填入的记录数,哈希表的长度,标志哈希表的装满程度。 越小，发生冲突的可能性就越小；反之，越大，表中已填入的记录越多，再填记录时，发生冲突的可能性就越大，则查找时，给定值与之进行比较的关键字的个数也就越多。,四、哈希表的查找及其分析,结论：查找成功时的ASL：Snl1/2(1+1/(1-) (线性探测再散列)Snr-1/ln(1-) (随机、二次探测和再哈希)Snc1+/2(链地址法) 平均查找长度仅和装填因子有关，选择合适的装填因子使平均查找长度限定在一定的范围内是很关键的。查找不成功的ASL：unl1/2(1+1/(1-)2) (线性探测再散列)unr1/ (1-) (随机、二次探测和再哈希)unc+ e -(链地址法),四、哈希表的查找及其分析,本章小结,例3：对以下关键字序列建立哈希表：(SUN,MON,TUE,WED,THU,FRI,SAT),哈希函数为H(K)=(关键字中第一个字母在字母表中的序号）MOD 7 ,用线性探测法处理冲突，构造一个装填因子为0.7的哈希表；并分别计算出在等概率情况下查找成功与不成功的平均查找长度。,解：由=0.7，表长m=7/0.7=10S:19 M:13 T:20 W:23 F:6,ASL succ=,(1+1+1+2+3+4+6) /7=18/7,ASL unsucc=,( 2+1+2+1+1+7+6+5+4+3）