C++數(shù)據(jù)結(jié)構(gòu)(第2版)課件第9章 索引技術.ppt

第 9 章 索引技術,本章的基本內(nèi)容是： 索引的基本概念 線性索引技術 樹形索引,9.1 索引的基本概念,數(shù)據(jù)結(jié)構(gòu)的最終目的是提高數(shù)據(jù)的處理速度，索引是為了加快查找速度而設計的一種數(shù)據(jù)結(jié)構(gòu)，索引技術是組織大型數(shù)據(jù)庫以及磁盤文件的一種重要技術。,在索引問題以及數(shù)據(jù)庫中，常常將數(shù)據(jù)元素稱為記錄。,文件：通常指存儲在外存上的記錄集合。 索引：把一個關鍵碼與它對應的記錄相關聯(lián)的過程稱為索引。索引由若干索引項構(gòu)成。 索引項至少應包含關鍵碼和關鍵碼對應的記錄在存儲器中的位置等信息。 靜態(tài)索引：索引結(jié)構(gòu)在文件創(chuàng)建時生成，一旦生成就固定下來，只有當文件再組織時才允許改變。 動態(tài)索引：在文件創(chuàng)建時生成索引結(jié)構(gòu)，在文件執(zhí)行插入/刪除操作時，索引結(jié)構(gòu)本身也隨之發(fā)生改變。,9.1 索引的基本概念,索引的基本概念,線性索引：若將索引項組織為線性結(jié)構(gòu)，則稱其為線性索引或索引表； 樹形索引：若將索引項組織為樹結(jié)構(gòu)，則稱其為樹形索引。 多級索引：對索引再建立一個索引，就構(gòu)成了多級索引。,9.1 索引的基本概念,索引的基本概念,對一些大型文件，其索引本身可能也很大，在這種情況下，可以建立多級索引。,稠密索引：在線性索引中，若文件中的每個記錄對應一個索引項，則這種索引稱為稠密索引。 在稠密索引中，無論文件是否按關鍵碼有序，索引項總是按關鍵碼順序排列。 只要內(nèi)存空間允許，通常把稠密索引存儲在內(nèi)存中，從而大大提高記錄的查找速度。,稠密索引,9.2 線性索引技術,稠密索引主要適用于靜態(tài)索引。,稠密索引示例,9.2 線性索引技術,有序,無序或有序,優(yōu)點：實現(xiàn)對數(shù)據(jù)庫記錄有效的查找（采用折半查找技術）和隨機訪問（按記錄號訪問）。 缺點：如果文件中包含的記錄太多，索引表本身可能會因為太大而無法在內(nèi)存中存儲；文件中插入或刪除記錄，必須更新稠密索引，而稠密索引的插入和刪除操作代價很高。,9.2 線性索引技術,稠密索引,文件,外存,稠密索引,內(nèi)存,分塊索引,9.2 線性索引技術,稠密索引空間代價很大,分塊索引,分塊索引需要將文件劃分為若干塊，且要求分塊有序。,多級索引,9.2 線性索引技術,分塊索引,有序,9.2 線性索引技術,分塊索引,在分塊索引表中進行的查找稱為分塊查找（也稱為索引順序查找），分兩步進行： 在索引表中確定待查關鍵碼所在的塊； 在相應塊中查找待查關鍵碼。,塊內(nèi)查找順序查找,設有n個記錄的文件分為m個塊，每個塊均為t個記錄，則n=mt。設Lb為查找索引表確定關鍵碼所在塊的平均查找長度，Lw為在塊內(nèi)查找關鍵碼的平均查找長度，則分塊查找的平均查找長度為： ASL=Lb + Lw 若采用順序查找對索引表進行查找，則分塊查找的平均查找長度為：,9.2 線性索引技術,分塊索引,ASL=Lb + Lw=,9.2 線性索引技術,多重表,稠密索引、分塊索引,對主關鍵碼建立索引,為文件建立索引的目的是什么?,對主關鍵碼進行查找,對次關鍵碼進行查找,對次關鍵碼建立索引,多重表、倒排表,9.2 線性索引技術,多重表,多重表除了為文件建立一個主索引外，還為每個需要查找的次關鍵碼建立一個索引。 在文件中，為建立索引的次關鍵碼分別增設一個指針域，用于將次關鍵碼相同的記錄鏈結(jié)在一起（稠密索引），或?qū)⒃谕粔K中的記錄鏈結(jié)在一起（分塊索引）。,9.2 線性索引技術,多重表,9.2 線性索引技術,倒排表,9.3 樹形索引,2 3 樹,2-3樹：是具有下列特性的樹： 一個結(jié)點包含1個或者2個關鍵碼。 每個內(nèi)部結(jié)點有2個子女（包含一個關鍵碼）或者3個子女（包含兩個關鍵碼）。 所有葉子結(jié)點都在樹的同一層。,9.3 樹形索引,2 3 樹示例,形狀上有什么特性?,9.3 樹形索引,2 3 樹示例,包含1個或者2個關鍵碼； 有2個子女或者3個子女； 葉子結(jié)點在同一層。,9.3 樹形索引,2 3 樹示例,結(jié)點的值有什么特性?,9.3 樹形索引,2 3 樹示例,左子樹中所有結(jié)點的值均小于第一個關鍵碼的值； 中間子樹中所有結(jié)點的值均大于第一個關鍵碼的值，且小于第二個關鍵碼的值； 右子樹中所有結(jié)點的值均大于第二個關鍵碼的值。,9.3 樹形索引,2 3 樹查找操作,21,182133,2123,9.3 樹形索引,2 3 樹插入操作,新記錄將插入到相應的葉子結(jié)點中。,18 33,9.3 樹形索引,2 3 樹插入操作,新記錄將插入到相應的葉子結(jié)點中。,9.3 樹形索引,2 3 樹插入操作,新記錄將插入到相應的葉子結(jié)點中。,9.3 樹形索引,2 3 樹插入操作,新記錄將插入到相應的葉子結(jié)點中。,18 33,12,23 30,48,10,15,20 21,24,31,45 47,50 52 55,插入,9.3 樹形索引,2 3 樹插入操作,新記錄將插入到相應的葉子結(jié)點中。,18 33,12,23 30,48,10,15,20 21,24,31,45 47,分裂,50,55,52,9.3 樹形索引,2 3 樹插入操作,新記錄將插入到相應的葉子結(jié)點中。,18 33,12,23 30,10,15,20 21,24,31,45 47,提升,50,55,48 52,9.3 樹形索引,2 3 樹刪除操作,情況1：從包含2個記錄的葉子結(jié)點刪除1個記錄。,解決方法：直接刪除這個記錄。,18 33,12,23 30,48,10,15,24,31,45 47,50 52,9.3 樹形索引,2 3 樹刪除操作,情況1：從包含2個記錄的葉子結(jié)點刪除1個記錄。,解決方法：直接刪除這個記錄。,21,9.3 樹形索引,2 3 樹刪除操作,情況2：從包含1個記錄的葉子結(jié)點中刪除這個記錄。,解決方法：向兄弟結(jié)點借一個記錄，同時修改雙親結(jié)點的記錄。,18 33,12,21 30,48,10,15,20,23,31,45 47,50 52,9.3 樹形索引,2 3 樹刪除操作,情況2：從包含1個記錄的葉子結(jié)點中刪除這個記錄。,解決方法：向兄弟結(jié)點借一個記錄，同時修改雙親結(jié)點的記錄。,18 33,12,21 30,48,10,15,20,23,31,45 47,50 52,9.3 樹形索引,2 3 樹刪除操作,情況2：從包含1個記錄的葉子結(jié)點中刪除這個記錄。,解決方法：兄弟結(jié)點不夠借，需要合并相鄰結(jié)點，并影響雙親結(jié)點。,18 33,12,20 21,48,10,15,30,31,45 47,50 52,9.3 樹形索引,2 3 樹刪除操作,情況2：從包含1個記錄的葉子結(jié)點中刪除這個記錄。,解決方法：兄弟結(jié)點不夠借，需要合并相鄰結(jié)點，并影響雙親結(jié)點。,18 33,12,20 21,48,10,15,30,31,45 47,50 52,9.3 樹形索引,2 3 樹刪除操作,情況2：從包含1個記錄的葉子結(jié)點中刪除這個記錄。,解決方法：兄弟結(jié)點不夠借，需要合并相鄰結(jié)點，并影響雙親結(jié)點。,20 21,48,33,31,45 47,50 52,9.3 樹形索引,2 3 樹刪除操作,情況2：從包含1個記錄的葉子結(jié)點中刪除這個記錄。,10 12,18 30,解決方法：兄弟結(jié)點不夠借，需要合并相鄰結(jié)點，并影響雙親結(jié)點。,48,33,30,45 47,50 52,9.3 樹形索引,2 3 樹刪除操作,情況2：從包含1個記錄的葉子結(jié)點中刪除這個記錄。,解決方法：兄弟結(jié)點不夠借，需要合并相鄰結(jié)點，并影響雙親結(jié)點，這可能減少樹的高度。,25,20,9.3 樹形索引,2 3 樹刪除操作,情況2：從包含1個記錄的葉子結(jié)點中刪除這個記錄。,解決方法：兄弟結(jié)點不夠借，需要合并相鄰結(jié)點，并影響雙親結(jié)點，這可能減少樹的高度。,2-3樹的優(yōu)點：能夠以相對較低的代價保持樹高平衡。,9.3 樹形索引,2 3 樹刪除操作,情況3：從內(nèi)部結(jié)點刪除一個記錄。,解決方法：將被刪除記錄用右邊子樹中的最小關鍵碼Y代替（ Y一定在某個葉子結(jié)點中），然后再刪除Y。,9.3 樹形索引,2 3 樹刪除操作,情況3：從內(nèi)部結(jié)點刪除一個記錄。,解決方法：將被刪除記錄用右邊子樹中的最小關鍵碼Y代替（ Y一定在某個葉子結(jié)點中），然后再刪除Y。,20 33,12,23 30,48,10,15,21,24,31,45 47,50 52,B樹,9.3 樹形索引,m階B樹：是滿足下列特性的樹： 所有葉子結(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）為關鍵碼的個數(shù)； Ki（1in）為關鍵碼，且KiKi+1（1in-1）； Ai（0in）為指向子樹根結(jié)點的指針，且指針Ai所指子樹中所有結(jié)點的關鍵碼均小于Ki+1大于Ki。,B樹,9.3 樹形索引,1 18,1 11,1 27,1 39,3 47 53 64,1 99,F,F,F,F,F,F,F,F,F,F,F,F,2 43 78,1 35,9.3 樹形索引,B樹示例,B+樹,m階B樹：是滿足下列特性的樹： 含有m個關鍵碼，每一個關