《索引技術(shù)教學》PPT課件.pptVIP

第十章 索引技術(shù),任課教員：張 銘 /mzhang/DS/ 北京大學信息科學與技術(shù)學院 網(wǎng)絡(luò)與信息系統(tǒng)研究所 版權(quán)所有，轉(zhuǎn)載或翻印必究,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 2,主要內(nèi)容,10.1 線性索引 10.2 靜態(tài)索引 10.3 倒排索引 10.4 動態(tài)索引 10.5 動態(tài)、靜態(tài)索引性能比較,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 3,基本概念,輸入順序文件 主碼與輔碼 索引與索引文件 稠密索引與稀疏索引,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 4,輸入順序文件,輸入順序文件( entry-sequenced file )按照記錄進入系統(tǒng)的順序存儲記錄 輸入順序文件的結(jié)構(gòu)相當于一個磁盤中未排序的線性表 因此不支持高效率的檢索,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 5,主碼,主碼( primary key )是數(shù)據(jù)庫中的每條記錄的唯一標識 例如，公司職員信息的記錄的主碼可以是職員的身份證號碼 如果只有主碼，不便于各種靈活檢索,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 6,輔碼,輔碼( secondary key )是數(shù)據(jù)庫中可以出現(xiàn)重復值的碼 輔碼索引把一個輔碼值與具有這個輔碼值的每一條記錄的主碼值關(guān)聯(lián)起來 大多數(shù)檢索都是利用輔碼索引來完成的,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 7,索引,索引( indexing )是把一個關(guān)鍵碼與它對應的數(shù)據(jù)記錄的位置相關(guān)聯(lián)的過程 索引技術(shù)是組織大型數(shù)據(jù)庫的一種重要技術(shù) 數(shù)據(jù)庫組織存儲在外存中的大量記錄 高效率的檢索 插入、更新、刪除,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 8,索引文件,索引文件( index file )是用于記錄這種聯(lián)系（關(guān)鍵碼與它對應的數(shù)據(jù)記錄的位置）的文件組織結(jié)構(gòu)。 索引文件的記錄 （關(guān)鍵碼，指針）對 將每個關(guān)鍵碼和一個指針關(guān)聯(lián) 指針指向主要數(shù)據(jù)庫文件（也稱為“主文件”）中的完整記錄,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 9,索引文件,索引文件并不需要重新排列記錄在磁盤中的順序（不用重排主文件） 一個數(shù)據(jù)庫可能有多個相關(guān)的索引文件 每個索引文件往往支持一個關(guān)鍵碼字段 可以通過該索引文件高效訪問記錄中該關(guān)鍵碼值,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 10,稠密索引,對每一個記錄建立一個索引項，這樣建立的索引被稱為稠密索引( dense index ) 數(shù)據(jù)庫文件中的記錄不按照關(guān)鍵碼的順序排列時（比如按照加入的順序排列）,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 11,稀疏索引,對一組記錄建立一個索引項，這種索引稱之為稀疏索引( spare index ) 當記錄在磁盤中是按照關(guān)鍵碼的順序存放 可以把記錄分成多個組（塊） 稀疏索引索引項的指針指向的是這一組記錄在磁盤中的起始位置,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 12,10.1 線性索引,基本概念 線性索引的優(yōu)點 線性索引的問題 二級線性索引,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 13,基本概念,線性索引(linear index)的索引文件 一組簡單的關(guān)鍵碼(key)/指針(pointer)對的序列,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 14,基本概念（續(xù)）,線性索引文件按照關(guān)鍵碼的順序進行排序 文件中的指針指向存儲在磁盤上的文件記錄起始位置或者主索引中主碼的起始位置,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 15,基本概念（續(xù)）,線性索引的索引文件 存儲在內(nèi)存中，把索引存儲在內(nèi)存中能大大地提高檢索速度 存儲在磁盤中 根據(jù)線性索引的文件大小和內(nèi)存的空間限制,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 16,線性索引的優(yōu)點,對變長的數(shù)據(jù)庫記錄的訪問 可以對數(shù)據(jù)進行高效檢索 二分檢索 順序處理 比較操作 批處理的操作 節(jié)省空間 (相對其它索引結(jié)構(gòu)),北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 17,線性索引的問題,線性索引太大，存儲在磁盤中 在一次檢索過程中有可能多次訪問磁盤，從而影響檢索的效率 解決辦法：使用二級線性索引 更新線性索引 在數(shù)據(jù)庫中插入或者刪除記錄時,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 18,二級線性索引,每一條二級線性索引記錄對應于一個一級線性索引文件的磁盤塊 關(guān)鍵碼的值與對應的線性索引文件的磁盤塊中第一條記錄(從物理位置上看的第一條)的關(guān)鍵碼的值相同 記錄中的指針則指向相應線性索引文件的磁盤塊的起始位置,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 19,二級線性索引,例如，磁盤塊的大小是1024字節(jié)，每個關(guān)鍵碼指針記錄需要8個字節(jié)，則每磁盤塊可以存儲128條這樣的記錄 假設(shè)線性文件索引中包含10000條記錄，那么該線性索引占用79個磁盤塊，相應的，二級線性索引文件中有79項記錄,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 20,二級線性索引的例子,關(guān)鍵碼與相應磁盤塊中第一條記錄的關(guān)鍵碼的值相同 指針指向相應磁盤塊的起始位置,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 21,二級線性索引檢索,在檢索時，線性索引文件并不被讀入內(nèi)存，被讀入內(nèi)存的是二級線性索引文件 由于二級索引往往存儲內(nèi)存，通常只需要訪問兩次磁盤即可：一次讀入線性索引文件，一次讀入數(shù)據(jù)庫記錄,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 22,二級線性索引檢索的例子,例如，檢索關(guān)鍵碼為2555的記錄 首先在內(nèi)存中的二級線性索引文件中找到關(guān)鍵碼的值小于等于2555的最大關(guān)鍵碼所在的記錄關(guān)鍵碼為2003的記錄 根據(jù)記錄中的指針找到其對應的線性索引文件的磁盤塊，并把該塊讀入內(nèi)存 按照二分法對該塊進行檢索，找到所需要的記錄在磁盤上的位置 最后把所需記錄讀入，完成檢索操作,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 23,10.2 靜態(tài)索引,10.2.1 多分樹 10.2.2 ISAM,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 24,基本概念,靜態(tài)索引 索引結(jié)構(gòu)在文件創(chuàng)建、初始裝入記錄時生成 一旦生成就固定下來，在系統(tǒng)運行(例如插入和刪除記錄)過程中索引結(jié)構(gòu)并不改變 只有當文件再組織時才允許改變索引結(jié)構(gòu),北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 25,10.2.1 多分樹,組織索引一般不用二叉樹而采用多分樹 大大減少訪問外存的次數(shù),北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 26,多分樹圖例,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 27,上圖訪問一個葉結(jié)點 查找二叉樹訪問六次外存 查找多分樹訪問兩次外存,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 28,結(jié)點更大 以更少的外存訪問次數(shù)來完成查找 需要較大的緩沖區(qū) 讀入一個結(jié)點也需較多時間 一個結(jié)點最好能放在一個磁盤塊中,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 29,“數(shù)據(jù)基本區(qū)” 多分樹的葉結(jié)點區(qū)域 存放數(shù)據(jù)記錄 “索引區(qū)” 多分樹的非葉結(jié)點區(qū)域 存放各子樹結(jié)點中的最大(或最小)的關(guān)鍵碼,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 30,溢出、溢出區(qū) 新記錄要插入的結(jié)點已滿 把溢出的記錄存放到另開辟的溢出區(qū) 不改變索引的結(jié)構(gòu) 記錄送入溢出區(qū)的兩種方式 保持順序，把最后一個記錄送往溢出區(qū) 不保持順序，把新插入的記錄送入溢出區(qū),北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 31,10.2.2 ISAM,ISAM是解決需要頻繁更新的大型數(shù)據(jù)庫的一個早期嘗試 在采用基于B+樹的VSAM技術(shù)之前，IBM公司曾經(jīng)廣泛地采用ISAM技術(shù),北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 32,多分樹的應用 為磁盤存取而設(shè)計 結(jié)構(gòu)采用多級索引 主索引 柱面索引 磁道索引,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 33,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 34,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 35,ISAM的查找,先查主索引，從主索引查出柱面索引的分布 主索引常駐內(nèi)存 從柱面索引查出磁道索引的分布 柱面索引放在中間位置的柱面 從磁道索引查出所要找的記錄的地址,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 36,ISAM的插入,磁道索引中，索引項的兩個子項在記錄插入之前是相同的，在插入記錄后就要改變 例如，插入R165 以后：,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 37,如果有多個溢出記錄，則這些溢出記錄必須按順序鏈接起來，在溢出索引項中是這些溢出記錄的最大關(guān)鍵碼和具有最小關(guān)鍵碼的溢出記錄所在磁道號 例如，再插入R168，R166以后：,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 38,如果有多個溢出記錄，則這些溢出記錄必須按順序鏈接起來，在溢出索引項中是這些溢出記錄的最大關(guān)鍵碼和具有最小關(guān)鍵碼的溢出記錄所在磁道號 例如，再插入R168，R166以后：,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 39,在溢出區(qū)中，除了存放記錄以外還存放鏈指針 柱面索引變化：,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 40,ISAM插入的好處,在進一步查找時，容易判斷要查找的記錄是在基本區(qū)還是在溢出區(qū) 若在基本區(qū)，則指針指出了記錄所在的磁道號； 若在溢出區(qū)，則指針指出了溢出記錄鏈中第一個(關(guān)鍵碼為最小)記錄所在的磁道號及在磁道中的相對記錄號，沿著該鏈可以找到要找的記錄。,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 41,10.3 倒排索引,10.3.1 基于屬性的倒排 10.3.2 對正文文件的倒排,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 42,基本概念,不僅需要按關(guān)鍵碼的值查找 還需要按照屬性的值來查找記錄,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 43,基本概念,倒排索引對某屬性按屬性值建立索引 （屬性值，具有該屬性值的各記錄的地址列表） 不是由記錄關(guān)鍵碼來確定屬性值，而是由屬性值來確定記錄的位置，因而稱為倒排索引(inverted index) 這種屬性往往是離散型的 對于連續(xù)型的索引，往往用B樹,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 44,基本概念,倒排索引文件 帶有倒排索引的文件 簡稱倒排文件(inverted file),北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 45,10.3.1 基于屬性的檢索,基于屬性的檢索 要求檢索結(jié)構(gòu)中某個或若干個屬性滿足一定條件的結(jié)點,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 46,例如，在某百貨公司的職工文件中，有如下的記錄格式：(EMP#，NAME，DEPT，AGE，SAL) 該記錄格式中的數(shù)據(jù)項其含義分別為職工號，姓名，所在部門，年齡，工資。,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 47,查詢實例,對這樣的職工文件進行下列類型的查詢： （1）簡單查詢。例如：列出玩具部(即DEPT=“Toy”)的所有職工記錄 （2）范圍查詢。例如：列出工資在40元和80元之間(即40SAL80)的所有職工記錄 （3）邏輯查詢。例如：列出玩具部中年齡在50歲以上或者工資在100元以上的職工記錄 (DEPT=“Toy”AND(AGE50 OR SAL100),北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 48,10.3.1 倒排表,倒排表(inverted list) 是基于屬性的倒排 在保留原表的同時，對于感興趣的（即可以用來作為檢索參數(shù)的）每個屬性的可能取值都建立一個稱作倒排表的線性表 存放與此屬性相對應的所有關(guān)鍵碼值,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 49,10.3.1 倒排文件,索引項 一個具體的索引值 一組指針（例如記錄的主碼） 這些指針分別指向在該屬性項上具有該具體值的各個記錄 一個倒排表 一個索引項 倒排文件 倒排表組成的索引文件,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 50,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 51,10.3.1 基于屬性的倒排,列出玩具部(即DEPT=“Toy”)的所有職工記錄。 從關(guān)于屬性DEPT的索引中，取出屬性值為“Toy”的倒排表，此倒排表中包合的指針所指向的各記錄即為所求。,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 52,列出工資在40元和80元之間(即40SAL80)的所有職工記錄。 從關(guān)于屬性SAL的索引中，找出屬性值在40與80之間的倒排表，每個倒排表中含有一個指針集合。 對這些集合進行并的運算，其結(jié)果集合中包含的指針所指的各記錄即為所求。,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 53,列出玩具部中年齡在50歲以上或者工資在100元以上的職工記錄 (DEPT=“Toy”AND(AGE50 OR SAL100)。 先采用類似（1）、（2）的方法，分別找出滿足條件DEPT=“Toy”，AGE50，和SAL100的指針集合，然后對后兩個指針集合求并，并且將結(jié)果集合與第一個指針集合求交，最后的結(jié)果集合中包含的指針所指的各記錄即為所求。,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 54,優(yōu)點：能夠?qū)τ诨趯傩缘臋z索進行較高效率的處理 缺點： 花費了保存倒排表的存儲代價 降低了更新運算的效率,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 55,10.3.2 對正文文件的倒排,正文索引(Text Indexing)處理的就是“建立一個數(shù)據(jù)結(jié)構(gòu)以提供對文本內(nèi)容的快速檢索”。 方法 詞索引(word index) 全文索引(full-text index),北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 56,詞索引,基本思想： 把正文看作由符號和詞所組成的集合，從正文中抽取出關(guān)鍵詞，然后用這些關(guān)鍵詞組成一些適合快速檢索的數(shù)據(jù)結(jié)構(gòu)。 適用于多種文本類型，特別是那些可以很容易就解析成一組詞的集合的文本 適用于英文 不適用于中文等東方文字,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 57,全文索引,基本思想： 把正文看作一個長的字符串 在數(shù)據(jù)結(jié)構(gòu)中記錄的是子字符串的開始位置 查詢就可以針對正文中的任何子字符串 可以對每一個字符建立索引，從而使查詢詞不再限于關(guān)鍵詞 需要更大的空間,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 58,詞索引使用最廣泛 一個已經(jīng)排過序的關(guān)鍵詞的列表 其中每個關(guān)鍵詞指向一個倒排表（posting list） 指向該關(guān)鍵詞出現(xiàn)文檔集合 在文檔中的位置,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 59,倒排文件的全文本索引,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 60,簡化的正文倒排文件,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 61,建立正文倒排文件,第一步，對文檔集中的所有文件都進行分割處理，把正文分成多條記錄文檔。 切分正文記錄取決于程序的需要 定長的塊、段落、章節(jié)，甚至一組文檔,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 62,第二步，給每條記錄賦一組關(guān)鍵詞。 以人工或者自動的方式從記錄中抽取關(guān)鍵詞 停用詞(Stopword) 抽詞干(Stemming) 切詞（segmentation）,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 63,第三步，建立正文倒排表、倒排文件 得到各個關(guān)鍵詞的集合 對于每一個關(guān)鍵詞得到其倒排表 然后把所有的倒排表存入文件 記錄在每個倒排表在索引文件中開始的位置以及每個表的大?。ㄒ部梢杂涗浢總€關(guān)鍵詞的出現(xiàn)次數(shù)）,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 64,對關(guān)鍵詞的檢索,第一步，在倒排文件中檢索關(guān)鍵詞。 第二步，如果找到了關(guān)鍵詞，那么獲取文件中的對應的倒排表，并獲取倒排表中的記錄。 通常使用另一個索引結(jié)構(gòu)（字典）進一步對關(guān)鍵詞表進行有序索引 Trie 散列,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 65,倒排文件優(yōu)劣,高效檢索，用于文本數(shù)據(jù)庫系統(tǒng) 支持的檢索類型有限 檢索詞有限 只能用索引文件中的關(guān)鍵詞 倒排文件中的索引效率可能不高 需要的空間代價往往很高,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 66,10.4 動態(tài)索引,10.4.1 B樹 10.4.2 B+樹 10.4.3 VSAM 10.4.4 B樹的性能分析,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 67,基本概念,動態(tài)索引結(jié)構(gòu) 索引結(jié)構(gòu)本身也可能發(fā)生改變 在系統(tǒng)運行過程中插入或刪除記錄時 目的 保持較好的性能 例如較高的檢索效率,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 68,10.4.1 B樹,B樹(Balanced Tree) 一種平衡的多分樹,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 69,B樹的結(jié)構(gòu)定義,定義：一個m階的B樹滿足下列條件： (1) 每個結(jié)點至多有m個子結(jié)點； (2) 除根結(jié)點和葉結(jié)點外，其它每個結(jié)點至少有 個子結(jié)點； (3) 根結(jié)點至少有兩個子結(jié)點 唯一例外的是根結(jié)點就是葉結(jié)點時沒有子結(jié)點 此時B樹只包含一個結(jié)點 (4) 所有的葉結(jié)點在同一層； (5) 有k個子結(jié)點的非根結(jié)點恰好包含k-1個關(guān)鍵碼。,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 70,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 71,B樹的結(jié)點結(jié)構(gòu),B樹的一個包含j個關(guān)鍵碼，j+1個指針的結(jié)點的一般形式為： 其中Ki是關(guān)鍵碼值，K1K2Kj， Pi是指向包括Ki到Ki+1之間的關(guān)鍵碼的子樹的指針。,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 72,B樹結(jié)點抽象數(shù)據(jù)類型,template class BNode int n; /子結(jié)點的個數(shù) /指向父結(jié)點的指針 BNode * parent; /存儲關(guān)鍵碼的數(shù)組，最多有MAXREC個關(guān)鍵碼 Key keyMAXREC; /指向子節(jié)點的指針，最多有MAXREC+1個指針 BNode * ptrMAXREC+1; ;,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 73,template /用于在B樹中檢索關(guān)鍵碼的數(shù)據(jù)結(jié)構(gòu) struct Triple /指向關(guān)鍵碼所在結(jié)點的指針 BNode * r; /記錄關(guān)鍵碼在結(jié)點中的位置 int i; /標識是否檢索到了關(guān)鍵碼 char tag; ;,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 74,B樹抽象數(shù)據(jù)類型(續(xù)),template class BTree BNode * root; int m; /B樹的階 BTree(); /構(gòu)造函數(shù) /檢索關(guān)鍵碼為x的結(jié)點， /檢索信息記錄在結(jié)構(gòu)Triple中 Triple ,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 75,/插入關(guān)鍵碼x int Insert(const Key,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 76,/調(diào)整結(jié)點的右兄弟和父節(jié)點 void LeftAdjust(BNode *p, BNode *q, const int d, const int j); /調(diào)整結(jié)點的左兄弟和父節(jié)點 void RightAdjust(BNode *p, BNode *q, const int d, const int j); /壓縮結(jié)點 void compress(BNode *p, const int j); /合并節(jié)點 void merge(BNode *p, BNode *q, BNode *p1, int j); ,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 77,B樹的查找,把根結(jié)點讀出來，在根結(jié)點所包含的關(guān)鍵碼K1，Kj中查找給定的關(guān)鍵碼值(當結(jié)點包含的關(guān)鍵碼不多時，就用順序檢索；當結(jié)點包含的關(guān)鍵碼數(shù)目較多時，可以用二分檢索)， 找到則檢索成功； 否則，確定要查的關(guān)鍵碼值是在某個Ki和Ki+1之間，于是取pi所指向的結(jié)點繼續(xù)查找。 如果pi指向外部結(jié)點，表示檢索失敗。,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 78,B樹的插入,葉結(jié)點處在第I層的B樹，插入的關(guān)鍵碼總是在第I-1層,插入14,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 79,外部結(jié)點處在第I層的B樹，插入的關(guān)鍵碼總是在第I-1層,插入14,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 80,插入可能導致B樹朝著根的方向生長,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 81,插入55,使得包含值50和52的頁分裂，把值52提升到父結(jié)點,階m=3,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 82,插入55結(jié)果,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 83,插入引起3階B樹根結(jié)點分裂的例子,插入19,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 84,插入引起3階B樹根結(jié)點分裂的例子,插入19,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 85,插入19,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 86,插入19,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 87,B樹的刪除,刪除的關(guān)鍵碼不在葉結(jié)點層 先把此關(guān)鍵碼與它在B樹里的后繼對換位置，然后再刪除該關(guān)鍵碼,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 88,B樹的刪除(續(xù)),刪除的關(guān)鍵碼在葉結(jié)點層 刪除后關(guān)鍵碼個數(shù)不小于 直接刪除 關(guān)鍵碼個數(shù)小于 如果兄弟結(jié)點關(guān)鍵碼個數(shù)不等于 從兄弟結(jié)點移若干個關(guān)鍵碼到該結(jié)點中來(父結(jié)點中的一個關(guān)鍵碼要做相應變化) 如果兄弟結(jié)點關(guān)鍵碼個數(shù)等于 合并,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 89,階m=4 刪除045,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 90,關(guān)鍵碼個數(shù)不足,從兄弟結(jié)點移動135,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 91,注意：兄弟結(jié)點中的135被移動到父結(jié)點中，被移動到結(jié)點中的是父結(jié)點中的112,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 92,刪除112,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 93,關(guān)鍵碼個數(shù)不足,兄弟結(jié)點關(guān)鍵碼個數(shù)也不足,兄弟結(jié)點關(guān)鍵碼個數(shù)也不足,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 94,合并,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 95,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 96,10.4.2 B+樹,是B樹的一種變形 在葉結(jié)點上存儲信息的樹 所有的關(guān)鍵碼均出現(xiàn)在葉結(jié)點上 各層結(jié)點中的關(guān)鍵碼均是下一層相應結(jié)點中最大關(guān)鍵碼（或最小關(guān)鍵碼）的復寫,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 97,B+樹的結(jié)構(gòu)定義,m階B+樹的結(jié)構(gòu)定義如下： (1)每個結(jié)點至多有m個子結(jié)點； (2)每個結(jié)點(除根外)至少有 個子結(jié)點； (3)根結(jié)點至少有兩個子結(jié)點； (4)有k個子結(jié)點的結(jié)點必有k個關(guān)鍵碼。,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 98,2階B+樹的例子,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 99,B+樹的抽象數(shù)據(jù)類型,template class PAIR /用于存儲關(guān)鍵碼和指向磁盤塊的指針的數(shù)據(jù)結(jié)構(gòu) public: void* ptr; /對于葉結(jié)點是指向磁盤塊的指針 /而對非葉節(jié)點是指向子結(jié)點的指針 Key key; ;,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 100,template class BPNode /定義B+樹結(jié)點 public: /存儲關(guān)鍵碼的數(shù)組 PAIR recsMAXRECS; int n; /子結(jié)點的個數(shù) /指向結(jié)點左兄弟的指針 BPNode *leftptr; /指向結(jié)點左兄弟的指針 BPNode *rightptr; /表示結(jié)點是否是葉結(jié)點 bool isLeaf; BPNode(); /構(gòu)造函數(shù) bool isFull(); /結(jié)點是否已滿 ;,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 101,/BPTree class template class BPTree /定義B樹 public: BPNode *root; /根結(jié)點 BPTree(); /構(gòu)造函數(shù) BPTree(); /析構(gòu)函數(shù) /檢索關(guān)鍵碼K bool Search(Key K,Elem*& e) /插入關(guān)鍵碼K bool insert(Key K,Elem*& e) /刪除關(guān)鍵碼K bool remove(Key K,Elem*& e) ,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 102,B+樹的查找,查找應該到葉結(jié)點層 在上層已找到待查的關(guān)鍵碼，并不停止 而是繼續(xù)沿指針向下一直查到葉結(jié)點層的這個關(guān)鍵碼 B+樹的葉結(jié)點一般鏈接起來，形成一個雙鏈表 適合順序檢索（范圍檢索） 實際應用更廣,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 103,B+樹的插入,插入分裂 過程和B樹類似 注意保證上一層結(jié)點中有這兩個結(jié)點的最大關(guān)鍵碼（最小關(guān)鍵碼）,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 104,階m=3 插入15,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 105,插入15后,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 106,插入16,結(jié)點滿，需要分裂,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 107,插入17,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 108,插入19,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 109,結(jié)點滿，需要分裂,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 110,結(jié)點滿，需要分裂,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 111,樹增加一層,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 112,B+樹的刪除,當關(guān)鍵碼不滿時，與左右兄弟進行調(diào)整、合并的處理和B樹類似 關(guān)鍵碼在葉結(jié)點層刪除后，其在上層的復本可以保留，做為一個“分界關(guān)鍵碼”存在 也可以替換為新的最大關(guān)鍵碼（或最小關(guān)鍵碼）,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 113,23被刪除 但上層結(jié)點中的副本保留,階m=3 刪除23,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 114,10.4.3 VSAM,VSAM(Virtual Storage Access Method)虛擬存儲存取方法 B+樹的應用 一種索引順序文件的組織方式 與存儲設(shè)備無關(guān)，存儲單位是“邏輯”的,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 115,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 116,VSAM的組成,索引集 順序集（順序集索引） 和索引集共同形成了B+樹結(jié)構(gòu)的文件索引 數(shù)據(jù)集 存放文件記錄 記錄可以是變長的,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 117,控制區(qū)間,控制區(qū)間(Control Interval) 在數(shù)據(jù)集中 I/O中數(shù)據(jù)傳輸?shù)幕締挝?內(nèi)部結(jié)構(gòu)如下圖,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 118,順序集的組成,控制區(qū)間的索引項 在順序集中 內(nèi)容為該控制區(qū)間中的最高關(guān)鍵碼和指向該控制區(qū)間的指針 若干“相鄰”的索引項構(gòu)成順序集一個結(jié)點葉結(jié)點 控制域(control area) 順序集的一個結(jié)點連同它們對應的全部數(shù)據(jù)集結(jié)點,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 119,文件初建時的控制與結(jié)構(gòu),北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 120,控制域的結(jié)構(gòu)和存放方式,順序集結(jié)點可以在一個磁道上重復地存放，以便減少讀索引的等待時間 修改時也要改多個復本,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 121,索引集的組成,順序集結(jié)點的索引項 在索引集中 內(nèi)容為該順序集結(jié)點所在控制域中的最高關(guān)鍵碼和指向該順序集結(jié)點的指針 相當于非葉結(jié)點,北京大學信息學院 版權(quán)所有，轉(zhuǎn)載或翻印必究 Page 122,VSAM的插入,調(diào)用B+樹的查找算法，找到該記錄關(guān)鍵碼應插入的順序集結(jié)點