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

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