索引與散列百度文庫

1、第十章 索引與散列v靜態(tài)索引結(jié)構(gòu)v動態(tài)索引結(jié)構(gòu)v散列10.1 靜態(tài)索引結(jié)構(gòu)線形索引索引表：由一組關(guān)鍵碼和對象地址組成的索引項構(gòu)成。線形索引：在一個線形表中存放對象的索引項。一個索引項對應(yīng)數(shù)據(jù)表中一個對象的索引結(jié)構(gòu)叫做稠密索引。數(shù)據(jù)表對象在外存中按加入的順序存放而不是按關(guān)鍵碼有序存放的索引結(jié)構(gòu)。稱為索引非順序結(jié)構(gòu)。如果對象在外存中有序存放,可以采用子表索引.子表索引要求做到分塊有序。即后一個子表中所有的關(guān)鍵碼均大于前一個子表中所有對象的關(guān)鍵碼。圖10.2所示的結(jié)構(gòu)是索引順序結(jié)構(gòu)。它由索引表和子表構(gòu)成。索引時首先在索引表中搜索給定值K，然后根據(jù)IDi-1.max_key 。找到待查子表序號 i,

2、再在第 i 個子表中查找。 索引順序搜索成功的平均搜索長度為：ASLIndexSeq=ASLIndex+ASLSublist設(shè)把長度為n的表分成均等的b個子表，每個子表有S個對象，則b=n/s.又設(shè)表中每個對象的搜索概率相等。子表為1/b，子表內(nèi)各對象為1/s，則順序搜索的平均搜索長度為：ASLIndexSeq=(b+1/2+(s+1/2=(b+s/2+1子表內(nèi)折半搜索成功平均搜索程度為：ASLIndexSeq=log2(b+1-1+(s+1/2=log(1+n/s+s/2可見，索引搜索的平均搜索長度與表的長度n和子表內(nèi)對象的個數(shù)S有關(guān)。倒排表是次索引的一種實現(xiàn)。在倒排表中所有次關(guān)鍵碼的鏈都保

3、存在次索引中。倒排表一般的搜索步驟是：首先通過次索引找到主索引的主關(guān)鍵碼，再通過主關(guān)鍵碼找到相應(yīng)的對象。 當數(shù)據(jù)對象數(shù)目特別大，索引表本身也很大，在內(nèi)存中放不下，可以建立索引的索引，稱為二級索引。如果二級索引內(nèi)存中也放不下，可以建立多級索引，這種多級索引結(jié)構(gòu)形成一種m叉樹。每一個分支結(jié)點表示一個索引塊，最多有m個索引塊，每個索引塊分別給出各子樹結(jié)點最大關(guān)鍵碼和結(jié)點地址樹的葉結(jié)點中各索引項給出在數(shù)據(jù)表中存放的對象的關(guān)鍵碼和存放地址。這種m叉樹用來作為多級索引，就是m路搜索樹.10.2 動態(tài)索引結(jié)構(gòu)動態(tài)的m路搜索樹的定義為：一個空樹或滿足以下條件(1根結(jié)點最多有m棵子樹，并具有如下的結(jié)構(gòu)：n,P0

4、,(K1,P1,(K2,P2,(Kn,Pn其中，Pi是指向子樹的指針，0inm;Ki是關(guān)鍵碼(2Ki i n. (3 在子樹 Pi 中所有的關(guān)鍵碼都小于 Ki+1, 且大于 Ki,0 i n (4在子樹Pn中所有的關(guān)鍵碼都大于Kn,而子樹P0中的所有關(guān)鍵碼都小于K1.(5子樹Pi也是m路搜索樹，0in.m路搜索樹的C+描述：template class Mtree protected:Mnode root; int m;public:Triple &search(const Type& AVL樹是2路搜索樹。已知m路搜索樹的度為m和它的高度為h，則樹的最大結(jié)點數(shù)為：Triple

5、 resulegetnode(root;mnode *p=root,*p=NULL; while (p!=NULL int I=0;p->key(p->n+1=MAXKEY; while(p->keyI+1 if (p->keyI+1=x result.r=p;result.I=I+1;result.tag=0; return result; q=p;p=p->ptrI;getnode(p; result.r=p;result.I=I+1;result.tag=1;return result; 對于給定的關(guān)鍵碼數(shù)n，如果搜索樹是平衡的，可以使m路搜索樹的性能接近最

6、佳.樹一棵m階B樹是一棵平衡的m路搜索樹，它或者是空樹，或滿足下列條件。(1根結(jié)點至少有兩個子女(2除根結(jié)點以外的所有結(jié)點(不包括失敗結(jié)點至少有m/2個子女。(3所有的失敗結(jié)點都位于同一層。B樹的類聲明和B樹結(jié)點類的聲明如下：template class Btree;public Mtree public:int insert(const Type&x;int remove(const Type &x;template class Mnode; private;int n;Mnode *parent; Type keym+1;Mnode *ptrm+1; ;struct Tri

7、pleMnode *r; int I;int tag;B樹的搜索過程是一個在結(jié)點內(nèi)搜索和循某一條路徑向下一層搜索交替進行的過程。因此，B樹的搜索時間與B樹的階層m和B樹的高度h直接有關(guān)。B樹的高度h與關(guān)鍵碼個數(shù)N的關(guān)系為： hlogm/2(N+1/2+1樹的插入 B樹是從空樹起，逐個插入關(guān)鍵碼而生成的。但在插入關(guān)鍵碼時，如果結(jié)點中關(guān)鍵碼的個數(shù)超過m-1，則結(jié)點要發(fā)生“分裂” .否則直接插入. 實現(xiàn)結(jié)點“分裂”的原則是: 設(shè)結(jié)點P已經(jīng)有m-1個關(guān)鍵碼,當再插入一個關(guān)鍵碼后結(jié)點中的狀態(tài)為 (m,P0,K1,P1,K2,P2,Km,Pm,其中Ki I 這是必須把結(jié)點分成 p 和 q 兩個結(jié)點 . 結(jié)

8、點p:(m/2-1,P0,K1,P1,Km/2-1,Pm/2-1結(jié)點q:(m-m/2,Pm/2,Km/2+1,Pm/2+1,Km,Pm位于中間的關(guān)鍵碼Km/2與指向新結(jié)點q的指針形成一個二元組(Km/2,q插入到這兩個結(jié)點的雙親結(jié)點中樹的刪除刪除非葉結(jié)點的關(guān)鍵碼.將被刪關(guān)鍵碼Ki刪除,并從Pi所指示的子樹中的最小關(guān)鍵碼x代替Ki,然后將x所在的葉結(jié)點中將x刪除.在葉結(jié)點上刪除有四種情況:(1若被刪關(guān)鍵碼所在的葉結(jié)點同時又是根結(jié)點,且該結(jié)點中關(guān)鍵碼的個數(shù)n2,可直接刪除.(2若被刪關(guān)鍵碼所在的葉結(jié)點不是根結(jié)點,且該結(jié)點中關(guān)鍵碼的個數(shù)nm/2,可直接刪除.3被刪關(guān)鍵碼所在葉結(jié)點刪除前關(guān)鍵碼有n=m

9、/2-1,若這是與該結(jié)點相鄰的右兄弟(或左兄弟結(jié)點的關(guān)鍵碼個數(shù)nm/2,則可按以下的步驟調(diào)整左、右兄弟和雙親結(jié)點。a. 將雙親結(jié)點中剛剛大于(或小于被刪關(guān)鍵碼Ki下移到被刪關(guān)鍵碼所在的結(jié)點中。b. 將右兄弟(或左兄弟結(jié)點中最小(或最大關(guān)鍵碼上移到雙親結(jié)點Ki位置。c. 將右兄弟(或左兄弟結(jié)點中最左(或最右子樹指針平移到被刪關(guān)鍵碼所在結(jié)點最后(或最前子樹指針位置。d. 將右兄弟(或左兄弟結(jié)點中，將被移走的關(guān)鍵碼和指針位置用剩余的關(guān)鍵碼和指針填補、調(diào)整，再將結(jié)點中的關(guān)鍵碼個數(shù)減一。4被刪關(guān)鍵碼所在的葉結(jié)點關(guān)鍵碼的個數(shù)為n=m/2-1,若這時右兄弟(或左兄弟結(jié)點的關(guān)鍵碼個數(shù)n=m/2-1,則必須按以

10、下步驟合并這兩個結(jié)點。a. 將雙親結(jié)點p中相應(yīng)關(guān)鍵碼下移到選定保留的結(jié)點中，若要合并p中的子樹指針Pi和Pi+1所指的結(jié)點，且保留Pi所指的結(jié)點，則把p中的關(guān)鍵碼Ki+1下移到Pi所指的結(jié)點中。b. 把p中子樹指針Pi+1所指結(jié)點中的全部指針和關(guān)鍵碼都照搬到Pi所指結(jié)點的后面。刪去P i+1所指的結(jié)點。c. 在雙親結(jié)點p中用后面剩余的關(guān)鍵碼和指針填補關(guān)鍵碼Ki+1和指針Pi+1。d. 修改雙親結(jié)點p和選定保留結(jié)點的關(guān)鍵碼個數(shù). (1樹中每個結(jié)點最多有m棵樹(2根結(jié)點(非葉結(jié)點至少有2棵樹,除根結(jié)點外，其他的非葉結(jié)點至少有m/2棵子樹，有n棵子樹的非葉結(jié)點有n-1個關(guān)鍵碼。(3所有的葉結(jié)點都處于

11、同一層次上，包含了全部關(guān)鍵碼及指向相應(yīng)數(shù)據(jù)對象存放地址的指針，且葉結(jié)點本身按關(guān)鍵碼從小到大順序鏈接。(4每個葉結(jié)點中子樹棵數(shù)可以多于m，可以少于m，視關(guān)鍵碼字節(jié)及對象地址指針字節(jié)數(shù)而定。若設(shè)結(jié)點可容納最大關(guān)鍵碼數(shù)為m1，則指向?qū)ο蟮刂分羔樢灿衜1個，因此，結(jié)點中的子樹棵數(shù)應(yīng)滿足nm1/2,m1.(5所有的非葉結(jié)點可以看成是索引部分。結(jié)點格式同b樹在圖10.15中所有非葉結(jié)點中子樹的棵數(shù)n2,4,其所有的關(guān)鍵碼都出現(xiàn)在葉結(jié)點中。上層結(jié)點中的關(guān)鍵碼都是其右子樹上最小關(guān)鍵碼的副本。B+樹有兩個指針，一個指向樹的根結(jié)點，一個指向關(guān)鍵碼最小的結(jié)點。因此，可以對B+樹進行兩種搜索，一種是從根結(jié)點開始，另一

12、種是循葉結(jié)點自己拉起的鏈表順序搜索。在B+樹上搜索在非葉結(jié)點上找到給定值，搜索并不停止，一直要找到葉結(jié)點上的給定值，搜索才結(jié)束。因此，每次搜索都從根結(jié)點走到葉結(jié)點。在B+樹中刪除葉結(jié)點中的最小關(guān)鍵碼，并不需要刪除上層結(jié)點中的副本。因為其上層的副本只起引導(dǎo)搜索的“分界關(guān)鍵碼”的作用。10.3 散列詞典的抽象數(shù)據(jù)類型在計算機科學(xué)中，詞典也當作一種抽象數(shù)據(jù)類型。在討論詞典抽象數(shù)據(jù)類型時，把詞典定義為<名字-屬性>對的集合。通常用文件或表格來表示實際的對象集合，用文件中的記錄或表格中的表項來表示單個對象。<名字-屬性>被存于記錄(或表項中，通過表項的關(guān)鍵碼來標識該表項。表項的存

13、放位置及其關(guān)鍵碼之間的對應(yīng)關(guān)系可以用一個二元組表示：(關(guān)鍵碼key,表項位置指針這個二元組構(gòu)成了搜索某一指定表項的索引項。可以使用多種方式搜索索引項。但是使用散列結(jié)構(gòu)是一種搜索效率很高的詞典的組織方法。散列表與散列方法散列方法在表項的存儲位置與它的關(guān)鍵碼之間建立一個確定的對應(yīng)函數(shù)關(guān)系Hash(,使每個關(guān)鍵碼與結(jié)構(gòu)中的唯一存儲位置相對應(yīng)：Address=Hash(Rec.key散列方法：在存放表項時，通過相同函數(shù)計算存儲位置，并按此位置存放，這種方法稱為散列方法。散列函數(shù)：在散列方法中使用的函數(shù)。散列表：按上述方法構(gòu)造出來的表稱為散列表。通常關(guān)鍵碼集合比散列表地址集合大的多，因此有可能經(jīng)過散列函

14、數(shù)的計算，把不同的關(guān)鍵碼映射到同一個散列地址上。稱這些散列地址相同的不同關(guān)鍵碼為同義詞。對于散列方法需要討論兩個問題(1對于給定的一個關(guān)鍵碼集合，選擇一個計算簡單且地址分布比較均勻的散列函數(shù)，避免或盡量減少沖突。(2擬訂解決沖突的方案。構(gòu)造散列函數(shù)應(yīng)注意以下幾個問題：(1散列函數(shù)的定義域必須包括需要存儲的全部關(guān)鍵碼，而如果散列表允許有m個地址，其值域必須在1m-1之間。(2散列函數(shù)計算出來的地址應(yīng)能均勻分布在整個地址空間中。(3散列函數(shù)應(yīng)是簡單的。.直接定址法此類方法取關(guān)鍵碼的某個線形函數(shù)值作為散列地址：Hash(key=a*key+b 其中a,b為常數(shù)這類散列函數(shù)是一對一的映射，一般不會產(chǎn)生

15、沖突。但是，它要求散列地址空間的大小與關(guān)鍵碼集合的大小相同，這種要求一般很難實現(xiàn)。2.數(shù)字分析法設(shè)有n個d位數(shù)，每一位可能有r種不同的符號。這r種不同的符號在各位上出現(xiàn)的頻率不一定相同。可根據(jù)散列表的大小，選取其中各種符號分布均勻的若干位作為散列地址。計算各位數(shù)字中符號分布均勻度其中， 表示第I個符號在第k位上出現(xiàn)的次數(shù)，n/r表示各種符號在n個數(shù)中均勻出現(xiàn)的期望值。計算 值越小，表明在該位各種符號分布的越均勻。3.除留余數(shù)法設(shè)散列表中允許的地址數(shù)為m，取一個不大于m，但最接近或等于m的質(zhì)數(shù)p，或選取一個不含有小于20的質(zhì)因子的合數(shù)作為除數(shù)。這樣的散列函數(shù)為：hash(key=key%p pm

16、其中，“%”是整數(shù)除法取余的運算，要求這時的質(zhì)數(shù)p不是接近2的冪。4.平方取中法先計算構(gòu)成關(guān)鍵碼的表示符的內(nèi)碼的平方，然后按照散列表的大小取中間的若干位作為散列地址。在平方取中法中，一般取散列地址為2的某次冪。5.折疊法有兩種方法：(1移位法-把各部分的最后一位對齊相加。(2分界法-各部分不折斷，沿各部分的分界來回折疊，然后對齊相加，將相加的結(jié)果當作散列地址。處理沖突的閉散列方法若設(shè)散列表有m個地址，將其改為m個桶。其桶號與散列地址一一對應(yīng)。每個桶可存放s個表項。如果對不同的關(guān)鍵碼用散列函數(shù)計算得到同一個散列地址，就產(chǎn)生了沖突，它們可以放到桶內(nèi)的不同位置，只有當桶內(nèi)所s個表項都放滿后才會產(chǎn)生沖

17、突。處理沖突的一種常用的方法就是閉散列，也叫開地址法。所有的桶都直接放在散列表數(shù)組中。因此，每一個桶只有一個表項。如果在存放表項時發(fā)現(xiàn)，該位置已被別的表項占據(jù)，則在整個表中查找新的位置，如果表未被裝滿，則在允許的范圍內(nèi)必定有新的位置。查找的主要方法有3種。1.線形探測法方法為：一旦發(fā)生沖突，在表中順序向后尋找“下一個”空桶Hi的遞推公式為:Hi=(Hi-1+1%m i=1,2,.,m-1或Hi=(H0+I%m I=1,2,.,m-1實例:已知關(guān)鍵碼Burke,Ekers,Broad,Blum,Attlee,Alton,Hecht, Ederly散列函數(shù)為:Hash(x=ord(x-ord(a可

18、得:Hash(Burke=1,Hash(Ekers=4,Hash(Broad=1, Hash(Blum=1,Hash(Attlee=0,Hash(Alton=0,Hash(Hecht=7, Hash(Ederly=40 1 2 3 4 5 6 7 2.二次探查法線形探查法容易產(chǎn)生“堆積”的問題,即不同探查序列的關(guān)鍵碼占據(jù)可利用的空桶,使得為尋找某一關(guān)鍵碼需要經(jīng)歷土同的探查序列的元素,導(dǎo)致搜索時間增加.使用二次探查法,在表中尋找“下一個”空桶的公式為:Hi=(H0+i2%m,Hi=(H0-i2%m,I=1,2,3,(m-1/2式中H0=hash(x是通過某一個散列函數(shù)hash(對表項的關(guān)鍵碼x進行計算得到的桶號,它是一個非負整數(shù).m是表的大小,它應(yīng)是一個值為4k+3的質(zhì)數(shù),其中k是一個整數(shù).實例:若設(shè)表的長度為Tablesize=31,根據(jù)線形探查結(jié)果利用二次探查法所得到的結(jié)果為:0 1 2 3 4 5 6 7設(shè)散列表的桶數(shù)為m,待查表項的關(guān)鍵碼為x,第一次通過散列函數(shù)計