第十索引與散列靜態(tài)索引結(jié)構(gòu)動態(tài)索引結(jié)構(gòu)散列研究報告

第十章索引與散列靜態(tài)索引結(jié)構(gòu)動態(tài)索引結(jié)構(gòu)散列10.1靜態(tài)索引結(jié)構(gòu)10.1.1線形索引索引表：由一組關(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ù)ID[i-1].max_key<K<=ID[i].max_key。找到待查子表序號i,再在第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)鍵碼的鏈都保存在次索引中。倒排表一般的搜索步驟是：首先通過次索引找到主索引的主關(guān)鍵碼，再通過主關(guān)鍵碼找到相應(yīng)的對象。10.1.3m路靜態(tài)搜索樹當(dā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,(K1,P1),(K2,P2),…,(Kn,Pn)

其中，Pi是指向子樹的指針，0≤i≤n≤m;Ki是關(guān)鍵碼(2)Ki<Ki+1,1≤i≤n.

(3)在子樹Pi中所有的關(guān)鍵碼都小于Ki+1,且大于Ki,0≤i≤n

(4)在子樹Pn中所有的關(guān)鍵碼都大于Kn,而子樹P0中的所有關(guān)鍵碼都小于K1.

(5)子樹Pi也是m路搜索樹，0≤i≤n.m路搜索樹的C++描述：

template<classType>classMtree{

protected:

Mnode<Type>root;

intm;

public:

Triple<Type>&search(constType&);

AVL樹是2路搜索樹。已知m路搜索樹的度為m和它的高度為h，則樹的最大結(jié)點數(shù)為：

Tripleresule

getnode(root);

mnode<Type>*p=root,*p=NULL;

while(p!=NULL){

intI=0;p->key[(p->n)+1]=MAXKEY;

while(p->key[I+1]<x)I++;

if(p->key[I+1]==x){

result.r=p;result.I=I+1;result.tag=0;

returnresult;}

q=p;p=p->ptr[I];getnode(p);}

result.r=p;result.I=I+1;result.tag=1;returnresult;}

對于給定的關(guān)鍵碼數(shù)n，如果搜索樹是平衡的，可以使m路搜索樹的性能接近最佳.10.2.2B樹

一棵m階B樹是一棵平衡的m路搜索樹，它或者是空樹，或滿足下列條件。

(1)根結(jié)點至少有兩個子女

(2)除根結(jié)點以外的所有結(jié)點(不包括失敗結(jié)點)至少有m/2個子女。

(3)所有的失敗結(jié)點都位于同一層。B樹的類聲明和B樹結(jié)點類的聲明如下：

template<Type>classBtree;publicMtree<Type>{

public:

intinsert(constType&x);

intremove(constType&x);

};

template<classType>classMnode;

private;

intn;

Mnode<Type>*parent;

Typekey[m+1];

Mnode<Type>*ptr[m+1];

};

structTriple{

Mnode<Type>*r;

intI;inttag;

};B樹的搜索過程是一個在結(jié)點內(nèi)搜索和循某一條路徑向下一層搜索交替進(jìn)行的過程。因此，B樹的搜索時間與B樹的階層m和B樹的高度h直接有關(guān)。B樹的高度h與關(guān)鍵碼個數(shù)N的關(guān)系為：

h≤logm/2((N+1)/2)+110.2.3B樹的插入

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)鍵碼,當(dāng)再插入一個關(guān)鍵碼后結(jié)點中的狀態(tài)為

(m,P0,K1,P1,K2,P2,…,Km,Pm),其中Ki<Ki+1,1≤I<m

這是必須把結(jié)點分成p和q兩個結(jié)點.結(jié)點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é)點中.10.2.4B樹的刪除

刪除非葉結(jié)點的關(guān)鍵碼.將被刪關(guān)鍵碼Ki刪除,并從Pi所指示的子樹中的最小關(guān)鍵碼x代替Ki,然后將x所在的葉結(jié)點中將x刪除.

在葉結(jié)點上刪除有四種情況:

(1)若被刪關(guān)鍵碼所在的葉結(jié)點同時又是根結(jié)點,且該結(jié)點中關(guān)鍵碼的個數(shù)n≥2,可直接刪除.

(2)若被刪關(guān)鍵碼所在的葉結(jié)點不是根結(jié)點,且該結(jié)點中關(guān)鍵碼的個數(shù)n≥m/2,可直接刪除.(3)被刪關(guān)鍵碼所在葉結(jié)點刪除前關(guān)鍵碼有n=m/2-1,若這是與該結(jié)點相鄰的右兄弟(或左兄弟)結(jié)點的關(guān)鍵碼個數(shù)n≥m/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)鍵碼和指針填補(bǔ)、調(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,則必須按以下步驟合并這兩個結(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é)點的后面。刪去Pi+1所指的結(jié)點。

c.在雙親結(jié)點p中用后面剩余的關(guān)鍵碼和指針填補(bǔ)關(guān)鍵碼Ki+1和指針Pi+1。

d.修改雙親結(jié)點p和選定保留結(jié)點的關(guān)鍵碼個數(shù).10.2.5B+數(shù)

B+樹的定義如下：

(1)樹中每個結(jié)點最多有m棵樹

(2)根結(jié)點(非葉結(jié)點)至少有2棵樹,除根結(jié)點外，其他的非葉結(jié)點至少有m/2棵子樹，有n棵子樹的非葉結(jié)點有n-1個關(guān)鍵碼。

(3)所有的葉結(jié)點都處于同一層次上，包含了全部關(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)滿足n∈[m1/2,m1].

(5)所有的非葉結(jié)點可以看成是索引部分。結(jié)點格式同b樹在圖10.15中所有非葉結(jié)點中子樹的棵數(shù)n∈[2,4],其所有的關(guān)鍵碼都出現(xiàn)在葉結(jié)點中。上層結(jié)點中的關(guān)鍵碼都是其右子樹上最小關(guān)鍵碼的副本。

B+樹有兩個指針，一個指向樹的根結(jié)點，一個指向關(guān)鍵碼最小的結(jié)點。因此，可以對B+樹進(jìn)行兩種搜索，一種是從根結(jié)點開始，另一種是循葉結(jié)點自己拉起的鏈表順序搜索。

在B+樹上搜索在非葉結(jié)點上找到給定值，搜索并不停止，一直要找到葉結(jié)點上的給定值，搜索才結(jié)束。因此，每次搜索都從根結(jié)點走到葉結(jié)點。在B+樹中刪除葉結(jié)點中的最小關(guān)鍵碼，并不需要刪除上層結(jié)點中的副本。因為其上層的副本只起引導(dǎo)搜索的“分界關(guān)鍵碼”的作用。10.3散列(Hashing)

10.3.1詞典的抽象數(shù)據(jù)類型

在計算機(jī)科學(xué)中，詞典也當(dāng)作一種抽象數(shù)據(jù)類型。在討論詞典抽象數(shù)據(jù)類型時，把詞典定義為<名字-屬性>對的集合。通常用文件或表格來表示實際的對象集合，用文件中的記錄或表格中的表項來表示單個對象。<名字-屬性>被存于記錄(或表項)中，通過表項的關(guān)鍵碼來標(biāo)識該表項。表項的存放位置及其關(guān)鍵碼之間的對應(yīng)關(guān)系可以用一個二元組表示：

(關(guān)鍵碼key,表項位置指針)

這個二元組構(gòu)成了搜索某一指定表項的索引項?？梢允褂枚喾N方式搜索索引項。但是使用散列結(jié)構(gòu)是一種搜索效率很高的詞典的組織方法。

10.3.2散列表與散列方法

散列方法在表項的存儲位置與它的關(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)過散列函數(shù)的計算，把不同的關(guān)鍵碼映射到同一個散列地址上。稱這些散列地址相同的不同關(guān)鍵碼為同義詞。

對于散列方法需要討論兩個問題

(1)對于給定的一個關(guān)鍵碼集合，選擇一個計算簡單且地址分布比較均勻的散列函數(shù)，避免或盡量減少沖突。

(2)擬訂解決沖突的方案。

10.3.3散列函數(shù)

構(gòu)造散列函數(shù)應(yīng)注意以下幾個問題：

(1)散列函數(shù)的定義域必須包括需要存儲的全部關(guān)鍵碼，而如果散列表允許有m個地址，其值域必須在1～m-1之間。

(2)散列函數(shù)計算出來的地址應(yīng)能均勻分布在整個地址空間中。

(3)散列函數(shù)應(yīng)是簡單的。1.直接定址法

此類方法取關(guān)鍵碼的某個線形函數(shù)值作為散列地址：

Hash(key)=a*key+b{其中a,b為常數(shù)}

這類散列函數(shù)是一對一的映射，一般不會產(chǎn)生沖突。但是，它要求散列地址空間的大小與關(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%pp≤m

其中，“%”是整數(shù)除法取余的運算，要求這時的質(zhì)數(shù)p不是接近2的冪。4.平方取中法

先計算構(gòu)成關(guān)鍵碼的表示符的內(nèi)碼的平方，然后按照散列表的大小取中間的若干位作為散列地址。在平方取中法中，一般取散列地址為2的某次冪。5.折疊法

有兩種方法：

(1)移位法----把各部分的最后一位對齊相加。

(2)分界法----各部分不折斷，沿各部分的分界來回折疊，然后對齊相加，將相加的結(jié)果當(dāng)作散列地址。10.3.4處理沖突的閉散列方法

若設(shè)散列表有m個地址，將其改為m個桶。其桶號與散列地址一一對應(yīng)。每個桶可存放s個表項。如果對不同的關(guān)鍵碼用散列函數(shù)計算得到同一個散列地址，就產(chǎn)生了沖突，它們可以放到桶內(nèi)的不同位置，只有當(dāng)桶內(nèi)所s個表項都放滿后才會產(chǎn)生沖突。處理沖突的一種常用的方法就是閉散列，也叫開地址法。所有的桶都直接放在散列表數(shù)組中。因此，每一個桶只有一個表項。如果在存放表項時發(fā)現(xiàn)，該位置已被別的表項占據(jù)，則在整個表中查找新的位置，如果表未被裝滿，則在允許的范圍內(nèi)必定有新的位置。查找的主要方法有3種。

1.線形探測法

方法為：一旦發(fā)生沖突，在表中順序向后尋找“下一個”空桶Hi的遞推公式為:Hi=(Hi-1+1)%mi=1,2,….,m-1或

Hi=(H0+I)%mI=1,2,….,m-1實例:已知關(guān)鍵碼Burke,Ekers,Broad,Blum,Attlee,Alton,Hecht,Ederly

散列函數(shù)為:Hash(x)=ord(x)-ord(‘a(chǎn)’)

可得:Hash(Burke)=1,Hash(Ekers)=4,Hash(Broad)=1,

Hash(Blum)=1,Hash(Attlee)=0,Hash(Alton)=0,

Hash(Hecht)=7,Hash(Ederly)=4

012345672.二次探查法

線形探查法容易產(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()對表項