第九章資料儲(chǔ)存結(jié)構(gòu)(參考版)
2024-10-28 14:34本頁面
【正文】 ? 找 ? 中華 ? 會(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 tree來處理以下查詢： SELECT * FROM Member WHERE address LIKE ‘ 臺(tái)北市 %中華 %’ 。 ?黃三益 2020 資料庫的核心理論與實(shí)務(wù)第三版 926 Suffix tree （ Cont.) ? Suffix tree是用來儲(chǔ)存一些字串的後段字串（ Suffix） ? ? 臺(tái)北市中華路一段 100號(hào) ? 的其後段字串包括 ? 臺(tái)北市中華路一段 100號(hào) ? 北市中華路一段 100號(hào) ? 市中華路一段 100號(hào) ? 中華路一段 100號(hào) ? 華路一段 100號(hào) ? 路一段 100號(hào) ? 一段 100號(hào) ? 段 100號(hào) ? 100號(hào) ? 00號(hào) ? 0號(hào) ? 號(hào) ?黃三益 2020 資料庫的核心理論與實(shí)務(wù)第三版 927 Suffix tree （ Cont.) ? Suffix tree的葉節(jié)點(diǎn)裡存的是一個(gè)後端字串所屬的記錄指標(biāo)以及其開始位置 ? 假設(shè)我們有四筆 Member記錄，其記錄指標(biāo)值分別為 pr1, pr2, pr3, pr4，且其 address屬性值分別為： ? pr1: 臺(tái)北市中華路三段 ? pr2: 高雄市中華三路 ? pr3: 臺(tái)北市南昌路 ? pr4: 高雄市中華二路 ? Suffix tree如 下圖 ?黃三益 2020 資料庫的核心理論與實(shí)務(wù)第三版 928 P r 2 , 1P r 4 , 1雄市中華中華華三二P r 2 , 2P r 4 , 2P r 4 , 4P r 2 , 4P r 1 , 4P r 4 , 5P r 2 , 5P r 2 , 6P r 1 , 7P r 4 , 6P r 1 , 1P r 3 , 1臺(tái)北市P r 1 , 6P r 2 , 7路P r 3 , 6P r 4 , 7P r 1 , 2P r 3 , 2北市P r 1 , 3P r 3 , 3P r 4 , 3P r 2 , 3P r 1 , 8段P r 1 , 5南P r 3 , 4高雄市中華市三段路三路二三路二中華路三二南P r 3 , 5昌中南三二三二中南?黃三益 2020 資料庫的核心理論與實(shí)務(wù)第三版 929 Suffix tree （ Cont.) ? Suffix tree也可用來輔助搜尋較複雜的 LIKE條件。 , 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。 , 6 0 0..39。 , 5 5 0.39。 , 3 5 0..39。 , 4 5 0.39。 , 5 0 0 , . ) .39。 , 5 0 0 , . ) 39。 , 4 0 0 , . ) .39。 , 4 5 0 , . ).( 39。 , 3 0 0 , . ) ( 39。 , 3 5 0 , . ).( 39。 , 4 5 0 , . ) ( 39。 , 6 0 0 , . ) .( 39。 , 7 0 0 , . ) ( 39。 , 550, . ) .( 39。 ? 葉節(jié)點(diǎn)裡是按照 catalog欄位值由小排到大，而同一 catalog欄位值的記錄則又按其 unitPrice欄位值由大排到小 ? 中間節(jié)點(diǎn)裡的索引值也是按照這樣的次序排列 ? 範(fàn)例結(jié)構(gòu)如下頁圖 ?黃三益 2020 資料庫的核心理論與實(shí)務(wù)第三版 919 多屬性值索引的 B+tree（ Cont.) n1n2n3n5n6n9n8n4n7( 39。 ? 一個(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) 第
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1