第9章索引技術(shù)

第9章索引技術(shù)本章的基本內(nèi)容是：索引的基本概念線性索引技術(shù)樹形索引9.1索引的基本概念數(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)建時生成索引結(jié)構(gòu)，在文件執(zhí)行插入/刪除操作時，索引結(jié)構(gòu)本身也隨之發(fā)生改變。9.1索引的基本概念索引的基本概念線性索引：若將索引項組織為線性結(jié)構(gòu)，則稱其為線性索引或索引表；樹形索引：若將索引項組織為樹結(jié)構(gòu)，則稱其為樹形索引。多級索引：對索引再建立一個索引，就構(gòu)成了多級索引。9.1索引的基本概念索引的基本概念對一些大型文件，其索引本身可能也很大，在這種情況下，可以建立多級索引。稠密索引：在線性索引中，若文件中的每個記錄對應(yīng)一個索引項，則這種索引稱為稠密索引。在稠密索引中，無論文件是否按關(guān)鍵碼有序，索引項總是按關(guān)鍵碼順序排列。只要內(nèi)存空間允許，通常把稠密索引存儲在內(nèi)存中，從而大大提高記錄的查找速度。稠密索引9.2線性索引技術(shù)稠密索引主要適用于靜態(tài)索引。稠密索引示例9.2線性索引技術(shù)

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

8203540525661關(guān)鍵碼指針?biāo)饕碛行驘o序或有序優(yōu)點：實現(xiàn)對數(shù)據(jù)庫記錄有效的查找（采用折半查找技術(shù)）和隨機訪問（按記錄號訪問）。缺點：如果文件中包含的記錄太多，索引表本身可能會因為太大而無法在內(nèi)存中存儲；文件中插入或刪除記錄，必須更新稠密索引，而稠密索引的插入和刪除操作代價很高。

9.2線性索引技術(shù)稠密索引文件外存稠密索引內(nèi)存分塊索引9.2線性索引技術(shù)稠密索引空間代價很大減少索引項的個數(shù)分塊索引分塊索引需要將文件劃分為若干塊，且要求分塊有序。塊內(nèi)無序：每一塊內(nèi)不要求有序塊間有序：塊與塊之間有序分塊有序多級索引每塊建立一個索引項9.2線性索引技術(shù)分塊索引35…20…8…52…40…61…65…88…76…第1塊文件關(guān)鍵碼其他數(shù)據(jù)項第2塊第3塊353613883索引表最大值塊長塊首地址有序9.2線性索引技術(shù)分塊索引在分塊索引表中進行的查找稱為分塊查找（也稱為索引順序查找），分兩步進行：⑴在索引表中確定待查關(guān)鍵碼所在的塊；⑵在相應(yīng)塊中查找待查關(guān)鍵碼。索引表查找順序查找折半查找塊內(nèi)查找——順序查找設(shè)有n個記錄的文件分為m個塊，每個塊均為t個記錄，則n=m×t。設(shè)Lb為查找索引表確定關(guān)鍵碼所在塊的平均查找長度，Lw為在塊內(nèi)查找關(guān)鍵碼的平均查找長度，則分塊查找的平均查找長度為：

ASL=Lb+Lw若采用順序查找對索引表進行查找，則分塊查找的平均查找長度為：

9.2線性索引技術(shù)分塊索引

ASL=Lb+Lw=當(dāng)t取時，ASL取最小值+1。nn9.2線性索引技術(shù)多重表稠密索引、分塊索引對主關(guān)鍵碼建立索引為文件建立索引的目的是什么?對主關(guān)鍵碼進行查找對次關(guān)鍵碼進行查找對次關(guān)鍵碼建立索引多重表、倒排表9.2線性索引技術(shù)多重表多重表除了為文件建立一個主索引外，還為每個需要查找的次關(guān)鍵碼建立一個索引。在文件中，為建立索引的次關(guān)鍵碼分別增設(shè)一個指針域，用于將次關(guān)鍵碼相同的記錄鏈結(jié)在一起（稠密索引），或?qū)⒃谕粔K中的記錄鏈結(jié)在一起（分塊索引）。關(guān)鍵碼指針000100020003000400050006主索引9.2線性索引技術(shù)多重表次關(guān)鍵碼頭指針長度男013女033“性別”次索引次關(guān)鍵碼頭指針長度24~2602327~30013“年齡”次索引∧24∧男王東0006∧30∧女李爽0005062505女齊梅0004052704女劉楠0003042506男張亮0002033002男王剛0001年

齡性

別姓

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

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

24～2602,04,06

27～30

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

次關(guān)鍵碼記錄號表男01,02,06女03,04,0524男王東000630女李爽000525女齊梅000427女劉楠000325男張亮000230男王剛0001年齡性別姓名職工號文件9.3樹形索引2–3樹2-3樹：是具有下列特性的樹：⑴一個結(jié)點包含1個或者2個關(guān)鍵碼。⑵每個內(nèi)部結(jié)點有2個子女（包含一個關(guān)鍵碼）或者3個子女（包含兩個關(guān)鍵碼）。⑶

所有葉子結(jié)點都在樹的同一層。9.3樹形索引2–3樹示例18331223304810152021243145475052形狀上有什么特性?9.3樹形索引2–3樹示例包含1個或者2個關(guān)鍵碼；有2個子女或者3個子女；葉子結(jié)點在同一層。183312233048101520212431454750529.3樹形索引2–3樹示例結(jié)點的值有什么特性?183312233048101520212431454750529.3樹形索引2–3樹示例左子樹中所有結(jié)點的值均小于第一個關(guān)鍵碼的值；中間子樹中所有結(jié)點的值均大于第一個關(guān)鍵碼的值，且小于第二個關(guān)鍵碼的值；右子樹中所有結(jié)點的值均大于第二個關(guān)鍵碼的值。18331223304810152021243145475052183312233048101520212431454750529.3樹形索引2–3樹——查找操作2118<21<3321<23比較次數(shù)不超過樹的深度。由于2-3樹是樹高平衡的，而且每一個內(nèi)部結(jié)點至少有2個子女，所以樹的最大深度是。??1log2+n9.3樹形索引2–3樹——插入操作新記錄將插入到相應(yīng)的葉子結(jié)點中。18331223304810152021243145475052葉子結(jié)點只包含1個記錄插入新記錄

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

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

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

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

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

提升50554852183312233048101520212431454750529.3樹形索引2–3樹——刪除操作情況1：從包含2個記錄的葉子結(jié)點刪除1個記錄。解決方法：直接刪除這個記錄。18331223304810152431454750529.3樹形索引2–3樹——刪除操作情況1：從包含2個記錄的葉子結(jié)點刪除1個記錄。解決方法：直接刪除這個記錄。21183312233048101520212431454750529.3樹形索引2–3樹——刪除操作情況2：從包含1個記錄的葉子結(jié)點中刪除這個記錄。解決方法：向兄弟結(jié)點借一個記錄，同時修改雙親結(jié)點的記錄。1833122130481015202331454750529.3樹形索引2–3樹——刪除操作情況2：從包含1個記錄的葉子結(jié)點中刪除這個記錄。解決方法：向兄弟結(jié)點借一個記錄，同時修改雙親結(jié)點的記錄。1833122130481015202331454750529.3樹形索引2–3樹——刪除操作情況2：從包含1個記錄的葉子結(jié)點中刪除這個記錄。解決方法：兄弟結(jié)點不夠借，需要合并相鄰結(jié)點，并影響雙親結(jié)點。18331220214810153031454750529.3樹形索引2–3樹——刪除操作情況2：從包含1個記錄的葉子結(jié)點中刪除這個記錄。解決方法：兄弟結(jié)點不夠借，需要合并相鄰結(jié)點，并影響雙親結(jié)點。18331220214810153031454750529.3樹形索引2–3樹——刪除操作情況2：從包含1個記錄的葉子結(jié)點中刪除這個記錄。解決方法：兄弟結(jié)點不夠借，需要合并相鄰結(jié)點，并影響雙親結(jié)點。2021483331454750529.3樹形索引2–3樹——刪除操作情況2：從包含1個記錄的葉子結(jié)點中刪除這個記錄。10121830解決方法：兄弟結(jié)點不夠借，需要合并相鄰結(jié)點，并影響雙親結(jié)點。483330454750529.3樹形索引2–3樹——刪除操作情況2：從包含1個記錄的葉子結(jié)點中刪除這個記錄。解決方法：兄弟結(jié)點不夠借，需要合并相鄰結(jié)點，并影響雙親結(jié)點，這可能減少樹的高度。25209.3樹形索引2–3樹——刪除操作情況2：從包含1個記錄的葉子結(jié)點中刪除這個記錄。解決方法：兄弟結(jié)點不夠借，需要合并相鄰結(jié)點，并影響雙親結(jié)點，這可能減少樹的高度。45475052334820252-3樹的優(yōu)點：能夠以相對較低的代價保持樹高平衡。9.3樹形索引2–3樹——刪除操作情況3：從內(nèi)部結(jié)點刪除一個記錄。解決方法：將被刪除記錄用右邊子樹中的最小關(guān)鍵碼Y代替（Y一定在某個葉子結(jié)點中），然后再刪除Y。183312233048101520212431454750529.3樹形索引2–3樹——刪除操作情況3：從內(nèi)部結(jié)點刪除一個記錄。解決方法：將被刪除記錄用右邊子樹中的最小關(guān)鍵碼Y代替（Y一定在某個葉子結(jié)點中），然后再刪除Y。203312233048101521243145475052B樹9.3樹形索引m階B樹：是滿足下列特性的樹：⑴所有葉子結(jié)點都在同一層上，并且不帶信息，葉子的雙親稱為終端結(jié)點。⑵樹中每個結(jié)點至多有m棵子樹；⑶若根結(jié)點不是終端結(jié)點，則至少有兩棵子樹；⑷除根結(jié)點外，其他非終端結(jié)點至少有m/2

棵子樹；B－樹是2－3樹的推廣，2-3樹是一個3階B－樹

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

1≤n