【正文】 【解答】（1）由于最先到的的請求是1000， 假設(shè)磁頭向下運(yùn)動，那么，電梯調(diào)度策略的塊訪問情況如下表所示。（1） 采用電梯算法，先從任何方向開始移動都是可能的。假定調(diào)度時已經(jīng)產(chǎn)生的請求共有4個，它們所在的柱面分別為: 1000 / 6000 / 500 / 5000，它們達(dá)到的先后時序值分別為0/1/10/20。 31個間隙）所占圓弧度=32**(360/1000)+ 31**(360/1000)=*360/1000旋轉(zhuǎn)通過這樣大小弧長需時間=((*360/1000) /360 )*6ms ≈平均尋道時間，取1/3的最大尋道時間 ＝ 2ms/3 = 平均旋轉(zhuǎn)等待時間，取1/2的最大旋轉(zhuǎn)等待時間 ＝6ms/2=3ms 所以，傳輸一個塊的時間＝ ＋ 3ms ＋ ≈ 假設(shè)我們正在為某磁盤調(diào)度I/O請求，磁頭的初始位置在磁道4000。（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 *16ms=160,000ms＝（3）根據(jù)題意，可認(rèn)為讀寫一個柱面時間＝最大的旋轉(zhuǎn)延遲時間＝ 一個柱面大?。奖P面數(shù)[10]*扇區(qū)數(shù)*字節(jié)數(shù)=10*50*512 B按柱面安排連續(xù)存儲文件需要的柱面數(shù)= 100,000*100/(10*50*512)= 40 （向上取整）所以，這種情況下，順序掃描文件需總時間＝40*≈ 假設(shè)某磁盤具有以下特性：有10個盤面，每個盤面10,000個磁道；每個磁道1000個扇區(qū)，每個扇區(qū)512個字節(jié)；每個磁道20%被用于間隙；磁盤旋轉(zhuǎn)速率10,000轉(zhuǎn)/分鐘；磁頭移動n個磁道所需時間為1+。假設(shè)有一個包含100,000個元組、每個元組100字節(jié)的關(guān)系文件存儲在該磁盤上，并規(guī)定記錄不允許跨塊存儲。因此，三個值中，只有2048可能是有效塊大小。（3） 在252048和51,200三個值中，那些值是可能的有效塊大?。繛槭裁?？（4） 如果每個磁盤塊大小占2個扇區(qū)，試估算傳輸一個塊的平均時間。（1） 計算每個盤面的格式化容量和整個磁盤的格式化容量。 考慮一個磁盤：它有5個雙面盤片，每個盤面2,000個磁道，每個磁道50個扇區(qū)，每個扇區(qū)512字節(jié)。（8） 定長記錄格式和可變記錄格式（）。系統(tǒng)預(yù)計或猜測到A 和B 兩塊可能會先后同時被訪問，故當(dāng)A塊需要被讀入主存時，系統(tǒng)順帶把B塊也讀入主存緩沖區(qū)。 c) 當(dāng)決定一個頁何時被寫回磁盤時，DBMS希望或需要有更多的控制權(quán)。所以，DBMS緩沖區(qū)管理器通常能更好、更靈活地選擇合適的頁置換策略，或采用一些特別的、適合于DB環(huán)境的特殊管理措施。從磁盤讀入請求頁，同時將dirty置0，返回包含請求頁的地址給請求者。一般有緩沖區(qū)管理器具體執(zhí)行pin/unpin頁，但頁請求者有責(zé)任通知緩沖區(qū)管理器unpin一個不再用的頁。（4） 緩存頁備閂住意味著與該頁對應(yīng)的pincount0，每pin一次，pincount加1。如果被請求頁位于緩沖池但未被閂住(pinned)，那么該頁不會被替換，即沒有新頁可被讀入該頁所占據(jù)的頁框。n 從磁盤讀入新請求頁到該frame中，同時置dirty=0。n 基于置換策略，選擇一個可被置換的frame，將該frame的pin_count計數(shù)加1。另外，記錄鏈接自動隱含了頁間鏈接。刪除記錄時僅做標(biāo)記并留下空位，暫不移動其它記錄；而在插入時，相應(yīng)位置即使沒有空位，也暫時不移動其它記錄來騰出位置，而是引入溢出頁。（2） 排序文件是指按指定的鍵排序記錄集的一種文件組織。顯然，指針混寫包含了持久化指針解引用過程，但前者比后者多了一個在主存中同一位置來回修改“持久化指?針內(nèi)存指針”過程。然后，將存放該持久指針的內(nèi)存單元，直接修改為目標(biāo)對象的內(nèi)存位置指針。指針混寫是一種減少定位已在內(nèi)存中持久對象所需代價的方法。如果指針?biāo)笇ο蟛辉趦?nèi)存，則必須從磁盤把它載入，并在轉(zhuǎn)換表中添加新映射項。給定一個內(nèi)存指針，查找對象本質(zhì)上只是對內(nèi)存單元的一個引用（C語法：*指針名）。（1） 存取數(shù)據(jù)庫記錄/數(shù)據(jù)頁要用到兩種類型指針：內(nèi)存指針與數(shù)據(jù)庫地址(持久化指針)。（3）這時選用堆文件的頁存儲方式最合適。但更多的現(xiàn)代大型DB系統(tǒng)，則是把所有關(guān)系都集中存儲在一個或幾個大文件中的復(fù)雜結(jié)構(gòu)。（2）通過磁盤空間管理器，可將DB中的“關(guān)系”映射到 “關(guān)系數(shù)據(jù)文件”，這種“文件”既可能是實際的OS文件，也可能只是一個虛擬的OS文件。n 讓OS分配給DB系統(tǒng)一個或幾個大的OS文件，然后自己管理（讀/寫）這個文件?！窘獯稹浚?）磁盤空間管理器支持以頁(page)為單位的數(shù)據(jù)管理，隱藏了下層硬件（甚至包括OS文件管理）的細(xì)節(jié)，且允許高層軟件認(rèn)為DB 數(shù)據(jù)是一系列以頁為單位的磁盤數(shù)據(jù)集合，是DBMS 體系結(jié)構(gòu)中最低層的軟件模塊。（11） 描述兩種可能的記錄格式，并指明它們的優(yōu)缺點。（6） 解釋緩沖區(qū)管理器處理一個讀頁請求的過程。（2） 解釋關(guān)系數(shù)據(jù)庫系統(tǒng)中關(guān)系表與文件的關(guān)系。第4章 數(shù)據(jù)存儲與組織管理 簡要回答以下問題。（1） 描述磁盤空間管理器的主要作用，并說明它與OS文件系統(tǒng)的關(guān)系。（3） 如果有一個大文件需要頻繁執(zhí)行順序掃描，那么，為該文件選擇哪種頁存儲方式最合適？（4） 分別描述持久化指針解引用(dereference)和指針混寫的這兩個基本過程，它們之間有何聯(lián)系？ （5） 說明排序文件中的記錄及頁的基本存儲組織方式。如果被請求頁位于緩沖池但未被閂住(pinned)，那么情況會怎樣？緩沖區(qū)管理器何時寫一個磁盤頁？（7） 一個緩存頁被閂?。╞e pinned）意味著什么？一般由誰負(fù)責(zé)給緩存頁上閂，由誰負(fù)責(zé)給緩存頁解閂?（8） 當(dāng)一個頁請求發(fā)生時，如果緩沖池中所有頁都是臟頁，將會發(fā)生什么？（9） 與OS緩存管理相比，DBMS緩沖區(qū)管理器具有那些獨特的重要能力？（10） 什么是預(yù)??？解釋為什么這種策略很重要。（12） 描述兩種可能的頁格式，說明它們優(yōu)缺點和適用場合。DB系統(tǒng)的磁盤空間管理器通常按三種方式來應(yīng)用OS的文件管理功能：n 將整個DB存儲在一個或幾個磁盤文件中，調(diào)用OS功能實現(xiàn)流式文件的磁盤R/W。n 完全自己來管理磁盤。 一些小規(guī)模的DB系統(tǒng)實現(xiàn)甚至可能將關(guān)系直接存儲在單獨的OS文件中。這時，我們?nèi)匀豢稍诟拍钌险J(rèn)為每個關(guān)系被存儲在一個“虛擬文件”中。當(dāng)不需要檢索特點的記錄，而只是全文件順序掃描時，選用堆文件的頁存儲方式最合適，因為這種情況不需維護(hù)順序，插入插入與刪除操作很直接，代價較小，另外，也不需要數(shù)據(jù)本身之外的額外存儲空間和輔助索引文件。根據(jù)給定的指針或地址尋找目標(biāo)對象的過程，稱為解引用。給定一個持久化指針，解引用一個對象需要額外的步驟，即需先在“轉(zhuǎn)換表”中查找持久化指針?biāo)韺ο蟮膶嶋H內(nèi)存地址。與內(nèi)存指針解引用相比，即使轉(zhuǎn)換表中有映射項，通過轉(zhuǎn)換表實現(xiàn)解引用仍是一個慢過程。其基本思想是，當(dāng)一個主存中對象/記錄所含的持久指針第一次解引用時，這個持久指針?biāo)赶虻哪繕?biāo)對象被定位――如果它不存在內(nèi)存中，就將它載入內(nèi)存并同時在轉(zhuǎn)換表中添加一個新的映射項。下一次同一持久化指針再次被解引用時，就可以直接使用內(nèi)存引用，從而可避免重復(fù)轉(zhuǎn)換內(nèi)存地址的過程開銷。指針混寫能降低持久化化對象解引用的過程。雖然在輔存中嚴(yán)格按排序順序先后安排文件中記錄存儲，能顯著提高記錄集檢索性能，但這樣做的維護(hù)代價太大，DB系統(tǒng)一般并不這種做，通常是指針把記錄按順序鏈接起來。對排序文件，頁內(nèi)的記錄索引項或目錄項通常是嚴(yán)格按順序的。（3） 緩沖區(qū)管理器執(zhí)行讀頁請求的基本過程如下： n 檢查DB緩沖池中是否存在該請求頁，如果該頁不在DB緩沖池中，則進(jìn)一步執(zhí)行以下一些操作。n 如果該frame中原先頁被修改過（即dirty=1），則將原先頁寫回磁盤。n 返回包含請求頁的frame地址給請求者。當(dāng)一個緩存頁已被修改過(dirty位置1)，且該頁未上閂，所占據(jù)頁框需讀入新頁時，通常會觸發(fā)緩沖區(qū)管理器寫一個磁盤頁。拴住一個能為高層DBMS軟件保證緩沖區(qū)管理器不會將該頁從緩沖池移除，即其它文件頁不會被讀入該被閂頁所占據(jù)的頁框。（5） 當(dāng)一個頁請求發(fā)生時，如果緩沖池中所有的頁都是臟頁，緩沖區(qū)管理器會依據(jù)緩沖區(qū)置換策略選擇要換出frame, 并將該frame中原先的頁寫回磁盤。（6） 與OS 緩存管理相比，DBMS 緩沖區(qū)管理器有以下幾個特別功能特性：a) 因為與一般應(yīng)用相比， DMBS更容易準(zhǔn)確預(yù)測磁盤頁存取順序。 b) 因可更準(zhǔn)確預(yù)測引用模式，DBMS緩沖區(qū)管理器可以使用一些很簡單、但卻非常有效的預(yù)取策略，以有效減少多個連續(xù)頁的磁盤I/O 時間。（7） 假設(shè)A塊、B 塊存儲在磁盤相鄰的位置上。 這種方案通常可減少I/O操作時間，顯著提高DBMS系統(tǒng)性能，是DBMS優(yōu)化的一個很重要策略。（9） 連續(xù)槽的頁組織格式和基于目錄槽的頁組織格式（）。另外，假設(shè)它的平均尋道時間為10msec。（2） 如果磁盤轉(zhuǎn)速為5,400轉(zhuǎn)/分鐘，計算磁盤的最大旋轉(zhuǎn)延遲和平均旋轉(zhuǎn)延遲時間?！窘獯稹浚?）每個盤面的格式化容量＝磁道數(shù)*扇區(qū)數(shù)*字節(jié)數(shù)=2000*50*512 B≈ 49MB整個磁盤的格式化容量＝盤面數(shù)*每個盤面的容量=10*49M=490MB（2）最大的旋轉(zhuǎn)延遲時間＝磁盤旋轉(zhuǎn)一周所用的時間＝1/轉(zhuǎn)速=60/5400=平均旋轉(zhuǎn)等待時間＝最大的旋轉(zhuǎn)延遲時間/2 = （3）塊是DBMS與OS實際讀寫磁盤的基本單位，必須是扇區(qū)大小的整數(shù)倍；其次，塊大小選擇要適中，太小會導(dǎo)致I/O數(shù)增加，太大則會造成磁盤讀寫操作浪費(fèi)加大，都不利于管理。（4）旋轉(zhuǎn)傳輸1個塊的時間=讀兩個扇區(qū)所用的時間=（60/5400）*（2/50）≈ ms傳輸一個塊的時間= 尋道時間＋旋轉(zhuǎn)延遲時間＋傳輸時間=10ms++=16ms ，若磁盤塊大小為1,024字節(jié)。（1） 每個塊中可存放多少個元組？存儲整個文件需要多少個塊？（2） 估算順序掃描該關(guān)系文件需要的總時間。請回答關(guān)于該磁盤的以下問題：（1） 磁盤的總?cè)萘渴嵌嗌?？?） 最大尋道時間和最大旋轉(zhuǎn)等待時間分別為多少？（3） 如果一個塊是16,384字節(jié)（即32扇區(qū)），那么，一個塊的傳輸時間是多少？【解答】（1）磁盤總?cè)萘浚?盤面數(shù)*磁道數(shù)*扇區(qū)數(shù)*字節(jié)數(shù)=10*10000*1000*512B=（2）最大尋道時間＝磁頭跨越所有磁道時間=1+*9999 ≈ 2ms最大的旋轉(zhuǎn)等待時間＝磁盤旋轉(zhuǎn)一周的時間= 60/10,000s = 6ms（3）一個塊（含32個扇區(qū)amp。已知該磁盤尋道時間可按公式（1+移動磁道數(shù)/500）毫秒來計算。試分別計算下列兩種情況下，服務(wù)完這些請求需要的時間。（2） 采用先到先服務(wù)算法。塊請求及被服務(wù)順序完成時間1000(1+3000/500)+=500+(1+500/500)+=5000+(1+4500/500)+=6000+(1+1000/500)+=（2）若采用先到先服務(wù)策略，則各塊請求被服務(wù)并完成時間如下：塊請求及被服務(wù)順序完成時間1000(1+3000/500)+ =6000+(1+5000/500)+=500+(1+5500/500)+=5000+(1+4500/500)+=對比這兩種磁頭調(diào)度策略，不難發(fā)現(xiàn)，采用電梯算法可節(jié)省約18s時間。若要實時播放一部MPEG影片要求每小時至少傳1GB字節(jié)。遠(yuǎn)小于1小時，所以完全可到達(dá)實時播放要求。（1） 管理目錄槽的一種方法是使用最大目錄槽號，并在頁創(chuàng)建時分配目錄數(shù)組。（2） 建議該方法的一種改進(jìn)，使得允許我們能在不移動記錄和不改變記錄rids的情況下，按某個字段排序記錄。【解答】（1） 采用最大目錄槽號方法比較簡單，但不靈活。（2）一種允許記錄按指定的字段排序的改進(jìn)方案是：在頁首存儲象頁內(nèi)邏輯記錄號,記錄偏移地址結(jié)構(gòu)形式為記錄槽目錄項數(shù)組。假設(shè)塊為單字節(jié)，如果數(shù)據(jù)盤中相應(yīng)的塊值如下，試給出冗余盤的塊值。（2） 11110000，11111000，00111111和00000001。（2） 盤1＃和盤4＃。（2）先用5號盤恢復(fù) 盤1的數(shù)據(jù)，再用6號盤恢復(fù) 盤4的數(shù)據(jù)。（1） 如果要頻繁進(jìn)行：①基于某字段值的范圍搜索；②執(zhí)行插入和掃描操作，不關(guān)心記錄順序；③基于特定的屬性值搜索記錄。（3） ①說明順序索引的基本概念，并指出稠密索引在哪些情況下，不需要數(shù)據(jù)文件是排序文件。③二級或二級以上索引肯定是稀疏索引嗎？為什么？（4） 辨析以下概念對，說明它們之間的差異?！窘獯稹浚?）以操作代價作為依據(jù)：要頻繁作基于字段值的范圍搜索：應(yīng)該選用排序文件作為基本的文件組織方式。要頻繁作基于特定屬性值的搜索記錄，應(yīng)該選用散列文件作為基本的文件組織方式。k, rid，有獨立的索引文件，每個索引項只能給出一個rid.k,ridlist, 有獨立的索引文件，每個索引項允許包含多個rid.（3）① 順序索引是指按索引鍵值順序來組織索引項的索引文件。在稠密索引情況下，如果每個記錄都對應(yīng)有一個索引項，或在每個索引項中存儲包含鍵值的記錄指針鏈表，則可以不要求數(shù)據(jù)文件是排序的。聚集索引是指一個索引文件中索引項的排序方式和數(shù)據(jù)文件記錄的排序方式一致的索引方式， 所以，與稀疏索引對應(yīng)的數(shù)據(jù)文件一定是排序文件。作為索引一定是排好序的，故在低級索引基礎(chǔ)上可建立更稀疏的上級索引。 區(qū)別聚簇文件與聚集索引 聚簇文件：指數(shù)據(jù)文件，這種數(shù)據(jù)文件的每個頁中，都只存放同一個關(guān)系表的記錄。雖然一個數(shù)據(jù)文件可以根據(jù)不同索引鍵