數(shù)據(jù)結(jié)構(gòu)與算法北京大學(xué)8張銘索引技術(shù)

1、數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 第第11 11章章 索引技術(shù)索引技術(shù) 本章由張銘主寫本章由張銘主寫http:/ 索引指針指向的這一組記錄在磁盤中的起始位置92733755數(shù)據(jù)庫記錄線形索引文件Go 10000/128 = 78.1 那么一級線性索引占用79個(gè)磁盤塊 1 2003 5744 10723 1 2002 2002 2003 5583 5744 9297 10723 13293 磁磁盤盤塊塊 一級索引二級索引例如：檢索關(guān)鍵碼為2555的記錄 1. 二級線性索引文件讀入內(nèi)存2. 二分法找關(guān)鍵碼的值小于等于2555的最大關(guān)鍵碼所在一級索引磁盤塊地址關(guān)鍵碼為2003的記錄3. 根據(jù)記錄2003

2、中的地址指針找到其對應(yīng)的一級線性索引文件的磁盤塊，并把該塊讀入內(nèi)存4. 按照二分法對該塊進(jìn)行檢索，找到所需要的記錄在磁盤上的位置5. 最后把所需記錄讀入，完成檢索操作二叉樹轉(zhuǎn)換成多分樹632次訪問索引塊1次訪問外存數(shù)據(jù)塊教師數(shù)據(jù)庫主表教師數(shù)據(jù)庫主表 （屬性值，具有該屬性值的各記錄指針） 記錄指針可以是關(guān)鍵碼，或該記錄的主文件地址教師數(shù)據(jù)庫倒排表教師數(shù)據(jù)庫倒排表Department listEMP#數(shù)學(xué)數(shù)學(xué)物理物理計(jì)算機(jī)計(jì)算機(jī)外語外語0155, 0132, 01190208, 02110330, 0310, 03410421, 0455Profession listEMP#教授教授講師講師助教助

3、教0155, 03300211, 0119, 0455, 03100421, 0208, 0132, 0341Specialty listEMP#代數(shù)代數(shù)幾何幾何力學(xué)力學(xué)原子物理原子物理軟件軟件英語英語法語法語0155, 01190132020802110330, 03410421, 03100455 指向該關(guān)鍵詞出現(xiàn)文檔集合 在文檔中的位置 正文文件：由6個(gè)文檔組成，每個(gè)文檔都是長字符串Pease porridge hot, please porridge cold,文檔編號文本內(nèi)容1Pease porridge in the pot,Nine days old.Some like it h

4、ot, some like it cold,Some like it in the pot,Nine days old.23456倒排索引12345678910111213編號詞語（文檔編號，位置）colddayshotinlikenine oldpeaseporridgeitpotsomethe(1,1)(1,2)(1,3)(1,4)(1,5)(1,6)類似處理1中的其他詞語同理，處理2中的詞語（2,1）依次處理所有文檔 定長的塊、段落、章節(jié)，甚至一組文檔 記錄在每個(gè)倒排表在索引文件中開始的位置以及每個(gè)表的大小（也可以記錄每個(gè)關(guān)鍵詞的出現(xiàn)次數(shù)） 只能用索引文件中的關(guān)鍵詞 例如較高的檢索效率

5、18 33 12 23 30 48 24 20 21 31 10 15 45 47 50 52 3階B樹2-3樹 18 33 12 23 30 48 24 20 21 31 10 15 45 47 50 52 (18,a1) (33,a2)(10,a7)(15,a8) (20,a9) (21,a10) (24,a11)(31,a12) (45,a13)(47,a14)(50,a5) (52,a16)(12,a3)(23,a4) (30,a5)(48,a6) 關(guān)鍵碼關(guān)鍵碼文件頁內(nèi)地址文件頁內(nèi)地址主文件/2m P0， K1， P1， K2， P2， ， Pj-1， Kj， Pj 18 33 12

6、23 30 48 10 15 20 21 24 31 45 47 50 52 找到則檢索成功 分裂過程可能傳達(dá)到根結(jié)點(diǎn)(則樹升高一層)插入143階B樹18 33 12 23 30 48 10 20 21 24 31 45 47 50 52151418 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52插入5550 5255 結(jié)點(diǎn)分裂18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 55525055插入1918 33 12 23 30 48 10 15 20 21 24 31 45 47 50 521919 20

7、 21 葉結(jié)點(diǎn)分裂18 33 12 23 30 48 10 15 24 31 45 47 50 5219 20 21 1921 23 30 20 第二層結(jié)點(diǎn)分裂192118 33 12 48 10 15 24 31 45 47 50 5220 23 30 30 2018 33 23 根結(jié)點(diǎn)分裂 30192112 48 10 15 24 31 45 47 50 5220 23 1833訪外次數(shù)訪外次數(shù)o上述插入過程有10次對B樹的訪外操作n 其中讀盤3次（a、c、g）n 寫盤7次（g、g、c、c、a、a、t）o這里不考慮對主數(shù)據(jù)文件的訪外操作，也不考慮申請新磁盤塊的開銷 直接刪除 如果兄弟結(jié)點(diǎn)關(guān)

8、鍵碼個(gè)數(shù)不等于從兄弟結(jié)點(diǎn)移若干個(gè)關(guān)鍵碼到該結(jié)點(diǎn)中來(父結(jié)點(diǎn)中的一個(gè)關(guān)鍵碼要做相應(yīng)變化) 如果兄弟結(jié)點(diǎn)關(guān)鍵碼個(gè)數(shù)等于合并/21m/21m/21m120 150 25 50 103 acedfg hbi11 15 35 43 81 95 100 108 110 115 118134 146 156 177 刪除刪除120，先與后繼交換，刪后下溢出，向左鄰借關(guān)鍵碼，先與后繼交換，刪后下溢出，向左鄰借關(guān)鍵碼 150 25 50 103 acedfg hbi11 15 35 43 81 95 100 108 110 115 146 156 177 120 134 與后繼交換與后繼交換刪除刪除120, h

9、120, h溢出溢出向左鄰借關(guān)鍵碼向左鄰借關(guān)鍵碼 118146 146 134 118 25 50 103 cedfg hbi11 15 35 43 81 95 100 108 110 115 134 146 177 156150繼續(xù)刪除繼續(xù)刪除150與后繼交換與后繼交換刪除刪除150, i150, i溢出溢出向左鄰借關(guān)鍵碼向左鄰借關(guān)鍵碼借不到，借不到，h, i合并合并177 134 146 a118 25 50 103 cedfg hb11 15 35 43 81 95 100 108 110 115 134 146 156 177h, i合并成為合并成為hc 溢出，向左鄰借關(guān)鍵碼溢出，向左

10、鄰借關(guān)鍵碼 借不到，借不到，b,c結(jié)點(diǎn)合并結(jié)點(diǎn)合并 118 25 50 a25 50 103 118 a/2m其實(shí)，根可以為空，或其實(shí)，根可以為空，或者獨(dú)根者獨(dú)根 70 95 10 20 35 40 44 51 65 70 85 91 93 95 20 40 51 70 91 95 40 70 95 需要的話，每一層結(jié)點(diǎn)也可以順序鏈接abefghkldijc50 60 7040 70 9080 9075 80 85 9065 7055 6045 48 5035 4025 30155 10 201020 30 4040abefghkldijc50 60 7080 9075 80 85 9065

11、7055 6045 48 5035 4025 305 1015 2010 2030 402070 9040 90ta準(zhǔn)備在準(zhǔn)備在3 3階階B+B+樹中刪除樹中刪除75 75 o沿a、d、k查找，找到葉結(jié)點(diǎn)o在k中刪去75，發(fā)生下溢出，剩余關(guān)鍵碼80與右鄰l結(jié)點(diǎn)合并為新k（80，85，90）o父結(jié)點(diǎn)d中原分界碼80刪除n d結(jié)點(diǎn)下溢出n 借左鄰c的關(guān)鍵碼，c和d的關(guān)鍵碼平分n 父結(jié)點(diǎn)a中的分界碼70修改為60 控制域控制域 控制區(qū)間控制區(qū)間 索引索引 順序集順序集 數(shù)據(jù)集數(shù)據(jù)集 VSAM文件結(jié)構(gòu)文件結(jié)構(gòu) 239 240 279 008 040 052 110 135 142 212 045 11

12、2 236 m/ 2,2/211kmN)21(log12/Nkm221mk/Nmp 1211(/)()pNm 1121/spNNmNm1121121(/)/ 239 240 279 008 040 052 110 135 142 212 045 112 236 其中的記錄地址也稱為“隱含指針” 因此可以把此層形成順序鏈表log. 0 75mNlog. 0 5mNstate=AKstate=ALstate=NY0001010 11 00 10 00 10 03/13/13/13/13/13/1323638414346NYALNYAKNYAKAABAAB6951193101010110110 da

13、te store state class sales StateNYClass=A記錄bar baz foo304050 1 1 1 0 1 1 0 0 11表示在那個(gè)記錄中出現(xiàn)了相應(yīng)的字段值91546212721“紅色紅色”“黑色黑色”擴(kuò)充擴(kuò)充91546212721rank=2rank=1rank=2915462127最短是最短是k最小是最小是k+1，最長是，最長是2k，最高是，最高是2k+16926386384XAAX插入插入4X以祖結(jié)點(diǎn)為軸以祖結(jié)點(diǎn)為軸旋轉(zhuǎn)父結(jié)點(diǎn)旋轉(zhuǎn)父結(jié)點(diǎn)AXBBACC246624642264264X父祖換色父祖換色AXBBACC對對B繼續(xù)繼續(xù)紅紅檢查紅紅檢查112141157854X112141157854X578112141157854X5772111854514156384vXw634X刪除刪除8BDXCDXBCBXECDCBDXEBXEDCBCEDX有 可 能 繼 續(xù)有 可 能 繼 續(xù)雙