1、第九章 查找與索引技術(shù),本章的基本內(nèi)容是： 9.4 索引的基本概念 9.5 線性索引技術(shù) 9.6 樹(shù)形索引,9.4 索引的基本概念,數(shù)據(jù)結(jié)構(gòu)的最終目的是提高數(shù)據(jù)的處理速度，索引是為了加快查找速度而設(shè)計(jì)的一種數(shù)據(jù)結(jié)構(gòu)，索引技術(shù)是組織大型數(shù)據(jù)庫(kù)以及磁盤文件的一種重要技術(shù)。,在索引問(wèn)題以及數(shù)據(jù)庫(kù)中，常常將數(shù)據(jù)元素稱為記錄。,文件：通常指存儲(chǔ)在外存上的記錄集合。 索引：把一個(gè)關(guān)鍵碼與它對(duì)應(yīng)的記錄相關(guān)聯(lián)的過(guò)程。索引由若干索引項(xiàng)構(gòu)成，索引項(xiàng)至少應(yīng)包含關(guān)鍵碼和關(guān)鍵碼對(duì)應(yīng)的記錄在存儲(chǔ)器中的位置等信息。 靜態(tài)索引：索引結(jié)構(gòu)在文件創(chuàng)建時(shí)生成，一旦生成就固定下來(lái)，只有當(dāng)文件再組織時(shí)才允許改變。 動(dòng)態(tài)索引：在文件創(chuàng)建

2、時(shí)生成索引結(jié)構(gòu)，在文件執(zhí)行插入/刪除等操作時(shí)，索引結(jié)構(gòu)本身也隨之發(fā)生改變。,9.4 索引的基本概念,索引的基本概念,線性索引：若將索引項(xiàng)組織為線性結(jié)構(gòu)，則稱其為線性索引或索引表； 樹(shù)形索引：若將索引項(xiàng)組織為樹(shù)結(jié)構(gòu)，則稱其為樹(shù)形索引。 多級(jí)索引：對(duì)索引再建立一個(gè)索引，就構(gòu)成了多級(jí)索引。,9.4 索引的基本概念,索引的基本概念,對(duì)一些大型文件，其索引本身可能也很大，在這種情況下，可以建立多級(jí)索引。,稠密索引：在線性索引中，若文件中的每個(gè)記錄對(duì)應(yīng)一個(gè)索引項(xiàng)，則這種索引稱為稠密索引。 在稠密索引中，無(wú)論文件是否按關(guān)鍵碼有序，索引項(xiàng)總是按關(guān)鍵碼順序排列。 只要內(nèi)存空間允許，通常把稠密索引存儲(chǔ)在內(nèi)存中，從

3、而大大提高記錄的查找速度。,稠密索引,9.5 線性索引技術(shù),稠密索引主要適用于靜態(tài)索引。,稠密索引示例,9.5 線性索引技術(shù),有序,無(wú)序或有序,優(yōu)點(diǎn)：實(shí)現(xiàn)對(duì)數(shù)據(jù)庫(kù)記錄有效的查找（采用折半查找技術(shù)）和隨機(jī)訪問(wèn)（按記錄號(hào)訪問(wèn)）。 缺點(diǎn)：如果文件中包含的記錄太多，索引表本身可能會(huì)因?yàn)樘蠖鵁o(wú)法在內(nèi)存中存儲(chǔ)；文件中插入或刪除記錄，必須更新稠密索引，而稠密索引的插入和刪除操作代價(jià)很高。,9.5 線性索引技術(shù),稠密索引,文件,外存,稠密索引,內(nèi)存,分塊索引,9.5 線性索引技術(shù),稠密索引空間代價(jià)很大,分塊索引,分塊索引需要將文件劃分為若干塊，且要求分塊有序。,多級(jí)索引,9.5 線性索引技術(shù),分塊索引,有序

4、,9.5 線性索引技術(shù),分塊索引,在分塊索引表中進(jìn)行的查找稱為分塊查找（也稱為索引順序查找），分兩步進(jìn)行： 在索引表中確定待查關(guān)鍵碼所在的塊； 在相應(yīng)塊中查找待查關(guān)鍵碼。,塊內(nèi)查找順序查找,設(shè)有n個(gè)記錄的文件分為m個(gè)塊，每個(gè)塊均為t個(gè)記錄，則n=mt。設(shè)Lb為查找索引表確定關(guān)鍵碼所在塊的平均查找長(zhǎng)度，Lw為在塊內(nèi)查找關(guān)鍵碼的平均查找長(zhǎng)度，則分塊查找的平均查找長(zhǎng)度為： ASL=Lb + Lw 若采用順序查找對(duì)索引表進(jìn)行查找，則分塊查找的平均查找長(zhǎng)度為：,9.5 線性索引技術(shù),分塊索引,ASL=Lb + Lw=,9.5 線性索引技術(shù),多重表,稠密索引、分塊索引,對(duì)主關(guān)鍵碼建立索引,為文件建立索引的

5、目的是什么?,對(duì)主關(guān)鍵碼進(jìn)行查找,對(duì)次關(guān)鍵碼進(jìn)行查找,對(duì)次關(guān)鍵碼建立索引,多重表、倒排表,9.5 線性索引技術(shù),多重表,多重表除了為文件建立一個(gè)主索引外，還為每個(gè)需要查找的次關(guān)鍵碼建立一個(gè)索引。 在文件中，為建立索引的次關(guān)鍵碼分別增設(shè)一個(gè)指針域，用于將次關(guān)鍵碼相同的記錄鏈結(jié)在一起（稠密索引），或?qū)⒃谕粔K中的記錄鏈結(jié)在一起（分塊索引）。,9.5 線性索引技術(shù),多重表,倒排表： 倒排表（reverse list）是對(duì)次關(guān)鍵字建立的一種索引表，在倒排表中，索引項(xiàng)包括次關(guān)鍵字的值和具有該值的各記錄的地址，其結(jié)構(gòu)如下：,9.5 線性索引技術(shù),9.5 線性索引技術(shù),倒排表,9.6 樹(shù)形索引2-3樹(shù),2

6、3 樹(shù),2-3樹(shù)：是具有下列特性的樹(shù)： 一個(gè)結(jié)點(diǎn)包含1個(gè)或者2個(gè)關(guān)鍵碼。 每個(gè)內(nèi)部結(jié)點(diǎn)有2個(gè)子女（包含一個(gè)關(guān)鍵碼）或者3個(gè)子女（包含兩個(gè)關(guān)鍵碼）。 所有葉子結(jié)點(diǎn)都在樹(shù)的同一層。,2 3 樹(shù)示例,形狀上有什么特性?,9.6 樹(shù)形索引2-3樹(shù),2 3 樹(shù)示例,包含1個(gè)或者2個(gè)關(guān)鍵碼； 有2個(gè)子女或者3個(gè)子女； 葉子結(jié)點(diǎn)在同一層。,9.6 樹(shù)形索引2-3樹(shù),2 3 樹(shù)示例,結(jié)點(diǎn)的值有什么特性?,9.6 樹(shù)形索引2-3樹(shù),2 3 樹(shù)示例,左子樹(shù)中所有結(jié)點(diǎn)的值均小于第一個(gè)關(guān)鍵碼的值； 中間子樹(shù)中所有結(jié)點(diǎn)的值均大于第一個(gè)關(guān)鍵碼的值，且小于第二個(gè)關(guān)鍵碼的值； 右子樹(shù)中所有結(jié)點(diǎn)的值均大于第二個(gè)關(guān)鍵碼的值。,9

7、.6 樹(shù)形索引2-3樹(shù),2 3 樹(shù)查找操作,21,182133,2123,9.6 樹(shù)形索引2-3樹(shù),2 3 樹(shù)插入操作,新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。,18 33,9.6 樹(shù)形索引2-3樹(shù),2 3 樹(shù)插入操作,新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。,9.6 樹(shù)形索引2-3樹(shù),2 3 樹(shù)插入操作,新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。,9.6 樹(shù)形索引2-3樹(shù),2 3 樹(shù)插入操作,新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。,18 33,12,23 30,48,10,15,20 21,24,31,45 47,50 52 55,插入,9.6 樹(shù)形索引2-3樹(shù),2 3 樹(shù)插入操作,新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。,18

8、33,12,23 30,48,10,15,20 21,24,31,45 47,分裂,50,55,52,9.6 樹(shù)形索引2-3樹(shù),2 3 樹(shù)插入操作,新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。,18 33,12,23 30,10,15,20 21,24,31,45 47,提升,50,55,48 52,9.6 樹(shù)形索引2-3樹(shù),2 3 樹(shù)刪除操作,情況1：從包含2個(gè)記錄的葉子結(jié)點(diǎn)刪除1個(gè)記錄。,解決方法：直接刪除這個(gè)記錄。,9.6 樹(shù)形索引2-3樹(shù),18 33,12,23 30,48,10,15,24,31,45 47,50 52,2 3 樹(shù)刪除操作,情況1：從包含2個(gè)記錄的葉子結(jié)點(diǎn)刪除1個(gè)記錄。,解決方法

9、：直接刪除這個(gè)記錄。,21,9.6 樹(shù)形索引2-3樹(shù),2 3 樹(shù)刪除操作,情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。,解決方法：向兄弟結(jié)點(diǎn)借一個(gè)記錄，同時(shí)修改雙親結(jié)點(diǎn)的記錄。,9.6 樹(shù)形索引2-3樹(shù),18 33,12,21 30,48,10,15,20,23,31,45 47,50 52,2 3 樹(shù)刪除操作,情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。,解決方法：向兄弟結(jié)點(diǎn)借一個(gè)記錄，同時(shí)修改雙親結(jié)點(diǎn)的記錄。,9.6 樹(shù)形索引2-3樹(shù),18 33,12,21 30,48,10,15,20,23,31,45 47,50 52,2 3 樹(shù)刪除操作,情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除

10、這個(gè)記錄。,解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)。,9.6 樹(shù)形索引2-3樹(shù),18 33,12,20 21,48,10,15,30,31,45 47,50 52,2 3 樹(shù)刪除操作,情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。,解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)。,9.6 樹(shù)形索引2-3樹(shù),18 33,12,20 21,48,10,15,30,31,45 47,50 52,2 3 樹(shù)刪除操作,情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。,解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)。,9.6 樹(shù)形索引2-3樹(shù),20 21,48

11、,33,31,45 47,50 52,2 3 樹(shù)刪除操作,情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。,10 12,18 30,解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)。,9.6 樹(shù)形索引2-3樹(shù),48,33,30,45 47,50 52,2 3 樹(shù)刪除操作,情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。,解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)，這可能減少樹(shù)的高度。,25,20,9.6 樹(shù)形索引2-3樹(shù),2 3 樹(shù)刪除操作,情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。,解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)，這可能減少樹(shù)的高度

12、。,2-3樹(shù)的優(yōu)點(diǎn)：能夠以相對(duì)較低的代價(jià)保持樹(shù)高平衡。,9.6 樹(shù)形索引2-3樹(shù),2 3 樹(shù)刪除操作,情況3：從內(nèi)部結(jié)點(diǎn)刪除一個(gè)記錄。,解決方法：將被刪除記錄用右邊子樹(shù)中的最小關(guān)鍵碼Y代替（ Y一定在某個(gè)葉子結(jié)點(diǎn)中），然后再刪除Y。,9.6 樹(shù)形索引2-3樹(shù),2 3 樹(shù)刪除操作,情況3：從內(nèi)部結(jié)點(diǎn)刪除一個(gè)記錄。,解決方法：將被刪除記錄用右邊子樹(shù)中的最小關(guān)鍵碼Y代替（ Y一定在某個(gè)葉子結(jié)點(diǎn)中），然后再刪除Y。,20 33,12,23 30,48,10,15,21,24,31,45 47,50 52,9.6 樹(shù)形索引2-3樹(shù),1. B樹(shù)的定義,9.6 樹(shù)形索引B_樹(shù),m階B樹(shù)：是滿足下列特性的樹(shù)：

13、 所有葉子結(jié)點(diǎn)都在同一層上，并且不帶信息，葉子的雙親稱為終端結(jié)點(diǎn)。 樹(shù)中每個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)； 若根結(jié)點(diǎn)不是終端結(jié)點(diǎn)，則至少有兩棵子樹(shù)； 除根結(jié)點(diǎn)外，其他非終端結(jié)點(diǎn)至少有m/2 棵子樹(shù)；,B樹(shù)是23樹(shù)的推廣，2-3樹(shù)是一個(gè)3階B樹(shù) 。,所有非終端結(jié)點(diǎn)都包含以下數(shù)據(jù)： （n，A0，K1，A1，K2，Kn，An） 其中，n（m/2 1nm 1）為關(guān)鍵碼的個(gè)數(shù)； Ki（1in）為關(guān)鍵碼，且KiKi+1（1in-1）； Ai（0in）為指向子樹(shù)根結(jié)點(diǎn)的指針，且指針Ai所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵碼均小于Ki+1大于Ki。,1. B樹(shù)的定義,9.6 樹(shù)形索引B_樹(shù),1 18,1 11,1 27,1 39,

14、3 47 53 64,1 99,F,F,F,F,F,F,F,F,F,F,F,F,2 43 78,1 35,B樹(shù)示例,9.6 樹(shù)形索引B_樹(shù),從根結(jié)點(diǎn)出發(fā)，沿指針?biāo)阉鹘Y(jié)點(diǎn)和在結(jié)點(diǎn)內(nèi)進(jìn)行順序（或折半）查找 兩個(gè)過(guò)程交叉進(jìn)行。,2.查找過(guò)程：,若查找成功，則返回指向被查關(guān)鍵字所在結(jié)點(diǎn)的指針和關(guān)鍵字在結(jié)點(diǎn)中的位置；,若查找不成功，則返回插入位置。,9.6 樹(shù)形索引B_樹(shù),在查找不成功之后，需進(jìn)行插入。 顯然，關(guān)鍵字插入的位置必定在最下 層的非葉結(jié)點(diǎn)，有下列幾種情況：,3插入,1）插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)nm，不修改指針; 例如,9.6 樹(shù)形索引B_樹(shù),2）插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù) n=m， 則需進(jìn)

15、行“結(jié)點(diǎn)分裂”，令 s = m/2， 在原結(jié)點(diǎn)中保留 （A0，K1， Ks-1，As-1）； 建新結(jié)點(diǎn) （As，Ks+1， ，Kn，An）； 將（Ks，p）插入雙親結(jié)點(diǎn)；例如,3）若雙親為空，則建新的根結(jié)點(diǎn)。 例如,9.6 樹(shù)形索引B_樹(shù),例如:下列為 3 階B-樹(shù),50, 20 40 , 80 ,插入關(guān)鍵字 = 60, 60 80 ,90,608090,90,50 80,60,30, 40 , 20 ,30 50 80,80,30,50,和插入的考慮相反，首先必須找到待刪關(guān)鍵字所在結(jié)點(diǎn)，并且要求刪除之后，結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)不能小于m/2-1，否則，要從其左(或右)兄弟結(jié)點(diǎn)“借調(diào)”關(guān)鍵字，若其

16、左和右兄弟結(jié)點(diǎn)均無(wú)關(guān)鍵字可借(結(jié)點(diǎn)中只有最少量的關(guān)鍵字),則必須進(jìn)行結(jié)點(diǎn)的“合并”。,4刪除,9.6 樹(shù)形索引B_樹(shù),1B+樹(shù)的結(jié)構(gòu)特點(diǎn)：, 每個(gè)葉子結(jié)點(diǎn)中含有 n 個(gè)關(guān)鍵字和 n 個(gè)指向記錄的指針；并且，所有葉子結(jié)點(diǎn)彼此相鏈接構(gòu)成一個(gè)有序鏈表，其頭指針指向含最小關(guān)鍵字的結(jié)點(diǎn)；,9.6 樹(shù)形索引B+樹(shù),B+樹(shù)是B-樹(shù)的一種變型, 每個(gè)非葉結(jié)點(diǎn)中的關(guān)鍵字 Ki 即為其相應(yīng)指針 Ai 所指子樹(shù)中關(guān)鍵字的最大值；, 所有葉子結(jié)點(diǎn)都處在同一層次上，每個(gè)葉子結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)均介于 m/2和 m 之間。,9.6 樹(shù)形索引B+樹(shù),2查找過(guò)程,在 B+ 樹(shù)上，既可以進(jìn)行縮小范圍的查 找，也可以進(jìn)行順序查找；, 在進(jìn)行縮小范圍的查找時(shí)，不管成功 與否，都必須查到葉子結(jié)點(diǎn)才能結(jié)束；,若在結(jié)點(diǎn)內(nèi)查找時(shí)，給定值Ki， 則 應(yīng)繼續(xù)在 Ai 所指子樹(shù)中進(jìn)行查找；,9.6 樹(shù)形索引B+樹(shù),3插入和刪除的操作