北京信息科技大學(xué)數(shù)據(jù)機(jī)構(gòu)課件第9章 索引技術(shù).ppt

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

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

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

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

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

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

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

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

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

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

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

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

13、 所有葉子結(jié)點都在同一層上，并且不帶信息，葉子的雙親稱為終端結(jié)點。 樹中每個結(jié)點至多有m棵子樹； 若根結(jié)點不是終端結(jié)點，則至少有兩棵子樹； 除根結(jié)點外，其他非終端結(jié)點至少有m/2 棵子樹；,B樹是23樹的推廣，2-3樹是一個3階B樹 。,所有非終端結(jié)點都包含以下數(shù)據(jù)： （n，A0，K1，A1，K2，Kn，An） 其中，n（m/2 1nm 1）為關(guān)鍵碼的個數(shù)； Ki（1in）為關(guān)鍵碼，且KiKi+1（1in-1）； Ai（0in）為指向子樹根結(jié)點的指針，且指針Ai所指子樹中所有結(jié)點的關(guān)鍵碼均小于Ki+1大于Ki。,1. B樹的定義,9.6 樹形索引B_樹,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樹示例,9.6 樹形索引B_樹,從根結(jié)點出發(fā)，沿指針?biāo)阉鹘Y(jié)點和在結(jié)點內(nèi)進(jìn)行順序（或折半）查找 兩個過程交叉進(jìn)行。,2.查找過程：,若查找成功，則返回指向被查關(guān)鍵字所在結(jié)點的指針和關(guān)鍵字在結(jié)點中的位置；,若查找不成功，則返回插入位置。,9.6 樹形索引B_樹,在查找不成功之后，需進(jìn)行插入。 顯然，關(guān)鍵字插入的位置必定在最下 層的非葉結(jié)點，有下列幾種情況：,3插入,1）插入后，該結(jié)點的關(guān)鍵字個數(shù)nm，不修改指針; 例如,9.6 樹形索引B_樹,2）插入后，該結(jié)點的關(guān)鍵字個數(shù) n=m， 則需進(jìn)

15、行“結(jié)點分裂”，令 s = m/2， 在原結(jié)點中保留 （A0，K1， Ks-1，As-1）； 建新結(jié)點 （As，Ks+1， ，Kn，An）； 將（Ks，p）插入雙親結(jié)點；例如,3）若雙親為空，則建新的根結(jié)點。 例如,9.6 樹形索引B_樹,例如:下列為 3 階B-樹,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é)點，并且要求刪除之后，結(jié)點中關(guān)鍵字的個數(shù)不能小于m/2-1，否則，要從其左(或右)兄弟結(jié)點“借調(diào)”關(guān)鍵字，若其

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