東南大學數(shù)據(jù)結構-Lec012

第12講多路查找樹、哈希表B-樹和B+樹哈希表1數(shù)據(jù)結構樹形索引表平衡二叉排序樹便于動態(tài)查找，因此用平衡二叉排序樹來組織索引表是一種可行的選擇。當用于大型數(shù)據(jù)庫時，所有數(shù)據(jù)及索引都存儲在外存，因此，涉及到內(nèi)、外存之間頻繁的數(shù)據(jù)交換，這種交換速度的快慢成為制約動態(tài)查找的瓶頸。若以二叉樹的結點作為內(nèi)、外存之間數(shù)據(jù)交換單位，則查找給定關鍵字時對磁盤平均進行(㏒2n)次訪問是不能容忍的，因此，必須選擇一種能盡可能降低磁盤I/O次數(shù)的索引組織方式。樹結點的大小盡可能地接近頁的大小。R.Bayer和E.McCreight在1972年提出了一種多路平衡查找樹，稱為B-樹(其變型體是B+樹)。數(shù)據(jù)結構2B-樹的概念一棵m階的B-樹，或為空樹，或為滿足下列特性的m叉樹：樹中每個結點至多有m棵子樹；若根結點不是葉子結點，則至少有兩棵子樹；除根之外的所有非終端結點至少有

m/2

棵子樹；所有的非終端結點中包含下列信息數(shù)據(jù)(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)為關鍵字的個數(shù)（或n+1為子樹個數(shù)）。所有的葉子結點都出現(xiàn)在同一層次上，并且不帶信息。數(shù)據(jù)結構3B-樹的結構條件(1)和(3)使每個結點至少半滿；條件(2)使B-樹不至于一開始就偏向一邊；條件(4)結點中關鍵字遞增排列，使B-樹具有某種“中序”遞增性，可看成二叉排序樹的擴充，是一種平衡多叉排序樹；而子樹數(shù)比關鍵字個數(shù)多1，使得最終葉子數(shù)比樹中所含關鍵字數(shù)多1。條件(5)葉子都在同一層，使B-樹高度上平衡；而葉子不含關鍵字，表示葉子實際上是樹中并不存在的外部結點，且指向這些外部結點的指針為空；數(shù)據(jù)結構4B-樹的結點類型定義根據(jù)m階B-樹的定義，結點類型定義如下：#defineM5/*根據(jù)實際需要定義B_樹的階數(shù)*/typedefstruct

BTNode{intkeynum; /*結點中關鍵字的個數(shù)*/KeyTypekey[M+1]; /*關鍵字向量,key[0]未用*/RecType*recptr[M+1];/*記錄指針向量，recptr[0]未用*/structBTNode*parent;/*指向父結點的指針*/structBTNode*ptr[M+1];/*子樹指針向量*/}BTNode;數(shù)據(jù)結構5B-樹的查找過程數(shù)據(jù)結構6在B-樹上進行查找的過程是一個順指針查找結點和在結點的關鍵字中進行查找交叉進行的過程。例：查找26查找100

類似二叉排序樹的查找root50157184382026435662788996B-樹查找分析兩種基本操作在B-樹中找結點B-樹通常存儲在磁盤上，第1步查找操作在磁盤上進行。在結點中找關鍵字在磁盤上找到指針p所指結點后，先將結點中的信息讀入內(nèi)存，因此，第2步查找操作在內(nèi)存中進行；然后再利用順序查找或折半查找查詢等于給定值的關鍵字。由于訪外（磁盤）耗時，在磁盤上進行查找的次數(shù)，即待查關鍵字所在結點在B-樹上的層次數(shù)，是決定B-樹查找效率的首要因素。數(shù)據(jù)結構7B-樹查找分析考慮最壞的情況，即待查結點在B-樹的最大層次上。含N個關鍵字的m階B-樹的最大深度是多少？

根據(jù)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數(shù)據(jù)結構8結論：在含有N個關鍵字的B-樹上進行查找時，從根結點到關鍵字所在結點的路徑上涉及的結點數(shù)不超過log

m/2

((N+1)/2)+1B-樹的插入操作每插入一個關鍵字不是在樹中添加一個葉子結點，而是首先在最低層的非終端結點中添加一個關鍵字。若該結點的關鍵字個數(shù)不超過m?1，則插入完成；否則要產(chǎn)生結點“分裂”，將位于中間的關鍵字提升到雙親結點，使分裂后的兩個結點大小相當，都約半滿；如果雙親結點原來也是滿的，則需要繼續(xù)分裂和提升。最壞的情況一直到根，若根也要分裂，由于它沒有雙親，就要另外建立一個新的根結點，整個B-樹增加一層。比較：二叉排序樹插入的結點可在任何層。數(shù)據(jù)結構9B-樹的插入操作數(shù)據(jù)結構10113階B-樹的生成B-樹的生成也是從空樹起，逐個插入關鍵字而得。數(shù)據(jù)結構1253插入535375插入757513953插入139751391454953插入49,14549751391455336插入3649533613914510175插入101B-樹的刪除操作在B-樹上刪除一個關鍵字，首先應找到該關鍵字所在結點，并從中刪除之：若該結點為最下層的非終端結點，且其中的關鍵字數(shù)目不少于

m/2

，則刪除完成，否則要進行“合并”結點的操作；若所刪關鍵字為非終端結點中的Ki，則可以指針Ai所指子樹中的最小關鍵字Y代替Ki，然后在相應結點中刪去Y。討論刪除最下層非終端結點中的關鍵字的3種情形。數(shù)據(jù)結構1355587580104065607030acbdefgh刪除55用后繼替換刪后繼14587580104060657030acbdefhB-樹的刪除操作被刪關鍵字所在結點中的關鍵字數(shù)目不小于

m/2

，則只需從該結點中刪去該關鍵字Ki和相應指針Ai，樹的其他部分不變。數(shù)據(jù)結構1555587580m=310406560703050acbdefghad58758010406560703050cbefgh直接刪除55B-樹的刪除操作被刪關鍵字所在結點中的關鍵字數(shù)目等于

m/2-1，而與該結點相鄰的右兄弟(或左兄弟)結點中的關鍵字數(shù)目大于

m/2-1，則需將其兄弟結點中的最小(或最大)的關鍵字上移至雙親結點中，而將雙親結點中小于(或大于)且緊靠該上移關鍵字的關鍵字下移至被刪關鍵字所在結點中。數(shù)據(jù)結構165558758010406560703050acbdefgh刪除6555588010407060753050acbdefgh移動B-樹的刪除操作被刪關鍵字所在結點和其相鄰的兄弟結點中的關鍵字數(shù)目均等于

m/2-1。假設該結點有右兄弟(Ai所指)，則在刪去關鍵字之后，它所在結點中剩余的關鍵字和指針，加上雙親結點中的關鍵字Ki一起，合并到Ai所指兄弟結點中。數(shù)據(jù)結構17558010406058753050acbdefgh刪除5518合并5860801040753050acbdefhB-樹的刪除操作雙親拿出關鍵字后，雙親可能要合并，并可能一直傳播到根；如果根只一個關鍵字，則下移與兩孩子合并后，形成新根結點，整個樹減少一層。數(shù)據(jù)結構1958801040606530acbdefh刪除1080304060fh5865dbB+樹的概念B+樹是應文件系統(tǒng)所需而出的一種B-樹的變型樹。一棵m階的B+樹和m階的B-樹的差異在于：有n棵子樹的結點中含有n個關鍵字；所有的葉子結點中包含了全部關鍵字的信息，及指向含這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大順序鏈接；所有的非終端結點可以看成是索引部分，結點中僅含有其子樹(根結點)中的最大(或最小)關鍵字。數(shù)據(jù)結構20B+樹的結構B+樹有兩個頭指針：一個指向根結點，另一個指向關鍵字最小的葉子結點。因此，可以對B+樹進行兩種查找運算：從最小關鍵字開始進行順序查找；從根結點開始進行隨機查找。數(shù)據(jù)結構21B+樹的查找、插入和刪除對B+樹不僅可以從根結點開始按關鍵字隨機查找，而且可以從最小關鍵字起，按葉子結點的鏈接順序進行順序查找。在B+樹上進行隨機查找、插入、刪除的過程基本上和B-樹類似。查找時，若在非終端結點上找到，并不終止查找，而是繼續(xù)向下查找直至葉子。在B+樹中，不管查找成功與否，每次都是走了一條從根到葉結點的路徑。插入僅在葉結點上進行。當結點中的關鍵字個數(shù)大于m時要分裂成兩個結點，它們所含關鍵字的個數(shù)分別為

(m+1)/2

和

(m+1)/2

，并且，它們的雙親結點中應同時包含這兩個結點的最大關鍵字。刪除也僅在葉結點上進行。當葉子結點中的最大關鍵字被刪除時，其在非終端結點中的值可以作為一個“分界關鍵字”存在（即不必刪除）。若因刪除而使結點中關鍵字的個數(shù)少于

m/2

時，要和該結點的兄弟結點進行合并。數(shù)據(jù)結構22第12講多路查找樹、哈希表B-樹和B+樹哈希表23數(shù)據(jù)結構引言記錄在線性表、樹等結構中的相對位置是隨機的，和記錄的關鍵字之間不存在確定的關系，因此，在結構中查找記錄時需進行一系列和關鍵字的比較。這一類查找方法建立在“比較”的基礎上。查找效率依賴于查找過程中進行比較的次數(shù)。在順序查找時，比較的結果為“=”與“≠”兩種可能；在折半查找、二叉排序樹查找和B-樹查找時，比較的結果為“<”、“=”和“>”3種可能。是否可以不作比較就直接得到記錄的存儲地址，從而找到所要的結點呢？回答是肯定的，這就是散列技術?；舅枷耄涸谟涗浀拇鎯Φ刂泛退年P鍵字之間建立一個確定的對應關系；不經(jīng)過任何比較，一次存取便能得到所查記錄。數(shù)據(jù)結構24什么是哈希表在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系f，使每個關鍵字和結構中一個惟一的存儲位置相對應。在查找時，只要根據(jù)這個關系f找到給定值K的像f(K)。若結構中存在關鍵字和K相等的記錄，則必定在f(K)的存儲位置上。稱這個對應關系f為哈希(Hash)函數(shù)，按這個思想建立的表為哈希表。對于不同的關鍵字可能得到同一哈希地址，即key1≠key2，而f(key1)=f(key2)，這種現(xiàn)象稱沖突。具有相同函數(shù)值的關鍵字對該哈希函數(shù)來說稱做同義詞。根據(jù)設定的哈希函數(shù)H(key)和處理沖突的方法將一組關鍵字映像到一個有限的連續(xù)的地址集(區(qū)間)上，并以關鍵字在地址集中的“像”作為記錄在表中的存儲位置，這種表便稱為哈希表，這一映像過程稱為哈希造表或散列，所得存儲位置稱哈希地址或散列地址。數(shù)據(jù)結構25一個哈希表的簡單例子數(shù)據(jù)結構2630個地區(qū)的各民族人口統(tǒng)計表以編號作關鍵字；構造哈希函數(shù)：H(key)=key

H(1)=1，H(2)=2以地區(qū)名稱作關鍵字；取地區(qū)名稱第1個拼音字母的序號作哈希函數(shù)：H(Beijing)=2

H(Shanghai)=19

H(Shenyang)=19編號省、市(區(qū))總人口漢族回族…...1北京2上海…...…...哈希表的建造在一般情況下，哈希函數(shù)是一種壓縮映象，不可避免產(chǎn)生沖突，只能盡量減少。因此，建造哈希表主要解決兩個問題：哈希函數(shù)的構造和沖突的處理。設計一個哈希表應包括：哈希表的空間范圍，即確定哈希函數(shù)的值域；構造合適的哈希函數(shù)，使得對于所有可能的元素(記錄的關鍵字)，函數(shù)值均在哈希表的地址空間范圍內(nèi)，且出現(xiàn)沖突的可能盡量??；處理沖突的方法，即當沖突出現(xiàn)時如何解決。數(shù)據(jù)結構27哈希函數(shù)的構造方法哈希函數(shù)是一個映像，其設定很靈活，只要使得任何關鍵字由此所得的哈希函數(shù)值都落在表長允許范圍之內(nèi)即可。哈希函數(shù)“好壞”的主要評價因素：函數(shù)的構造簡單；能“均勻”地將哈希表中的關鍵字映射到地址空間。若對于關鍵字集合中的任一個關鍵字，經(jīng)哈希函數(shù)映像到地址集合中任何一個地址的概率是相等的，則稱此類哈希函數(shù)為均勻的哈希函數(shù)，有助于減少沖突。數(shù)據(jù)結構28常用的構造哈希函數(shù)的方法直接定址法取關鍵字或關鍵字的某個線性函數(shù)值為哈希地址。即：

H(key)=key

或H(key)=a·key+b

其中a和b為常數(shù)(這種哈希函數(shù)叫做自身函數(shù))。特點：直接定址法所得地址集合和關鍵字集合的大小相同；對于不同的關鍵字不會發(fā)生沖突；實際中能使用這種哈希函數(shù)的情況很少。數(shù)據(jù)結構29常用的構造哈希函數(shù)的方法數(shù)字分析法對關鍵字進行分析，取關鍵字的若干位或組合作為哈希地址。適用于關鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關鍵字事先知道的情況。數(shù)據(jù)結構30例：設有80個記錄，關鍵字為8位十進制數(shù)，哈希地址為2位十進制數(shù)。┇8134653281372242813874228130136781322817813389678136853781419355

分析：

只取8

只取1

只取3、4

只取2、7、5

數(shù)字分布近乎隨機因此：取

任意兩位或兩位與另兩位的疊加作哈希地址常用的構造哈希函數(shù)的方法平方取中法取關鍵字平方后的中間幾位作為哈希地址。

一個數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都相關，由此使隨機分布的關鍵字得到的哈希地址也是隨機的。適用于在選定哈希函數(shù)時不一定能知道關鍵字的全部情況，取其中哪幾位也不一定合適的情況。數(shù)據(jù)結構31常用的構造哈希函數(shù)的方法折疊法將關鍵字分割成位數(shù)相同的幾部分(最后一部分的位數(shù)可以不同)，然后取這幾部分的疊加和(舍去進位)作為哈希地址。數(shù)位疊加有移位疊加和間界疊加兩種。移位疊加：將分割后的每一部分的最低位對齊相加；間界疊加：從一端到另一端沿分割界來回折疊，然后對齊相加。適用于關鍵字位數(shù)很多，而且關鍵字中每一位上數(shù)字分布大致均勻的情況。例：設關鍵字為0442205864，哈希地址位數(shù)為4。數(shù)據(jù)結構32586442200410088H(key)=0088移位疊加5864022404

6092H(key)=6092間界疊加常用的構造哈希函數(shù)的方法除留余數(shù)法取關鍵字被某個不大于哈希表表長m的數(shù)p除后所得余數(shù)為哈希地址，即：

H(key)=keyMODp，(p

m)一種最簡單、也最常用的構造哈希函數(shù)的方法，可以對關鍵字直接取模(MOD)，也可在折疊、平方取中等運算之后取模。p的選擇很重要。若p選的不好，容易產(chǎn)生同義詞。選取p=2i：運算便于用移位來實現(xiàn)，但等于將關鍵字的高位忽略而僅留下低位二進制數(shù)，則高位不同而低位相同的關鍵字是同義詞。選取p=q

f(q、f都是質因數(shù))：則所有含有q或f因子的關鍵字的哈希地址均是q或f的倍數(shù)。選取p為素數(shù)或不包含小于20的質因數(shù)的合數(shù)：經(jīng)驗；常用的選取方法；能減少沖突出現(xiàn)的可能性。數(shù)據(jù)結構33常用的構造哈希函數(shù)的方法隨機數(shù)法選擇一個隨機函數(shù)，取關鍵字的隨機函數(shù)值為哈希地址，即H(key)=random(key)通常，當關鍵字長度不等時，采用此法較恰當。視不同的情況采用不同的哈希函數(shù)，考慮的因素有：計算哈希函數(shù)所需時間；關鍵字的長度；哈希表的大?。ü５刂贩秶魂P鍵字的分布情況；記錄的查找頻率。數(shù)據(jù)結構34沖突處理的方法沖突處理：當出現(xiàn)沖突時，為沖突元素找到另一個存儲位置。開放定址法基本方法：當沖突發(fā)生時，形成某個探測序列；按此序列逐個探測哈希表中的其他地址，直到找到給定關鍵字或一個空地址(開放的地址)為止，將發(fā)生沖突的記錄放到該地址中。哈希地址的計算公式是：Hi(key)=(H(key)+di)MODm，i=1,2,…,k(km-1)其中：H(key)為哈希函數(shù)；m為哈希表長；

di為第i次探測時的增量序列；

Hi(key)為經(jīng)第i次探測后得到的哈希地址。數(shù)據(jù)結構35沖突處理的方法:開放定址法線性探測再散列增量序列為：di=1,2,3,…,m-1將哈希表T[0…m-1]看成循環(huán)向量。當發(fā)生沖突時，從初次發(fā)生沖突的位置依次向后探測其他地址。探測過程終止的情況是：探測到的地址為空：表中沒有記錄。若是查找則失??；若是插入則將記錄寫入到該地址；探測到的地址有給定的關鍵字。若是查找則成功；若是插入則失?。恢钡絋[h]：仍未探測到空地址或給定的關鍵字，哈希表滿。數(shù)據(jù)結構36沖突處理的方法:開放定址法數(shù)據(jù)結構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線性探測法的特點◆

優(yōu)點：只要哈希表未滿，總能找到一個不沖突的哈希地址；◆

缺點：每個產(chǎn)生沖突的記錄被散列到離沖突最近的空地址上，從而又增加了更多的沖突機會（這種現(xiàn)象稱為沖突的“聚集”）。沖突處理的方法:開放定址法二次探測再散列增量序列為：di=12,-12,22,-22,32,……±k2(k

m/2)二次探測法的特點◆優(yōu)點：探測序列跳躍式地散列到整個表中，不易產(chǎn)生沖突的“聚集”現(xiàn)象；◆缺點：不能保證探測到散列表的所有地址。偽隨機探測再散列增量序列使用一個偽隨機函數(shù)來產(chǎn)生一個落在閉區(qū)間[1,m-1]的隨機序列。數(shù)據(jù)結構38沖突處理的方法:開放定址法例：表長為11的哈希表中已填有關鍵字17,60,29的記錄，哈希函數(shù)為H(key)=keyMOD11?，F(xiàn)有第4個記錄(關鍵字為38)，按三種處理沖突的方法，將它填入哈希表中。(1)H(38)=38MOD11=5

沖突

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

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

H3=(5+3)MOD11=8不沖突數(shù)據(jù)結構3901234567891060172938沖突處理的方法:開放定址法(2)H(38)=38MOD11=5沖突

H1=(5+12)MOD11=6

沖突

H2=(5-12)MOD11=4

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

沖突設偽隨機數(shù)序列為9，則H1=(5+9)MOD11=3

不沖突數(shù)據(jù)結構400123456789106017293838012345678910601729383838沖突處理的方法再哈希法構造若干個哈希函數(shù)，在同義詞產(chǎn)生地址沖突時，利用不同的哈希函數(shù)計算另一個哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。即：

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

其中，RHi

均是不同的哈希函數(shù)。第一次發(fā)生沖突時，用RH1計算，第二次發(fā)生沖突時，用RH2計算，依此類推直到得到的某個Hi不再沖突為止?！魞?yōu)點：不易產(chǎn)生沖突的“聚集”現(xiàn)象；◆缺點：計算時間增加。數(shù)據(jù)結構41沖突處理的方法鏈地址法將所有關鍵字為同義詞(哈希地址相同)的記錄存儲在同一線性鏈表中，并用一維數(shù)組存放鏈表的頭指針。假設哈希表長為m，設立一個一維指針數(shù)組：

ChainChainHash[m];其每個分量的初始狀態(tài)都是空指針。凡哈希地址為i

的記錄都插入到頭指針為ChainHash[i]的鏈表中，插入位置可以在表頭或表尾，或按關鍵字排序插入。優(yōu)點：不易產(chǎn)生沖突的“聚集”；刪除記錄也很簡單。數(shù)據(jù)結構42沖突處理的方法:鏈地址法例：(19,13,33,02,06,29,17,05)，

H(key)=key

%11，

尾插建表數(shù)據(jù)結構432105438761093319％11＝813％11＝233％11＝002％11＝206％11＝629％11＝717％11＝605％11＝513052919020617^^^^^^^^^^^沖突處理的方法建立一個公共溢出區(qū)在基本哈希表之外，另外設立一個溢出表保存與基本表中記錄沖突的所有記錄。所有關鍵字和基本表中關鍵字為同義詞的記錄，不管它們由哈希函數(shù)得到的哈希地址是什么，一旦發(fā)生沖突，都填入溢出表。例：已知一組關鍵字(15,4,18,7,37,47)，哈希表長度為7，哈希函數(shù)為：H(key)=key

MOD

7，用建立公共溢出區(qū)法處理沖突。數(shù)據(jù)結構44Hashtable表：散列地址

012345

6

關鍵字71537447OverTable表：溢出地址

0123456

關鍵字18哈希查找過程哈希表的主要目的是用于快速查找，且插入和刪除操作都要用到查找。由于散列表的特殊組織形式，其查找有特殊的方法。設散列為HT[0…m-1]，散列函數(shù)為H(key)，解決沖突的方法為R(x,i)，則在散列表上查找給定值K的記錄的過程如右圖所示。數(shù)據(jù)結構45給定k值計算H(k)此地址為空?關鍵字==k?查找失敗查找成功按處理沖突方法計算HiNYYN哈希查找分析從哈希查找過程可見：盡管哈希表在關鍵字與記錄的存儲地址之間建立了直接映象，但由于“沖突”，查找過程仍是一個給定值與關鍵字進行比較的過程，評價哈希查找效率仍要用ASL。哈希查找時關鍵字與給定值比較的次數(shù)取決于：哈希函數(shù)；處理沖突的方法；哈希表的填滿因子

。數(shù)據(jù)結構46表中填入的記錄數(shù)哈希表長度

=例：(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