资源描述
按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,*,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,資料庫的核心理論與實務第三版,9-,*,第九章 資料儲存結構,資料庫裡資料的儲存特性,資料表的資料結構,B,+,-tree的索引結構,二元樹,B+-tree的索引結構,B,+,-tree的搜尋,B,+,-tree的索引結構大小,記錄增刪,Suffix tree,1,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,第九章 資料儲存結構資料庫裡資料的儲存特性1Copyrigh,資料庫裡資料的儲存特性,DBMS所管理的資料量一般相當的龐大，必須存在硬碟,硬碟的存取單位是硬碟頁,硬碟的存取方式如下：,2,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,資料庫裡資料的儲存特性 DBMS所管理的資料量一般相當的龐大,練習9-1：,請問上頁圖中，(1)、(2)，和（3）那個動作最快？,Ans:,由於(1)和(3)都是主記憶體與硬碟交換資料，速度,較慢。（2）則是CPU處理主記憶體裡的資料，速度最快,3,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,練習9-1：請問上頁圖中，(1)、(2)，和（3）那個動作最,資料表的資料結構,一個資料表是由數個資料頁所構成,一個資料頁又包括數筆記錄,邏輯結構如右圖所示,4,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,資料表的資料結構 一個資料表是由數個資料頁所構成4Copyr,資料表的資料結構（Cont.),在硬碟裡，同一個資料表的資料頁在硬碟裡不一定連續,資料頁的順序關係是用鍊結（Linked list）來表達,資料頁裡的記錄也不一定連續儲存,DBMS系統裡也記載每一個資料表的第一個資料頁的頁數和各個屬性的順序和型態，稱為資料字典,資料字典也可存成資料表,5,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,資料表的資料結構（Cont.)在硬碟裡，同一個資料表的資料頁,資料表的資料結構（Cont.),6,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,資料表的資料結構（Cont.)6Copyright 黃三益,練習9-2,假設資料字典已被載入主記憶體，但Product的資料頁還沒被載入。,上例,中若想取得v01888的產品資料，請描述其處理動作。此時共需載入幾個資料頁？,Ans:,檢查資料字典後，先載入Product資料表的第一頁（P3），再載入第二頁（P15），即發現所要的資料。所以共載入二個資料頁,7,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,練習9-2假設資料字典已被載入主記憶體，但Product的資,B+-tree索引結構,要找出滿足某個條件的所有記錄，可以對相關資料表的所有資料頁一個一個的順序找尋,效率可能很差,索引結構是用來將某些屬性的屬性值組織起來，以便快速找出滿足這些屬性的條件之記錄,最普遍的索引結構為B,+,-tree,B,+,-tree的基本概念是由二元樹而來,8,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,B+-tree索引結構 要找出滿足某個條件的所有記錄，可以對,傳統二元樹,節點,根節點,葉節點,子樹,左子樹,右子樹,9,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,傳統二元樹節點9Copyright 黃三益 2003 資料,傳統二元樹（Cont.),不適合資料庫使用,存在主記憶體裡,不是一棵平衡樹,沒有存記錄的指標值,資料庫的索引結構應具有以下特性,每一個節點就是硬碟裡的一頁,一個節點裡要包括多個,該樹狀結構必須是平衡的。,空間的利用率不能太低,10,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,傳統二元樹（Cont.)不適合資料庫使用10Copyrigh,B,+,-tree索引結構（Cont.),B,+,-tree 的結構包含兩種節點：,中間節點：包括多個索引值和節點指標值,葉節點：包含多個，再加上一個指標值指到下一個葉節點,除了根節點外，每一個節點的空間利用率至少為50%,搜尋方式類似二元樹,範例（結構如下頁）,CREATE INDEX I1,ON Product(unitPrice);,11,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,B+-tree索引結構（Cont.)B+-tree 的結構包,12,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,12Copyright 黃三益 2003 資料庫核心理論與,B,+,-tree的搜尋,類似二元樹，但每一個節點可能必須檢視多個索引值,範例,SELECT,*,FROM,Product,WHERE,unitPrice=550;,按,上圖,，共檢視了4個硬碟頁,3個索引頁（n1,n3,n8）,1個資料頁（p15）,13,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,B+-tree的搜尋類似二元樹，但每一個節點可能必須檢視多個,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個硬碟頁,14,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,B+-tree的搜尋（Cont.)B+-tree也可用來做範,B,+,-tree的搜尋（Cont.),練習9-4：考慮以下SQL查詢句：,SELECT*,FROM Product,WHERE unitPrice=700;,請問，若系統已有一個索引結構如,圖9-6,，要執行以上查詢，共需造訪幾個硬碟頁（包括索引頁和資料頁）？,Ans:,索引頁會造訪n1,n3和n9，資料頁則造訪p9。所以共造訪四個硬碟頁,15,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,B+-tree的搜尋（Cont.)練習9-4：考慮以下SQL,B,+,-tree索引結構的大小,假設：,一個硬碟頁有4KB容量。,一個索引值（屬性值）佔20B,一個節點指標佔8B,一個記錄指標佔10B,每一中間節點可容納p個節點指標及p-1個索引值,(p,8)+(p-1),20)4K,p 147,p=74,每一葉節點可容納P,leaf,個記錄指標加上屬性值,再加上一個節點指標指到下一個鄰接的葉節點,(P,leaf,(10+20)+8 4K,P,leaf,136,p,leaf,=68,每一節點的空間利用率至少一半,三層B,+,-tree範例,第一層中間節點,1,74 節點指標,第二層中間節點,74,7474=5476節點指標,第三層葉節點,5476,547668=372,368 記錄指標,B,+,-tree是一顆,非常扁平,的樹,16,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,B+-tree索引結構的大小假設：第一層中間節點174 節,練習9-3,有些研究已經證明B,+,-tree的每一節點平均利用率為69%，請據此計算在以上範例裡，一個三層的B+-tree平均可容納幾個記錄指標,Ans:,每一個中間節點平均有1470.69=101個節點指標,每一個葉節點平均有1360.69=93 個記錄指標。,對於三層的B+-tree，我們可以計算如下：,總節點數,總指標數,第一層中間節點,1,101 節點指標,第二層中間節點,101,101101=10201節點指標,第三層葉節點,10201,1020193=948,693 記錄指標,17,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,練習9-3有些研究已經證明B+-tree的每一節點平均利用率,多屬性值索引的B,+,-tree,B,+,-tree也可用於多屬性索引的建立,CREATE INDEX,I2,ON,Product(catalog,ASC,unitPrice,DESC,);,葉節點裡是按照catalog欄位值由小排到大，而同一catalog欄位值的記錄則又按其unitPrice欄位值由大排到小,中間節點裡的索引值也是按照這樣的次序排列,範例結構如下頁圖,18,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,多屬性值索引的B+-tree B+-tree也可用於多屬性索,多屬性值索引的B,+,-tree（Cont.),19,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,多屬性值索引的B+-tree（Cont.)19Copyrig,練習9-6,在,圖9-7,的索引裡，如果要搜尋所有250元的書，請問會經過哪些節點？,Ans:,要搜尋(Book,250)，先找n1,由於該索引裡unitPrice是由大排到小，而250 500，所以接下來找n3，由於pName是由小排到大且Book CD，所以接下來找n7。至此，可以發現沒有(Book,250)這筆記錄,20,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,練習9-6在圖9-7的索引裡，如果要搜尋所有250元的書，請,B,+,-tree的記錄增刪,B,+,-tree是一棵平衡樹，且每一節點具有至少50%的空間利用率,記錄的增刪必須有適當的處理,圖9-6,中，增加一筆記錄(假設是存在p9的第三筆記錄）：,(b40333,測試專用書1,380,Book),21,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,B+-tree的記錄增刪B+-tree是一棵平衡樹，且每一節,B+-tree的記錄增刪（Cont.),再增加一筆記錄：,(b40334,測試專用書2,330,Book),假設一個中間節點只能存2個索引值，以上中間節點n2裡存了過多的索引值，,必須切割，如下頁圖,22,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,B+-tree的記錄增刪（Cont.)再增加一筆記錄：假設一,B+-tree的記錄增刪（Cont.),23,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,B+-tree的記錄增刪（Cont.)23Copyright,B+-tree的記錄增刪（Cont.),刪除記錄,(b40333,測試專用書1,380,Book）,刪除unitPrice=350的記錄,24,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,B+-tree的記錄增刪（Cont.)刪除記錄刪除unitP,Suffix tree,前述B,+,-tree適用於搜尋整個屬性值的條件,相等值的查詢,屬性值位於一定範圍的查詢,SQL敘述裡對於字串欄位常用,LIKE,來搜尋,Suffix tree，可用來加快具有文字欄位匹配條件的查詢句之處理,比如以下的查詢句：,SELECT,*,FROM,Member,WHERE,address,LIKE,%中華路%;,25,Copyright 黃三益 2003 資料庫核心理論與實務,黃三益2007,Suffix tree 前述B+-tree適用於搜尋整個屬性,Suffix tree（,Cont.),Suffix tree是用來儲存一些字串的後段字串（Suffix）,“台北市中華路一段100號”的其後段字串包括,台北市中華路一段100號,北市中華路一段100號,市中華路一段100號,中華路一段100號,華
展开阅读全文