九章资料储存结构.pptVIP

Copyright 黃三益 2003 資料庫核心理論與實務 第九章 資料儲存結構 資料庫裡資料的儲存特性 資料表的資料結構 B+-tree的索引結構 二元樹 B+-tree的索引結構 B+-tree的搜尋 B+-tree的索引結構大小 記錄增刪 Suffix tree 資料庫裡資料的儲存特性 DBMS所管理的資料量一般相當的龐大，必須存在硬碟 硬碟的存取單位是硬碟頁 硬碟的存取方式如下： 練習9-1： 請問上頁圖中，(1)、(2)，和（3）那個動作最快？ Ans: 由於(1)和(3)都是主記憶體與硬碟交換資料，速度 較慢。（2）則是CPU處理主記憶體裡的資料，速度最快 資料表的資料結構 一個資料表是由數個資料頁所構成 一個資料頁又包括數筆記錄 邏輯結構如右圖所示 資料表的資料結構（Cont.) 在硬碟裡，同一個資料表的資料頁在硬碟裡不一定連續 資料頁的順序關係是用鍊結（Linked list）來表達 資料頁裡的記錄也不一定連續儲存 DBMS系統裡也記載每一個資料表的第一個資料頁的頁數和各個屬性的順序和型態，稱為資料字典 資料字典也可存成資料表 資料表的資料結構（Cont.) 練習9-2 假設資料字典已被載入主記憶體，但Product的資料頁還沒被載入。上例中若想取得’v01888’的產品資料，請描述其處理動作。此時共需載入幾個資料頁？ Ans: 檢查資料字典後，先載入Product資料表的第一頁（P3），再載入第二頁（P15），即發現所要的資料。所以共載入二個資料頁 B+-tree索引結構 要找出滿足某個條件的所有記錄，可以對相關資料表的所有資料頁一個一個的順序找尋 效率可能很差 索引結構是用來將某些屬性的屬性值組織起來，以便快速找出滿足這些屬性的條件之記錄 最普遍的索引結構為B+-tree B+-tree的基本概念是由二元樹而來 傳統二元樹 節點 根節點 葉節點 子樹 左子樹 右子樹 傳統二元樹（Cont.) 不適合資料庫使用 存在主記憶體裡 不是一棵平衡樹 沒有存記錄的指標值 資料庫的索引結構應具有以下特性 每一個節點就是硬碟裡的一頁 一個節點裡要包括多個索引值，指標 該樹狀結構必須是平衡的。 空間的利用率不能太低 B+-tree索引結構（Cont.) B+-tree 的結構包含兩種節點： 中間節點：包括多個索引值和節點指標值 葉節點：包含多個屬性值, 記錄指標值，再加上一個指標值指到下一個葉節點 除了根節點外，每一個節點的空間利用率至少為50% 搜尋方式類似二元樹 範例（結構如下頁） CREATE INDEX I1 ON Product(unitPrice); B+-tree的搜尋 類似二元樹，但每一個節點可能必須檢視多個索引值 範例 SELECT * FROM Product WHERE unitPrice=550; 按上圖，共檢視了4個硬碟頁 3個索引頁（n1, n3, n8） 1個資料頁（p15） B+-tree的搜尋（Cont.) B+-tree也可用來做範圍條件的搜尋。考慮以下的SQL指令： SELECT * FROM Product WHERE unitPrice BETWEEN 400 AND 550; 在圖9-6裡，共需搜尋索引頁有n1, n2, n5, n6, n7, n8共6個，資料頁則有p9, p15, 和p3共3個。所以共需抓取9個硬碟頁 B+-tree的搜尋（Cont.) 練習9-4：考慮以下SQL查詢句： SELECT * FROM Product WHERE unitPrice = 700; 請問，若系統已有一個索引結構如圖9-6，要執行以上查詢，共需造訪幾個硬碟頁（包括索引頁和資料頁）？ Ans: 索引頁會造訪n1, n3和n9，資料頁則造訪p9。所以共造訪四個硬碟頁 B+-tree索引結構的大小 假設： 一個硬碟頁有4KB容量。 一個索引值（屬性值）佔20B 一個節點指標佔8B 一個記錄指標佔10B 每一中間節點可容納p個節點指標及p-1個索引值 (p×8) + ((p-1) × 20) ≦ 4K p ≦147, p=74 每一葉節點可容納Pleaf個記錄指標加上屬性值, 再加上一個節點指標指到下一個鄰接的葉節點 (Pleaf ×(10 +20)) + 8 ≦ 4K Pleaf≦136, pleaf=68 每一節點的空間利用率至少一半 三層B+-tree範例 練習9-3 有些研究已經證明B+-tree的每一節點平均利用率為69%，請據此計算在以上範例裡，一個三層的B+-tree平均可容納幾個記錄指標 Ans: 每一個中間節點平均有147×0.69 = 101個節點指標 每一個葉節點平均有136×0.69 =93 個記