《查詢處理》ppt課件-文庫吧

【正文】 (續 ) ?算法 A2 (二叉搜索 ):如果文件有序且選擇條件是在排序屬性上的相等性比較即可用 ?假設關系的塊連續存儲 ?求值代價 (掃描的磁盤塊數 ): ??log2(br)? — 通過對塊的二叉搜索來定位第一條元組的代價 ?再加上包含滿足選擇條件的記錄的塊數 ?第 6章討論如何求這個代價 169。Silberschatz, Korth and Sudarshan Database System Concepts 利用索引的選擇 ? 索引掃描 – 使用索引的搜索算法 ?選擇條件必須針對索引的搜索鍵 ? A3 (候選鍵上的主索引 , 相等 ): 檢索滿足對應等式條件的單個記錄 ? Cost = HTi + 1 ? A4 (非鍵屬性上的主索引 , 相等 ): 檢索多條記錄 ?記錄位于連續的塊上 ? Cost = HTi + 包含檢索記錄的塊數 ? A5 (輔助索引搜索鍵上的相等 ) ?若搜索鍵是候選鍵則檢索單個記錄 ?Cost = HTi + 1 ?若搜索鍵不是候選鍵則檢索多個記錄 ?Cost = HTi + 檢索到的記錄數 – 可能非常昂貴 ! ?各記錄可能位于不同的塊上 – 對每條檢索到的記錄都有一次塊存取 169。Silberschatz, Korth and Sudarshan Database System Concepts 涉及比較的選擇 ? 為實現形如 ?A?V (r ) 或者 ?A ? V(r ) 的選擇 , 可以使用 ?線性文件掃描或二叉搜索 ? 或者按如下方式使用索引 : ? A6 (主索引 , 比較 ) (關系在 A上排序 ) ?對 ?A ? V (r) 利用索引找到第一條 ?v 的元組 , 再從該處順序掃描關系 ?對 ?A?V (r) 順序掃描關系直至第一條 v 的元組 。 不用索引 ? A7 (輔助索引 , 比較 ) ?對 ?A ? V (r) 利用索引找到第一條 ?v 的索引項 , 再從該處順序掃描索引 , 查處指向記錄的指針 . ?對 ?A?V (r) 只需掃描索引的葉頁來找出指向記錄的指針 , 直至第一條 v 的項 ?在每種情況下 , 檢索被指向的記錄時 : ?每條記錄需要一次 I/O ?如果有很多記錄需要取出 , 則線性文件掃描可能更廉價 ! 169。Silberschatz, Korth and Sudarshan Database System Concepts 復雜選擇的實現 合取 : ??1? ?2?. . . ?n(r) ? A8 (利用一個索引的合取選擇 ) ?選擇一個 ?i 和算法 A1到 A7的組合使得 ??i (r)的代價最小 ?將元組取進內存緩沖區之后再測試其他條件 ? A9 (利用多鍵索引的合取選擇 ) ?如果可能 , 使用合適的復合 (多鍵 )索引 ? A10 (求標識符交集的合取選擇 ) ?需要帶有記錄指針的索引 ?對每個條件使用對應的索引 , 再求所有得到的記錄指針集合的交集 ?然后從文件讀取記錄 ?如果某些條件沒有對應的索引 , 則對已讀取記錄進行該條件的測試 . 169。Silberschatz, Korth and Sudarshan Database System Concepts 復雜選擇的算法 析取 : ??1? ?2 ?. . . ?n (r) ? A11 (利用標識符的并集求析取選擇 ). ?應用于所有條件都有可用的索引的情況 . ?否則使用線性掃描 ?利用每個條件的對應索引 , 再求所得到的各記錄指針集的并集 ?然后從文件讀取記錄 169。Silberschatz, Korth and Sudarshan Database System Concepts 排序 (略 ) ?小關系排序，內存能裝下，用 quicksort等內存排序算法 ?大文件排序，由于內存裝不下，可以先在關系上建立一個索引 , 然后利用該索引來按排好的順序讀入關系 ?可能導致每條元組需要一次磁盤塊存取 ?對不能放進內存的大關系 , 外排序是一個好的選擇 169。Silberschatz, Korth and Sudarshan Database System Concepts 排序 ?下面將介紹用于大文件的歸并排序法 ?思想：設三個班已經分別排序，現全年級排序，在各班第一中選第一名，移動到年級第一名位置，以此類推（遞歸） ,如果要排全校序，再歸并 169。Silberschatz, Korth and Sudarshan Database System Concepts 外排序 歸并 1. 創建有序 序段 (run): 令 i 初始為 0 重復下列步驟直至關系末尾 : (a) 將關系的 M 塊讀入內存 (b) 對內存塊排序 (c) 將以排序數據寫到序段 Ri 。 遞增 i 設 i 的最后的值為 N ?令 M 表示內存大小 (以頁為單位 ) 169。Silberschatz, Korth and Sudarshan Database System Concepts 外排序 歸并 2. 歸并序段 (N路歸并 ):目前假設 N M I. 利用內存的 N 塊來緩沖輸入序段 , 一塊緩沖輸出 . 將各序段的第一塊讀入其緩沖頁 II. repeat ① 從所有緩沖頁中挑選第一條記錄 (按排序順序 ) ② 將該記錄寫到輸出緩沖區 . 如果輸出緩沖已滿則寫入磁盤 ③ 從輸入緩沖頁刪除該記錄 If 緩沖頁變空 then 將該序段的下一塊 (若有的話 )讀入緩沖 III. until 所有輸入緩沖頁都為空 : 169。Silberschatz, Korth and Sudarshan Database System Concepts 外排序 歸并 ? 若 i ? M, 需要若干歸并趟 ?在每一趟中 , 歸并 M 1個序段 ?每一趟可按因子 M 1來減少序段數目 , 也可按相同因子創建更長的序段 ?例如 若 M=11, 并有 90個序段 , 則一趟就將序段數減少到 9, 而序段長度則是初始序段的 10倍 ?重復執行若干趟直至所有序段被歸并為一個序段 169。Silberschatz, Korth and Sudarshan Database System Concepts 例 : 外排序 歸并 169。Silberschatz, Korth and Sudarshan Database System Concepts 外排序 歸并 (續 ) ?代價分析 : ?所需總的歸并趟數 : ?logM–1(br/M)? ?初始以及各趟中的序段創建所需磁盤存取次數為 2br ?對最后一趟 , 我們不計算寫代價 –我們對所有操作都忽略最后的寫代價 , 因為操作的輸出可能送往父操作 , 不許要寫到磁盤 ?因此外排序的總的磁盤存取數為 : br ( 2 ?logM–1(br / M)? + 1) ?這是建立數學模型，忽略一些次要因素，得到的定量結果 (估計值 )對選擇的評估結束 ?下面將介紹連接的代價分析 169。Silberschatz, Korth and Sudarshan Database System Concepts 聯接操作 ? 有多種不同算法實現聯接 ?嵌套循環聯接 ?塊嵌套循環聯接 ?索引嵌套循環聯接 ?歸并聯接 ?散列聯接 ? 根據代價進行選擇 ? 例子中用到下列信息 ?記錄數 customer : 10,000 depositor : 5000 ?塊數 customer : 400 depositor : 100 ? 書上介紹了多種連接算法的代價，掌握主要思想即可 169。Silberschatz, Korth and Sudarshan Database System Concepts 嵌套循環聯接 ? 計算 ?聯接 r ? s ? 最樸素算法： 雙重循環，作 m*n次比較 ? 有若干次讀寫盤 ? 簡化模型只專注于讀寫磁盤塊的次數 ? 一般方法： ?如果一個關系能全裝入內存，作為內循環對象，很快 ?如兩關系都裝不進內存，則 較小的一個作外循環對象（要被全掃描） ?如果一個有散列或索引，就不一定全掃描，有優化潛力可挖 169。Silberschatz, Korth and Sudarshan Database System Concepts 嵌套循環聯接 ? 計算 ?聯接 r ? s for each tuple tr in r do begin for