第五章數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)-資料下載頁(yè)
2025-10-02 12:19本頁(yè)面
【導(dǎo)讀】采用多級(jí)存儲(chǔ)器，用的最多的輔存是磁盤。光盤由于速度和價(jià)格上的原因，近期無(wú)法取。磁帶是順序存取存儲(chǔ)器，通常用作后備存儲(chǔ)。用內(nèi)存作為數(shù)據(jù)庫(kù)的存儲(chǔ)介質(zhì)是不合適的?；顒?dòng)頭磁盤的存取時(shí)間由三部分組成：尋道。盤與內(nèi)存間的數(shù)據(jù)交換以物理塊為單位。1).減少I/O的次數(shù)，從而減少尋道和等待的時(shí)間。2).減少間隙的數(shù)目，提高磁盤空間利用率。物理快的大小由OS決定。一般，在磁盤和內(nèi)存之間設(shè)立緩沖區(qū)以解決。二者的速度不匹配問(wèn)題。操作和讀寫(xiě)數(shù)據(jù)的處理可以重疊進(jìn)行。不少DBMS采用延遲寫(xiě)與提前讀技術(shù)，減少。記錄是目前商用數(shù)據(jù)庫(kù)的基本數(shù)據(jù)單元，有定。被分散到磁盤的不同區(qū)域。多塊文件，不利于文件的擴(kuò)充。例如，bbbbb可以用#5表示；000000可以用@6表示等。傳統(tǒng)文件系統(tǒng)不能提供實(shí)現(xiàn)DBMS功能所需的附。DBMS為了實(shí)現(xiàn)其功能，須在文件目錄、堆文件插入容易、查找。若堆文件的記錄按檢索屬性排序，可用二分查找法。的第2，4，6條數(shù)據(jù)記錄。
【正文】 15 10, 15 20 25 20,25 30 10 15 20 30 25 20 10 15,25 30 15 25 35 10 20 30 40,50 先從根節(jié)點(diǎn)出發(fā)，找到待刪除鍵值所在葉節(jié)點(diǎn)；若刪除該鍵值后，葉節(jié)點(diǎn)中鍵值數(shù)減為 K1個(gè)，則 向其左右兄弟葉節(jié)點(diǎn)借一個(gè)鍵值，以保持每個(gè)葉節(jié)點(diǎn)存放鍵值不少于 K個(gè) ；若其左右葉節(jié)點(diǎn)都只有 K個(gè)鍵值，則可 將該葉節(jié)點(diǎn)與其左（或右）葉節(jié)點(diǎn)合并成包含 2K1個(gè)鍵值的葉節(jié)點(diǎn)，合并后，其雙親節(jié)點(diǎn)要減少一個(gè)鍵值 ，有可能導(dǎo)致雙親節(jié)點(diǎn)的合并。 刪除算法： 15 25 35 10 20 30 40,50 10,15 35 25,35 10,15 30 40,50 SH ST 索引集 順序集 B+樹(shù)實(shí)現(xiàn)的主索引 B+樹(shù)實(shí)現(xiàn)的主索引包含如下 2部分：索引集和順序集。 節(jié)點(diǎn)類型 塊中索引鍵數(shù) … 0P 0K 1P 1K 1?nK nP索引集節(jié)點(diǎn) 節(jié)點(diǎn)類型 塊中索引鍵數(shù) 前向指針 后向指針 … 0K 0tid 1K 1tid nK ntid順序集節(jié)點(diǎn) 注： 。 tid， 實(shí)際上是記錄的地址，由塊號(hào)和 記錄在塊中 的指針號(hào) 組成（使用 記錄在塊中的指針號(hào) 表示記錄在塊中的位置， 好于直接用記錄在塊中的地址，方便記錄在塊內(nèi)移動(dòng)）。 ? 要找鍵值 KX所對(duì)應(yīng)的記錄時(shí)，從索引樹(shù)的根開(kāi)始，按下面的規(guī)則自上而下地搜索： KxK0， 則沿 P0所指的節(jié)點(diǎn)向下搜索； KxKn1， 則沿 Pn所指的節(jié)點(diǎn)向下搜索； Ki1Kx≤Ki， 則沿 Pi所指的節(jié)點(diǎn)向下搜索。 P0 K0 … Ki1 Pi Ki … Kn1 Pn Kx Kx Kx 注意： 索引集節(jié)點(diǎn)中的鍵值 不一定 是文件中當(dāng)前存在的鍵值（僅起 “導(dǎo)航路標(biāo)” 的作用）。在搜索過(guò)程中，即使發(fā)現(xiàn)索引集節(jié)點(diǎn)中的鍵值等于要找的鍵值，查找仍要按上述規(guī)則進(jìn)行下去。 問(wèn)題：若在某個(gè)索引集結(jié)點(diǎn)中找到了待查找記錄相應(yīng)的索引鍵值，是否還要繼續(xù)遍歷 B+樹(shù)，為什么？ 索引集與順序集的聯(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。 如果 Pi=Pn， 則 Ks(n1)…K s1Ks0Kn1。 否則： Ki1Ks0Ks1…K s(n1)≤Ki . ? B+樹(shù)實(shí)現(xiàn)的主索引稍加修改后也可用于次索引 （把順序集結(jié)點(diǎn)的 tid換成指針，因?yàn)橐粋€(gè)鍵值可能對(duì)應(yīng)多個(gè)tid） 。 ? B+樹(shù)實(shí)現(xiàn)的各種索引都是稠密索引（非稠密索引的概念源于靜態(tài)索引），提供了順序搜索的功能，這是它的優(yōu)點(diǎn)。 ? 搜索 B+樹(shù)所需的 I/O次數(shù)決定于其級(jí)數(shù)。 設(shè)索引屬性不同鍵值的數(shù)目為 N， 若索引鍵不是候選鍵，則記錄數(shù)通常大于 N。 B+樹(shù)的級(jí)數(shù)決定于 N， 而不是記錄數(shù)！ 假設(shè) B+樹(shù)索引部分共有 L級(jí)，其秩為 k， 則各級(jí)的最小結(jié)點(diǎn)數(shù)依次為： 1， 2， 2(k+1)， … ， 2(k+1)L2 L決定了找到所需順序集結(jié)點(diǎn)所需的 I/O次數(shù)（訪問(wèn)數(shù)據(jù)還要額外的 I/O）， 例如 k=99， N=2,000,000，有 L5， 即至多經(jīng)過(guò) 4次 I/O就可以找到相應(yīng)的順序集結(jié)點(diǎn)。 順序集至少有 2(k+1)L2個(gè)結(jié)點(diǎn)。 得出： N≥2(k+1)L2 k L≤2+log(k+1)(N/2k)≈1+ log(k+1)(N/2) ? B+樹(shù)提供 3種存取路徑： ，再沿順序集順 序搜索
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1