華東理工815數(shù)據(jù)結(jié)構(gòu)chap6-查找-V2003

第六章查找查找的概念順序查找折半查找靜態(tài)查找樹(shù)索引結(jié)構(gòu)與B樹(shù)散列法內(nèi)容提要查找(Search)的概念所謂查找，就是在數(shù)據(jù)集合中尋找滿(mǎn)足某種條件的數(shù)據(jù)元素。查找的結(jié)果通常有兩種可能：

查找成功，即找到滿(mǎn)足條件的數(shù)據(jù)元素。這時(shí)，作為結(jié)果,可報(bào)告該元素在結(jié)構(gòu)中的位置,還可給出該元素中的具體信息。

查找不成功，或查找失敗。作為結(jié)果,應(yīng)報(bào)告一些信息，如失敗標(biāo)志、位置等。通常稱(chēng)用于查找的數(shù)據(jù)集合為查找結(jié)構(gòu)，它是由同一數(shù)據(jù)類(lèi)型的元素（或記錄）組成。在每個(gè)元素中其值可唯一地標(biāo)識(shí)這個(gè)元素的屬性稱(chēng)為關(guān)鍵字（key）。使用基于關(guān)鍵字的查找，查找結(jié)果是唯一的。查找還可以使用基于其他屬性的查找方法，但查找結(jié)果可能不唯一。衡量一個(gè)查找算法的時(shí)間效率的標(biāo)準(zhǔn)是查找過(guò)程中關(guān)鍵字的平均比較次數(shù)，也稱(chēng)為平均查找長(zhǎng)度ASL(AverageSearchLength)。其中:n為表長(zhǎng)，Pi為查找第i個(gè)記錄的概率，且

Ci為找到該記錄時(shí)，曾和給定值比較過(guò)的關(guān)鍵字的個(gè)數(shù)靜態(tài)查找表結(jié)構(gòu)的定義#definemaxSize100//查找表最大尺寸typedefintElemType;//查找數(shù)據(jù)的類(lèi)型

typedefstruct{//查找表結(jié)點(diǎn)定義

ElemTypekey;//關(guān)鍵字域

other;//其他數(shù)據(jù)信息}ListNode;typedefstructdataList

{//查找表結(jié)點(diǎn)定義

ListNodedata[maxSize];//數(shù)據(jù)存儲(chǔ)數(shù)組

intn; //數(shù)組當(dāng)前長(zhǎng)度}順序查找(SequentialSearch)所謂順序查找,又稱(chēng)線性查找,主要用于在線性結(jié)構(gòu)中進(jìn)行查找。設(shè)若表中有n個(gè)元素，則順序查找從表的先端（或后端）

開(kāi)始，依次用各元素的關(guān)鍵字與給定值x進(jìn)行比較，直到找到與其值相等的元素，則查找成功；給出該元素在表中的位置。若整個(gè)表都已檢測(cè)完仍未找到關(guān)鍵字與x相等的元素,則查找失敗。給出失敗信息。intlocation(SqListL,DataType&x){i=0;while(i<=L.length&&L.data[i].key!=x.key)i++;if(i<=L.length)returni;elsereturn0;}//locationi<=L.lengthL.data[i].key!=x.keyST.elemiST.elemi60ikval=64kval=60i64設(shè)置“監(jiān)視哨”的順序查找算法intLinearSearch(dataList&L,ElemTypex){//在數(shù)據(jù)表L.data[0]..L.data[n-1]

中順序查找關(guān)鍵字//值與給定值x相等的數(shù)據(jù)元素,

L.data[n].key

作為//控制搜索自動(dòng)結(jié)束的“監(jiān)視哨”使用

L.data[L.n].key=x;

inti=0;

//將

x

送表尾的下一個(gè)位置設(shè)置監(jiān)視哨

while(L.data[i].key!=x)i++;

//從前向后順序查找

returni;}每次循環(huán)減少了一次控制循環(huán)結(jié)束的條件判斷i<L.length()。當(dāng)n很大時(shí)，可節(jié)省很多時(shí)間設(shè)查找第i

個(gè)元素的概率為

pi，查找到第i

個(gè)元素所需比較次數(shù)為

ci，則查找成功的平均查找長(zhǎng)度為:在順序查找并設(shè)置“監(jiān)視哨”情形，ci=i+1,i=0,1,,n-1，因此算法分析設(shè)查找概率相等，即pi=1/n,i=1,2,,n。則查找成功的平均查找長(zhǎng)度為：而查找不成功時(shí)，一定把表中所有元素檢測(cè)了一遍，一直到監(jiān)視哨。所以查找不成功的平均查找長(zhǎng)度為：ASLunsucc=

n+1。順序查找可以用遞歸方法實(shí)現(xiàn)。當(dāng)查找表中第一個(gè)元素即為所求，查找成功；否則對(duì)除第一個(gè)元素外的后續(xù)表元素構(gòu)成的查找表使用相同方法遞歸查找。當(dāng)后續(xù)查找表為空，則查找失敗。順序查找的遞歸算法int

SeqSearch(dataList&L,ElemTypex,intloc){//在數(shù)據(jù)表L.data[0]..L.data[n-1]中查找其關(guān)鍵字值//與給定值x匹配的元素,函數(shù)返回其表中位置。//參數(shù)

loc

是在表中開(kāi)始查找位置

if(loc>=L.n)return

-1;//查找失敗

elseif(L.data[loc].key==x)returnloc;

//查找成功

elsereturnSeqSearch(L,x,loc+1);

//遞歸查找}基于有序順序表的順序查找有序順序表限定表中的元素按照其關(guān)鍵字值從小到大或從大到小依次排列。在這類(lèi)表中進(jìn)行查找比表中元素任意存放，查找速度會(huì)有所提高。在有序順序表中做順序查找時(shí)，若查找不成功，不必檢測(cè)到表尾才停止，只要發(fā)現(xiàn)有比它的關(guān)鍵字值大的即可停止查找?；谟行蝽樞虮淼捻樞虿檎宜惴╥ntSeqSearch(dataList&L,ElemTypex){//在數(shù)據(jù)表L.data[0]..L.dada[n-1]

中順序查找關(guān)鍵字//值為x

的數(shù)據(jù)元素

for(inti=0;i<L.n;i++)

if(L.data[i].key==x)returni;//成功成功

elseif(L.data[i].key>x)break;//查找失敗return

-1;

//順序查找失敗,返回失敗信息}折半查找折半查找只適用于有序順序表。做折半查找時(shí),先求位于查找區(qū)間正中的元素的下標(biāo)mid，用其關(guān)鍵字值與給定值x比較:A.data[mid].key==x,查找成功；A.data[mid].key>x,把查找區(qū)間縮小到表的前半部分，繼續(xù)折半查找；A.data[mid].key<x，把查找區(qū)間縮小到表的后半部分，繼續(xù)折半查找。如果查找區(qū)間已縮小到一個(gè)元素，仍未找到想要查找的元素，則查找失敗。查找成功的例子-101346810126012345678查找lowmidhigh6

6810125678lowmidhigh665lowmidhigh6low

指示查找區(qū)間的下界;high

指示查找區(qū)間的上界;mid=(low+high)/2。查找失敗的例子-101346810125012345678查找lowmidhigh5

6810125678lowmidhigh655lowmidhigh5折半查找的算法intBinSearch(dataList&L,ElemTypex){

inthigh=L.n-1,low=0,mid;

while(low<=high){ //low>high表明失敗mid=(low+high)／2;

if(L.data[mid].key<x)low=mid+1; //右縮查找區(qū)間

else

if(L.data[mid].key>x)high=mid-1;//左縮查找區(qū)間

elsereturnmid;//查找成功

}

return

-1;//查找失敗}遞歸的折半查找算法intBinSearch(dataList&L,ElemTypex,

intlow,

inthigh){intmid=-1;if(low<=high){

mid=(low+high)／2;

if(L.data[mid].key<x)mid=BinSearch(L,x,mid+1,high);

elseif(L.data[mid].key>x) mid=BinSearch(L,x,low,mid-1);}returnmid;}//調(diào)用方式

BinSearch(L,x,0,L.n-1);有序順序表的折半查找的判定樹(shù)

(10,20,30,40,50,60)50(20，30)（-∞，10）（10,20）(30,40)(40,50)(50,60)(60,70)======30<<<<<<>>>>>>204060ASLunsucc=(2*1+3*6)/7=20/7ASLsucc

=(1+2*2+3*3)/6=14/6

10表示有序表中已有的結(jié)點(diǎn)，樹(shù)的根結(jié)點(diǎn)是查找序列的第一個(gè)數(shù)據(jù)元素失敗結(jié)點(diǎn)，表示表中兩個(gè)相鄰元素之間的不在表中的數(shù)據(jù)值的集合折半查找性能分析若設(shè)

n=2h-1，則描述折半查找的判定樹(shù)是高度為

h

的滿(mǎn)二叉樹(shù)。

2h=n+1,h=log2(n+1)第1層結(jié)點(diǎn)有1個(gè),查找第1層結(jié)點(diǎn)要比較1次;第2層結(jié)點(diǎn)有2個(gè),查找第2層結(jié)點(diǎn)要比較2次;…,

第i(1

i

h)

層結(jié)點(diǎn)有2i-1個(gè),查找第i層結(jié)點(diǎn)要比較i

次，…。假定每個(gè)結(jié)點(diǎn)的查找概率相等，即pi=1/n，則查找成功的平均查找長(zhǎng)度為可以用歸納法證明：這樣索引結(jié)構(gòu)與B樹(shù)當(dāng)數(shù)據(jù)元素個(gè)數(shù)很多，n很大時(shí)，可采用索引方法來(lái)實(shí)現(xiàn)存儲(chǔ)和查找。示例：有一個(gè)存放職工信息的數(shù)據(jù)表，每一個(gè)職工元素有近1k字節(jié)的信息，正好占據(jù)一個(gè)頁(yè)塊的存儲(chǔ)空間。假設(shè)內(nèi)存工作區(qū)僅能容納64k字節(jié)的數(shù)據(jù)，在某一時(shí)刻內(nèi)存最多可容納64個(gè)元素以供查找。線性索引(LinearIndexList)

01k2k3k4k5k6k7k職工號(hào)

姓名

性別

職務(wù)

婚否

83

林達(dá)

女

教師已婚

…

08

陳洱

男

教師已婚...

03

張珊

男

教務(wù)員已婚...

95

李斯

女

實(shí)驗(yàn)員未婚...

24

何武

男

教師已婚...

47

王璐

男

教師已婚...

17

劉淇

男

實(shí)驗(yàn)員未婚...

51

岳跋

女

教師未婚...

索引表數(shù)據(jù)表keyaddr032k081k176k244k475k517k830953k如果元素總數(shù)有

14400

個(gè)，不可能把所有元素的數(shù)據(jù)一次都讀入內(nèi)存。無(wú)論是順序查找或折半查找,都需要多次讀取外存記錄。如果在索引表中每一個(gè)索引項(xiàng)占4個(gè)字節(jié)，索引項(xiàng)給出一個(gè)職工元素的關(guān)鍵字及其存儲(chǔ)地址，用以索引一個(gè)職工元素，則14400

個(gè)索引項(xiàng)需要56.25k字節(jié)，在內(nèi)存中可以容納所有的索引項(xiàng)。這樣只需從外存中把索引表讀入內(nèi)存，經(jīng)過(guò)查找索引后確定了職工元素的存儲(chǔ)地址，再經(jīng)過(guò)1次讀取元素操作就可以完成查找。只需2次讀盤(pán)即可。所以，采用索引結(jié)構(gòu)可以加速查找速度，特別是在有大量?jī)?nèi)外存交換的情形。索引可分為2種：稠密索引：一個(gè)索引項(xiàng)對(duì)應(yīng)數(shù)據(jù)表中一個(gè)元素。當(dāng)元素在外存中按加入順序存放而不是按關(guān)鍵字值有序存放時(shí)必須采用稠密索引，這時(shí)的索引結(jié)構(gòu)叫做索引非順序結(jié)構(gòu)。稀疏索引：當(dāng)元素在外存中有序存放時(shí)，可以把所有n個(gè)元素分為b個(gè)子表存放，一個(gè)索引項(xiàng)對(duì)應(yīng)數(shù)據(jù)表中一組元素（子表）。第i個(gè)索引項(xiàng)是第i個(gè)子表的索引項(xiàng),i=0,1,…,n-1。這種索引結(jié)構(gòu)叫做索引順序結(jié)構(gòu)。對(duì)索引順序結(jié)構(gòu)進(jìn)行查找時(shí)，采用分塊查找:先在索引表ID

中查找給定值K,確定滿(mǎn)足

ID[i-1].max_key<K

ID[i].max_key 的

i

值,即待查元素可能在的子表的序號(hào)。2212133029333642444839406074567980669282889894子表1子表2子表3子表4數(shù)據(jù)區(qū)33488098索引表1234max_max_keyaddr再在第i個(gè)子表中按給定值查找要求的元素。索引表是按max_key有序的，且長(zhǎng)度也不大，可以折半查找，也可以順序查找。各子表內(nèi)各個(gè)元素如果也按元素關(guān)鍵字值有序，可以采用折半查找或順序查找;如果不是按元素關(guān)鍵字值有序，只能順序查找。索引順序查找的查找成功時(shí)的平均查找長(zhǎng)度

ASLIndexSeq=ASLIndex

+ASLSubList 其中,

ASLIndex

是在索引表中查找子表位置的平均查找長(zhǎng)度，ASLSubList是在子表內(nèi)查找元素位置的查找成功的平均查找長(zhǎng)度。用數(shù)學(xué)方法可導(dǎo)出,當(dāng)s=

時(shí)，ASLIndexSeq取極小值+1。這個(gè)值比順序查找強(qiáng)，但比折半查找差。但如果子表存放在外存時(shí)，還要受到頁(yè)塊大小的制約。若采用折半查找確定元素所在的子表,則查找成功時(shí)的平均查找長(zhǎng)度為

ASLIndexSeq=ASLIndex

+ASLSubList

log2(b+1)-1+(s+1)/2

log2(1+n/s)+s/2m

路查找樹(shù)當(dāng)數(shù)據(jù)元素?cái)?shù)目特別大，索引表本身很大，在內(nèi)存中放不下，需要分批多次讀取外存才能把索引表查找一遍。此時(shí),可以建立索引的索引（二級(jí)索引）。二級(jí)索引中一個(gè)索引項(xiàng)對(duì)應(yīng)一個(gè)索引塊，登記該索引塊的最大關(guān)鍵字及該索引塊的存儲(chǔ)地址。如果二級(jí)索引在內(nèi)存中也放不下，需要分為許多塊多次從外存讀入?？梢越⒍?jí)索引的索引（三級(jí)索引）。這時(shí)，訪問(wèn)外存次數(shù)等于讀入索引次數(shù)再加上1次讀取元素。必要時(shí),還可以有4級(jí)索引,5級(jí)索引,…。這種多級(jí)索引結(jié)構(gòu)形成一種m叉樹(shù)。樹(shù)中每一個(gè)分支結(jié)點(diǎn)表示一個(gè)索引塊,每個(gè)索引項(xiàng)給出各子樹(shù)結(jié)點(diǎn)的最大關(guān)鍵字和結(jié)點(diǎn)地址。02061115182329323841454952607795(06,)(15,)(23,)(32,)(41,)(49,)(60,)(95,)(23,)(49,)(95,)roothead多級(jí)索引結(jié)構(gòu)形成m路查找樹(shù)數(shù)據(jù)區(qū)一級(jí)索引（葉結(jié)點(diǎn)）二級(jí)索引三級(jí)索引四級(jí)索引樹(shù)的葉結(jié)點(diǎn)中各索引項(xiàng)給出在數(shù)據(jù)表中存放的元素的關(guān)鍵字和存放地址。這種m叉樹(shù)用來(lái)作為多級(jí)索引，就是m路查找樹(shù)。B

樹(shù)B樹(shù)的定義： 一棵m

階B樹(shù)是一棵平衡的

m路查找樹(shù)，它或者是空樹(shù)，或者是滿(mǎn)足下列性質(zhì)的樹(shù)：每個(gè)結(jié)點(diǎn)最多有m

棵子樹(shù)，并具有如下結(jié)構(gòu)：

n,P0,(K1,P1),(K2,P2),……,(Kn,Pn)。其中,Pi是指向子樹(shù)的指針,0≤i≤n＜m;Ki是關(guān)鍵字,

1≤i≤n＜m。Ki<Ki+1,1≤i＜n。根結(jié)點(diǎn)至少有2個(gè)子女;除根結(jié)點(diǎn)外的所有結(jié)點(diǎn)至少有m/2

個(gè)子女。所有失敗結(jié)點(diǎn)都位于同一層，它們是查找失敗時(shí)查找指針到達(dá)的結(jié)點(diǎn)。所有失敗結(jié)點(diǎn)都是空結(jié)點(diǎn)，指向它們的指針都為空。除失敗結(jié)點(diǎn)外，其他結(jié)點(diǎn)

在子樹(shù)Pi中所有的關(guān)鍵字都小于

Ki+1,且大于Ki，0＜i＜n。在子樹(shù)Pn中所有的關(guān)鍵字都大于Kn；在子樹(shù)P0

中的所有關(guān)鍵字都小于K1。子樹(shù)Pi也是m路查找樹(shù)，0≤i≤n。事實(shí)上，在B樹(shù)的每個(gè)結(jié)點(diǎn)中還包含有一組 指針D[m]，指向?qū)嶋H元素的存放地址。K[i]與D[i]（1≤i≤n＜m）形成一個(gè)索引項(xiàng)(K[i],D[i])。下面左圖不是B樹(shù)。右圖是B樹(shù)。302040253010154550root4550354020root101525非B樹(shù) B樹(shù)35B樹(shù)的定義和B樹(shù)結(jié)點(diǎn)的定義typedefintBTreeData;//關(guān)鍵字的數(shù)據(jù)類(lèi)型typedefstructnode{//B樹(shù)結(jié)點(diǎn)的定義

intn;//結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)

structnode

*parent;//雙親指針

BTreeDatakey[m+1];//關(guān)鍵字?jǐn)?shù)組

1m-1

structnode*ptr[m+1];//子樹(shù)指針數(shù)組0m-1}BTreeNode,*BTree;//B樹(shù)定義

nptr0key1ptr1key2ptr2…ptrn-1keynptrn

B樹(shù)的查找算法B樹(shù)的查找過(guò)程是從根開(kāi)始的一個(gè)在結(jié)點(diǎn)內(nèi)查找和循某一條路徑向下一層查找交替進(jìn)行的過(guò)程。B樹(shù)的查找時(shí)間與B樹(shù)的階數(shù)m

和B樹(shù)的高度h

直接有關(guān)。304550354020root101525查找15查找43在查找不成功之后，需進(jìn)行插入。有下列幾種情況：1）插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)n<m，不修改指針;B樹(shù)的插入2）插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)n=m，則需進(jìn)行“結(jié)點(diǎn)分裂”，令s=m/2，在原結(jié)點(diǎn)中保留

（P0，K1，。。。，Ks-1，Ps-1）；建新結(jié)點(diǎn)（Ps，Ks+1，。。。，Kn，Pn）；

將（Ks，p）插入雙親結(jié)點(diǎn)；3）若雙親為空，則建新的根結(jié)點(diǎn)。例如:下列為3階B-樹(shù)每個(gè)結(jié)點(diǎn)最少3/2-1=1個(gè)Key，最多3-1=2個(gè)key50204080插入關(guān)鍵字=60,

608090,60809090

50806030,40203050808030

50從空樹(shù)開(kāi)始加入關(guān)鍵字(53,75,139,49,145,36)建立3階B樹(shù)4975n=1加入5353n=2加入755375n=3加入1397513953n=5加入49,145751391454953n=6加入361391455336在插入新關(guān)鍵字時(shí)，需要自底向上分裂結(jié)點(diǎn)，最壞情況下從被插關(guān)鍵字所在葉結(jié)點(diǎn)到根的路徑上的所有結(jié)點(diǎn)都要分裂。若設(shè)B樹(shù)的高度為h,

那么在自頂向下查找到葉結(jié)點(diǎn)的過(guò)程中需要進(jìn)行h

次讀盤(pán)。n=7加入10149533613914510175

和插入的考慮相反，刪除首先必須找到待刪關(guān)鍵字所在結(jié)點(diǎn)，并且要求刪除之后，結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)不能小于m/2-1，否則，要從其左(或右)兄弟結(jié)點(diǎn)“借調(diào)”關(guān)鍵字，若其左和右兄弟結(jié)點(diǎn)均無(wú)關(guān)鍵字可借(結(jié)點(diǎn)中只有最少量的關(guān)鍵字),則必須進(jìn)行結(jié)點(diǎn)的“合并”。B樹(shù)的刪除B樹(shù)的刪除刪除關(guān)鍵字Ki分為在葉子結(jié)點(diǎn)上刪除和在非葉子結(jié)點(diǎn)上刪除：若Ki不在葉子結(jié)點(diǎn)上,則在刪去Ki之后,應(yīng)以該結(jié)點(diǎn)Pi指針?biāo)甘咀訕?shù)中的最小關(guān)鍵字x來(lái)代替被刪關(guān)鍵字Ki所在的位置。在x所在的葉結(jié)點(diǎn)中刪除x。在葉結(jié)點(diǎn)上的刪除有4種情況。情況1被刪關(guān)鍵字所在葉結(jié)點(diǎn)同時(shí)又是根結(jié)點(diǎn)且刪除前該結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)n

2，則直接刪去該關(guān)鍵字并將修改后的結(jié)點(diǎn)寫(xiě)回磁盤(pán)。3649m=3刪除3649情況2被刪關(guān)鍵字所在葉結(jié)點(diǎn)不是根結(jié)點(diǎn)且刪除前該結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)n

m/2

,則直接刪去該關(guān)鍵字并將修改后的結(jié)點(diǎn)寫(xiě)回磁盤(pán),刪除結(jié)束。5558刪除55簡(jiǎn)單刪除7580m=3刪除5510406560703050acbdefgh58758010406560703050acbdefgh被刪關(guān)鍵字所在葉結(jié)點(diǎn)在刪除前結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)

n=m/2

-1，若這時(shí)與該結(jié)點(diǎn)相鄰的右兄弟（或左兄弟）

結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)

n

m/2，則調(diào)整：該結(jié)點(diǎn)右兄弟

(或左兄弟)

結(jié)點(diǎn)其雙親結(jié)點(diǎn)以達(dá)到新的平衡。情況3結(jié)點(diǎn)聯(lián)合調(diào)整55587580m=3刪除6510406560703050acbdefgh55588010407060753050acbdefgh調(diào)整g,c,h刪除65被刪關(guān)鍵字所在葉結(jié)點(diǎn)在刪除前的關(guān)鍵字個(gè)數(shù)n=m/2

-1，若這時(shí)與該結(jié)點(diǎn)相鄰的右兄弟（或左兄弟）結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)n=m/2

-1，則必須合并這兩個(gè)結(jié)點(diǎn)。情況455刪除55結(jié)點(diǎn)合并80m=3刪除5510406058753050acbdefgh合并f,g5860801040753050acbdefh8055刪除80結(jié)點(diǎn)合并m=3刪除8010406058753050acbdefgh合并g,h6075551040583050acbdefg1.首先需要找到這個(gè)關(guān)鍵字Ki所在的結(jié)點(diǎn),從中刪去這個(gè)關(guān)鍵字。2.若該結(jié)點(diǎn)不是葉結(jié)點(diǎn),則在刪去Ki之后,應(yīng)以該結(jié)點(diǎn)Pi所指示子樹(shù)中的最小關(guān)鍵字x來(lái)代替被刪關(guān)鍵字Ki所在的位置。3.在x所在的葉結(jié)點(diǎn)中刪除x。在非葉子結(jié)點(diǎn)上刪除55刪除50刪除5555587580m=3刪除5010406560703050acbdefgh587580刪除55104065607030acbdefgh用55取代用58取代587580104065607030acbdefgh合并f,g587580104060657030acbdefh結(jié)點(diǎn)合并與調(diào)整刪除70刪除55用58取代5880104060657530acbdefh刪除70用75取代刪除7558104060658030acbdefh刪除75用80取代調(diào)整f,c,h58801040606530acbdefh刪除1080304060fh5865dbB+樹(shù)一棵m階B+樹(shù)是B樹(shù)的特殊情形，它與B樹(shù)的不同之處在于：所有關(guān)鍵字都存放在葉結(jié)點(diǎn)中，上層的非葉結(jié)點(diǎn)的關(guān)鍵字是其子樹(shù)中最大關(guān)鍵字的復(fù)寫(xiě)。葉結(jié)點(diǎn)包含了全部關(guān)鍵字及指向相應(yīng)數(shù)據(jù)記錄存放地址的指針，且葉結(jié)點(diǎn)本身按關(guān)鍵字從小到大順序鏈接（一級(jí)稠密索引）。一棵m階B+樹(shù)的結(jié)構(gòu)定義如下：每個(gè)結(jié)點(diǎn)最多有m棵子樹(shù)；根結(jié)點(diǎn)最少有1棵子樹(shù)，除根結(jié)點(diǎn)外，其他結(jié)點(diǎn)至少有m/2棵子樹(shù)；有m棵子樹(shù)的結(jié)點(diǎn)有m個(gè)關(guān)鍵字。所有非葉結(jié)點(diǎn)可以看成是葉結(jié)點(diǎn)的索引，結(jié)點(diǎn)中關(guān)鍵字Ki

與指向子樹(shù)的指針Pi

構(gòu)成對(duì)子樹(shù)的索引項(xiàng)(Ki,Pi)，Ki

是子樹(shù)中最大的關(guān)鍵字。所有葉結(jié)點(diǎn)在同一層，按從小到大的順序存放全部關(guān)鍵字，各個(gè)葉結(jié)點(diǎn)順序鏈接。葉結(jié)點(diǎn)中存放的是對(duì)實(shí)際數(shù)據(jù)記錄的索引，每個(gè)索引項(xiàng)(Ki,Pi)給出記錄的存儲(chǔ)地址。在一棵4階B+樹(shù)中，除根結(jié)點(diǎn)外，所有非葉結(jié)點(diǎn)中的子樹(shù)棵數(shù)4/2

≤n≤4，其所有的關(guān)鍵字都出現(xiàn)在葉結(jié)點(diǎn)中，且在葉結(jié)點(diǎn)中關(guān)鍵字有序地排列。上面各層結(jié)點(diǎn)中的關(guān)鍵字都是其子樹(shù)上最大關(guān)鍵字的副本。m=41015

18222734

404447

5467

727478

8184

15344767

7884

6784

root通常在B+樹(shù)中有兩個(gè)頭指針：一個(gè)指向B+樹(shù)的根結(jié)點(diǎn)，一個(gè)指向關(guān)鍵字最小的葉結(jié)點(diǎn)。因此，可以對(duì)B+樹(shù)進(jìn)行兩種搜索運(yùn)算：循葉結(jié)點(diǎn)自己拉起的鏈表順序搜索；從根開(kāi)始進(jìn)行自頂向下直到葉結(jié)點(diǎn)的隨機(jī)搜索。B+樹(shù)的插入僅在葉結(jié)點(diǎn)上進(jìn)行。每插入一個(gè)（關(guān)鍵字-指針）索引項(xiàng)后都要判斷結(jié)點(diǎn)中的索引項(xiàng)個(gè)數(shù)是否超出范圍m。

當(dāng)插入后葉結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)n>m

時(shí)，需要將葉結(jié)點(diǎn)分裂為兩個(gè)結(jié)點(diǎn)：它們包含的關(guān)鍵字個(gè)數(shù)分別為

(m+1)/2

和

(m+1)/2。并且它們的雙親結(jié)點(diǎn)中應(yīng)同時(shí)包含這兩個(gè)結(jié)點(diǎn)的最大關(guān)鍵字和結(jié)點(diǎn)地址。在非葉結(jié)點(diǎn)中關(guān)鍵字的插入與葉結(jié)點(diǎn)的插入情況類(lèi)似，但在做根結(jié)點(diǎn)分裂時(shí)，必須創(chuàng)建新的父結(jié)點(diǎn)，作為樹(shù)的新根。B+樹(shù)的插入例如，在一棵4階B+樹(shù)中的插入過(guò)程如下。連續(xù)插入24,72,01,39的B+樹(shù)01243972加入53,結(jié)點(diǎn)分裂01243953723972加入63,90,88,15的B+樹(shù)011524395363723972908890加入10,44,68,74的B+樹(shù)0110154453631539632439687274889072907290B+樹(shù)的刪除B+樹(shù)的刪除僅在葉結(jié)點(diǎn)上進(jìn)行。當(dāng)在葉結(jié)點(diǎn)上刪除一個(gè)（關(guān)鍵字-指針）索引項(xiàng)后，結(jié)點(diǎn)中的索引項(xiàng)個(gè)數(shù)仍然不少于m/2，這屬于簡(jiǎn)單刪除，其上層索引可以不改變。如果刪除結(jié)點(diǎn)的最大關(guān)鍵字，但因在其上層的副本只起了一個(gè)引導(dǎo)搜索的“分界關(guān)鍵字”的作用，所以即使樹(shù)中已經(jīng)刪除了關(guān)鍵字，但上層的副本仍然可以保留。如果在葉結(jié)點(diǎn)中刪除后，結(jié)點(diǎn)中索引項(xiàng)個(gè)數(shù)小于m/2，必須做結(jié)點(diǎn)的調(diào)整或合并工作。

從4階B+樹(shù)中做簡(jiǎn)單刪除

m=41015182227344044475467727478818415344767

7884

6784簡(jiǎn)單刪除關(guān)鍵字47,上層索引可以不改10151822273440445467727478818415344767

7884

6784

從4階B+樹(shù)中刪除時(shí)的調(diào)整

m=41015182227344044475467727478818415344767

7884

6784刪除關(guān)鍵字15,調(diào)整上層索引改變1018

2227344044475467727478818418344767

7884

6784如果右兄弟結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)已達(dá)到下限m/2，沒(méi)有多余的關(guān)鍵字可以移入被刪關(guān)鍵字所在的結(jié)點(diǎn)，必須進(jìn)行結(jié)點(diǎn)的合并。將右兄弟結(jié)點(diǎn)中的所有（關(guān)鍵字-指針）索引項(xiàng)移入被刪關(guān)鍵字所在結(jié)點(diǎn)，再將右兄弟結(jié)點(diǎn)刪去。這種結(jié)點(diǎn)合并將導(dǎo)致雙親結(jié)點(diǎn)中“分界關(guān)鍵字”的減少，有可能減到非葉結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)的下限m/2

以下。這樣將引起雙親結(jié)點(diǎn)的調(diào)整或合并。刪除關(guān)鍵字74,78,A，B結(jié)點(diǎn)合并1018

2227344044475467727478818418344767

7884

67841018

2227344044475467728184183447

6784

4784ABCD散列(Hashing)散列方法在表項(xiàng)存儲(chǔ)位置與其關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)函數(shù)關(guān)系Hash(

)，使每個(gè)關(guān)鍵字與結(jié)構(gòu)中一個(gè)唯一存儲(chǔ)位置相對(duì)應(yīng)：

Address

＝Hash(Rec.key)在查找時(shí),先對(duì)表項(xiàng)的關(guān)鍵字進(jìn)行函數(shù)計(jì)算,把函數(shù)值當(dāng)做表項(xiàng)的存儲(chǔ)位置,在結(jié)構(gòu)中按此位置取表項(xiàng)比較。若關(guān)鍵字相等,則查找成功。在存放表項(xiàng)時(shí),依相同函數(shù)計(jì)算存儲(chǔ)位置,并按此位置存放。這種方法就是散列方法。在散列方法中使用的轉(zhuǎn)換函數(shù)叫做散列函數(shù)。按此方法構(gòu)造出來(lái)的表或結(jié)構(gòu)就叫做散列表。{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}

例如：對(duì)于如下9個(gè)關(guān)鍵字設(shè)

哈希函數(shù)f(key)=

(Ord(第一個(gè)字母)-Ord('A')+1)/2ChenZhaoQianSunLiWuHanYeDei問(wèn)題:

若添加關(guān)鍵字Zhou,怎么辦？1)哈希函數(shù)是一個(gè)映象，即：將關(guān)鍵字的集合映射到某個(gè)地址集合上，

它的設(shè)置很靈活，只要這個(gè)地址集合的大小不超出允許范圍即可;從這個(gè)例子可見(jiàn)，2)由于哈希函數(shù)是一個(gè)壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，即：key1key2，而f(key1)=f(key2)。產(chǎn)生沖突的關(guān)鍵字叫同義詞3)很難找到一個(gè)不產(chǎn)生沖突的哈希函數(shù)。這是因?yàn)椋涸谠O(shè)計(jì)查找表時(shí)，只可能知道關(guān)鍵字所屬范圍，而不知道確切的關(guān)鍵字。一般情況下，只能選擇恰當(dāng)?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。因此，在構(gòu)造這種特殊的“查找表”時(shí)，除了需要選擇一個(gè)“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外;還需要找到一種“處理沖突”

的方法。散列函數(shù)構(gòu)造散列函數(shù)時(shí)的幾點(diǎn)要求：散列函數(shù)應(yīng)是簡(jiǎn)單的，能在較短的時(shí)間內(nèi)計(jì)算出結(jié)果。散列函數(shù)的定義域必須包括需要存儲(chǔ)的全部關(guān)鍵字,如果散列表允許有m個(gè)地址時(shí)，其值域必須在0到m-1之間。散列函數(shù)計(jì)算出來(lái)的地址應(yīng)能均勻分布在整個(gè)地址空間中。構(gòu)造哈希函數(shù)的常用方法

對(duì)數(shù)字的關(guān)鍵字可有下列構(gòu)造方法:

若是非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行數(shù)字化處理。1.直接定址法3.平方取中法5.除留余數(shù)法4.折疊法6.隨機(jī)數(shù)法2.數(shù)字分析法哈希函數(shù)為關(guān)鍵字的線性函數(shù)

H(key)=key

或者

H(key)=akey+b1.

直接定址法此法僅適合于：地址集合的大小==關(guān)鍵字集合的大小此方法僅適合于：能預(yù)先估計(jì)出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。2.數(shù)字分析法假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。數(shù)字分析法構(gòu)造：對(duì)關(guān)鍵字進(jìn)行分析，取關(guān)鍵字的若干位或其組合作哈希地址適于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關(guān)鍵字事先知道的情況例有80個(gè)記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地址為2位十進(jìn)制數(shù)8134653281372242813874228130136781322817813389678136853781419355…..…..分析：位只取8位只取1位只取3、4位只取2、7、5位數(shù)字分布近乎隨機(jī)所以：取位任意兩位或兩位與另兩位的疊加作哈希地址除留余數(shù)法構(gòu)造：取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng)m的數(shù)p除后所得余數(shù)作哈希地址，即H(key)=keyMODp，pm特點(diǎn)簡(jiǎn)單、常用，可與上述幾種方法結(jié)合使用p的選取很重要；p選的不好，容易產(chǎn)生同義詞

實(shí)際造表時(shí)，采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。三、處理沖突的方法