第九章資料儲(chǔ)存結(jié)構(gòu)-wenkub
2022-11-04 14:34:30 本頁面
【正文】 u n i t P r i c ec a t a l o gm I dp I dn a m e...1234....V A R C H A R ( 3 0 ). . . . . . . . . . .. . . . . . . . . . .C H A R ( 8 )..... . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .....C H A R ( 6 )123C H A R ( 1 0 ). . . . . . . . . . .?黃三益 2020 資料庫的核心理論與實(shí)務(wù)第三版 96 資料表的資料結(jié)構(gòu)（ Cont.) 資 料 表 P r o d u c t第 一 頁P(yáng) 3P 1 5P 91 59N U L L1 2 81 0 2 45 1 22 5 639。39。‘ d 2 0 7 7 7 , 蔡 依 林 … , 3 5 0 , C D ’‘ b 4 0 5 5 5 , 系 統(tǒng) 分 析 . . . , 5 5 0 , B o o k ’39。 39。 v 0 0 1 1 1 ,英 雄 , 4 0 0 , D V D 39。所以共載入二個(gè)資料頁 ?黃三益 2020 資料庫的核心理論與實(shí)務(wù)第三版 98 B+tree索引結(jié)構(gòu) ? 要找出滿足某個(gè)條件的所有記錄，可以對(duì)相關(guān)資料表的所有資料頁一個(gè)一個(gè)的順序找尋 ? 效率可能很差 ? 索引結(jié)構(gòu)是用來將某些屬性的屬性值組織起來，以便快速找出滿足這些屬性的條件之記錄 ? 最普遍的索引結(jié)構(gòu)為 B+tree ? B+tree的基本概念是由二元樹而來 ?黃三益 2020 資料庫的核心理論與實(shí)務(wù)第三版 99 傳統(tǒng)二元樹 ? 節(jié)點(diǎn) ? 根節(jié)點(diǎn) ? 葉節(jié)點(diǎn) ? 子樹 ? 左子樹 ? 右子樹 2010 30256 17121 19 27n1n2 n3n5 n6n9 n10n8n4n7?黃三益 2020 資料庫的核心理論與實(shí)務(wù)第三版 910 傳統(tǒng)二元樹（ Cont.) ? 不適合資料庫使用 ? 存在主記憶體裡 ? 不是一棵平衡樹 ? 沒有存記錄的指標(biāo)值 ? 資料庫的索引結(jié)構(gòu)應(yīng)具有以下特性 ? 每一個(gè)節(jié)點(diǎn)就是硬碟裡的一頁 ? 一個(gè)節(jié)點(diǎn)裡要包括多個(gè) 索引值，指標(biāo) ? 該樹狀結(jié)構(gòu)必須是平衡的。39。39。39。39。 v 0 0 1 1 1 ,英 雄 , 4 0 0 , D V D 39。 ? 在 圖 96裡，共需搜尋索引頁有 n1, n2, n5, n6, n7, n8共 6個(gè)，資料頁則有 p9, p15, 和 p3共 3個(gè)。 ? 一個(gè)索引值（屬性值）佔(zhàn) 20B ? 一個(gè)節(jié)點(diǎn)指標(biāo)佔(zhàn) 8B ? 一個(gè)記錄指標(biāo)佔(zhàn) 10B ? 每一中間節(jié)點(diǎn)可容納 p個(gè)節(jié)點(diǎn)指標(biāo)及 p1個(gè)索引值 ? (p8) + ((p1) 20) ≦ 4K ? p ≦ 147, p=74 ? 每一葉節(jié)點(diǎn)可容納 Pleaf個(gè)記錄指標(biāo)加上屬性值 , 再加上一個(gè)節(jié)點(diǎn)指標(biāo)指到下一個(gè)鄰接的葉節(jié)點(diǎn) ? (Pleaf (10 +20)) + 8 ≦ 4K ? Pleaf≦ 136, pleaf=68 ? 每一節(jié)點(diǎn)的空間利用率至少一半 ? 三層 B+tree範(fàn)例 第一層中間節(jié)點(diǎn) 1 74 節(jié)點(diǎn)指標(biāo) 第二層中間節(jié)點(diǎn) 74 7474=5476節(jié)點(diǎn)指標(biāo) 第三層葉節(jié)點(diǎn) 5476 547668=372,368 記錄指標(biāo) B+tree是一顆 非常扁平 的樹 ?黃三益 2020 資料庫的核心理論與實(shí)務(wù)第三版 917 練習(xí) 93 ? 有些研究已經(jīng)證明 B+tree的每一節(jié)點(diǎn)平均利用率為69%，請(qǐng)據(jù)此計(jì)算在以上範(fàn)例裡，一個(gè)三層的 B+tree平均可容納幾個(gè)記錄指標(biāo) ? Ans: 每一個(gè)中間節(jié)點(diǎn)平均有 147 = 101個(gè)節(jié)點(diǎn)指標(biāo) 每一個(gè)葉節(jié)點(diǎn)平均有 136 =93 個(gè)記錄指標(biāo)。 , 550, . ) .( 39。 , 6 0 0 , . ) .( 39。 , 3 5 0 , . ).( 39。 , 4 5 0 , . ).( 39。 , 5 0 0 , . ) 39。 , 4 5 0.39。 , 5 5 0.39。 , 5 0 0..?黃三益 2020 資料庫的核心理論與實(shí)務(wù)第三版 920 練習(xí) 96 ? 在 圖 97的索引裡，如果要搜尋所有 250元的書，請(qǐng)問會(huì)經(jīng)過哪些節(jié)點(diǎn)？ ? Ans: 要搜尋 (‘ Book’ , 250)，先找 n1, 由於該索引裡unitPrice是由大排到小，而 250 500，所以接下來找n3，由於 pName是由小排到大且 ’ Book’ ‘ CD’ ，所以接下來找 n7。 ? 找 ? 中華 ? 會(huì)找到（ Pr1, 4） , (Pr2, 4), (Pr4, 4) ? 找 ? 路 ? 也可找到（ Pr1, 6） , (Pr2, 7), （ Pr3, 6） , (Pr4, 7) ? ’ 中華 ’ 和 ’ 路 ’ 的開始位置必須差 3個(gè)字元 ? Pr2, Pr4 ?黃三益 2020 資料庫的核心理論與實(shí)務(wù)第三版 930 練習(xí) 97 ? 請(qǐng)問如何利用 圖 912的 Suffix
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1