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

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

2、非空，則右子樹中的所有結(jié)點(diǎn)的關(guān)鍵碼都大于根結(jié)點(diǎn)的關(guān)鍵碼,5,二叉排序樹的插入與構(gòu)造,如果二叉排序樹為空，則新結(jié)點(diǎn)作為根結(jié)點(diǎn)。 如果二叉排序樹非空，則將新結(jié)點(diǎn)的關(guān)鍵碼與根結(jié)點(diǎn)的關(guān)鍵碼比較， 若相等表示該結(jié)點(diǎn)已在二叉排序樹中；若小于根結(jié)點(diǎn)的關(guān)鍵碼，則將新結(jié)點(diǎn)插入到根結(jié)點(diǎ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í)行檢索，將檢索中遇到的還未在二叉排序樹中的關(guān)鍵碼插入二叉排序樹中

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

4、由一個(gè)結(jié)點(diǎn)的關(guān)鍵碼和該結(jié)點(diǎn)的存儲(chǔ)位置組成的關(guān)聯(lián)。 索引的實(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

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

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

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

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

9、連同其右子樹向右下旋轉(zhuǎn)成為新根C的右子樹，原C的右子樹成為A的左子樹,4,1,0,4,1,0,LR(L,LR(R,29,RL型調(diào)整,破壞平衡的原因是由于在A的右子女(R)的左子樹(L)中插入結(jié)點(diǎn)，使A的平衡因子由1變?yōu)?而失去平衡。 調(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的右子樹,30,31,調(diào)整控制在最小不平衡子樹內(nèi),上述所有的調(diào)整操作中，A為根的最小不平衡子樹的高度在插入結(jié)點(diǎn)之前和調(diào)整之

10、后相同，對(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,索引文件 多分樹,如果文件很大，索引順序文件的索引可以采用多級(jí)索引結(jié)構(gòu)以提高檢索的效率。 即為主文件建立了

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

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

13、加新的索引項(xiàng)和索引頁塊，需要對(duì)外存上的頁塊進(jìn)行大量的調(diào)整。 多分樹主要實(shí)用于靜態(tài)的索引順序文件，對(duì)于經(jīng)常需要插入和刪除的動(dòng)態(tài)索引順序文件，需要采用動(dòng)態(tài)索引結(jié)構(gòu)，即下面要討論的樹和樹,39,B樹,一棵m階的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)鍵碼按遞增次序排列,40,define m 1024 struct BTNode; typedef struct BT

14、Node * 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)類型定義,41,B樹的運(yùn)算,檢索 插入 刪除,42,檢索 在B樹中檢索關(guān)鍵碼key的思路,根據(jù)要查找的關(guān)鍵碼key，在根結(jié)點(diǎn)

15、的關(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ù)上述工作，最壞

16、情況一直分裂到根結(jié)點(diǎn)，建立一個(gè)新的根結(jié)點(diǎn)，整個(gè)B樹增加一層,45,在以下B樹中插入關(guān)鍵碼200、460,46,47,48,在B樹中刪除關(guān)鍵碼key的思路,49,7.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)都在同一層中,50,說明,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)鍵碼的分界值

17、及指向子結(jié)點(diǎn)的指針,51,B+樹和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)鍵碼,52,B+樹的運(yù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)

18、分裂成兩個(gè)結(jié)點(diǎn)，分別使關(guān)鍵碼個(gè)數(shù)為 和 。 刪除 僅在葉結(jié)點(diǎn)刪除關(guān)鍵碼。若因刪除操作使結(jié)點(diǎn)中關(guān)鍵碼數(shù)少于 時(shí)，則從兄弟結(jié)點(diǎn)調(diào)整或者合并。合并的過程和B樹相似，區(qū)別是父結(jié)點(diǎn)中作為分界的關(guān)鍵碼，不放入合并后的結(jié)點(diǎn)中,54,B+樹在索引順序文件中的應(yīng)用,B+樹可以表示主文件的密集索引，也可以表示稀疏索引，以稀疏索引為例： 通常在B+樹表示的索引順序文件中設(shè)兩個(gè)頭指針一個(gè)指向B+樹的根結(jié)點(diǎn)，另一個(gè)指向主文件中關(guān)鍵碼最小的頁塊，所有主文件的頁塊順序鏈成單鏈表。 在索引順序文件中可以采用兩種檢索方式一種直接從最小關(guān)鍵碼開始順序檢索；另一種從B+樹的根結(jié)點(diǎn)開始逐層檢索。 當(dāng)主文件中需要增加或減少一個(gè)頁塊時(shí)，只需在B+樹中為之插入或刪除一個(gè)索引項(xiàng)，問題歸結(jié)為B+樹本身的運(yùn)算,55,56,B+樹的主要優(yōu)點(diǎn),B+樹可以比B