九章资料储存结构.ppt
《九章资料储存结构.ppt》由会员分享,可在线阅读,更多相关《九章资料储存结构.ppt(30页珍藏版)》请在三一文库上搜索。
1、黃三益2007 資料庫的核心理論與實務第三版,9-1,第九章 資料儲存結構,資料庫裡資料的儲存特性 資料表的資料結構 B+-tree的索引結構 二元樹 B+-tree的索引結構 B+-tree的搜尋 B+-tree的索引結構大小 記錄增刪 Suffix tree,黃三益2007 資料庫的核心理論與實務第三版,9-2,資料庫裡資料的儲存特性,DBMS所管理的資料量一般相當的龐大,必須存在硬碟 硬碟的存取單位是硬碟頁 硬碟的存取方式如下:,黃三益2007 資料庫的核心理論與實務第三版,9-3,練習9-1:,請問上頁圖中,(1)、(2),和(3)那個動作最快? Ans: 由於(1)和(3)都是主記憶
2、體與硬碟交換資料,速度 較慢。(2)則是CPU處理主記憶體裡的資料,速度最快,黃三益2007 資料庫的核心理論與實務第三版,9-4,資料表的資料結構,一個資料表是由數個資料頁所構成 一個資料頁又包括數筆記錄 邏輯結構如右圖所示,黃三益2007 資料庫的核心理論與實務第三版,9-5,資料表的資料結構(Cont.),在硬碟裡,同一個資料表的資料頁在硬碟裡不一定連續 資料頁的順序關係是用鍊結(Linked list)來表達 資料頁裡的記錄也不一定連續儲存 DBMS系統裡也記載每一個資料表的第一個資料頁的頁數和各個屬性的順序和型態,稱為資料字典 資料字典也可存成資料表,黃三益2007 資料庫的核心理論
3、與實務第三版,9-6,資料表的資料結構(Cont.),黃三益2007 資料庫的核心理論與實務第三版,9-7,練習9-2,假設資料字典已被載入主記憶體,但Product的資料頁還沒被載入。上例中若想取得v01888的產品資料,請描述其處理動作。此時共需載入幾個資料頁? Ans: 檢查資料字典後,先載入Product資料表的第一頁(P3),再載入第二頁(P15),即發現所要的資料。所以共載入二個資料頁,黃三益2007 資料庫的核心理論與實務第三版,9-8,B+-tree索引結構,要找出滿足某個條件的所有記錄,可以對相關資料表的所有資料頁一個一個的順序找尋 效率可能很差 索引結構是用來將某些屬性的屬
4、性值組織起來,以便快速找出滿足這些屬性的條件之記錄 最普遍的索引結構為B+-tree B+-tree的基本概念是由二元樹而來,黃三益2007 資料庫的核心理論與實務第三版,9-9,傳統二元樹,節點 根節點 葉節點 子樹 左子樹 右子樹,黃三益2007 資料庫的核心理論與實務第三版,9-10,傳統二元樹(Cont.),不適合資料庫使用 存在主記憶體裡 不是一棵平衡樹 沒有存記錄的指標值 資料庫的索引結構應具有以下特性 每一個節點就是硬碟裡的一頁 一個節點裡要包括多個 該樹狀結構必須是平衡的。 空間的利用率不能太低,黃三益2007 資料庫的核心理論與實務第三版,9-11,B+-tree索引結構(C
5、ont.),B+-tree 的結構包含兩種節點: 中間節點:包括多個索引值和節點指標值 葉節點:包含多個,再加上一個指標值指到下一個葉節點 除了根節點外,每一個節點的空間利用率至少為50% 搜尋方式類似二元樹 範例(結構如下頁) CREATE INDEX I1 ON Product(unitPrice);,黃三益2007 資料庫的核心理論與實務第三版,9-12,黃三益2007 資料庫的核心理論與實務第三版,9-13,B+-tree的搜尋,類似二元樹,但每一個節點可能必須檢視多個索引值 範例 SELECT * FROM Product WHERE unitPrice=550; 按上圖,共檢視了4
6、個硬碟頁 3個索引頁(n1, n3, n8) 1個資料頁(p15),黃三益2007 資料庫的核心理論與實務第三版,9-14,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個硬碟頁,黃三益2007 資料庫的核心理論與實務第三版,9-15,B+-tree的搜尋(Cont.),練習9-4:考慮以
7、下SQL查詢句: SELECT * FROM Product WHERE unitPrice = 700; 請問,若系統已有一個索引結構如圖9-6,要執行以上查詢,共需造訪幾個硬碟頁(包括索引頁和資料頁)? Ans: 索引頁會造訪n1, n3和n9,資料頁則造訪p9。所以共造訪四個硬碟頁,黃三益2007 資料庫的核心理論與實務第三版,9-16,B+-tree索引結構的大小,假設: 一個硬碟頁有4KB容量。 一個索引值(屬性值)佔20B 一個節點指標佔8B 一個記錄指標佔10B 每一中間節點可容納p個節點指標及p-1個索引值 (p8) + (p-1) 20) 4K p 147, p=74 每一葉
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 资料 储存 结构
链接地址:https://www.31doc.com/p-2552426.html