數(shù)據(jù)庫(kù)系統(tǒng)概念12-索引與散列(1)

1、數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-31/131Book :數(shù)據(jù)庫(kù)概念數(shù)據(jù)庫(kù)概念 Ver.5 by Silberschatz 等等Chapter 12 : Indexing and Hashing第第12章章 索引與散列索引與散列1數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-32/131項(xiàng)目驅(qū)動(dòng)目標(biāo)：項(xiàng)目驅(qū)動(dòng)目標(biāo)：如何快速存取數(shù)據(jù)庫(kù)中的數(shù)據(jù)：如何快速存取數(shù)據(jù)庫(kù)中的數(shù)據(jù)：一、順序索引一、順序索引二、二、B+B+樹樹 主要討論問題：主要討論問題：什么是順序索引，有何用途什么是順序索引，有何用途 什么是稠密與稀疏索引什么是稠密與稀疏索引什么是多級(jí)索引什么是多級(jí)索引, ,有何用途有何用途順序索引如何更新順序索引如何更新何時(shí)需要建立輔

2、助索引何時(shí)需要建立輔助索引什么是什么是B+B+樹索引樹索引B+B+樹有何特點(diǎn)樹有何特點(diǎn)B+B+樹索引如何用于查詢樹索引如何用于查詢1.1.B+B+樹索引如何更新樹索引如何更新 數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-33/131Basic Concepts 基本概念Ordered Indices 順序索引 B+-Tree Index Files B-樹索引B-Tree Index Files B-樹文件Static Hashing 靜態(tài)散列Dynamic Hashing 動(dòng)態(tài)散列Comparison of Ordered Indexing and Hashing 比較Index Definition in S

3、QL SQL 中的索引數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-34/131l“檢”與“索（辦手續(xù)）”。在圖書館借書時(shí)，l關(guān)鍵字到記錄位置的對(duì)查表,即下列三元組的集合: l索引項(xiàng) (關(guān)鍵字，記錄地址，附加信息)， ll例 以年齡為關(guān)鍵字，定義Hash(Age) = Age Mod 12，把人按年齡分成12個(gè)組，即 通常的12屬相“鼠、牛、虎、兔，.”。 在同一屬相中再線性搜索，尋址效率提高 12倍。 找書的時(shí)間比辦理找書的時(shí)間比辦理手續(xù)的時(shí)間長(zhǎng)得多手續(xù)的時(shí)間長(zhǎng)得多數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-35/131“檢”與“索（辦手續(xù)）”。在圖書館借書時(shí)，關(guān)鍵字到記錄位置的對(duì)查表,即下列三元組的集合: 索引項(xiàng) (關(guān)鍵字，記錄地

4、址，附加信息)， 例1 以年齡為關(guān)鍵字， 定義 Hash(Age) = Age Mod 12， 把人按年齡分成12個(gè)組，即 通常的12屬相“鼠、牛、虎、兔，.”。 在同一屬相中再線性搜索，尋址效率提高 12倍。 數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-36/131例2 影劇場(chǎng)分單雙號(hào)進(jìn)門，相當(dāng)于Hash（N ）= N Mod 2，使觀眾入座速度提高一倍。 例3 在英文字典每個(gè)字母開始處貼一標(biāo)簽，相當(dāng)于定 Hash（WordStr） WordStr0， 提高了查字典的效率例4 寶光寺：數(shù)羅漢, 領(lǐng)取所謂命運(yùn)卡. Hash(Person)=(RedomSeed+Age+1)*2+SexSex is 0 or 1數(shù)

5、據(jù)統(tǒng)系統(tǒng)2022-6-37/1312. 無(wú)序索引 索引映射 IndexMap：關(guān)鍵字 - 記錄號(hào) ，而索引文件不排序。平均搜索次 數(shù)為關(guān)鍵字總數(shù)/2 ，由于索引文件比主文件小（通常小一個(gè)數(shù)量級(jí)， 可以全部或大部分 讀入內(nèi)存，在內(nèi)存中搜索定位，從而提高了速度。可以比喻為小無(wú)序管大有序。 例 一本書的目錄可看成是無(wú)序索引映射 IndexMap : 章節(jié)名稱集合 頁(yè)碼集合。 由于目錄相對(duì)較小，易于一目十行地瀏覽，加快了檢索內(nèi)容的速度。 數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-38/1312. 無(wú)序索引 索引映射 IndexMap：關(guān)鍵字 - 記錄號(hào) ，而索引文件不排序。平均搜索次 數(shù)為關(guān)鍵字總數(shù)/2 ，由于索引文件

6、比主文件小（通常小一個(gè)數(shù)量級(jí)， 可以全部或大部分 讀入內(nèi)存，在內(nèi)存中搜索定位，從而提高了速度?？梢员扔鳛樾o(wú)序管大有序。 例 一本書的目錄書的目錄可看成是無(wú)序索引映射 IndexMap : 章節(jié)名稱集合 頁(yè)碼集合。 。 由于目錄相對(duì)較小，由于目錄相對(duì)較小，易于一目十行地易于一目十行地瀏覽瀏覽，加快了檢索內(nèi)容的速度，加快了檢索內(nèi)容的速度數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-39/1313. 順序索引（Sequential Index) 在無(wú)序索引的基礎(chǔ)上作如下改進(jìn)：將索引文件排序后保存，因而在索引文件中搜索關(guān)鍵字可以用二分法，計(jì)算復(fù)雜度為 Log2（N ），當(dāng)N 30 時(shí)，就有顯著效益。順序索引 又分為兩類：

7、 “小有序管大有序” 和 “小有序管大無(wú)序”。 數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-310/1314.稀索引 是小有序管大有序的改進(jìn)型。既然索引文件和主文件都是排序的。那么，隔 N抽 一而建立起來(lái)的索引集合就縮小到原來(lái)的 1/N，其定位誤差小于N ，然后在N 個(gè)項(xiàng)中線性搜索。 例 英漢字典中的眉索引，再每頁(yè)頂上列出當(dāng)頁(yè)的始詞和尾詞，組成了高效的，節(jié)省空間的稀索引。 數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-311/131例 在1971年版的新華字典中查“飛”字，利用了“ 部首檢字”和“檢字表”兩級(jí) 索引，因而能在正文中迅速查出釋義，如圖5.1所示。 部首檢字 - 檢字表第15頁(yè) - 正文111頁(yè) 乙 15fei飛：111一

8、劃 部首檢字 檢字表第15頁(yè) 正文111頁(yè) 密索引飛：鳥在空中的運(yùn)動(dòng)-稀索引（書眉）數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-312/131Indexing mechanisms used to speed up access to desired data. l E.g., author catalog in librarySearch Key - attribute to set of attributes used to look up records in a file.index filefile of index entries (search-key, pointer)Index files sm

9、aller than the original file （以小引大）Two basic kinds of indices:l Ordered indices: 順序索引順序索引l Hash indices: 散列索引 keys 分散散 列列入 “buckets”數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-313/131Access types supported efficiently. E.g., 有效支持類型l records with a specified value in the attributel or records with an attribute value falling in a sp

10、ecified range of values.Access time 查 時(shí)間 Insertion time 插 時(shí)間Deletion time 刪改 時(shí)間Space overhead 空間數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-314/131Basic Concepts 基本概念Ordered Indices 順序索引B+-Tree Index Files B-樹索引B-Tree Index Files B-樹文件Static Hashing 靜態(tài)散列Dynamic Hashing 動(dòng)態(tài)散列Comparison of Ordered Indexing and Hashing 比較Index Definit

11、ion in SQL SQL 中的索引Multiple-Key Access 多關(guān)鍵字存取數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-315/131In an ordered index, index entries are stored sorted on the search key value. E.g., author catalog in library. 1表可以有多個(gè)！Primary index(主索引主索引/聚集索引聚集索引): in a sequentially ordered file, the index whose search key specifies the sequential o

12、rder of the file. 使使文件記錄同其序Also called 聚集clustering index 1表僅能有1個(gè)！The search key of a primary index is usually (but not necessarily) the primary key.Secondary index(輔助索引輔助索引/非聚集索引非聚集索引): an index whose search key specifies an order different from the sequential order of the file. Also called non-clu

13、stering index.Index-sequential file(索引順序文件索引順序文件): ordered sequential file with a primary index. 即某個(gè)搜索碼上有主索引的記錄文件問題1答案數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-316/131索引索引有序有序，可用二分法，可用二分法(O(log(n) 比線性搜索比線性搜索O(n/2)快快Primary index: (Key, RecPos) , 有序文件，較小有序文件，較小Secondary index: (Key, RecPos . 類似一般書類似一般書書籍最后的索引書籍最后的索引non-clustering

14、 index. 小有序管大無(wú)序Index-sequential file: ordered sequential file with a primary index. 小有序管大有序數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-317/131Dense index Index record appears for every search-key value in the file. 每個(gè)搜索碼值都有一個(gè)索引項(xiàng)每個(gè)搜索碼值都有一個(gè)索引項(xiàng)索引項(xiàng)索引項(xiàng) 與與 記錄記錄 1-1 對(duì)應(yīng)對(duì)應(yīng)問題2答案數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-318/131Sparse Index: contains index records for onl

15、y some search-key values. 索引碼的部分值建立索引項(xiàng)Key Block 塊中 順序搜索，塊 可全裝入內(nèi)存新華字典 筆畫索引，1-多 眉索引 1 1頁(yè)，優(yōu)點(diǎn)，索引文件小，可全入內(nèi)存比密索引慢一點(diǎn) slower than dense index for locating records.Good tradeoff: Spacetime問題2答案數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-319/131例 在1971年版的新華字典中查“飛”字，利用了“ 部首檢字”和“檢字表”兩級(jí) 索引，因而能在正文中迅速查出釋義，如下圖 所示。 部首檢字 - 檢字表第15頁(yè) - 正文111頁(yè) 乙 15fei飛：

16、111一劃 部首檢字 檢字表第15頁(yè) 正文111頁(yè) 密索引 飛：鳥在空中的運(yùn)動(dòng)-稀索引（書眉）數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-320/131稀索引 Block數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-321/131Compared to dense indices:比較l Less space and less maintenance overhead for insertions and deletions.節(jié)省空間l Generally slower than dense index for locating records.慢一點(diǎn)Good tradeoff: sparse index with an index

17、entry for every block in file, corresponding to least search-key value in the block. 細(xì)節(jié)自己看書數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-322/131新華字典例子，筆畫索引 是 索引的索引的索引減小索引 以便全部入內(nèi)存 To reduce number of disk accesses to index records, treat primary index kept on disk as a sequential file and construct a sparse index on it.l outer index

18、a sparse index of primary indexl inner index the primary index filel 任務(wù)下達(dá)，層層傳遞，軍師團(tuán)營(yíng)l 索引 與時(shí)俱進(jìn)，查插刪改 Indices at all levels must be updated on insertion or deletion from the file.問題3答案數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-323/131新華字典例子，筆畫索引 是 索引的索引的索引減小索引 以便全部入內(nèi)存 To reduce number of disk accesses to index records, treat primary

19、index kept on disk as a sequential file and construct a sparse index on it.l outer index a sparse index of primary indexl inner index the primary index filel 任務(wù)下達(dá)，層層傳遞，軍任務(wù)下達(dá)，層層傳遞，軍師師團(tuán)團(tuán)營(yíng)營(yíng)l 索引索引 與時(shí)俱進(jìn)，查插刪改與時(shí)俱進(jìn)，查插刪改 Indices at all levels must be updated on insertion or deletion from the file.數(shù)據(jù)統(tǒng)系統(tǒng)2022-6

20、-324/131軍師團(tuán)營(yíng)數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-325/131主記錄和索引 ，主仆關(guān)系，索引為主文件服務(wù)。Single-level index insertion:l 密索引 Dense indices 插主插仆 if the search-key value does not appear in the index, insert it.l 稀索引 Sparse indices 加主塊（分裂），加索引l if index stores an entry for each block of the file, no change needs to be made to the index un

21、less a new block is created. In this case, the first search-key value appearing in the new block is inserted into the index.數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-326/131密索引 ：主刪 仆刪Single-level index deletion:l Dense indices deletion of search-key is similar to file record deletion.l 稀索引 Sparse indices l if an entry for the se

22、arch key exists in the index, it is deleted by replacing the entry in the index with the next search-key value in the file (in search-key order). If the next search-key value already has an index entry, the entry is deleted instead of being replaced.Multilevel insertion (as well as deletion) algorit

23、hms are simple extensions of the single-level algorithms主刪主刪 ，仆調(diào)整，仆調(diào)整多層，遞歸處理，下層的塊分裂，對(duì)應(yīng)上多層，遞歸處理，下層的塊分裂，對(duì)應(yīng)上層加一項(xiàng)層加一項(xiàng)問題4答案數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-327/131l Dense indices deletion of search-key:similar to file record deletion. Key對(duì)應(yīng)的最一個(gè)記錄被刪除時(shí)，刪掉它對(duì)應(yīng)的最一個(gè)記錄被刪除時(shí)，刪掉它 皮之不存，毛將焉附皮之不存，毛將焉附數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-328/131非關(guān)鍵字搜索 、記錄非順序排列 (

24、key, RecPos ） , 如書末索引 Key RecPosl Example 2: as above, but where we want to find all accounts with a specified balance or range of balancesWe can have a secondary index with an index record for each search-key value; index record points to a bucket that contains pointers to all the actual records wi

25、th that particular search-key value.問題5答案數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-329/131 次索引（1 ：多）稠密， 主稠密索引 1：1査余額700的賬戶 賬號(hào) 支行 余額數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-330/131次索引 必 密 Secondary indices have to be dense.Indices offer substantial benefits when searching for records.When a file is modified, every index on the file must be updated, Updating

26、indices imposes overhead on database modification.索引 與 主文件 同 與時(shí)俱進(jìn)主索引順序掃描 快 （因 按關(guān)鍵字 排序）Sequential scan using primary index is efficient, but a 次索引順序查找 慢 sequential scan using a secondary index is expensive l each record access may fetch a new block from disk數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-331/131Basic Concepts 基本概念Order

27、ed Indices 順序索引B+-Tree Index Files B-樹索引B-Tree Index Files B-樹文件Static Hashing 靜態(tài)散列Dynamic Hashing 動(dòng)態(tài)散列Comparison of Ordered Indexing and Hashing 比較Index Definition in SQL SQL 中的索引Multiple-Key Access 多關(guān)鍵字存取數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-332/131indexed-sequential files: 小有序 管 大有序順序索引的缺點(diǎn) ：索引變大 效率降低，溢出塊太多， 需要定期re-index B

28、+-tree 優(yōu)點(diǎn) ，平、 半、 序 在生長(zhǎng)中保持 平衡，裝載因子 過半 ，有序 自動(dòng)重組，局部更新 與時(shí)俱進(jìn)B+-tree的小缺點(diǎn) 結(jié)點(diǎn)分裂合并時(shí)的開銷大l 插入刪除時(shí)可能遞歸作幾次，裝載因子5075%l 利大于弊， 廣泛采用是多級(jí)索引的特例數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-333/131indexed-sequential files: 小有序 管 大有序順序索引的缺點(diǎn) ：索引變大 效率降低，溢出快太多， 需要定期re-index B+-tree 優(yōu)點(diǎn)優(yōu)點(diǎn) ，平、 半、 序 在生長(zhǎng)中保持 平衡，裝載因子 過半 ，有序 自動(dòng)重組，局部更新 與時(shí)俱進(jìn)B+-tree的小缺點(diǎn)的小缺點(diǎn) 結(jié)點(diǎn)分裂合并時(shí)的開銷大

29、l 插入刪除時(shí)可能遞歸作幾次，裝載因子5075%l 利大于弊， 廣泛采用問題6答案數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-334/131葉根距 一致 ，平衡性， All paths from root to leaf are of the same length裝載因子過半 Each node that is not a root or a leaf has between n/2 and n children.A leaf node has between (n1)/2 and n1 valuesSpecial cases: 特例l 根非葉，有2 子節(jié)點(diǎn)。簡(jiǎn)單l 只有一個(gè)節(jié)點(diǎn)時(shí)，根即葉，含 0 (n1) 個(gè)

30、值.l 注意Hbase中是B-樹， 不是B+樹，實(shí)現(xiàn)上容易一些B+-tree 是滿足下列條件的有根樹:問題7答案數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-335/131Typical nodel Ki are the search-key values l Pi are pointers to children (for non-leaf nodes) or pointers to records or buckets of records (for leaf nodes).The search-keys in a node are ordered K1 K2 K3 . . . Kn1 關(guān)鍵字排序關(guān)鍵字排序n

31、個(gè)指針個(gè)指針關(guān)鍵字 n-1 個(gè)數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-336/131For i = 1, 2, . . ., n1, pointer Pi either points to a file record with search-key value Ki, or to a bucket of pointers to file records, each record having search-key value Ki. Only need bucket structure if search-key does not form a primary key.If Li, Lj are leaf n

32、odes and i k.If such a value exists, assume it is Ki. Then set N = PiOtherwise k Kn1. Set N = Pn Until N is a leaf nodel If for some i, key Ki = k follow pointer Pi to the desired record or bucket. l Else no record with search-key value k exists.數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-344/131關(guān)于部隊(duì)編制的常識(shí) 來(lái)說明 B+-樹在插入或刪除時(shí)，節(jié)點(diǎn)的分裂與合并

33、以及B+樹高度的增減和根節(jié)點(diǎn)浮動(dòng)等遞歸過程。 部隊(duì)的編制。 葉節(jié)點(diǎn)為連隊(duì)。 三三制一 個(gè)團(tuán)至多三個(gè)營(yíng)，至少二個(gè)營(yíng)，一個(gè)營(yíng)應(yīng)至多三個(gè)連，至少二個(gè)連， 表示缺編的空白位置。 在 (a)中，根節(jié)點(diǎn)為團(tuán)級(jí)，葉節(jié)點(diǎn)為連級(jí)。以部隊(duì)番號(hào)（即層次序列碼）為關(guān)鍵字， 例如， 1團(tuán)2營(yíng)4連 （理解為字符串） 數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-345/131 連 ( a ) (b). 增加第9 、10連后 圖5.3 一個(gè)編制樹, 后面解釋1 2 3 4 5 6 7 8 .1 2 34 5 6 7 89 101 團(tuán)1 師1 團(tuán)2 團(tuán)4營(yíng)3營(yíng)2營(yíng)1 營(yíng)3營(yíng)2營(yíng)1營(yíng)數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-346/131易知，上述的編制樹摹擬了B+

34、-樹三大特點(diǎn)（平衡性，過半性，順序性）。 1.搜索 查找關(guān)鍵字 k=1團(tuán) 2 營(yíng) 4 連的項(xiàng)。按字典序比較關(guān)鍵字，利用順序性， (1) 按字典序， 2團(tuán) K 1 團(tuán)，搜索以1 團(tuán)為根的子樹 ； (2) 因 1團(tuán)2營(yíng) K 1團(tuán)3營(yíng)，問題遞歸地化為搜索以 1團(tuán)2營(yíng)為根的子樹； (3) 該子樹為葉節(jié)點(diǎn)，通過二分法（二次）查得第一索引項(xiàng)為所求。 1 2 34 5 67 8 .1 團(tuán)3營(yíng)2營(yíng)1營(yíng)數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-347/131易知，上述的編制樹摹擬了B-樹三大特點(diǎn)（平衡性，過半性，順序性）。 1.搜索 查找關(guān)鍵字 k=1團(tuán) 2 營(yíng) 4 連的項(xiàng)。按字典序比較關(guān)鍵字，利用順序性， (1) 按字典序，

35、2團(tuán) K 1 團(tuán)，搜索以1 團(tuán)為根的子樹 ； (2) 因 1團(tuán)2營(yíng) K 1團(tuán)3營(yíng)，問題遞歸地化為搜索以 1團(tuán)2營(yíng)為根的子樹； (3) 該子樹為葉節(jié)點(diǎn)，通過二分法（二次）查得第一索引項(xiàng)為所求。 1 2 34 5 67 8 .1 團(tuán)3營(yíng)2營(yíng)1營(yíng)數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-348/131給定關(guān)鍵字 search-key，求記錄號(hào)（或記錄指針）.l 從根起, l 如果 search-key 結(jié)點(diǎn)中最大Key,沿最右子樹搜索l 否則 搜索 Kj=Min( k | K search-key)，必存在l 則 以Pi為子樹根，遞歸 查找l 最后到葉結(jié)點(diǎn) l 如存在 i, Ki = k ，沿指針 Pi 到主文件中目

36、標(biāo)桶l(fā) 否則 搜索目標(biāo)不存在數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-349/1312.不發(fā)生節(jié)點(diǎn)分裂的插入不發(fā)生節(jié)點(diǎn)分裂的插入 插入 關(guān)鍵字 K= 1團(tuán)3營(yíng)9連 的索引項(xiàng)。先搜索K 所在項(xiàng)，得到其位置在 處,現(xiàn)為空白，填入 K=9即可。3. 發(fā)生節(jié)點(diǎn)分裂的插入 再插入 K= 1團(tuán)3營(yíng)10連 的索引項(xiàng)。按關(guān)鍵字搜索，似應(yīng)插入到 1團(tuán)3營(yíng)9連 右方。但如此 則 3營(yíng)有 4個(gè)連，超編 1 2 34 5 67 8 .1 團(tuán)3營(yíng)2營(yíng)1營(yíng)問題9答案數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-350/1312.不發(fā)生節(jié)點(diǎn)分裂的插入不發(fā)生節(jié)點(diǎn)分裂的插入 插入 關(guān)鍵字 K= 1團(tuán)3營(yíng)9連 的索引項(xiàng)。先搜索K 所在項(xiàng)，得到其位置在 處,現(xiàn)為空白，填

37、入 K=9即可。3. 發(fā)生節(jié)點(diǎn)分裂的插入 再插入 K= 1團(tuán)3營(yíng)10連 的索引項(xiàng)。按關(guān)鍵字搜索，似應(yīng)插入到 1團(tuán)3營(yíng)9連 右方。但如此 則 3營(yíng)有 4個(gè)連，1 2 34 5 67 8 .1 團(tuán)3營(yíng)2營(yíng)1營(yíng)超編數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-351/131分裂節(jié)點(diǎn)如下： 從3 營(yíng)中分出 9、10連作為第4 營(yíng)。問題遞歸到上一層次，即增加第4 營(yíng)，于是1 團(tuán)中有4 個(gè)營(yíng)，超編。分為1 團(tuán)、2 團(tuán)新設(shè)一個(gè)師作為根節(jié)點(diǎn)。結(jié)果如 圖 ,1 2 34 5 67 89 101 師1 團(tuán)2 團(tuán)4營(yíng)3營(yíng)2營(yíng)1 營(yíng)此師戰(zhàn)斗實(shí)力甚 虛 數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-352/131分裂節(jié)點(diǎn)如下： 從3 營(yíng)中分出 9、10連作為第4

38、 營(yíng)。問題遞歸到上一層次，即增加第4 營(yíng)，于是1 團(tuán)中有4 個(gè)營(yíng)，超編。分為1 團(tuán)、2 團(tuán)新設(shè)一個(gè)師作為根節(jié)點(diǎn)。結(jié)果如 圖 ,1 2 34 5 67 89 101 師1 團(tuán)2 團(tuán)4營(yíng)3營(yíng)2營(yíng)1 營(yíng)數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-353/131當(dāng)從(b) 中刪除10連后，4 營(yíng)缺編，4營(yíng)與3營(yíng)合并，從而造2團(tuán)缺編，2團(tuán)與1團(tuán)合并， 于是1 師缺編，從而取1師編制。結(jié)果相當(dāng)于在圖5.3 (a)中增加了第9連。 1 2 34 5 67 8 91 團(tuán)3營(yíng)2營(yíng)1營(yíng)數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-354/131在上面結(jié)果中再刪除1團(tuán)3營(yíng)9連，搜索到位后，改9 連為空白。結(jié)果如圖5 3(a)所示 以上 遞歸過程的 思路和大

39、方向。下面講 合并與合并與 分裂時(shí)分裂時(shí) 索引項(xiàng)升索引項(xiàng)升降，重新安排降，重新安排 等技術(shù)細(xì)節(jié)。 1 2 34 5 67 8 1 團(tuán)3營(yíng)2營(yíng)1營(yíng)數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-355/131在上面的部隊(duì)編制例子中，為了借助于常識(shí)，采用了三三制。一個(gè)節(jié)點(diǎn)的最大子節(jié)點(diǎn)數(shù)為奇數(shù)。 但是實(shí)用中，如在HBASE中（及其它 一些 實(shí)際DBMS ）規(guī)定一個(gè)節(jié)點(diǎn)上允許的最多索引項(xiàng)數(shù)為偶數(shù)偶數(shù)偶數(shù) 好計(jì)算好計(jì)算 半節(jié)點(diǎn)（移位）半節(jié)點(diǎn)（移位）數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-356/131為了使例子簡(jiǎn)單、原理清楚，下面假定：B+-樹的一個(gè)節(jié)點(diǎn)上最多四項(xiàng)，最少兩項(xiàng)。相當(dāng)于一個(gè)非根節(jié)點(diǎn)的團(tuán)最多5個(gè)營(yíng)（節(jié)點(diǎn)上四個(gè)，節(jié)點(diǎn)再帶一個(gè)左邊兒子）

40、，最少2個(gè)營(yíng)。 數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-357/1316. 節(jié)點(diǎn)分裂時(shí)中項(xiàng)晉級(jí)，節(jié)點(diǎn)數(shù)增加，根節(jié)點(diǎn)可能浮動(dòng) k1 n1.k2 n2.k3 n3.k4 n4 k3 n3k1 n1.k2 n2.K4 n4.k5 n5插入(k5,n5) 后, 節(jié)點(diǎn)分裂, 中項(xiàng) (k3, n3) 升為父項(xiàng) （保持順序性）數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-358/131上頁(yè)，上一層次為空， (k3,n3)成為新的根節(jié)點(diǎn)，且其中只有一個(gè)索引項(xiàng)，這就是為什么 根點(diǎn)裝載率可以不過半的原因。 由此可見，在插入索引項(xiàng)時(shí)，節(jié)點(diǎn)數(shù)可能增加，根節(jié)點(diǎn)可能浮動(dòng)。節(jié)點(diǎn)數(shù)可能增加，根節(jié)點(diǎn)可能浮動(dòng)。 數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-359/131從圖 中刪去(k

41、5,n5)，其所在的結(jié)點(diǎn)非根節(jié)點(diǎn)且項(xiàng)數(shù)不過半，因而缺編。問題“反映”到上一級(jí),（在程序中為遞歸和回溯）需在以(k3, n3)為根的子樹中來(lái)處 理缺編問題，向左第或右兄借,(要維持過半性和順序性)。 但此例中借不出，上級(jí)節(jié)點(diǎn)中的(k3,n3)項(xiàng)“因損失部屬因損失部屬而引咎辭職，下放以充實(shí)基層而引咎辭職，下放以充實(shí)基層”。 k3 n3k1 n1.k2 n2.K4 n4.k5 n5數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-360/131“刪除操作后，刪除操作后，B+樹中內(nèi)節(jié)點(diǎn)的樹中內(nèi)節(jié)點(diǎn)的Key值，值， 可能在葉節(jié)點(diǎn)上不可能在葉節(jié)點(diǎn)上不存在存在”。 這是實(shí)現(xiàn)時(shí)，廠商的策略這是實(shí)現(xiàn)時(shí)，廠商的策略。 內(nèi)節(jié)點(diǎn)上Key作分水

42、嶺值， 目的是 能分出左右邊 如果加一道函數(shù)： check ( ) if (內(nèi)節(jié)點(diǎn)的內(nèi)節(jié)點(diǎn)的Key1值，不出現(xiàn)在葉節(jié)點(diǎn)上）值，不出現(xiàn)在葉節(jié)點(diǎn)上） 把把Key1 換成有子樹中換成有子樹中 葉上最小葉上最小Key 有些開發(fā)商認(rèn)為，這道程序不調(diào)用也不會(huì)出錯(cuò)， 還可以省時(shí)間。所以出現(xiàn)了這種情況。 B+樹強(qiáng)調(diào)樹強(qiáng)調(diào) 節(jié)省空間，中間節(jié)點(diǎn)節(jié)省空間，中間節(jié)點(diǎn) 完全不出現(xiàn)在葉節(jié)點(diǎn)上完全不出現(xiàn)在葉節(jié)點(diǎn)上。數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-361/131一般，一個(gè)大數(shù)據(jù)庫(kù)（100G) 的索引 (2-10G) 不能全部進(jìn)入內(nèi)存，駐留磁盤。 因此檢索瓶頸是 讀寫盤塊數(shù)（大約是B+-樹的高度，大約為關(guān)鍵字總數(shù)的對(duì)數(shù)， 下面分析數(shù)據(jù)

43、統(tǒng)系統(tǒng)2022-6-362/131給定一個(gè)查詢 ，產(chǎn)生 一條從根到某個(gè)葉的路徑如果總的關(guān)鍵字為 K 個(gè)，每個(gè)結(jié)點(diǎn)上至少（n/2)項(xiàng)，則路徑長(zhǎng)度則路徑長(zhǎng)度 或樹高或樹高 HT= logn/2(K). （下頁(yè)證明）一般結(jié)點(diǎn)大小512b 4 kb , n =128 ( 半個(gè)結(jié)點(diǎn)裝的項(xiàng)數(shù)）當(dāng) 100 萬(wàn) 記錄 n = 100, 最多l(xiāng)og50(1,000,000) = 4 個(gè)結(jié)點(diǎn)從磁盤讀到內(nèi)存 用二分法搜索，可能讀20個(gè)結(jié)點(diǎn)（220=10242 100萬(wàn)每讀一個(gè)磁盤塊大約 20 毫秒數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-363/131 設(shè)m= n/22層 m2 項(xiàng)3層 m3 項(xiàng)p層 mp項(xiàng)如果總的關(guān)鍵字為如果總的關(guān)

44、鍵字為 K 個(gè)個(gè),部分小于全量部分小于全量葉節(jié)點(diǎn)數(shù)量 mpK , 路徑長(zhǎng)度(樹高 Hight)，即讀塊數(shù) HT = plogm(K) . . .數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-364/131前面已經(jīng)講過，1 . 先搜索 待插入項(xiàng)應(yīng)該 出現(xiàn) 的葉結(jié)點(diǎn)2 如果找到了，則不重復(fù)，不再插入，否則插入，3 如果超編。分裂結(jié)點(diǎn)，遞歸我們已經(jīng)通過補(bǔ)充的例子解釋了思想，后面幾個(gè)頁(yè)面留作自學(xué)數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-365/131Splitting a node:分裂結(jié)點(diǎn)， 一分為二，中項(xiàng)晉升Result of splitting node containing Brighton and Downtown on inse

45、rting Clearview數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-366/131B+-Tree before and after insertion of “Clearview”新插入項(xiàng)目數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-367/131Before and after deleting “Downtown” cp253數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-368/131Deletion of “Perryridge” from result of previous example 導(dǎo)致根結(jié)點(diǎn) ，缺編， 被取消數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-369/131underfull,缺編 向左兄借，其孫子跟著轉(zhuǎn)戶口Before and after

46、 deletion of “Perryridge” from earlier example數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-370/131傳統(tǒng)索引文件用 一段時(shí)間，性能退化（ degradation）.但B+-樹在生長(zhǎng)中保持 “平、 半、 序”把主記錄存在B+-樹葉結(jié)點(diǎn)中，主索合一 數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-371/131葉節(jié)點(diǎn)中存主記錄 優(yōu)點(diǎn) 節(jié)省一些空間缺點(diǎn) 當(dāng)葉節(jié)點(diǎn)分類合并時(shí)，代價(jià)大 （輔助索引解決 參見 CP334）Example of B+-tree File Organization3/2n數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-372/131Variable length strings as keys

47、實(shí)踐中， 關(guān)鍵字是變長(zhǎng)串l Variable fanoutl Use space utilization as criterion for splitting, not number of pointersPrefix compression 可壓縮可壓縮 節(jié)省存儲(chǔ)空間節(jié)省存儲(chǔ)空間l Key values at internal nodes can be prefixes of full keyKeep enough characters to distinguish entries in the subtrees separated by the key valueE.g. “Silas”

48、and “Silberschatz” can be separated by “Silb”l Keys in leaf node can be compressed by sharing common prefixes數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-373/131類似B+.但項(xiàng)目在樹中出現(xiàn)一次，節(jié)約空間非頁(yè)結(jié)點(diǎn)中，頭尾都是指針，指針比項(xiàng)目多一個(gè)關(guān)鍵字通常預(yù)留56字節(jié)，多的一個(gè)指針 節(jié)省一個(gè)關(guān)鍵字空間Nonleaf node pointers Bi are the bucket or file record pointers.數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-374/131B樹 算法復(fù)雜一些， 為了節(jié)約空間， 隨

49、機(jī)訪問 速度并不慢 順序訪問 比B+樹慢 （B+樹 可以簡(jiǎn)單順序搜索葉節(jié)點(diǎn)） 如移動(dòng)設(shè)備上， 用B樹 節(jié)約空間 是可行的 數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-375/131B-tree (above) and B+-tree (below) on same dataB+，3層B樹 2層數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-376/131Advantages of B-Tree indices:l 比 B+-Tree 結(jié)點(diǎn)少，不到葉 ，也可以找到一些指針.Disadvantages of B-Tree indices:l 提前找到的只是一小部分（非葉結(jié)點(diǎn)只有 1/(2*n) )l 非葉結(jié)點(diǎn)占內(nèi)存多，項(xiàng)目數(shù)少一些，層數(shù)多一

50、些插入刪除復(fù)雜一點(diǎn)l 實(shí)現(xiàn)難一點(diǎn)l Typically, advantages of B-Trees do not out weigh disadvantages. 與B+相比，弊大于利數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-377/131用合成關(guān)鍵字 快用兩個(gè)單個(gè)的關(guān)鍵字. 較快效率 與次序有關(guān)，如where branch-name = “Perryridge” and balance 1000較快where branch-name “Perryridge” and balance = 1000慢， 這里的結(jié)果是較大集合數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-378/131 多個(gè)單碼索引： 如 “姓名” 建一個(gè)縮影， “年齡” 建一個(gè)索引多碼縮影 如 KeyStr= “姓名”+ “年齡” , 建一個(gè)索引數(shù)據(jù)統(tǒng)系統(tǒng)2022-6-379/131 With the where clause where branch_name = “Perryridge” and balance = 1000the index on (branch_name, balance) can be used to fetch only records that satisfy both conditions.Using separate indices in less efficient we may fetch many reco