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