第五章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)(參考版)
2024-10-15 12:19本頁面
【正文】 得出： N≥2(k+1)L2 k L≤2+log(k+1)(N/2k)≈1+ log(k+1)(N/2) ? B+樹提供 3種存取路徑： ，再沿順序集順 序搜索 。 B+樹的級(jí)數(shù)決定于 N， 而不是記錄數(shù)！ 假設(shè) B+樹索引部分共有 L級(jí)，其秩為 k， 則各級(jí)的最小結(jié)點(diǎn)數(shù)依次為： 1， 2， 2(k+1)， … ， 2(k+1)L2 L決定了找到所需順序集結(jié)點(diǎn)所需的 I/O次數(shù)（訪問數(shù)據(jù)還要額外的 I/O）， 例如 k=99， N=2,000,000，有 L5， 即至多經(jīng)過 4次 I/O就可以找到相應(yīng)的順序集結(jié)點(diǎn)。 ? 搜索 B+樹所需的 I/O次數(shù)決定于其級(jí)數(shù)。 否則： Ki1Ks0Ks1…K s(n1)≤Ki . ? B+樹實(shí)現(xiàn)的主索引稍加修改后也可用于次索引 （把順序集結(jié)點(diǎn)的 tid換成指針，因?yàn)橐粋€(gè)鍵值可能對(duì)應(yīng)多個(gè)tid） 。 問題：若在某個(gè)索引集結(jié)點(diǎn)中找到了待查找記錄相應(yīng)的索引鍵值，是否還要繼續(xù)遍歷 B+樹，為什么？ 索引集與順序集的聯(lián)系 … … 0P 0K iP1?iK iK nP1?nK… … 0sK 0tid sjK jtid )1( ?nsK 1?ntid順序集節(jié)點(diǎn)中的鍵值要滿足如下關(guān)系： 如果 Pi=P0， 則 Ks0Ks1…K s(n1)≤K0。 P0 K0 … Ki1 Pi Ki … Kn1 Pn Kx Kx Kx 注意： 索引集節(jié)點(diǎn)中的鍵值 不一定 是文件中當(dāng)前存在的鍵值（僅起 “導(dǎo)航路標(biāo)” 的作用）。 tid， 實(shí)際上是記錄的地址，由塊號(hào)和 記錄在塊中 的指針號(hào) 組成（使用 記錄在塊中的指針號(hào) 表示記錄在塊中的位置， 好于直接用記錄在塊中的地址，方便記錄在塊內(nèi)移動(dòng)）。 刪除算法： 15 25 35 10 20 30 40,50 10,15 35 25,35 10,15 30 40,50 SH ST 索引集 順序集 B+樹實(shí)現(xiàn)的主索引 B+樹實(shí)現(xiàn)的主索引包含如下 2部分：索引集和順序集。 10 20 15 從根向葉搜索，直至相應(yīng)葉節(jié)點(diǎn)，若該葉節(jié)點(diǎn)不滿，則將鍵值插入葉節(jié)點(diǎn)中；如葉節(jié)點(diǎn)已滿（ 即已經(jīng)有 2K個(gè)鍵值 ）， 則將此葉節(jié)點(diǎn)分裂為二，葉節(jié)點(diǎn)分裂后，其雙親節(jié)點(diǎn)也必須增加一個(gè)鍵值，若雙親節(jié)點(diǎn)不滿，插入過程結(jié)束；否則雙親節(jié)點(diǎn)繼續(xù)分裂為兩個(gè)節(jié)點(diǎn)，如此繼續(xù)直到插入過程中止。 ? 除葉節(jié)點(diǎn)無子女外，其它節(jié)點(diǎn)若有 J個(gè)鍵值，則有J+1個(gè)子女 。 B+樹的限制和規(guī)定： ? 每個(gè)節(jié)點(diǎn)最多有 2k個(gè)鍵值， k稱為 B+樹的秩(Order)。 鍵 指針 頭塊 鏈塊 1 鏈塊 n 索引區(qū) ——簇集索引（ clustering index） ： 建立簇集索引的開銷較大，整個(gè)文件要重新組織。如果這些記錄分散在不同的物理塊內(nèi)，稠密索引的優(yōu)點(diǎn)并不能體現(xiàn)出來 （并不一定能減少I/O）。 解決方法： 例如：某個(gè)鍵值對(duì)應(yīng) 100個(gè)記錄，且這 100個(gè)記錄分散在 100個(gè)物理塊中，雖然通過稠密索引可以一次獲得這 100個(gè)地址，但仍然要訪問 100個(gè)物理塊。 ? 索引溢出的問題 稠密索引中，每增加一個(gè)鍵值，就要增加一個(gè)索引項(xiàng)。 1 2 3 4 5 6 7 8 9 10 11 12 121 134 167 182 203 211 223 229 231 237 241 13 14 15 16 … 255 259 267 271 … 單元存儲(chǔ)區(qū) 182 4 201
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1