4-9章習題解答

第 4 章 數(shù)據(jù)存儲與組織管理 要回答以下問題。 （ 1） 描述磁盤空間管理器的主要作用，并說明它與 件系統(tǒng)的關(guān)系。 （ 2） 解釋關(guān)系數(shù)據(jù)庫系統(tǒng)中關(guān)系表與文件的關(guān)系。 （ 3） 如果有一個大文件需要頻繁執(zhí)行順序掃描，那么，為該文件選擇哪種頁存儲方式最合適？ （ 4） 分別描述持久化指針解引用 (指針混寫的這兩個基本過程，它們之間有何聯(lián)系？ （ 5） 說明排序文件中的記錄及頁的基本存儲組織方式。 （ 6） 解釋緩沖區(qū)管理器處理一個讀頁請求的過程。如果被請求頁位于緩沖池但未被閂住 (那么情況會怎樣？緩沖區(qū)管理器何時寫一 個磁盤頁？ （ 7） 一個緩存頁被閂?。?be 味著什么？一般由誰負責給緩存頁上閂，由誰負責給緩存頁解閂 ? （ 8） 當一個頁請求發(fā)生時，如果緩沖池中所有頁都是臟頁，將會發(fā)生什么？ （ 9） 與 存管理相比， 沖區(qū)管理器具有那些獨特的重要能力？ （ 10） 什么是預?。拷忉尀槭裁催@種策略很重要。 （ 11） 描述兩種可能的記錄格式，并指明它們的優(yōu)缺點。 （ 12） 描述兩種可能的頁格式，說明它們優(yōu)缺點和適用場合。 【解答】 （ 1） 磁盤空間管理器支持以頁 (單位的數(shù)據(jù)管理，隱藏了下層硬件（甚至包括 件管理）的細節(jié)，且允許高層軟件認為 據(jù)是一系列以頁為單位的磁盤數(shù)據(jù)集合，是 系結(jié)構(gòu)中最低層的軟件模塊。 統(tǒng)的磁盤空間管理器通常按三種方式來應用 文件管理功能： 將整個 用 。 讓 配給 統(tǒng)一個或幾個大的 件，然后自己管理（讀 /寫）這個文件。 完全自己來管理磁盤。 （ 2） 通過磁盤空間管理器，可將 的 “關(guān)系 ”映射到 “關(guān)系數(shù)據(jù)文件 ”，這種 “文件 ”既可能是實際的 件，也可能只是一個虛擬的 件。 一些小規(guī)模的 統(tǒng) 實現(xiàn)甚至可能 將關(guān)系直接存 儲在單獨的 件中。 但 更多的現(xiàn)代大型 統(tǒng)，則是把所有關(guān)系都集中存儲在一個或幾個大文件中的復雜結(jié)構(gòu)。這時，我們?nèi)匀豢稍诟拍钌险J為每個關(guān)系被存儲在一個 “虛擬文件 ”中。 （ 3）這時選用堆文件的頁存儲方式最合適。當不需要檢索特點的記錄，而只是全文件順序掃描時，選用堆文件的頁存儲方式最合適，因為這種情況不需維護順序，插入插入與刪除操作很直接，代價較小，另外，也不需要數(shù)據(jù)本身之外的額外存儲空間和輔助索引文件。 （ 1） 存取數(shù)據(jù)庫記錄 /數(shù)據(jù)頁要用到兩種類型指針：內(nèi)存指針與數(shù)據(jù)庫地址 (持久化指針 )。 根據(jù)給定的指針或地址尋找 目標對象的過程，稱為解引用。給定一個內(nèi)存指針，查找對象本質(zhì)上只是對內(nèi)存單元的一個引用（ *指針名）。給定一個持久化指針，解引用一個對象需要額外的步驟，即需先在“轉(zhuǎn)換表”中查找持久化指針所代表對象的實際內(nèi)存地址。如果指針所指對象不在內(nèi)存，則必須從磁盤把它載入，并在轉(zhuǎn)換表中添加新映射項。與內(nèi)存指針解引用相比，即使轉(zhuǎn)換表中有映射項，通過轉(zhuǎn)換表實現(xiàn)解引用仍是一個慢過程。 指針混寫 是一種減少定位已在內(nèi)存中持久對象所需代價的方法。其基本思想是，當一個主存中對象 /記錄所含的持久指針第一次解引用時，這個持久指針所指向 的目標對象被定位如果它不存在內(nèi)存中，就將它載入內(nèi)存并同時在轉(zhuǎn)換表中添加一個新的映射項。然后，將存放該持久指針的內(nèi)存單元，直接修改為目標對象的內(nèi)存位置指針。下一次同一持久化指針再次被解引用時，就可以直接使用內(nèi)存引用，從而可避免重復轉(zhuǎn)換內(nèi)存地址的過程開銷。 顯然，指針混寫包含了持久化指針解引用過程，但前者比后者多了一個在主存中同一位置來回修改“持久化指 針內(nèi)存指針”過程。指針混寫能降低持久化化對象解引用的過程。 （ 2） 排序文件是指按指定的鍵排序記錄集的一種文件組織。雖然在輔存中嚴格按排序順序先后安排文件中記錄存 儲，能顯著提高記錄集檢索性能，但這樣做的維護代價太大， 統(tǒng)一般并不這種做，通常是指針把記錄按順序鏈接起來。 刪除記錄時僅做標記并留下空位，暫不移動其它記錄；而在插入時，相應位置即使沒有空位，也暫時不移動其它記錄來騰出位置，而是引入溢出頁。 對排序文件，頁內(nèi)的記錄索引項或目錄項通常是嚴格按順序的。另外，記錄鏈接自動隱含了頁間鏈接。 （ 3） 緩沖區(qū)管理器執(zhí)行讀頁請求的基本過程如下： 檢查 沖池中是否存在該請求頁，如果該頁不在 沖池中，則進一步執(zhí)行以下一些操作。 基于置換策略，選擇一個可被置換的 該 數(shù)加 1。 如果該 原先頁被修改過（即 ），則將原先頁寫回磁盤。 從磁盤讀入新請求頁到該 ，同時置 。 返回包含請求頁的 址給請求者。 如果被請求頁位于緩沖池但未被閂住 (那么該頁不會被替換，即沒有新頁可被讀入該頁所占據(jù)的頁框。 當一個緩存頁已被修改過 (置 1)，且該頁未上閂，所占據(jù)頁框需讀入新頁時，通常會觸發(fā)緩沖區(qū)管理器寫一個磁盤頁。 （ 4） 緩存頁備閂住意味著與該頁對應的 ，每 次， 1。拴住一個能為高層 件保證緩沖區(qū)管理器不會將該頁從緩沖池移除，即其它文件頁不會被讀入該被閂頁所占據(jù)的頁框。一般有緩沖區(qū)管理器具體執(zhí)行 ，但頁請求者有責任通知緩沖區(qū)管理器 個不再用的頁。 （ 5） 當一個頁請求發(fā)生時，如果緩沖池中所有的頁都是臟頁，緩沖區(qū)管理器會依據(jù)緩沖區(qū)置換策略選擇要換出 并將該 原先的頁寫回磁盤。從磁盤讀入請求頁，同時將 0，返回包含請求頁的地址給請求者。 （ 6） 與 存管理相比， 沖區(qū)管 理器 有以下幾個特別功能特性： a) 因為與一般應用相比， 容易 準確預測磁盤頁存取順序。 所以， 沖區(qū)管理器通常能更好、更靈活地 選擇合適的頁置換策略，或采用一些特別的、適合于 境的特殊管理措施。 b) 因可更準確 預測引用模式， 沖區(qū)管理器可以使用一些很簡單、但卻非常有效的預取策略，以有效減少多個連續(xù)頁的磁盤 I/O 時間。 c) 當決定一個頁何時被寫回磁盤時， 望或需要有更多的控制權(quán)。 （ 7） 假設 A 塊、 B 塊存儲在磁盤相鄰的位置上。系統(tǒng)預計或猜測到 A 和 B 兩塊可能會先后同時被訪問，故當 A 塊需要 被讀入主存時，系統(tǒng)順帶把 B 塊也讀入主存緩沖區(qū)。 這種方案通?？蓽p少 I/O 操作時間，顯著提高 統(tǒng)性能，是 化的一個很重要策略。 （ 8） 定長記錄格式和可變記錄格式（詳見書本 ）。 （ 9） 連續(xù)槽的頁組織格式和基于目錄槽的頁組織格式（參見書本 ）。 慮一個磁盤：它有 5 個雙面盤片，每個盤面 2,000 個磁道，每個磁道 50個扇區(qū)，每個扇區(qū) 512 字節(jié)。另外，假設它的平均尋道時間為 10 （ 1） 計算每個盤面的格式化容量和整個磁盤的格式化容量。 （ 2） 如果磁盤轉(zhuǎn)速為 5,400 轉(zhuǎn) /分鐘，計算磁盤的最 大旋轉(zhuǎn)延遲和平均旋轉(zhuǎn)延遲時間。 （ 3） 在 256、 2048 和 51,200 三個值中，那些值是可能的有效塊大??？為什么？ （ 4） 如果每個磁盤塊大小占 2 個扇區(qū)，試估算傳輸一個塊的平均時間。 【解答】 （ 1） 每個盤面的 格式化 容量 磁道數(shù) *扇區(qū)數(shù) *字節(jié)數(shù) =2000*50*512 B 49個磁盤的格式化容量盤面數(shù) *每個盤面的容量 =10*49M=490 2） 最大的旋轉(zhuǎn)延遲時間 磁盤 旋轉(zhuǎn)一周所用的時間 1/轉(zhuǎn)速 =60/5400=均旋轉(zhuǎn)等待時間 最大的旋轉(zhuǎn)延遲時間 /2 = = 3） 塊是 際讀寫磁盤的基本單位 ，必須是扇區(qū)大小的整數(shù)倍；其次 ， 塊大小選擇要適中， 太小 會導致 I/O 數(shù)增加，太大 則 會造成磁盤讀寫操作浪費加大 ，都不利于管理 。因此，三個值中，只有 2048 可能是有效塊大小 。 （ 4）旋轉(zhuǎn) 傳輸 1 個塊的 時間 =讀兩個扇區(qū)所用的時間 =（ 60/5400） *（ 2/50） 輸一個塊的時間 = 尋道時間旋轉(zhuǎn)延遲時間傳輸時間 =106 對習題 磁盤，若磁盤塊大小為 1,024 字節(jié)。假設有一個包含 100,000個元組、每個元組 100 字節(jié)的關(guān)系文件存儲在該磁盤上，并規(guī)定記錄不允許跨塊存儲。 （ 1） 每個塊中可存放多少個元組？存儲整個文件需要多少個塊？ （ 2） 估算順序掃描該關(guān)系文件需要的總時間。 （ 3） 如果該磁盤的各盤面上磁頭能并行讀 /寫數(shù)據(jù)，且磁盤數(shù)據(jù)是按可能的最優(yōu)方式安排存儲，這種情況下，執(zhí)行全文件順序掃描需要多少時間？ 【解答】 （ 1） 每個塊可存放元組數(shù) 磁盤塊大小 /每個元組字節(jié)數(shù) =1024/100 = 10 個 存儲整個文件需要塊數(shù)總的元組數(shù) /每個塊元組數(shù) =100,000/10=10,000 塊 （ 2）順序掃描文件需總時間文 件總存儲塊數(shù) *每塊存取時間 10,000 *1660,000鐘 （ 3）根據(jù)題意，可認為讀寫一個柱面時間 最大的旋轉(zhuǎn)延遲時間 個柱面大小盤面數(shù) 10*扇區(qū)數(shù) *字節(jié)數(shù) =10*50*512 B 按柱面安排連續(xù)存儲文件需要的柱面數(shù) = 100,000*100/(10*50*512)= 40 （向上取整） 所以，這種情況下，順序掃描文件需總時間 40* 假設某磁盤具有以下特性：有 10 個盤面，每個盤面 10,000 個磁道；每個磁道 1000 個扇區(qū)，每個扇區(qū) 512 個字節(jié)；每個磁道 20%被用于間隙；磁盤旋轉(zhuǎn)速率 10,000轉(zhuǎn) /分鐘；磁頭移動 +回答關(guān)于該磁盤的以下問題： （ 1） 磁盤的總?cè)萘渴嵌嗌伲?（ 2） 最大尋道時間和最大旋轉(zhuǎn)等待時間分別為多少？ （ 3） 如果一個塊是 16,384 字節(jié)（即 32 扇區(qū)），那么，一個塊的傳輸時間是多少？ 【解答】 （ 1） 磁盤總?cè)萘?盤面數(shù) *磁道數(shù) *扇區(qū)數(shù) *字節(jié)數(shù) =10*10000*1000*512B= 2）最大 尋道 時間磁頭跨越所有磁道時間 =1+999 2大的旋 轉(zhuǎn)等待時間磁盤旋轉(zhuǎn)一周的時間 = 60/10,000s = 6 3）一個塊（含 32 個扇區(qū) & 31 個間隙 ）所占圓弧度 =32*360/1000)+ 31*360/1000)=60/1000 旋轉(zhuǎn)通過這樣大小弧長需時間 =(60/1000) /360 )*6均尋道時間，取 1/3 的最大尋道時間 2 = 均旋轉(zhuǎn)等待時間，取 1/2 的最大旋轉(zhuǎn)等待時間 6=3以，傳輸一個塊的 時間 3 假設我們正在為某磁盤調(diào)度 I/O 請求，磁頭的初始位置在磁道 4000。已知該磁盤尋道時間可按公式（ 1+移動磁道數(shù) /500）毫秒來計算，到達磁道后訪問一個塊的平均時間還需要約 秒。假定調(diào)度時已經(jīng)產(chǎn)生的請求共有 4 個，它們所在的柱面分別為 : 1000 / 6000 / 500 / 5000，它們達到的先后時序值分別為 0/1/10/20。試分別計算下列兩種情況下，服務完這些請求需要的時間。 （ 1） 采用電梯算法，先從任何方向開始移動都是可能的。 （ 2） 采用 先到先服務算法。 【解答】 （ 1）由于最先到的的請求是 1000， 假設磁頭向下運動，那么，電梯調(diào)度策略的塊訪問情況如下表所示。 塊請求及被服務順序 完成時間 1000 (1+3000/500)+00 1+500/500)+000 1+4500/500)+000 1+1000/500)+ 2）若采用先到先服務策略，則各塊請求被服務并完成時間如下： 塊請求及被服務順序 完成時間 1000 (1+3000/500)+ 000 1+5000/500)+00 1+5500/500)+000 1+4500/500)+比這兩種磁頭調(diào)度策略，不難發(fā)現(xiàn)，采用電梯算法可節(jié)省約 18s 時間。 某磁盤傳輸速率是傳送每個 4096 字節(jié)塊 秒。若要實時播放一部片要求每小時至少傳 1節(jié)。如果我們能以最好的方式在該磁盤上安排 片的塊，能實時播放該影片嗎？如 果不能，則需要多少個該型磁盤？且應如何在這些磁盤上安排塊，才能使影片在播放時有最小的延遲？ 【解答】 如果我們按連續(xù)柱面方式安排存儲塊，這樣可忽略尋道時間和旋轉(zhuǎn)等待時間，那么，傳送 1節(jié)至少需要時間為：（ 230/ 4096） 31s，約 2 分鐘。遠小于 1 小時，所以完全可到達實時播放要求。 慮基于目錄槽變長記錄頁格式。 （ 1） 管理目錄槽的一種方法是使用最大目錄槽號，并在頁創(chuàng)建時分配目錄數(shù)組。給出贊成和反對該方法的理由。 （ 2） 建議該方法的一種改進，使得允許我們能在不移動記錄和不改變記錄 情況下，按某個字段排序記錄。 （ 3） 估算順序掃描該關(guān)系文件需要的總時間。 【解答】 （ 1） 采用最大目錄槽號方法比較簡單，但不靈活。因為這種方法很容易導致保留過多的槽或槽不夠用情況，這是因為系統(tǒng)無法預測頁中存儲記錄的長度。 （ 2）一種允許記錄按指定的字段排序的改進方案是：在頁首存儲象 結(jié)構(gòu)形式為記錄槽目錄項數(shù)組。 設我們使用 方案，有 4 個數(shù)據(jù)盤和一個冗余盤。假設塊為單字節(jié)，如果數(shù)據(jù)盤中相應的塊值如下，試給出冗余盤的塊值。 （ 1） 01010110, 11000000,00111011 和 11111011。 （ 2） 11110000， 11111000， 00111111 和 00000001。 【解答】（ 1） 01010110；（ 2） 00110110 用帶有 7 個磁盤的 方案 ,描述從下列故障中恢復所要采取的步驟 （ 1） 盤 1和盤 7。 （ 2） 盤 1和盤 4。 【解答】 （ 1）先用 2#、 3#、 5#號盤恢復 盤 1#的數(shù)據(jù)，再用 1#、 3#、 4#號盤恢復 盤 7#的數(shù)據(jù)。 （ 2）先用 2#、 3#、 5#號盤恢復 盤 1#的數(shù)據(jù)，再用 1#、 2#、 6#號盤恢復 盤 4#的數(shù)據(jù)。 第五章 數(shù)據(jù)庫 索引技術(shù) 要回答以下問題。 （ 1） 如果要頻繁進行：基于某字段值的范圍搜索；執(zhí)行插入和掃描操作，不關(guān)心記錄順序；基于特定的屬性值搜索記錄。那么，我們應分別選擇基本文件組織方式中的哪一種？ （ 2） 說明索引項的三種基本形式。 （ 3） 說明順序索引的基本概念，并指出稠密索引在哪些情況下，不需要數(shù)據(jù)文件是排序文件。說明稀疏索引的概念，稀疏索引肯定是聚集索引嗎？相應的數(shù)據(jù)文件肯定是排序文件嗎？請解釋原因。二級或二級以上索引肯定是稀疏索引嗎？為什么？ （ 4） 辨析以下概念對，說明它們之間的差異。 （ a） 聚簇文件與聚集索引； （ b） 稠密索 引與稀疏索引； （ c） 主（碼）索引與輔助索引。 【解答】 （ 1）以操作代價作為依據(jù)： 要頻繁作基于字段值的范圍搜索：應該選用排序文件作為基本的文件組織方式。 要頻繁執(zhí)行插入和掃描操作，應該選用堆文件作為基本的文件組織方式。 要頻繁作基于特定屬性值的搜索記錄，應該選用散列文件作為基本的文件組織方式。 （ 2）索引項的三種基本形式： 索引項 k*就是數(shù)據(jù)記錄本身，沒有另外單獨的索引文件。 ，有獨立的索引文件，每個索引項只能給出一個 , 有獨立的索引文件，每個索引項允許包含多 個 （ 3） 順序索引是指按索引鍵值順序來組織索引項的索引文件。 如果每個索引鍵值都至少對應有一個索引項，則稱索引為稠密索引 。在稠密索引情況下，如果每個記錄都對應有一個索引項，或在 每個索引項中存儲包含鍵值的記錄指針鏈表 ，則可以不要求數(shù)據(jù)文件是排序的。 只為搜索鍵的某些值建立索引項的索引稱為稀疏索引， 稀疏索引必須是聚集索引 。 聚集索引 是指一 個索引文件中索引項的排序方式和數(shù)據(jù)文件記錄的排序方式一致 的索引方式 ， 所以，與稀疏索引對應的數(shù)據(jù)文件一定是排序文件。 二級或二級以上索引肯定是稀疏索引，因為如 果還是像稠密索引那樣一對一地建立二級索引的話，索引項或索引文件大小沒有實質(zhì)減少，沒有什么意義。作為索引一定是排好序的，故在低級索引基礎(chǔ)上可建立更稀疏的上級索引。 （ 4） 區(qū)別聚簇文件與 聚集索引 聚簇文件：指數(shù)據(jù)文件，這種數(shù)據(jù)文件的每個頁中，都只存放同一個關(guān)系表的記錄。 聚集索引：指一種索引文件，這類 索引文件中索引項的排序方式和數(shù)據(jù)文件記錄的排序方式一致時 。雖然一個數(shù)據(jù)文件可以根據(jù)不同索引鍵建立不同索引文件，但至多只能有一個索引文件是聚集的。 稠密索引與稀疏索引（參見前一小題說明） 區(qū)別主 (碼 )索引與輔助 索引 主索引或主碼索引：指 搜索鍵恰好是主碼的索引 。因為一個關(guān)系數(shù)據(jù)文件最多只有一個主碼，所有每個關(guān)系最多也只有一個主碼索引。通常主碼索引往往也是聚集索引。主碼索引中肯定沒有重復索引項，因為主碼肯定是候選碼，沒有重復鍵。 輔助索引：非主索引的索引文件。輔助索引中通常會有重復索引項。 慮圖 示的階數(shù) m=4 的 B+樹索引。 （ 1） 標示插入數(shù)據(jù)項 9*之后的 B+樹，并指出完成該插入需要讀多少個頁和寫多少7 3 8 51 8 * 2 7 * 3 2 * 3 9 * 4 1 * 4 5 *9 1 * 9 9 *1 * 2 * 5 * 6 * 8 * 1 0 *8 1 8 3 2 4 05 0R O O * 5 8 * 7 3 * 8 0 *圖 題 圖 6 8 *9 0 9 85 1 * 5 2 * 5 6 * 6 0 *6 9 * 7 0 * 7 9 * 9 8 * 9 9 * 1 0 0 * 1 0 5 *3 0 * 3 1 *3 6 * 3 8 *3 5 4 2 5 0 6 51 0 3 0 8 0R O O 8 1 * 8 2 *4 2 * 4 3 *9 4 * 9 5 * 9 6 * 9 7 *A B I 2 I 3L 1L 2L 3L 4L 5 L 6L 7L 8圖 題 圖 個頁。 （ 2） 給出在原樹中刪除數(shù)據(jù)項 8*之后的 B+樹，并指出完成該操作需要讀多少個頁和寫多少個頁。 （ 3） 給出在 原樹中先插入數(shù)據(jù)項 46*，然后再刪除數(shù)據(jù)項 52*之后的 B+樹。 （ 4） 給出在原樹中，依次刪除 32*、 39*、 41*、 45*和 73*之后的 B+樹。 【解答】 （ 1） 由圖看出插入 9*不需要分裂，直接插入即可。 由于索引項即數(shù)據(jù)文件本身，從根結(jié)點到索引項 讀 3 個頁。只有葉結(jié)點改過，所以 寫 1 個頁 。插入后的局部圖如下： 5 08 1 8 3 2 4 08 * 9 * 1 0 *（ 2）刪除 8*后要跟前一個索引項重組，從根結(jié)點到兩個索引項要讀 4 個頁。操作完成后兩個葉結(jié)點和一個中間結(jié)點是臟頁，故要寫出 3 個頁。刪除后的局部圖： 5 06 1 8 3 2 4 06 * 1 0 *1 * 2 * 5 *(3) 可直接插入數(shù)據(jù)項 46*。刪除數(shù)據(jù)項 52*則要合并重組，操作完成后的局部圖： 4 08 1 8 3 29 1 * 9 9 *5 0 8 55 8 * 7 3 * 8 0 *4 1 * 4 5 * 4 6 *(4) 依次刪除 32*、 39*、 41*、 45*、 73*后的圖： 1 * 2 * 5 * 6 *8 1 8 5 0 7 35 2 * 5 8 *1 8 * 2 7 *8 * 1 0 * 8 0 * 9 1 * 9 9 * 慮圖 示 B+樹索引：內(nèi)節(jié)點可容納 4 個鍵值和 5 個指針；葉節(jié)點中直接存儲數(shù)據(jù)記錄，可容納 4 條記錄且相鄰葉節(jié)點之間用雙鏈連接在一起?；卮鹨韵聠栴}。 （ 1） 指出回答查詢“取搜索鍵值大于 38 的所有記錄”時，需要讀取的有關(guān)節(jié)點。 （ 2） 給出插入 109*后的 B+樹。 （ 3） 給出從原樹中刪除 81*后的 B+樹。 （ 4） 給出一個插入時會導致樹高度增加的鍵值。 （ 5） 圖中沒有詳細給出子樹 A、 B 和 C。你能推測出這些子樹的內(nèi)容和形狀嗎？ 【解答】 (1) 查詢大于 38*的所有記錄，要讀取的節(jié)點有： 2,3,5,7,2) 插入 109*后，原 點需要分裂，完成操作后的局部圖： (3) 刪除 81*后， 7 兩個節(jié)點要重組，操作完成后的局部圖如下： (4) 插入任何 65,79之間的搜索鍵值，都會分裂 點，而 是滿的，向上分裂到根結(jié)點，根結(jié)點也是滿的，就會導致高度增加一層。 (5) 關(guān)于子樹 A、 B、 C，我們可推出以下幾件事： 1） 它們都是樹高為 1 的子樹，因為它們的相鄰子樹，即以 根節(jié)點的子樹樹高都是 1； 2）子樹 A 包含的鍵值樹肯定少于 10 個，子樹 B 所包含的鍵值在范圍 10,20）之間，子樹 C 所包含的鍵值在范圍 20,30）之間； 3）每個中間節(jié)點至少會含有 3 個鍵值和 3 個指針。 定我們有一個排序文件，希望在該排序文件基礎(chǔ)上構(gòu)造一個稠密 B+樹聚集索引。 （ 1） 最簡單的方案是：掃描文件，并利用 B+樹插入算法將記錄逐個插入到樹中。指出該方案在性能和存儲利用率方面存在的問題。 （ 2） 說明如何用批量加載算法來改進以上方案。 【解答】 （ 1） 利用標準的 B+樹插入算法，逐項插入，這種方法可能代價非常昂貴，因為每個項加入都需要從根開始到達合適的葉節(jié)點。盡管在連續(xù)請求時索引層次的頁，可能仍保持在緩沖池中，但這樣的開銷可能仍然非?？捎^ ，在樹構(gòu)建過程中會經(jīng)歷大量葉節(jié)點及相關(guān)內(nèi)節(jié)點的分裂調(diào)整 。 （ 3）而采用批量加載方法的效率則要高得多，在樹的批量構(gòu)建過程中可以有效避免葉節(jié)點分裂調(diào)整，只有少量內(nèi)節(jié)點的順次分裂調(diào)整，以及與樹高 相對應的有限幾次根節(jié)點調(diào)整。批量加載構(gòu)建 B+樹的基本過程步可描述如下： 第一步，從一個關(guān)系記錄集創(chuàng)建要插入到索引的數(shù)據(jù)項 。 該步包括掃描關(guān)系記錄集，并生成和寫出相應的數(shù)據(jù)項。其代價為 (R+E)次 I/里， R 是包含記錄集的數(shù)據(jù)文件頁數(shù)， E 是包含數(shù)據(jù)項的總頁數(shù)。 第二步，排序數(shù)據(jù)項；外部排序含數(shù)據(jù)項的 E 個頁，保守估計需要 3E 次 I/分）。 第三步，從排序好的數(shù)據(jù)項中建立 B+樹索引。因為第二步中已排序數(shù)據(jù)項的數(shù)據(jù)頁，可在它們從排序步輸出時，直接調(diào)用批量加載算法依次加入到新的 B+樹 中，因此，第三步的代價只是寫出所有（內(nèi)節(jié)點）索引頁的代價。 批量加載算法的總代價為： R+4E+(B 樹索引節(jié)點數(shù) ) 慮表 示的 系示例。構(gòu)造以下幾種情況下的 4 階 B 樹，假定簡單使用溢出頁處理重復鍵值情況。要求使用比 k*約定更清晰的方式，在B+樹中標示數(shù)據(jù)項。 （ 1） 段上的稠密 B+樹索引，索引項為數(shù)據(jù)項。 （ 2） 段上的稀疏 B+樹索引，索引項為數(shù)據(jù)項。 （ 3） 段上的稠密 B+樹索引，索引項為鍵值加記錄指針。為便于問答這個問題，我們假定實際元組記錄存儲按圖中給定順序的排序文件中，每 個頁可存三個元組，前三個元組存儲在第 1 個頁的第 1/2/3 槽中，第 4/5/6 個元組存儲在第 2 個頁的第 1/2/3 槽中，。 【解答】 1 1 . 5 3 8 3 1 . . . 1 2 . 5 3 8 3 2 . . . 1 8 . 5 3 6 6 6 . . . 1 9 . 5 3 6 8 8 . . . 5 3 9 0 1 . . . 1 8 . 5 3 9 0 2 . . . 1 8 . 5 3 9 0 3 . . . 1 8 . 5 3 9 0 4 . . . 5 3 9 0 5 . . . 1 8 . 5 3 9 0 6 . . . 1 8 . 5 3 9 0 2 . . . 5 3 6 5 0 . . . 1 9 . 5 4 0 0 1 . . . 1 9 . 5 3 0 0 5 . . . 1 9 . 5 4 0 0 9 . . O O 41 . 8 : 2 . 2 : 3 . 2 : 3 . 4 : 3 . 5 : 3 . 4 : 3 . 8 : 3 . 4 : 3 . 4 : 3 . 4 : 3 . 8 : 3 . 4 : 3 . 4 : 3 . 8 : 3 . 8 : 溢 出 鏈溢 出 鏈( a ) 習 題 5 . 5 題 解 附 圖 - 1( c ) 習 題 5 . 5 題 解 附 圖 - 31 1 . 5 3 8 3 1 . . . 1 2 . 5 3 8 3 2 . . . 1 8 . 5 3 6 6 6 . . . 1 9 . 5 3 6 8 8 . . O T( b ) 習 題 5 . 5 題 解 附 圖 - 2圖 題 解附圖 （ 1）建立 的稠密索引，見圖 a） （ 2）建立 的稀疏索引，見圖 b） （ 3）建立 的稠密 B+樹索引，見圖 c） 注意，數(shù)據(jù)項未必按數(shù)據(jù)記錄同樣的順序存儲，因為它們可能按不同的順序被插入到 B+樹中。我們假設采用簡單的插入算法，首先以常規(guī)方法定位葉節(jié)點，如葉節(jié)點中已經(jīng)有同樣鍵值的數(shù)據(jù)項，就將新數(shù)據(jù)項安排到與該葉節(jié)點鏈接的溢出頁。這樣 ，可保證每個葉節(jié)點中的數(shù)據(jù)項都有不同的鍵值。這種做法會導致的一個問題是：當葉節(jié)點滿而需要分裂時，必須掃描溢出鏈以確保當一個鍵值被移動到一個新葉節(jié)點時，所有該鍵的重復項也能伴隨移動到新葉節(jié)點的溢出頁中。 另一種方案是分別維護每個鍵值的重復項溢出鏈，但考慮到每個頁的容量限制，且一個給定鍵值的重復項數(shù)可能很少，故這個方案可能導致很差的空間利用率。 于可擴展散列，請回答以下問題。 （ 1） 解釋為什么需要全局位深度和局部位深度。 （ 2） 在一個引發(fā)目錄項翻倍的插入后，有多少個桶恰好只有一個目錄項指向它？如果從這些桶中刪除 一個項，那么目錄項數(shù)是否會發(fā)生變化？請給出簡要解釋。 （ 3） 翻倍目錄項時，我們需要檢查所有局部位深度等于全局位深度的桶嗎？ （ 4） 對檢索一個給定鍵值記錄，可擴展散列能否保證只用 1 次磁盤 I/O 完成？ （ 5） 如果散列函數(shù)在數(shù)據(jù)項上嚴重偏斜，那么，關(guān)于桶目錄大小和桶空間利用率方面，你能得出什么結(jié)論？ （ 6） 對相同數(shù)據(jù)項，給出一個線性散列方法組織存儲需要的總頁數(shù)多于可擴展散列存儲方法的具體例子。 【解答】 （ 1） 可擴展散列允許根據(jù)插入或刪除而引起的數(shù)據(jù)項數(shù)目變化，動態(tài)調(diào)整目錄項的大小。一旦目錄項大小變化（翻倍增加或翻倍縮小），應用到搜索鍵 值的散列函數(shù)值需保留的有效位數(shù)也要隨之變化。擴展散列中用全局位深度（ 定散列函數(shù)值需保留的有效位數(shù)。 目錄大小的增加并不會導致每個新目錄項創(chuàng)建新數(shù)據(jù)桶。目錄項翻倍增加時，所有新目錄項都與對應的老目錄項共享相同的數(shù)據(jù)桶。當一個被兩個或更多目錄項所共享的數(shù)據(jù)桶需要分裂時，并不會導致目錄項翻倍增加。這意味著我們需要知道每個桶是否被兩個或多個目錄項共享。這個信息由局部位深度 (示。 （ 2）有且只有兩個桶是這種情況（只有一個指向它的目錄項），這是因為導致目錄翻倍哪個新插入項對應桶必須分裂為兩個桶。如果恰好有一個數(shù)據(jù)項要從這兩個桶中的某個桶刪除，那么可能會導致兩個桶合并，但是否一定進行桶合并，取決于具體的算法策略。如果算法只合并處理空桶，就不一定會發(fā)生桶合并情況；而如果算法策略是只要可能就合并桶，則就會導致插入翻倍目錄的逆操作不僅會導致桶合并，而且會導致目錄減半壓縮。 （ 3）不需要。因為僅當一個桶需要分裂時，才需要檢查該桶的局部位深度。 （ 4）可擴展散列并不保證僅用 1次磁盤存取來完成記錄檢索。當目錄文件不在主存，或數(shù)據(jù)桶中存儲的只是記錄指針或記錄指針列表時，都可能需要 額外的 I/O。 （ 5） 如果散列函數(shù)在數(shù)據(jù)項上嚴重偏斜，那么，桶目錄大小和桶空間利用率都會很差。 （ 6） 對于以下鍵值序列： 8, 16, 24, 32, 40, 48, 56, 64, 128, 7, 15, 31, 63, 3, 1, 10, 4。 可擴展散列需要 9個頁（包括目錄頁），而線性散列為 10個頁。具體索引結(jié)構(gòu)可參見習題題解附圖。 慮圖 示的可擴展散列索引文件。回答以下問題。 （ 1） 從圖中，我們能否看出哪個是最后插入的項，為什么？ 0 0 00 0 10 1 00 1 13數(shù) 據(jù) 頁 ( 桶 )目 錄1 0 01 0 11 1 01 1 14 * 1 2 * 2 0 * 3 6 *桶 A 236 4 * 1 6 *桶 5 * 2 1 *桶 *桶 * 7 * 5 1 *桶 * 4 4 *9 * 2 5 * 5 *1 0 *3 1 * 1 5 * 7 * 3 *L e v e l = 0 , N = 4N e x t = 0數(shù) 據(jù) 文 件 桶 的 存 儲 頁h 00 00 11 01 1h 10 0 00 0 10 1 00 1 1圖 題 圖 圖 題 0 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 11 0 0 01 0 0 11 0 1 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 141 6 3 2 4 8 6 44121 2 8桶 1 02桶 43桶 A 28 2 4 4 0 5 64桶 A 37 1 5 3 1 6 33桶 D 21 6 3 2 4 8 6 4 8 2 4 4 0 5 6 桶 811 03 7 1 5 3 146 3N e x t = 30 0 0 0 00 0 1 0 10 1 0 1 00 1 1 1 11 0 0 0 01 1 0 1 01 0 1 0 1h 1 h 0L e v e l = 1桶 桶 2桶 C 2桶 D 2（ a ) 習 題 5 . 6 題 解 附 圖 - 1 ( b ) 習 題 5 . 6 題 解 附 圖 - 2 圖 題 解附圖 （ 2） 若已知到目前為止沒有刪除發(fā)生，那么，從圖中我們能 否看出哪個是最后插入的項？ （ 3） 若已知到目前為止沒有刪除發(fā)生，那么，從圖中我們能否看出哪個是導致桶分裂的最后插入項？ （ 4） 給出或標示插入 68*后的索引文件結(jié)構(gòu)圖。 （ 5） 給出或標示插入 17*、 69*后的索引文件結(jié)構(gòu)圖。 （ 6） 給出或標識刪除 21*后的索引文件結(jié)構(gòu)圖。 【解答】 （ 1） 不能，它可能是索引中的任何數(shù)據(jù)項之一。 從當前已有索引項中，我們通?？偰苷页龆鄠€以某個特別鍵作為最后插入項的插入刪除序列。例如，考慮數(shù)據(jù)項 16，若先依次插入數(shù)據(jù)項 1 5 21 10 15 7 51 4 12 36 64 8 24 56 16（最后插入項） ，然后再依次刪除 56、 24 和 8 就會導致圖 可擴展索引結(jié)構(gòu)布局。顯然，對以任何一數(shù)據(jù)項做最后插入項，我們都總能找到一個或多個插入刪除序列。 （ 2） 雖然我們無法斷定那個是最后的插入項，但可以斷定最后一個插入項肯定沒有導致桶分裂，因為已分裂的桶只有 A，且 A 與 中數(shù)據(jù)項總數(shù)為 6，而不是 5。 （ 3） 首先，導致桶分裂的最后插入項不可能在桶 C 中，因為 C 只能與跟它局部位深度也是 2 的 B 或 D 構(gòu)成分裂映象對，且 C 與 B，或 C 與 D 的數(shù)據(jù)項數(shù)和都為 4，少于最少要求的項數(shù) 5。 如果開始時全局位深度為 1，且還沒有桶 情況下，那么，導致 桶分裂的最后插入項應在 B 與 D 桶中，因為 D 是 B 位深度相同（均為 2），且 D 與 B 桶的總數(shù)據(jù)項數(shù)為 6（超過 5）。 綜合以上分析，我們可得出結(jié)論：如果開始時全局位深度位 2，且沒有發(fā)生過刪除操作，那么導致桶分裂的最后插入項肯定在 A 與 中。 （ 4） 插入 68*后的索引文件結(jié)構(gòu)圖見：圖 a） 桶 桶 桶 A 2桶 A 3（ a） 習題 解附圖 桶 桶 A 2桶 B 2（ b）習題 解附圖 題 解附圖 （ 5） 插入 17*、 69*后的索引文件結(jié)構(gòu)圖圖見：圖 b） （ 6） 刪除 21*后的索引文件結(jié)構(gòu)圖見：圖 c） 桶 桶 桶 A 2圖 c）習題 解附圖 于可線性散列，請回答以下問題。 （ 1） 如果允許使用溢出頁，線性散列如何保證提供只比 1 多一點（比如 等值搜索平均代價。 （ 2） 對共包含有 N 個數(shù)據(jù)項（即 N 個記錄）、每頁可存儲 P 個記錄的情況，如果采用線性散列方法來組織存儲，且假設頁的平均利用率為 80%，那么，等值搜索的最壞代價是多少？ （ 3） 如果散列函數(shù)在數(shù)據(jù)項上 嚴重偏斜，那么，在數(shù)據(jù)頁的空間利用率方面，你能得出什么結(jié)論？ （ 4） 對相同數(shù)據(jù)項，給出一個線性散列方法組織存儲需要的總頁數(shù)少于可擴展散列方法的具體例子。 【解答】 （ 1） 在一個輪中，線性散列所有的桶將按順序依次分裂一次。如果 散列函數(shù)對散列鍵分布均勻 ，那么，這種在一個輪中的輪流分裂方式，一般都能導致鍵值在所有桶中的重新分配。即使一個桶有溢出頁，經(jīng)這樣的一輪分裂下來，每個桶增加的溢出頁長度一般不會超過 1（如果散列函數(shù)分布很好的話）。 （ 2） N / (這是當散列函數(shù)極度偏斜，所有鍵都被映射到同一個桶的情況。另外，這里占 有率，會影響需要的存儲頁數(shù)。 （ 3） 參考習題 )附圖。如果系列數(shù)據(jù)的鍵值為 2i, ik，那么，通過選擇適當?shù)?k 值，會導致所有的數(shù)據(jù)項都被映射到桶 0 中。若規(guī)定每次當需要增加一個溢出頁到桶 0 時，都會導致桶分裂。那么，這是空間利用率，還不到 50。 （ 4） 考慮如下鍵值序列： 0, 4, 1, 5, 2, 6, 3, 7。且兩者的散列函數(shù)相同，且每個頁都可容納 4 個記錄。在這種情況下，可擴展散列需要 4 個數(shù)據(jù)頁和 1 個目錄頁，而線性散列只需要正好 4 個頁。 慮一個包含有 1,000,000 個元組的關(guān)系 R(a, b, c, d)。已知：每頁可容納 10個元組； R 按堆文件組織、記錄無序。假設屬性 a 是 R 的一個候選鍵，取值范圍 0 999,999。若有三種可能的存取路徑： 1）掃描堆文件 R； 2) 利用 的 B+樹索引； 3）利用 的散列索引。那么，對以下給定的每個查詢，指明具有最小查詢處理代價應選用的存取方法。 （ 1） 檢索 R 的所有元組； （ 2） 檢索滿足 a(T)1/2以保證可按兩階段完成排序，相應算法代價都為 M+2T 次 I/基于散列算法要求可用緩存頁數(shù) B 足夠容納最大的劃分 (子桶 )，在劃分均勻情況下，也是要求B (T)1/2。但若散列劃分不均勻，則可能需要比 (T)1/2 更大一些的 B 值 。散列算法代價也是 M+2T 次 I/慮到 統(tǒng)有優(yōu)化得很好的排序工具 (函數(shù) )、排序方法的投影結(jié)果集是排序的、散列可能存在偏斜和 代價等因素，選用排序方法似乎更好些。 （ 6） 對等值連接，散列索引 通常 能提供很好的性能 。假 設兩個待連接關(guān)系的大小分別為 M、 N 個頁。當緩存較大 B (f*,N)1/2（這里， f 為主存散列因子）時，散列連接代價只有（ M+N） *3 次 I/果還有更大的緩存可能，除了實現(xiàn)正常散列算法需要的主存頁數(shù)外，還有額外緩存能駐留存儲 1 個甚至更多個桶，那么，采用混合散列連接還可以大幅度地改善性能。 B (,N)1/2 時，改進的排序 M+N） *3 次 I/排序 一個額外的優(yōu)勢可產(chǎn)生 按連接鍵 排序的 輸出 結(jié)果 。當主存很大時，用散列連接效果通常會更好，但當需要 基于連接屬性的排序輸出，也可能選擇排序 當可用主存很少，排序需要多個階段，散列需要遞歸進行多次子桶劃分時，排序 另外，對非等值連接，不能用散列連接算法，我們 只能選用排序 索引嵌入循環(huán)等連接實現(xiàn)方法。 （ 7） 混合索引連接能顯著改善性能 。例如， 通過在劃分階段（而不是將它留到探測階段）就完成首個桶的元組匹配比較， 這能節(jié)省掉第一個分區(qū)的讀 /寫代價。 （ 8） 全關(guān)系算法指操作施加于整個關(guān)系上而非施加于單個元組上，關(guān)系中的多個不同元組可能會共同影響一個結(jié)果元組，或已處理過 的元組對隨后的元組處理有影響。如果希望一趟完成全關(guān)系算法，那么要求主存比較大。對于消除重復或分組聚合等一元操作，要求能容納得下整個運算結(jié)果。對集合并交差，或連接等 二元操作符 ，要求能至少能容納整個較小輸入關(guān)系 。 （ 9） 略。 （ 10） 緩沖區(qū)置換策略 影響 連接性能的一個典型例子是：在簡單的嵌入循環(huán)連接時，使用 當 關(guān)系表不能全部載入主存 時 ，緩沖池置換策略是非常關(guān)鍵的。不妨假設我們有 M 個緩存頁，而其中 N 個已被第一個關(guān)系占用，若第二個關(guān)系大小為 ，這樣， 除了 P 個頁外，第二個關(guān)系的所有頁都能被讀入緩沖池。由于我們必 須多次掃描第二個關(guān)系，這 時， 若使用 當我們重新需要某個頁時，這個頁因為很長時間沒有使用，可能早已被替換 移出 了，因此，可能每個頁都需要重新讀 磁 盤。而若是采用 總先替換最近用過的頁，長時間未用的那些老頁可能一直留在緩沖 池 ，這樣第二次掃表內(nèi)層關(guān)系時，開始的 哪些 頁大都能在緩沖池中找到。每次掃描內(nèi)層關(guān)系（第二關(guān)系），可能只需要重復讀 頁。 考慮一個每頁 10 個記錄、共有 5,000,000 條記錄的關(guān)系 R(a,b,c,d)。假設 值從 0 4999,999，且 R 數(shù)據(jù)文件基于 序。若對 R 的元組，有三種可用存取方法： a) 直接掃描排序文件 R； b)利用 的聚集B+樹索引； c)利用 的線性散列索引。試對每個以下關(guān)系代數(shù)查詢： （ 1） 00 00 +樹索引，則該索引是否能為排序提供更便宜的代價？如果索引是非聚集的，或是一個散列索引，則結(jié)果又如何？ 【解答】 （ 1） B=10, 初始階段將產(chǎn)生 5000個排序子表，每個子表長度為 10個頁； 讀入 10， 000個頁，投影后寫出 5000個頁，需要總代價 =10000 5000 15000。 （ 2） 為合并 1000 個子表，我們還需另 外 3個 歸并 階段，代價為 2*3*5000=30000I/ 3） 可 合理假設每頁可存儲 10*4 個 性， B+樹至少會有 100,000/(10*4)=2500個葉節(jié)點。因此，掃描 B+樹本身至少需要 2500I/價。利用 的聚集 B+樹索引掃描關(guān)系的代價為 12500（超過簡單堆文件掃描的 10000次）。利用 能會超過 2500 100000,達到 2500 100000*10次 （假定每頁元組數(shù) 10)。如果散列索引是聚集的且散列桶中直接存儲元組，則使用散列索引 檢索并完成排序代價可能會很好。 （ 4） 利用 +樹索引，掃描代價為 12500。因為 描 B+樹檢索出的 對不會有重復，不需要在進行排序消除重復，因此，產(chǎn)生查詢結(jié)果的總估計代價也是 12500,代價遠遠低于簡單排序歸并的 (15000+30000)次I/非聚集 B+樹檢索所有目標元組的代價