第九章资料储存结构

第九章资料储存结构内容摘要：

p9,2 )(550 , p15,4 ) (600 ,p3,4)(700 , p9,1 ) ...........(500 ,p3,2) (500 ,p3,1).(450 ,p15,2 )(450 ,p15,1).(300 ,p3,3) (350 ,p15,3).黃三益 2020 資料庫的核心理論與實務第三版 913 B+tree的搜尋  類似二元樹，但每一個節點可能必須檢視多個索引值  範例 SELECT * FROM Product WHERE unitPrice=550。  按 上圖 ，共檢視了 4個硬碟頁  3個索引頁（ n1, n3, n8）  1個資料頁（ p15） 黃三益 2020 資料庫的核心理論與實務第三版 914 B+tree的搜尋（ Cont.)  B+tree也可用來做範圍條件的搜尋。 考慮以下的 SQL指令： SELECT * FROM Product WHERE unitPrice BETWEEN 400 AND 550。  在 圖 96裡，共需搜尋索引頁有 n1, n2, n5, n6, n7, n8共 6個，資料頁則有 p9, p15, 和 p3共 3個。 所以共需抓取 9個硬碟頁 黃三益 2020 資料庫的核心理論與實務第三版 915 B+tree的搜尋（ Cont.)  練習 94：考慮以下 SQL查詢句： SELECT * FROM Product WHERE unitPrice = 700。  請問，若系統已有一個索引結構如 圖 96，要執行以上查詢，共需造訪幾個硬碟頁（包括索引頁和資料頁）。  Ans: 索引頁會造訪 n1, n3和 n9，資料頁則造訪 p9。 所以共造訪四個硬碟頁 黃三益 2020 資料庫的核心理論與實務第三版 916 B+tree索引結構的大小  假設：  一個硬碟頁有 4KB容量。  一個索引值（屬性值）佔 20B  一個節點指標佔 8B  一個記錄指標佔 10B  每一中間節點可容納 p個節點指標及 p1個索引值  (p8) + ((p1) 20) ≦ 4K  p ≦ 147, p=74  每一葉節點可容納 Pleaf個記錄指標加上屬性值 , 再加上一個節點指標指到下一個鄰接的葉節點  (Pleaf (10 +20)) + 8 ≦ 4K  Pleaf≦ 136, pleaf=68  每一節點的空間利用率至少一半  三層 B+tree範例 第一層中間節點 1 74 節點指標 第二層中間節點 74 7474=5476節點指標 第三層葉節點 5476 547668=372,368 記錄指標 B+tree是一顆 非常扁平 的樹 黃三益 2020 資料庫的核心理論與實務第三版 917 練習 93  有些研究已經證明 B+tree的每一節點平均利用率為69%，請據此計算在以上範例裡，一個三層的 B+tree平均可容納幾個記錄指標  Ans: 每一個中間節點平均有 147 = 101個節點指標 每一個葉節點平均有 136 =93 個記錄指標。 對於三層的 B+tree，我們可以計算如下： 總節點數 總指標數 第一層中間節點 1 101 節點指標 第二層中間節點 101 101101=10201節點指標 第三層葉節點 10201 1020193=948,693 記錄指標 黃三益 2020 資料庫的核心理論與實務第三版 918 多屬性值索引的 B+tree  B+tree也可用於多屬性索引的建立 CREATE INDEX I2 ON Product(catalog ASC, unitPrice DESC)。  葉節點裡是按照 catalog欄位值由小排到大，而同一 catalog欄位值的記錄則又按其 unitPrice欄位值由大排到小  中間節點裡的索引值也是按照這樣的次序排列  範例結構如下頁圖 黃三益 2020 資料庫的核心理論與實務第三版 919 多屬性值索引的 B+tree（ Cont.) n1n2n3n5n6n9n8n4n7( 39。 Book39。 , 550, . ) .( 39。 B o o k 39。 , 7 0 0 , . ) ( 39。 B o o k 39。 , 6 0 0 , . ) .( 39。 C D 39。 , 4 5 0 , . ) ( 39。 C D 39。 , 3 5 0 , . ).( 39。 C D 39。 , 3 0 0 , . ) ( 39。 D V D 39。 , 4 5 0 , . ).( 39。 D V D 39。