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

《文件的索引結(jié)構(gòu).ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

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

2、結(jié)點的關(guān)鍵碼；如果任一結(jié)點的右子樹非空，則右子樹中的所有結(jié)點的關(guān)鍵碼都大于根結(jié)點的關(guān)鍵碼。101520406281530254二叉排序樹的插入與構(gòu)造如果二叉排序樹為空，則新結(jié)點作為根結(jié)點。如果二叉排序樹非空，則將新結(jié)點的關(guān)鍵碼與根結(jié)點的關(guān)鍵碼比較，若相等表示該結(jié)點已在二叉排序樹中；若小于根結(jié)點的關(guān)鍵碼，則將新結(jié)點插入到根結(jié)點的左子樹中；否則，插入到右子樹中。子樹中的插入過程和樹中的插入過程相同，如此進(jìn)行下去，直到找到該結(jié)點，或者直到左或右子樹為空二叉樹，新結(jié)點插入成為葉子結(jié)點為止。5最佳二叉排序樹的構(gòu)造(1)先將字典元素關(guān)鍵碼

3、排序。(2)對每個關(guān)鍵碼按二分法在排序關(guān)鍵碼序列中執(zhí)行檢索，將檢索中遇到的還未在二叉排序樹中的關(guān)鍵碼插入二叉排序樹中?！炊植檎抑兴龅降墓?jié)點依次插入二叉排序樹。6舉例（記錄二分查找的過程）對于K={27,73,10,5,18,41,99,51,25}，構(gòu)造最佳二叉排序樹的過程如下：首先將它們排序為：5，10，18，25，27，41，51，73，99，然后從空二叉樹出發(fā)，在排序的關(guān)鍵碼序列中用二分法檢索5，檢索中遇到的結(jié)點為27,10,5，將這三個結(jié)點插入二叉排序樹。再檢索第二個結(jié)點10，遇到的結(jié)點為27,10，二叉排序樹

4、中已經(jīng)有這兩個結(jié)點。再檢索第三個結(jié)點18，…。得到的插入次序為27，10，5，18，25，51，41，73，99。7靜態(tài)查找表索引結(jié)構(gòu)scorestudentIDnameassignmentfinialexam4523周夏司50394616李景文1043472葉佩霖50354829郭舒文60514917杜文杰6052509阮萃茵7029513龍國才0355221陳俊珊45455313李欣怡7555554劉星50295728郭凌典25485914李敏妍90746127唐慰夷30496211吳宇翔0477110何英華0517830

5、梁迪欣80698索引索引是索引項的集合，一個索引項是由一個結(jié)點的關(guān)鍵碼和該結(jié)點的存儲位置組成的關(guān)聯(lián)。索引的實質(zhì)還是字典，而且是元素類型相同的等長結(jié)點的字典。所有關(guān)于字典的討論都適合于索引；所有字典的實現(xiàn)也可以用來組織索引。9文件與索引結(jié)構(gòu)——打開一個文件10從文本文件中讀入數(shù)據(jù)集合11將數(shù)據(jù)集轉(zhuǎn)換為記錄集12通過記錄的某一項屬性值反過來查找到這個記錄的存放地址，或者記錄對應(yīng)的關(guān)鍵碼。我們稱這種索引為倒排索引（invertedindex）。13倒排索引的建立14利用函數(shù)指針實現(xiàn)倒排索引的建立15包含數(shù)據(jù)邏輯層的軟件架構(gòu)數(shù)據(jù)源1數(shù)

6、據(jù)源2…數(shù)據(jù)源n數(shù)據(jù)邏輯層數(shù)據(jù)處理層數(shù)據(jù)結(jié)構(gòu)及類型類型化計算數(shù)據(jù)對象XML文檔+Stylesheet數(shù)據(jù)呈現(xiàn)數(shù)據(jù)交換16動態(tài)查找表——平衡二叉排序樹以上的“最佳”二叉排序樹，不僅構(gòu)造的時間代價很大，而且很難動態(tài)的保持。通常用于表示一旦構(gòu)造后就不改動的靜態(tài)字典；對于動態(tài)字典，為了能夠在進(jìn)行元素的插入和刪除操作時，較快地對二叉排序樹進(jìn)行調(diào)整，通常不要求二叉排序樹總是保持“最佳的”檢索效率，而是希望達(dá)到一種比較容易調(diào)整的“較佳”的狀態(tài)。17平衡二叉排序樹，又稱AVL樹，要求從整體上看，在動態(tài)插入或刪除后，每個結(jié)點的左右子樹能夠基本保

7、持平衡。不會出現(xiàn)過分傾斜的現(xiàn)象，從而使得平均檢索長度保持比較短。結(jié)點右子樹高度與左子樹高度之差稱為該結(jié)點的平衡因子，平衡二叉排序樹中每個結(jié)點的平衡因子只能是1、0或－1。1819插入的影響在平衡二叉排序樹中插入新結(jié)點時，如果新結(jié)點插入后不影響其父結(jié)點為根的子樹高度，則不會破壞整個二叉排序樹的平衡；反之，若父結(jié)點為根的子樹高度增加了，則可能引起一連串的反映。其結(jié)果又有兩種可能，一種是在其祖先的某一層上不再影響子二叉排序樹的高度，則整個二叉排序樹仍然是平衡的；另一種是在其祖先的某一層上破壞了平衡的要求，使整個二叉排序樹不再是AVL

8、樹。20最小不平衡子樹處理失去平衡的方法為首先找出最小不平衡子樹（指離插入結(jié)點最近，且以平衡因子絕對值大于1的結(jié)點為根的子樹），在保證排序樹性質(zhì)的前提下，調(diào)整最小不平衡子樹中各結(jié)點的連接關(guān)系，以達(dá)到新的平衡。2122AVL樹調(diào)整平衡的原則LL型調(diào)整破壞平衡的原因是由于在A的左