文件的索引結(jié)構(gòu)2

1、文件索引結(jié)構(gòu)與倒排表2007/05/142本講主要內(nèi)容： n平衡二叉樹n文件的索引結(jié)構(gòu)n倒排表與倒排索引n類型無關(guān)的軟件平臺(tái)架構(gòu)3字典的二分查找n二分查找(binary search)q要求：n查找表為有序表，即表中 結(jié)點(diǎn)按關(guān)鍵字有序排列，并且采用順序存儲(chǔ)結(jié)構(gòu)。q基本思想：1. 確定搜索區(qū)間的中點(diǎn)位置：2. 然后將待查的key值與rangemid.key比較：若相等，則查找成功并返回此位置，否則確定新的查找區(qū)間，繼續(xù)二分查找.4動(dòng)態(tài)查找表結(jié)構(gòu) 二叉排序樹（又稱二叉搜索樹）n以關(guān)鍵碼值關(guān)鍵碼值為結(jié)點(diǎn)的二叉樹q如果任一結(jié)點(diǎn)的左子樹非空，則左子樹中的所有結(jié)點(diǎn)的關(guān)鍵碼都小于根結(jié)點(diǎn)的關(guān)鍵碼；q如果任一結(jié)

2、點(diǎn)的右子樹非空，則右子樹中的所有結(jié)點(diǎn)的關(guān)鍵碼都大于根結(jié)點(diǎn)的關(guān)鍵碼。 10152040 6 2 81530255二叉排序樹的插入與構(gòu)造 n如果二叉排序樹為空，則新結(jié)點(diǎn)作為根結(jié)點(diǎn)。n如果二叉排序樹非空，則將新結(jié)點(diǎn)的關(guān)鍵碼與根結(jié)點(diǎn)的關(guān)鍵碼比較，q若相等表示該結(jié)點(diǎn)已在二叉排序樹中；若小于根結(jié)點(diǎn)的關(guān)鍵碼，則將新結(jié)點(diǎn)插入到根結(jié)點(diǎn)的左子樹中；q否則，插入到右子樹中。n子樹中的插入過程和樹中的插入過程相同，如此進(jìn)行下去，直到找到該結(jié)點(diǎn)，或者直到左或右子樹為空二叉樹，新結(jié)點(diǎn)插入成為葉子結(jié)點(diǎn)為止。6最佳二叉排序樹的構(gòu)造(1) 先將字典元素關(guān)鍵碼排序。(2) 對(duì)每個(gè)關(guān)鍵碼按二分法在排序關(guān)鍵碼序列中執(zhí)行檢索，將檢索中

3、遇到的還未在二叉排序樹中的關(guān)鍵碼插入二叉排序樹中。 按二分查找中所遇到的節(jié)點(diǎn)依次插入二叉排序樹。7舉例（記錄二分查找的過程）n對(duì)于K=27,73,10,5,18,41,99,51,25，構(gòu)造最佳二叉排序樹的過程如下：n首先將它們排序?yàn)椋?，10，18，25，27，41，51，73，99，n然后從空二叉樹出發(fā)，在排序的關(guān)鍵碼序列中用二分法檢索5，檢索中遇到的結(jié)點(diǎn)為27,10,5，將這三個(gè)結(jié)點(diǎn)插入二叉排序樹。n再檢索第二個(gè)結(jié)點(diǎn)10，遇到的結(jié)點(diǎn)為27,10，二叉排序樹中已經(jīng)有這兩個(gè)結(jié)點(diǎn)。n再檢索第三個(gè)結(jié)點(diǎn)18，。n得到的插入次序?yàn)?7，10，5，18，25，51，41，73，99。8靜態(tài)查找表索引結(jié)

4、構(gòu)scoscorerestudestudentIDntIDnamenameassignassignmentmentfinial finial examexam4523周夏司50394616李景文1043472葉佩霖50354829郭舒文60514917杜文杰6052509阮萃茵7029513龍國(guó)才0355221陳俊珊45455313李欣怡7555554劉星50295728郭凌典25485914李敏妍90746127唐慰夷30496211吳宇翔0477110何英華0517830梁迪欣80699索引n索引索引是索引項(xiàng)的集合，一個(gè)索引項(xiàng)索引項(xiàng)是由一個(gè)結(jié)點(diǎn)的關(guān)鍵碼和該結(jié)點(diǎn)的存儲(chǔ)位置組成的關(guān)聯(lián)。n索引的

5、實(shí)質(zhì)還是字典，而且是元素類型相同的等長(zhǎng)結(jié)點(diǎn)的字典。所有關(guān)于字典的討論都適合于索引；所有字典的實(shí)現(xiàn)也可以用來組織索引。 10文件與索引結(jié)構(gòu) 打開一個(gè)文件11從文本文件中讀入數(shù)據(jù)集合12將數(shù)據(jù)集轉(zhuǎn)換為記錄集13通過記錄的某一項(xiàng)屬性值反過來查找到這個(gè)記錄的存放地址，或者記錄對(duì)應(yīng)的關(guān)鍵碼。我們稱這種索引為倒排索引（inverted index）。 14倒排索引的建立15利用函數(shù)指針實(shí)現(xiàn)倒排索引的建立16包含數(shù)據(jù)邏輯層的軟件架構(gòu)數(shù)據(jù)源1數(shù)據(jù)源2數(shù)據(jù)源n數(shù)據(jù)邏輯層數(shù)據(jù)處理層數(shù)據(jù)結(jié)構(gòu)及類型類型化計(jì)算數(shù)據(jù)對(duì)象XML 文檔+Style sheet數(shù)據(jù)呈現(xiàn)數(shù)據(jù)交換17動(dòng)態(tài)查找表 平衡二叉排序樹n以上的“最佳”二叉

6、排序樹，不僅構(gòu)造的時(shí)間代價(jià)很大，而且很難動(dòng)態(tài)的保持。通常用于表示一旦構(gòu)造后就不改動(dòng)的靜態(tài)字典靜態(tài)字典；n對(duì)于動(dòng)態(tài)字典動(dòng)態(tài)字典，為了能夠在進(jìn)行元素的插入和刪除操作時(shí)，較快地對(duì)二叉排序樹進(jìn)行調(diào)整，通常不要求二叉排序樹總是保持“最佳的”檢索效率，而是希望達(dá)到一種比較容易調(diào)整的“較佳”的狀態(tài)。18平衡二叉排序樹平衡二叉排序樹，n又稱AVL樹，樹，要求從整體上看，在動(dòng)態(tài)插入或刪除后，每個(gè)結(jié)點(diǎn)的左右子樹能夠基本保持平衡。不會(huì)出現(xiàn)過分傾斜的現(xiàn)象，從而使得平均檢索長(zhǎng)度保持比較短。n結(jié)點(diǎn)右子樹高度與左子樹高度之差稱為該結(jié)點(diǎn)的平衡因子平衡因子，平衡二叉排序樹中每個(gè)結(jié)點(diǎn)的平衡因子只能是1、0或1。 1920插入的影

7、響n在平衡二叉排序樹中插入新結(jié)點(diǎn)時(shí)，如果新結(jié)點(diǎn)插入后不影響其父結(jié)點(diǎn)為根的子樹高度，則不會(huì)破壞整個(gè)二叉排序樹的平衡；反之，若父結(jié)點(diǎn)為根的子樹高度增加了，則可能引起一連串的反映。n其結(jié)果又有兩種可能，一種是在其祖先的某一層上不再影響子二叉排序樹的高度，則整個(gè)二叉排序樹仍然是平衡的；另一種是在其祖先的某一層上破壞了平衡的要求，使整個(gè)二叉排序樹不再是AVL樹。 21最小不平衡子樹n處理失去平衡的方法為首先找出最小不平衡子最小不平衡子樹樹（指離插入結(jié)點(diǎn)最近，且以平衡因子絕對(duì)值大于1的結(jié)點(diǎn)為根的子樹），n在保證排序樹性質(zhì)的前提下，調(diào)整最小不平衡子樹中各結(jié)點(diǎn)的連接關(guān)系，以達(dá)到新的平衡。 2223AVL樹調(diào)整

8、平衡的原則 LL型調(diào)整n破壞平衡的原因是由于在A的左子女(L)的左子樹(L)中插入新結(jié)點(diǎn)，使A的平衡因子由 -1變?yōu)?-2而失去平衡。n調(diào)整不破壞節(jié)點(diǎn)間的序關(guān)系。n調(diào)整不增加子樹的高度。24LL-調(diào)整規(guī)則n將A的左子女B提升為新二叉樹的根；原來的根A連同其右子樹向右下旋轉(zhuǎn)成為B的右子樹；B的原右子樹作為A的左子樹。n調(diào)整后仍保持二叉排序樹的性質(zhì)，而且整個(gè)（子）二叉樹的高度與插入前相同，因此不會(huì)影響包含它的更大（子）二叉樹的平衡。421370-1-125RR型調(diào)整n破壞平衡的原因是由于在A的右子女(R)的右子樹(R)中插入結(jié)點(diǎn)，使A的平衡因子由1變?yōu)?而失去平衡。n調(diào)整規(guī)則：調(diào)整規(guī)則：與LL型的

9、對(duì)稱。將A的右子女B提升為新二叉樹的根；原來的根A連同其左子樹向左下旋轉(zhuǎn)成為B的左子樹；B的原左子樹作為A的右子樹。 428970-1-126LR型調(diào)整n破壞平衡的原因是由于在A的左子女(L)的右子樹(R)中插入結(jié)點(diǎn)，使A的平衡因子由1變?yōu)?而失去平衡。n若、全為空樹，C就是新插入的結(jié)點(diǎn)，記為L(zhǎng)R(0)。否則，新結(jié)點(diǎn)可能插在C的左子樹中，也可能插在C的右子樹中，分別記為L(zhǎng)R(L)和LR(R)。 2728LR-調(diào)整規(guī)則n設(shè)C為A的左子女的右子女，將A的孫子結(jié)點(diǎn)C提升為新二叉樹的根；原C的父結(jié)點(diǎn)B連同其左子樹向左下旋轉(zhuǎn)成為新根C的左子樹，原C的左子樹成為B的右子樹；原根A連同其右子樹向右下旋轉(zhuǎn)成為

10、新根C的右子樹，原C的右子樹成為A的左子樹。421372.5-10421373.5-10LR(L)LR(R)29RL型調(diào)整n破壞平衡的原因是由于在A的右子女(R)的左子樹(L)中插入結(jié)點(diǎn)，使A的平衡因子由1變?yōu)?而失去平衡。n調(diào)整規(guī)則調(diào)整規(guī)則與LR型的對(duì)稱。設(shè)C為A的右子女的左子女，將A的孫子結(jié)點(diǎn)C提升為新二叉樹的根，原來C的父結(jié)點(diǎn)B連同其右子樹向右下旋轉(zhuǎn)成為新根C的右子樹，C的原右子樹成為B的左子樹；原來的根A連同其左子樹向左下旋轉(zhuǎn)成為新根C的左子樹，原來C的左子樹成為A的右子樹。 3031調(diào)整控制在最小不平衡子樹內(nèi)n上述所有的調(diào)整操作中，A為根的最小不平衡子樹的高度在插入結(jié)點(diǎn)之前和調(diào)整之后

11、相同，對(duì)A為根的子樹之外的其它結(jié)點(diǎn)的平衡性無影響，調(diào)整后二叉排序樹成為平衡二叉排序樹。 32元素的刪除 與二叉排序樹中的結(jié)點(diǎn)刪除類似，首先找到被刪除的結(jié)點(diǎn)，如果它不是葉結(jié)點(diǎn)，也需要根據(jù)二叉排序樹的要求轉(zhuǎn)換成一個(gè)葉結(jié)點(diǎn)的刪除。不同之處在于：為了保持刪除后的二叉樹是平衡的，必須參考插入時(shí)的調(diào)整方案設(shè)計(jì)刪除后調(diào)整的算法；僅僅從最小不平衡子樹的調(diào)整來看，它與插入時(shí)的調(diào)整類似，但困難的是：對(duì)最小不平衡子樹的調(diào)整，可能降低它的高度，所以又可能產(chǎn)生更大的最小不平衡子樹。因此可能需要反復(fù)多次調(diào)整。 33索引文件 多分樹n如果文件很大，索引順序文件的索引可以采用多級(jí)索引結(jié)構(gòu)以提高檢索的效率。n即為主文件建立了索

12、引之后，又針對(duì)本級(jí)索引所占的每一個(gè)頁塊建立一個(gè)索引項(xiàng)，用這些索引項(xiàng)構(gòu)成索引的索引。如果新建的這一級(jí)索引仍然占用多個(gè)頁塊，則再為它建立索引。這樣可以得到一種多級(jí)索引結(jié)構(gòu)多分樹。n如果每個(gè)內(nèi)部結(jié)點(diǎn)（根除外）有個(gè)子女，則稱為分樹。 34多分樹與索引文件n如果文件很大，索引順序文件的索引可以采用多多級(jí)索引結(jié)構(gòu)級(jí)索引結(jié)構(gòu)以提高檢索的效率。n即為主文件建立了索引之后，又針對(duì)本級(jí)索引所占的每一個(gè)頁塊建立一個(gè)索引項(xiàng)，用這些索引項(xiàng)構(gòu)成索引的索引。如果新建的這一級(jí)索引仍然占用多個(gè)頁塊，則再為它建立索引。這樣可以得到一種多級(jí)索引結(jié)構(gòu)多分樹多分樹。n如果每個(gè)內(nèi)部結(jié)點(diǎn)（根除外）有個(gè)子女，則稱為分樹分樹。 35表示方法n

13、多分樹的每個(gè)結(jié)點(diǎn)分配一個(gè)頁塊，結(jié)點(diǎn)上的信息是許多二元組（，）的序列，它們?cè)诮Y(jié)點(diǎn)內(nèi)按關(guān)鍵碼的值排序。n第個(gè)二元組中的是本結(jié)點(diǎn)的第個(gè)子結(jié)點(diǎn)（頁塊）的地址，是這個(gè)子結(jié)點(diǎn)上的最小（或者最大）關(guān)鍵碼。n多分樹的葉結(jié)點(diǎn)就是主文件的最底層索引。n主文件的每個(gè)頁塊可以看成是多分樹的外部結(jié)點(diǎn)。 3637索引檢索 要檢索一個(gè)關(guān)鍵碼為的記錄，則讀入根結(jié)點(diǎn)的頁塊，在這個(gè)頁塊上找到最后一個(gè)滿足的索引項(xiàng)（，），讀入所指的下一級(jí)索引的頁塊。這樣一級(jí)一級(jí)地進(jìn)行，直到讀入主文件頁塊，在其上查找關(guān)鍵碼為的記錄。38索引插入 在這種文件上插入記錄是不太方便的。為了使主文件的記錄保持關(guān)鍵碼遞增的次序，需要把插入位置之后的每個(gè)記錄向后

14、移動(dòng)，從而導(dǎo)致增加新的索引項(xiàng)和索引頁塊，需要對(duì)外存上的頁塊進(jìn)行大量的調(diào)整。 多分樹主要實(shí)用于靜態(tài)的索引順序文件，對(duì)于經(jīng)常需要插入和刪除的動(dòng)態(tài)索引順序文件，需要采用動(dòng)態(tài)索引結(jié)構(gòu)，即下面要討論的樹和樹 39B樹一棵一棵m m階的階的B B樹滿足下列條件樹滿足下列條件1，每個(gè)結(jié)點(diǎn)至多有m棵子樹。2，除根結(jié)點(diǎn)外，其它每個(gè)分支結(jié)點(diǎn)至少有 棵子樹。3，根結(jié)點(diǎn)至少有兩棵子樹(除非B樹只包含一個(gè)結(jié)點(diǎn))。4，所有葉結(jié)點(diǎn)在同一層上。B樹的葉結(jié)點(diǎn)可以看成一種外部結(jié)點(diǎn)，不包含任何信息。5，有j個(gè)孩子的非葉結(jié)點(diǎn)恰好有j-1個(gè)關(guān)鍵碼，關(guān)鍵碼按遞增次序排列。2/m40#define m 1024struct BTNode;

15、typedef struct BTNode * PBTNode;struct BTNode int keyNum; /* 實(shí)際關(guān)鍵字個(gè)數(shù)，keyNumm */ PBTNode parent; /* 指向父結(jié)點(diǎn) */ PBTNode *ptr; /* 子樹指針向量: ptr0ptrkeyNum */ KeyType *key; /* 關(guān)鍵字向量: key 0key keyNum1 */ typedef struct BTNode *BTree;typedef BTree * PBTree;B樹的類型和結(jié)點(diǎn)類型定義：41B樹的運(yùn)算n檢索n插入n刪除42檢索 在B樹中檢索關(guān)鍵碼key的思路根據(jù)要查找

16、的關(guān)鍵碼key，在根結(jié)點(diǎn)的關(guān)鍵碼集合中進(jìn)行順序或二分法檢索，若key=ki，則檢索成功；否則，key一定在某ki和ki+1之間，取指針pi所指結(jié)點(diǎn)繼續(xù)查找，重復(fù)上述檢索過程，直到檢索成功，或指針pi為空，檢索失敗。 43在以下B樹中檢索關(guān)鍵碼為400的結(jié)點(diǎn) 44在B樹中插入關(guān)鍵碼key的思路對(duì)高度為h的m階B樹，新結(jié)點(diǎn)一般是插在第h層。通過檢索可以確定關(guān)鍵碼應(yīng)插入的結(jié)點(diǎn)位置。然后分兩種情況討論：1，若該結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù)小于m-1，則直接插入即可。2，若該結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù)等于m-1，則將引起結(jié)點(diǎn)的分裂。以中間關(guān)鍵碼為界將結(jié)點(diǎn)一分為二，產(chǎn)生一個(gè)新結(jié)點(diǎn)，并把中間關(guān)鍵碼插入到父結(jié)點(diǎn)（h-1層）中；重復(fù)

17、上述工作，最壞情況一直分裂到根結(jié)點(diǎn)，建立一個(gè)新的根結(jié)點(diǎn)，整個(gè)B樹增加一層。 45n在以下B樹中插入關(guān)鍵碼200、460 464748在B樹中刪除關(guān)鍵碼key的思路497.6.3 B+樹一個(gè)m階的B+樹滿足下列條件1、每個(gè)結(jié)點(diǎn)至多有m棵子樹。2、除根結(jié)點(diǎn)外，其它每個(gè)分支至少有 棵子樹3、非葉結(jié)點(diǎn)的根結(jié)點(diǎn)至少有兩棵子樹。4、葉結(jié)點(diǎn)都在同一層中。 2/m50說明（1）有j棵子樹的結(jié)點(diǎn)有j個(gè)關(guān)鍵碼，它們按照遞增次序排列。 （2） 每個(gè)葉結(jié)點(diǎn)中至少包含 個(gè)關(guān)鍵碼。所有主文件記錄的索引項(xiàng)都存放在B+樹的葉結(jié)點(diǎn)中。 （3） 所有分支結(jié)點(diǎn)可看成是索引的索引。結(jié)點(diǎn)中僅包含它的各個(gè)子結(jié)點(diǎn)中最大(或最小)關(guān)鍵碼的分

18、界值及指向子結(jié)點(diǎn)的指針。 2/m51B+樹和B樹的差異：（1）B+樹有n棵子樹的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵碼；而B樹有n棵子樹的結(jié)點(diǎn)中含有n-1個(gè)關(guān)鍵碼。（2）B+樹所有的葉子結(jié)點(diǎn)中包含了完整的索引的信息，而B樹中非葉結(jié)點(diǎn)的關(guān)鍵碼與葉結(jié)點(diǎn)的關(guān)鍵碼均不重復(fù)，它們共同構(gòu)成全部索引信息。（3）B+樹所有的非葉結(jié)點(diǎn)可以看成是高層索引，結(jié)點(diǎn)中僅含有其子樹中最大（或最?。╆P(guān)鍵碼. 52B+樹的運(yùn)算n檢索檢索 在B樹中檢索關(guān)鍵碼key的方法與B樹的檢索方式相似，但若在分支結(jié)點(diǎn)上找到檢索的關(guān)鍵碼時(shí)，檢索并不結(jié)束，要繼續(xù)找到B+樹的葉結(jié)點(diǎn)為止。 53插入 與B樹的插入操作相似，總是插在葉結(jié)點(diǎn)上。當(dāng)結(jié)點(diǎn)中原關(guān)鍵碼個(gè)數(shù)等于m時(shí)，該結(jié)點(diǎn)分裂成兩個(gè)結(jié)點(diǎn)，分別使關(guān)鍵碼個(gè)數(shù)為 和 。刪除 僅在葉結(jié)點(diǎn)刪除關(guān)鍵碼。若因刪除操作使結(jié)點(diǎn)中關(guān)鍵碼數(shù)少于 時(shí)，則