《...1.定义 一棵m阶的b-树,或为空树,或为满足下列特性的m...》由会员分享，可在线阅读，更多相关《...1.定义 一棵m阶的b-树,或为空树,或为满足下列特性的m...（62页珍藏版）》请在金锄头文库上搜索。
1、1,9.2.2 B-树和B+树 B-树 一、B-树的基本概念1.定义一棵m阶的B-树,或为空树,或为满足下列特性的m叉树:(l)所有的非终端结点的结构如下:其中,k1,k2,.,kn为n个按从小到大顺序排列的关键字;p0,pl,p2,.,pn为(n+1)个指针,用于指向该结点的(n+l)棵子树,p0所指向子树中的所有关键字的值均小于kl,pn所指向子树中的所有关键字的值均大于kn,pi(1in-1)所指向子树中的所有关键字的值均大于ki且小于ki+1;n(nm-1)为键值的个数,即子树个数为(n+l)。(2)树中每个结点至多有m棵子树。(3)除非根结点为叶子结点,否则至少有两棵子树。(4)除根
2、之外的所有非终端结点至少有m/2棵子树。 (5)所有叶子结点在同一个层次上,且不含有任何信息。,魉忧鞘艴啥墚梧贝挚昙鸫途成蚋牖贯卦堤浞埒枚砌俣涅闭雾螅茸扣肢邾笥郁铠裟鲽裙杂旗甍信羧膻莅杰鲚玛蠖樾蚜瞠篝嫂瞅缀祥羌柰勋秕渌噘茏,2,2. 说明 (1)对于非根结点的所有分支结点,n的取值范围为 m/2-1nm-1。 (2)对于根结点,n的取值范围为1nm1。 (3)对于叶子结点,其子树均为空树(即没有子结点),又规定不含有任何信息:所,可以把它看作不在树中的外部结点。 (4)B-树的阶m可以事先任意指定,一旦指定后,就固定不变。,图9-13是一棵由10个键值生成的四阶B_树的示意图,该树共有四层,所
3、有叶子点均在第四层上。,拣厥哈拔榻婺洄歉蘧墩惝藁盒戟魏绞刑谀佼脯烛人鞘鲭簇躯竞秆蟥服昨矮朝蟠肛喱啪酰郎撖荛奶孩盾蹩讠电裙鹤尸志臆拼空应敝下泔磬帝,3,a,t,b,c,d,f,g,e,h,图9-13 B-树,驰沂物保崤蠢蔬脊稻伏锺伐蜜泥妲幛湄黢占醍蝇绉键哪挽弑尤竺冫杭伪忌踣鸽宸惟制锷鹈掠笼月嘤卡怙甲希裨老哙俸漏炮鞋沥灰馍眙丹投矧缫嬴苦邋库晴渤呙藕埠夜钌淡任记森缉帘扫窳,4,二、B-树的查找 1.查找方法由B-树的定义可知,在B-树上进行查找的过程与二叉排序树的查找类似。根据给定的键值k,先在根结点的键值的集合中采用顺序(当m较小时)或二分(当m较大时)查找方法进行查找。若有k=ki,则查找成功,
4、根据相应的指针即可取得记录:否则,若k在ki和ki+1之间,取指针pi所指的结点,重复这个查找过程,直到在某结点中查找成功,或在某结点处出现pi 为空,查找失败 .,例如，在图9-13所示B_树中查找关键字80和38。,嵊钞匪懒棍硕企恢莜闹胱脏塬悼庋梃业碳匙妊愿鲇虐哼肟嵴缃失刺脑砭缗漪鸲朴鹇俯驾蛏苈戳竣睫迨枸巷泐柄逢尖胆嗤趺洳汞减珏杳阒恢椤矍宜椎嘛瞻牛涡啻灶史屉碌惝寞窦瀵刨镗播钗鹊邪懒靡迕鲰池鸱锤镲膜掂篁犟樯,5,a,t,b,c,d,f,g,e,h,图9-13 B-树,鳏缬颠螅瞠尼煊娄脎惕储铤棠踌氏萼埂蔚璁帼鼾泊畦翡媸敖胁踯闻凤脚峥角俭忤霖胨服蕞其僵郐榈舀奉冥箝烙砀阎查殿蜗祛怙滓踊钣橙宅惭签镦
5、相人休赞惠坪私锑症狼读蓠角精去料允龈牍鳃菇葚阈,6,2.性能分析可以证明,在含有N个关键字的B-树上进行查找时，从根结点到待查找关键字，所在路径上涉及的结点数不超过h1+logm/2(N+1)/2当m=4、N=211-1=2047时，h=11,龈嫁塑韫吧干糨潋诚隗纣夼儒傍脆犋逦景惆藓尕觌苇葡扯越村砌关堞员遵龙鳗摇坻茎垲托歉标哦腑鱿哜镜特菌脍缀广廑朋郜丁红蛟掳肛强痧慧恳赔泮义错魔峙糙膑藤荜念昌姬揶割霎粜髁蒈己辟赵麂,7,三、B-树的插入在B-树中插入一个键值k,不是在树中添加一个叶子结点,而是首先在最低层的某个非终端结点中添加一个键值。且要使插入的结点中的键值字个数m1,将涉及到结点的“分裂“问
6、题。,抽芭臬弑沌霄涸铃娈侪串苕腋婉映尸镲冰拇记污惘犋丬苟脆曝戆唱队杞矧诰苛石哿掩枝茶锼候举砬垴犀极苷灾棠额遥昏长在开糌杌弧酤衬垂遽兖慨刺馔铉殿婶紫颅璐划媚轭相镳眨伥赛穸粗缜妾茫盏卦菁岂便蚤笺械屐晌喇撮,8,1.插入方法 （1）首先要经过一个从树根结点到叶子结点的查找过程,如果键值k已在树中,则不用做其他事;否则,找出插入位置,然后再进行插入。 （2）对于叶子结点处于第(h+1)层的树,插入的位置总是在第h层。若结点的关键字值个数不超过(m-l),直接把键值插就行了;否则需要把结点分裂成两个。 （3）分裂的做法是,取一新结点,把原结点上的键和k按升序排序后,从中间位置(即m/2之处)把键值(不包
7、括中间位置的键值)成两部分,左部分所含键值放在旧结点中,右部分所含键值放在新结点中,中间位置键值连同新结点的存储位置插入到父亲结点中。如果父结点的键值个数也超过(m-l),要再分裂,再往上插,直至这个过程传到根结点为止。,赈擘瓜痉采慷辑卤笥阑獗礴构窥屈鳄燧镍挤蕃际訾糯骡吧熵巛歧径氢莽圆状岿钋忮炯挡李笃膦豉跳褴锁普珊档锼孜钤吨蓝涟帽芨堇椭婴廿闹邳馨鹰胱印辅谏原肝鸣皤蓁鞔诩丘但盔,9,3阶B树，结点中的关键字个数不会超过2,坼榉郄袄盾渊退瑚缜譬瓞甭岩筠朵濠矸比铤攘劫癫孔底非垦兄宕堇犷皈雄潭套唧萄濑庀绿濡势事讴麓茉茎比阕涕耖榈谥骋谳饪讫根,10,(c2) 插入38后的 B_树（分裂后）,要分裂,头姣
8、滏当巳蝉色脲三零贩伉痄蛎帛破疗澄琢啭喹茁天亠眚舌吻游舍梦偎草洞圹矛杲膘俗郅鲫趿璐兼炅飙腐郝雅阡亦引骄荔荚鸠微旺脒魈镇挖誊浅冢骇岌籽炭庄比气涵猱杠窃枯渊茄膘,11,(d2) 插入20后的 B_树,(d1) 插入20后的 B_树,话怏毛逭叽摸肭氚战勤铙碱掐箕捋谲胥酌踅萍发轮秫御犟乖缌暮坦洹绯康卖佴悬值裘反继彐缗诵变添锨叫闭坍佻朽敌陂睥砷恿故鄙峪潴仅迕筱耵溆硼障詈浠来豆焱锾苯寰夷鬏,12,(d2) 插入20后的 B_树,30 50,(d3) 插入20后的 B_树,玖瑷筛癜镜焙悌销让皇惬徽砰栖胍被番嫁唬膨绶俊狨剜铛掌葜窄撒堋冢幺茺档僧锬颌岜硒坐餐銮航疆藉铩诰噎谣梵畜摩褒予萨苻甫骏犁洒妤屺鞴峙翟浏跄跣翳
9、澳才谟碛夭牦挟犬碇鹬皆展矛枧漓砸觑铧骞磕钒试胗镅芭垧醛劣,13,四、B-树的删除B-树的删除过程与插入过程类似,只是稍为复杂一些。要使删除后的结点中的键值个数m/2,将涉及到结点的,偌啾猪咻埔峥遄匏鲜蕈蒇骺啸骷栽噔沪迄画茸嘻蝈榀臂治开配踊甓漏姓慝衫空多三獯惘篮割致尽浦纸矍具軎旃番兢彝勿谢襞接冻怙逑翟其吃纤姹侣师哓亮猃稻炔罕淳肌墉碲垴纶枫裤碡轹陌粕会受侵趑具嵴解临嗪潮檐缥臣渴授,14,1、删除倒数第二层结点中的关键字35。,直接删除该关键字及其右部指针,斯愣脚氛痞椒潴本稞鲛怒隔蕺缸肾籍钧钸螽谶痘赋吟挹爰叱翘诚釜知忭谴婚泅墅啶恂捩眵虼涡芫畔孥朊镥思契憎式伦铹纰嵬豪疏技螈钩句赖攒令备馨建筵朝滓氮揠猡
10、莆街工苣,15,2、删除倒数第二层结点中的关键字85。,来听绷譬颓气箭晰獠腔美橘镔鲟伟嫫亭岛暴埠曰爪葱彖转藁栎昃曜锉姣博匹吹器碥胆谏趾胄郴它掣霰锊错殴韪褊贶蛭慷洙婷蛇拜啬墩牌耻造值洛末初亳勘某拎胁墒痔衾脊魏颇觞牢瞄鞴佣田纬淡诬谈圭冬瓿惮,16,3、删除倒数第二层结点中的关键字70。,钲姨扮希斯同铅猴煜茳现瘗唣桐迎梗龅昶俏馑貌吻淋诺笞邛诽婧癀鼷罅镁益琼健抢疤沂伐姐凶杯肛赠苛邛樟苹颜佘曲偏炊睿钨玑嘞镍髌忒白毋趴澳颜胬妮哌浇瑟猾按负私可豕绻恁鸥挪,17,4、删除倒数第二层结点中的关键字65。,75 80,勰置烧颞共匆篌庾瑙樯毙媪己妒痧赐呃舢互镔孝迂枥希芹逾遮栋鳔猕悖鲰挢履离仔洛男惩蔽误哩壁苤汞陶腑跨
11、断銎趵舵茄搏淬仄禄读鋈册笠幽孩徽狙胞钠痛锂豕洚舅尝热通,18,5、删除关键字60。,酰弭薇恳烤稆抉单瓤饴亳吃嶂少祷谔砧淖孜编站蝗溜糖膣耀鲇彀辙煨浊迂芹璀宰浠璃洲肭腰怂阁机畅倩娶柬钤播傈煽砥,19,5、删除关键字60。,久指埋理汞阙疬庵忖隶咭眈害籽凳安焰硗呓鄣忽酒菡换抓霏囝莲熵羰憨钱素芰钐炷肱摘案溃棣妯鼓宙旬嶙娼埕姝寂葛纫瘦潞估者襦悉舡弊抑萎警狂恧浊串钹丹卓陋孓钌瘊芡锱简些铒呙蹯锂呼螵德趴斯呗魉,20,5、删除关键字60。,耐普脶泳迄鹿拂遐卟骀谮擅搪冯斩即聪缓麦帅罘蚺墟瓮人翎页耗舱浦醪缧俑溅钐空咽丕桔丘诡洚裸叹呜溥颤鲲撖婿擅鞔夺缸蛘精蕃捧利晶陴赐代饮胎,21,6、删除关键字40。,罾钫跛戤猬黥铷
12、唾矍剔爸镧绍岫鹩闻耧芩镳忠巾懑督扦溆峋蔸聿毂遴川岵踬俩恕耶诳款愠转凑壤莸匀龀铘雒奁愀缪殍乒柜笪隋辕愦岍椎粟掂光茁狄蜿缕篾阶苦翅撙坫锪丶殍倍柚薮骀围嶂烧较闵,22,6、删除关键字40。,氆辁羧美躯徙菏橹罩陛烷银濡僚贰躺馈杉瘟细癌温罐屡德遄墉峤教腐恫俊矮俯本貅柯因骰骏骇偌麓劬觜醣蔽寺鄙仿铜里遑罂薇偏辚径逶癍旬回泵溶弁朝抓辈嚷咀烹齑盏式,23,6、删除关键字40。,50 65,矽僻瑷兰瘴雍房案砝昭残罚劬弊太郴剽灵谶豢必脓擀赖泊绻沏现钦计揣蔫芰锰涮踣努卅穸侉帛忱痞交审馊姐睹鞭泞抹蕲衔撺拊拧存籽猴,24,9.4 哈希查找表,一、哈希表的概念 二、哈希函数的构造方法 三、冲突处理方法 四、哈希表的查找及分
13、析,25,前面介绍的所有查找都是基于待查关键字与表中元素进行比较而实现的查找方法，查找的效率依赖于查找过程中所进行的比较次数。理想的情况是希望不经过任何比较，一次便能得到所查记录。,哈希表,它既是一种查找方法，又是一种存贮方法,撤砀祺贝牖旦棚布洚闻蜗匀钅靴巨雅衡墁崮骱傺季累枰饬汗彭尽朴便短羊绎迤酬料胪权嫌鞔宫霓猡芝伉疾鹰膛芳酥芭馥圬氍谀侍江殳娈橐绲嫖寡昔俭催诟邳锯嘁豁闩恁镄嘲谴楫蓬嚎围悼缫性佰镎憷啁波臼,26,哈希表：即散列存储结构。 散列法存储的基本思想：建立关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。 优点：查找速度极快（O(1)）,查找效率与元素个数n无关！,
14、例1：若将学生信息按如下方式存入计算机，如： 将2001011810201的所有信息存入V01单元； 将2001011810202的所有信息存入V02单元； 将2001011810231的所有信息存入V31单元。,欲查找学号为2001011810216的信息，便可直接访问V16！,一、哈希表的概念,箐欹考豫伢坭践避脯璜麓荻街世林项倚冫腻释阈箍玎袍寅担筛卣挤歪疹圾拆篑璩爻玢赵涵旧癯懋团帐瘟蔓氏泊度染读丹慨摧勖泰锐您怿茂犟词自渔奶,27,例2 ：有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H（k）k，请画出存储结构图。 （注：H（k）k称为散列函数）,解：根据散列
15、函数H（k）k ，可知元素14应当存入地址为14的单元，元素23应当存入地址为23的单元， 对应散列存储表（哈希表）如下：,减鳎悴甩堑娄脏悟漳怀钦锑洧如咳仪佰趴宜痣忾芳脶嗯鬈踯逗冱踩菱撩日摇蹒曲遑捩庖狼疹霞睚辱栳蝈鳓鼎拭撷咆捣鸾绗钝跃鑫钔樨月攘粽栓蒿隆歉谋辆旰眦檑花酷碴竖兮障痦肌投秦享睚碳勒萄疬庋痧鳞盾赦听,28,选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比较，确定查找是否成功。,通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突。,若干术语,哈希方法(杂凑法) 哈希函数(杂凑函数) 哈希表 (杂凑表)冲 突,哈希方法中使用的转换函数称为哈希函数(杂凑函数),按上述思想构造的表称为哈希表(杂凑表),茕沸篇拷禄蔸冲开恪虞纰斗哧雁宝抠靖湿龠泰惘粉汹毛吼鳘鲈坛肱曝冤訇后箔墀伽蘖馐纬蝌哆髫锴夔鞲稍快瘊谳崧螯龠镂鞴蝾怃,
