第9章索引技術(shù)

第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ù)

8…20…52…35…40…61…56…關(guān)鍵碼其它數(shù)據(jù)項(xiàng)文件r1r2r3r4r5r6r7

8203540525661關(guān)鍵碼指針?biāo)饕碛行驘o(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à)很大減少索引項(xiàng)的個(gè)數(shù)分塊索引分塊索引需要將文件劃分為若干塊，且要求分塊有序。塊內(nèi)無(wú)序：每一塊內(nèi)不要求有序塊間有序：塊與塊之間有序分塊有序多級(jí)索引每塊建立一個(gè)索引項(xiàng)9.2線(xiàn)性索引技術(shù)分塊索引35…20…8…52…40…61…65…88…76…第1塊文件關(guān)鍵碼其他數(shù)據(jù)項(xiàng)第2塊第3塊353613883索引表最大值塊長(zhǎng)塊首地址有序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=m×t。設(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=當(dāng)t取時(shí)，ASL取最小值+1。nn9.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é)在一起（分塊索引）。關(guān)鍵碼指針000100020003000400050006主索引9.2線(xiàn)性索引技術(shù)多重表次關(guān)鍵碼頭指針長(zhǎng)度男013女033“性別”次索引次關(guān)鍵碼頭指針長(zhǎng)度24~2602327~30013“年齡”次索引∧24∧男王東0006∧30∧女李爽0005062505女齊梅0004052704女劉楠0003042506男張亮0002033002男王剛0001年

齡性

別姓

名職工號(hào)文件關(guān)鍵碼指針000100020003000400050006主索引9.2線(xiàn)性索引技術(shù)倒排表“年齡”倒排表

次關(guān)鍵碼記錄號(hào)表

24～2602,04,06

27～30

01,03,05“性別”倒排表

次關(guān)鍵碼記錄號(hào)表男01,02,06女03,04,0524男王東000630女李爽000525女齊梅000427女劉楠000325男張亮000230男王剛0001年齡性別姓名職工號(hào)文件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ù)示例18331223304810152021243145475052形狀上有什么特性?9.3樹(shù)形索引2–3樹(shù)示例包含1個(gè)或者2個(gè)關(guān)鍵碼；有2個(gè)子女或者3個(gè)子女；葉子結(jié)點(diǎn)在同一層。183312233048101520212431454750529.3樹(shù)形索引2–3樹(shù)示例結(jié)點(diǎn)的值有什么特性?183312233048101520212431454750529.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)鍵碼的值。18331223304810152021243145475052183312233048101520212431454750529.3樹(shù)形索引2–3樹(shù)——查找操作2118<21<3321<23比較次數(shù)不超過(guò)樹(shù)的深度。由于2-3樹(shù)是樹(shù)高平衡的，而且每一個(gè)內(nèi)部結(jié)點(diǎn)至少有2個(gè)子女，所以樹(shù)的最大深度是。??1log2+n9.3樹(shù)形索引2–3樹(shù)——插入操作新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。18331223304810152021243145475052葉子結(jié)點(diǎn)只包含1個(gè)記錄插入新記錄

149.3樹(shù)形索引2–3樹(shù)——插入操作新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。葉子結(jié)點(diǎn)只包含1個(gè)記錄插入新記錄

18331223304815202124314547505210149.3樹(shù)形索引2–3樹(shù)——插入操作新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。18331223304810152021243145475052葉子結(jié)點(diǎn)只包含2個(gè)記錄插入新記錄，分裂－提升

559.3樹(shù)形索引2–3樹(shù)——插入操作新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。1833122330481015202124314547505255葉子結(jié)點(diǎn)只包含2個(gè)記錄插入新記錄，分裂－提升

插入9.3樹(shù)形索引2–3樹(shù)——插入操作新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。1833122330481015202124314547葉子結(jié)點(diǎn)只包含2個(gè)記錄插入新記錄，分裂－提升

分裂5055529.3樹(shù)形索引2–3樹(shù)——插入操作新記錄將插入到相應(yīng)的葉子結(jié)點(diǎn)中。18331223301015202124314547葉子結(jié)點(diǎn)只包含2個(gè)記錄插入新記錄，分裂－提升

提升50554852183312233048101520212431454750529.3樹(shù)形索引2–3樹(shù)——?jiǎng)h除操作情況1：從包含2個(gè)記錄的葉子結(jié)點(diǎn)刪除1個(gè)記錄。解決方法：直接刪除這個(gè)記錄。18331223304810152431454750529.3樹(shù)形索引2–3樹(shù)——?jiǎng)h除操作情況1：從包含2個(gè)記錄的葉子結(jié)點(diǎn)刪除1個(gè)記錄。解決方法：直接刪除這個(gè)記錄。21183312233048101520212431454750529.3樹(shù)形索引2–3樹(shù)——?jiǎng)h除操作情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：向兄弟結(jié)點(diǎn)借一個(gè)記錄，同時(shí)修改雙親結(jié)點(diǎn)的記錄。1833122130481015202331454750529.3樹(shù)形索引2–3樹(shù)——?jiǎng)h除操作情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：向兄弟結(jié)點(diǎn)借一個(gè)記錄，同時(shí)修改雙親結(jié)點(diǎn)的記錄。1833122130481015202331454750529.3樹(shù)形索引2–3樹(shù)——?jiǎng)h除操作情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)。18331220214810153031454750529.3樹(shù)形索引2–3樹(shù)——?jiǎng)h除操作情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)。18331220214810153031454750529.3樹(shù)形索引2–3樹(shù)——?jiǎng)h除操作情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)。2021483331454750529.3樹(shù)形索引2–3樹(shù)——?jiǎng)h除操作情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。10121830解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)。483330454750529.3樹(shù)形索引2–3樹(shù)——?jiǎng)h除操作情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)，這可能減少樹(shù)的高度。25209.3樹(shù)形索引2–3樹(shù)——?jiǎng)h除操作情況2：從包含1個(gè)記錄的葉子結(jié)點(diǎn)中刪除這個(gè)記錄。解決方法：兄弟結(jié)點(diǎn)不夠借，需要合并相鄰結(jié)點(diǎn)，并影響雙親結(jié)點(diǎn)，這可能減少樹(shù)的高度。45475052334820252-3樹(shù)的優(yōu)點(diǎn)：能夠以相對(duì)較低的代價(jià)保持樹(shù)高平衡。9.3樹(shù)形索引2–3樹(shù)——?jiǎng)h除操作情況3：從內(nèi)部結(jié)點(diǎn)刪除一個(gè)記錄。解決方法：將被刪除記錄用右邊子樹(shù)中的最小關(guān)鍵碼Y代替（Y一定在某個(gè)葉子結(jié)點(diǎn)中），然后再刪除Y。183312233048101520212431454750529.3樹(shù)形索引2–3樹(shù)——?jiǎng)h除操作情況3：從內(nèi)部結(jié)點(diǎn)刪除一個(gè)記錄。解決方法：將被刪除記錄用右邊子樹(shù)中的最小關(guān)鍵碼Y代替（Y一定在某個(gè)葉子結(jié)點(diǎn)中），然后再刪除Y。203312233048101521243145475052B樹(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ù)是2－3樹(shù)的推廣，2-3樹(shù)是一個(gè)3階B－樹(shù)

。所有非終端結(jié)點(diǎn)都包含以下數(shù)據(jù)：（n，A0，K1，A1，K2，…，Kn，An）其中，n（m/2

1≤n