數(shù)據(jù)庫原理與應(yīng)用(1)-閱讀頁
2025-05-29 03:08本頁面
【正文】 ， 由此可見 ， 通過 B+樹進行數(shù)據(jù)檢索的效率是相當(dāng)高的 ? ?? ? 12/2/ ?Klo g n數(shù)據(jù)庫原理與應(yīng)用 B+樹更新 ? 索引結(jié)構(gòu)必須與對應(yīng)的基本表中的數(shù)據(jù)相一致 ， 當(dāng)用戶插入 、 刪除基本表中的記錄或更新記錄中索引字段的值時 ， 必須同時更新相應(yīng)的索引結(jié)構(gòu) ? B+樹索引支持兩種基本的更新操作：插入和刪除一個入口項 20 30 40 分裂 20 30 60原節(jié)點 L 新節(jié)點 L ’ 上傳入口項 6 0 , L ’ 數(shù)據(jù)庫原理與應(yīng)用 插入操作 ? 首先用 B+樹檢索算法找到用于插入該鍵值的葉節(jié)點 ， 若該葉節(jié)點中已經(jīng)包含待插入的鍵值 ， 則將記錄的位置添加到相應(yīng)的指針桶中；否則 ， 將鍵值插入到該葉節(jié)點的合適位置 ， 使得在插入后節(jié)點中的鍵值仍保持遞增排列 ， 當(dāng)索引為 unique時 ， 同時插入記錄的位置 ， 當(dāng)索引不為 unique時， 創(chuàng)建一個只包含新插入記錄位置的指針桶 ， 同時插入指針桶的位置 ? B+樹插入操作的復(fù)雜性在于在特定情況下必須進行節(jié)點分裂操作 。 如果在刪除后使得該葉節(jié)點中余下的入口項不足 個 ， 即產(chǎn)生一次向下溢出 (underflow)， 則需要盡量找到一個兄弟節(jié)點以進行節(jié)點合并或入口項重新分配 ， 通常是向該節(jié)點 “ 借用 ” 一個入口項 。 由于節(jié)點的合并需要在父節(jié)點中刪除入口項 ， 因此又可能導(dǎo)致父節(jié)點向下溢出 。 若刪除后該塊為空且為溢出塊 ， 則將該塊從所處桶的溢出塊鏈表中刪除 數(shù)據(jù)庫原理與應(yīng)用 靜態(tài)哈希 ? 哈希函數(shù) ， 一個好的哈希函數(shù)能夠?qū)⑺饕I值比較平均的分配到各個桶中去 ? 桶的數(shù)量：為了不產(chǎn)生溢出現(xiàn)象 ， 桶的數(shù)量 nB需要滿足nB nr / fr， 其中 nr為預(yù)期的索引鍵值數(shù) ， fr為每個塊中所能存儲的索引鍵值數(shù) 。 如果桶的數(shù)量過小， 則隨著數(shù)據(jù)庫的運行 ， 索引中將會產(chǎn)生大量溢出塊 ， 從而導(dǎo)致性能降低 ， 反之 ， 如果一開始就將桶的數(shù)量設(shè)得很大 ， 則在很長一段時間內(nèi)又會造成空間的浪費 ? 動態(tài)哈希技術(shù)彌補了靜態(tài)哈希的上述缺陷 ， 動態(tài)哈希技術(shù)允許文件中的桶數(shù)動態(tài)增長 ， 同時又不需要重整 。 代數(shù)優(yōu)化一般是基于規(guī)則的優(yōu)化 ， 在代數(shù)優(yōu)化過程中一般較少使用統(tǒng)計信息 ， 不進行代價估計 。 ? 物理優(yōu)化 ：為代數(shù)優(yōu)化產(chǎn)生的最終查詢樹生成不同的物理執(zhí)行計劃 ， 并利用統(tǒng)計信息對計劃的執(zhí)行代價進行估計 ， 最后選擇其中代價最小的計劃作為輸出 ， 因此 ， 物理優(yōu)化是基于代價的優(yōu)化 數(shù)據(jù)庫原理與應(yīng)用 代數(shù)優(yōu)化 Pname σtitle=‘Database System Concepts’ book author Pname σtitle=‘Database System Concepts’ book author 數(shù)據(jù)庫原理與應(yīng)用 代數(shù)優(yōu)化的等價變換 s = ∧ = ∧ = ’張三 ’ P tag customer interest_in category 數(shù)據(jù)庫原理與應(yīng)用 代數(shù)優(yōu)化的等價變換（續(xù)） s = P tag customer interest_in category s = s = ’張三’ s = P tag customer interest_in category s = s = ’張三’ 數(shù)據(jù)庫原理與應(yīng)用 物理優(yōu)化 ? 物理優(yōu)化在代數(shù)優(yōu)化之后進行 ， 其過程可以概括為 “ 枚舉策略－估算代價－生成計劃 ” 三步 ? 物理優(yōu)化是基于代價進行的 。 ? br：關(guān)系 r的數(shù)據(jù)文件中包含的數(shù)據(jù)塊數(shù) 。 ? fr：關(guān)系 r的塊因子 ， 即一個塊中平均有多少條記錄 ， fr ≈ nr / br。 如果 A是主鍵 ， 則 V(A, r) = nr。 ? 使用 B+樹索引：當(dāng)在選擇條件涉及的列上建有 B+樹索引時 ， 可以考慮使用索引來進行選擇 。 數(shù)據(jù)庫原理與應(yīng)用 聯(lián)接操作的執(zhí)行策略 ? 嵌套循環(huán)聯(lián)接 ? 塊嵌套循環(huán)聯(lián)接 ? 索引嵌套循環(huán)聯(lián)接 ? 歸并聯(lián)接 數(shù)據(jù)庫原理與應(yīng)用 嵌套循環(huán)聯(lián)接 ? for (關(guān)系 R中的每個元組 tr) { ? for (關(guān)系 S中的每個元組 ts) { ? if (tr與 ts符合選擇條件 ) 將 tr ? } ? } 數(shù)據(jù)庫原理與應(yīng)用 塊嵌套循環(huán)聯(lián)接 ? for (關(guān)系 R中的每個塊 BR) { ? for (關(guān)系 S中的每個塊 BS) { ? for (BR中每個元組 tr) { ? for (BS中每個元組 ts) { ? if ( tr與 ts符合選擇條件 ) 將 tr ? } ? } ? } ? } 數(shù)據(jù)庫原理與應(yīng)用 索引嵌套循環(huán)聯(lián)接 ? for (關(guān)系 R中的每個元組 tr) { ? 利用索引找到 S中與 tr匹配的元組 ts。t s加入到聯(lián)接結(jié)果中 。 歸并聯(lián)接的輸出也是按聯(lián)接條件中的屬性按好序的 。
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1