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