【正文】 B+樹，并指出完成該插入需要讀多少個(gè)頁和寫多少個(gè)頁。主碼索引中肯定沒有重復(fù)索引項(xiàng)，因?yàn)橹鞔a肯定是候選碼，沒有重復(fù)鍵。 稠密索引與稀疏索引（參見前一小題說明）216。 區(qū)別聚簇文件與聚集索引 聚簇文件：指數(shù)據(jù)文件，這種數(shù)據(jù)文件的每個(gè)頁中，都只存放同一個(gè)關(guān)系表的記錄。聚集索引是指一個(gè)索引文件中索引項(xiàng)的排序方式和數(shù)據(jù)文件記錄的排序方式一致的索引方式， 所以，與稀疏索引對(duì)應(yīng)的數(shù)據(jù)文件一定是排序文件。k, rid，有獨(dú)立的索引文件，每個(gè)索引項(xiàng)只能給出一個(gè)rid.k,ridlist, 有獨(dú)立的索引文件，每個(gè)索引項(xiàng)允許包含多個(gè)rid.（3）① 順序索引是指按索引鍵值順序來組織索引項(xiàng)的索引文件?！窘獯稹浚?）以操作代價(jià)作為依據(jù)：要頻繁作基于字段值的范圍搜索：應(yīng)該選用排序文件作為基本的文件組織方式。（3） ①說明順序索引的基本概念，并指出稠密索引在哪些情況下，不需要數(shù)據(jù)文件是排序文件。（2）先用5號(hào)盤恢復(fù) 盤1的數(shù)據(jù)，再用6號(hào)盤恢復(fù) 盤4的數(shù)據(jù)。（2） 11110000，11111000，00111111和00000001。（2）一種允許記錄按指定的字段排序的改進(jìn)方案是：在頁首存儲(chǔ)象頁內(nèi)邏輯記錄號(hào),記錄偏移地址結(jié)構(gòu)形式為記錄槽目錄項(xiàng)數(shù)組。（2） 建議該方法的一種改進(jìn)，使得允許我們能在不移動(dòng)記錄和不改變記錄rids的情況下，按某個(gè)字段排序記錄。遠(yuǎn)小于1小時(shí)，所以完全可到達(dá)實(shí)時(shí)播放要求。塊請(qǐng)求及被服務(wù)順序完成時(shí)間1000(1+3000/500)+=500+(1+500/500)+=5000+(1+4500/500)+=6000+(1+1000/500)+=（2）若采用先到先服務(wù)策略，則各塊請(qǐng)求被服務(wù)并完成時(shí)間如下：塊請(qǐng)求及被服務(wù)順序完成時(shí)間1000(1+3000/500)+ =6000+(1+5000/500)+=500+(1+5500/500)+=5000+(1+4500/500)+=對(duì)比這兩種磁頭調(diào)度策略，不難發(fā)現(xiàn)，采用電梯算法可節(jié)省約18s時(shí)間。試分別計(jì)算下列兩種情況下，服務(wù)完這些請(qǐng)求需要的時(shí)間。請(qǐng)回答關(guān)于該磁盤的以下問題：（1） 磁盤的總?cè)萘渴嵌嗌?？?） 最大尋道時(shí)間和最大旋轉(zhuǎn)等待時(shí)間分別為多少？（3） 如果一個(gè)塊是16,384字節(jié)（即32扇區(qū)），那么，一個(gè)塊的傳輸時(shí)間是多少？【解答】（1）磁盤總?cè)萘浚?盤面數(shù)*磁道數(shù)*扇區(qū)數(shù)*字節(jié)數(shù)=10*10000*1000*512B=（2）最大尋道時(shí)間＝磁頭跨越所有磁道時(shí)間=1+*9999 ≈ 2ms最大的旋轉(zhuǎn)等待時(shí)間＝磁盤旋轉(zhuǎn)一周的時(shí)間= 60/10,000s = 6ms（3）一個(gè)塊（含32個(gè)扇區(qū)amp。（4）旋轉(zhuǎn)傳輸1個(gè)塊的時(shí)間=讀兩個(gè)扇區(qū)所用的時(shí)間=（60/5400）*（2/50）≈ ms傳輸一個(gè)塊的時(shí)間= 尋道時(shí)間＋旋轉(zhuǎn)延遲時(shí)間＋傳輸時(shí)間=10ms++=16ms ，若磁盤塊大小為1,024字節(jié)。（2） 如果磁盤轉(zhuǎn)速為5,400轉(zhuǎn)/分鐘，計(jì)算磁盤的最大旋轉(zhuǎn)延遲和平均旋轉(zhuǎn)延遲時(shí)間。（9） 連續(xù)槽的頁組織格式和基于目錄槽的頁組織格式（）。（7） 假設(shè)A塊、B 塊存儲(chǔ)在磁盤相鄰的位置上。（6） 與OS 緩存管理相比，DBMS 緩沖區(qū)管理器有以下幾個(gè)特別功能特性：a) 因?yàn)榕c一般應(yīng)用相比， DMBS更容易準(zhǔn)確預(yù)測(cè)磁盤頁存取順序。拴住一個(gè)能為高層DBMS軟件保證緩沖區(qū)管理器不會(huì)將該頁從緩沖池移除，即其它文件頁不會(huì)被讀入該被閂頁所占據(jù)的頁框。n 返回包含請(qǐng)求頁的frame地址給請(qǐng)求者。（3） 緩沖區(qū)管理器執(zhí)行讀頁請(qǐng)求的基本過程如下： n 檢查DB緩沖池中是否存在該請(qǐng)求頁，如果該頁不在DB緩沖池中，則進(jìn)一步執(zhí)行以下一些操作。雖然在輔存中嚴(yán)格按排序順序先后安排文件中記錄存儲(chǔ)，能顯著提高記錄集檢索性能，但這樣做的維護(hù)代價(jià)太大，DB系統(tǒng)一般并不這種做，通常是指針把記錄按順序鏈接起來。下一次同一持久化指針再次被解引用時(shí)，就可以直接使用內(nèi)存引用，從而可避免重復(fù)轉(zhuǎn)換內(nèi)存地址的過程開銷。與內(nèi)存指針解引用相比，即使轉(zhuǎn)換表中有映射項(xiàng)，通過轉(zhuǎn)換表實(shí)現(xiàn)解引用仍是一個(gè)慢過程。根據(jù)給定的指針或地址尋找目標(biāo)對(duì)象的過程，稱為解引用。這時(shí)，我們?nèi)匀豢稍诟拍钌险J(rèn)為每個(gè)關(guān)系被存儲(chǔ)在一個(gè)“虛擬文件”中。n 完全自己來管理磁盤。（12） 描述兩種可能的頁格式，說明它們優(yōu)缺點(diǎn)和適用場(chǎng)合。（3） 如果有一個(gè)大文件需要頻繁執(zhí)行順序掃描，那么，為該文件選擇哪種頁存儲(chǔ)方式最合適？（4） 分別描述持久化指針解引用(dereference)和指針混寫的這兩個(gè)基本過程，它們之間有何聯(lián)系？ （5） 說明排序文件中的記錄及頁的基本存儲(chǔ)組織方式。第4章 數(shù)據(jù)存儲(chǔ)與組織管理 簡(jiǎn)要回答以下問題。（6） 解釋緩沖區(qū)管理器處理一個(gè)讀頁請(qǐng)求的過程?！窘獯稹浚?）磁盤空間管理器支持以頁(page)為單位的數(shù)據(jù)管理，隱藏了下層硬件（甚至包括OS文件管理）的細(xì)節(jié)，且允許高層軟件認(rèn)為DB 數(shù)據(jù)是一系列以頁為單位的磁盤數(shù)據(jù)集合，是DBMS 體系結(jié)構(gòu)中最低層的軟件模塊。（2）通過磁盤空間管理器，可將DB中的“關(guān)系”映射到 “關(guān)系數(shù)據(jù)文件”，這種“文件”既可能是實(shí)際的OS文件，也可能只是一個(gè)虛擬的OS文件。（3）這時(shí)選用堆文件的頁存儲(chǔ)方式最合適。給定一個(gè)內(nèi)存指針，查找對(duì)象本質(zhì)上只是對(duì)內(nèi)存單元的一個(gè)引用（C語法：*指針名）。指針混寫是一種減少定位已在內(nèi)存中持久對(duì)象所需代價(jià)的方法。顯然，指針混寫包含了持久化指針解引用過程，但前者比后者多了一個(gè)在主存中同一位置來回修改“持久化指?針內(nèi)存指針”過程。刪除記錄時(shí)僅做標(biāo)記并留下空位，暫不移動(dòng)其它記錄；而在插入時(shí)，相應(yīng)位置即使沒有空位，也暫時(shí)不移動(dòng)其它記錄來騰出位置，而是引入溢出頁。n 基于置換策略，選擇一個(gè)可被置換的frame，將該frame的pin_count計(jì)數(shù)加1。如果被請(qǐng)求頁位于緩沖池但未被閂住(pinned)，那么該頁不會(huì)被替換，即沒有新頁可被讀入該頁所占據(jù)的頁框。一般有緩沖區(qū)管理器具體執(zhí)行pin/unpin頁，但頁請(qǐng)求者有責(zé)任通知緩沖區(qū)管理器unpin一個(gè)不再用的頁。所以，DBMS緩沖區(qū)管理器通常能更好、更靈活地選擇合適的頁置換策略，或采用一些特別的、適合于DB環(huán)境的特殊管理措施。系統(tǒng)預(yù)計(jì)或猜測(cè)到A 和B 兩塊可能會(huì)先后同時(shí)被訪問，故當(dāng)A塊需要被讀入主存時(shí)，系統(tǒng)順帶把B塊也讀入主存緩沖區(qū)。 考慮一個(gè)磁盤：它有5個(gè)雙面盤片，每個(gè)盤面2,000個(gè)磁道，每個(gè)磁道50個(gè)扇區(qū)，每個(gè)扇區(qū)512字節(jié)。（3） 在252048和51,200三個(gè)值中，那些值是可能的有效塊大??？為什么？（4） 如果每個(gè)磁盤塊大小占2個(gè)扇區(qū)，試估算傳輸一個(gè)塊的平均時(shí)間。假設(shè)有一個(gè)包含100,000個(gè)元組、每個(gè)元組100字節(jié)的關(guān)系文件存儲(chǔ)在該磁盤上，并規(guī)定記錄不允許跨塊存儲(chǔ)。 31個(gè)間隙）所占圓弧度=32**(360/1000)+ 31**(360/1000)=*360/1000旋轉(zhuǎn)通過這樣大小弧長(zhǎng)需時(shí)間=((*360/1000) /360 )*6ms ≈平均尋道時(shí)間，取1/3的最大尋道時(shí)間 ＝ 2ms/3 = 平均旋轉(zhuǎn)等待時(shí)間，取1/2的最大旋轉(zhuǎn)等待時(shí)間 ＝6ms/2=3ms 所以，傳輸一個(gè)塊的時(shí)間＝ ＋ 3ms ＋ ≈ 假設(shè)我們正在為某磁盤調(diào)度I/O請(qǐng)求，磁頭的初始位置在磁道4000。（1） 采用電梯算法，先從任何方向開始移動(dòng)都是可能的。 。 考慮基于目錄槽變長(zhǎng)記錄頁格式。（3） 估算順序掃描該關(guān)系文件需要的總時(shí)間。 假設(shè)我們使用RAID4級(jí)方案，有4個(gè)數(shù)據(jù)盤和一個(gè)冗余盤?！窘獯稹浚?）01010110；（2）00110110 采用帶有7個(gè)磁盤的RAID6級(jí)方案,描述從下列故障中恢復(fù)所要采取的步驟 （1） 盤1＃和盤7＃。第五章 數(shù)據(jù)庫索引技術(shù) 簡(jiǎn)要回答以下問題。②說明稀疏索引的概念，稀疏索引肯定是聚集索引嗎？相應(yīng)的數(shù)據(jù)文件肯定是排序文件嗎？請(qǐng)解釋原因。要頻繁執(zhí)行插入和掃描操作，應(yīng)該選用堆文件作為基本的文件組織方式。如果每個(gè)索引鍵值都至少對(duì)應(yīng)有一個(gè)索引項(xiàng)，則稱索引為稠密索引。③ 二級(jí)或二級(jí)以上索引肯定是稀疏索引，因?yàn)槿绻€是像稠密索引那樣一對(duì)一地建立二級(jí)索引的話，索引項(xiàng)或索引文件大小沒有實(shí)質(zhì)減少，沒有什么意義。 聚集索引：指一種索引文件，這類索引文件中索引項(xiàng)的排序方式和數(shù)據(jù)文件記錄的排序方式一致時(shí)。 區(qū)別主(碼)索引與輔助索引 主索引或主碼索引：指搜索鍵恰好是主碼的索引。 輔助索引：非主索引的索引文件。（2） 給出在原樹中刪除數(shù)據(jù)項(xiàng)8*之后的B+樹，并指出完成該操作需要讀多少個(gè)頁和寫多少個(gè)頁。由于索引項(xiàng)即數(shù)據(jù)文件本身，從根結(jié)點(diǎn)到索引項(xiàng)讀3個(gè)頁。刪除后的局部圖：(3) 可直接插入數(shù)據(jù)項(xiàng)46*。（2） 給出插入109*后的B+樹。你能推測(cè)出這些子樹的內(nèi)容和形狀嗎？【解答】(1) 查詢大于38*的所有記錄，要讀取的節(jié)點(diǎn)有：I1,I2,L2,L3,L4,L5,L6,L7,L8(2) 插入109*后，原L8節(jié)點(diǎn)需要分裂，完成操作后的局部圖：(3) 刪除81*后，L6,L7兩個(gè)節(jié)點(diǎn)要重組，操作完成后的局部圖如下：(4) 插入任何[65,79]之間的搜索鍵值，都會(huì)分裂L5節(jié)點(diǎn)，而I2也是滿的，向上分裂到根結(jié)點(diǎn)，根結(jié)點(diǎn)也是滿的，就會(huì)導(dǎo)致高度增加一層。指出該方案在性能和存儲(chǔ)利用率方面存在的問題。（3）而采用批量加載方法的效率則要高得多，在樹的批量構(gòu)建過程中可以有效避免葉節(jié)點(diǎn)分裂調(diào)整，只有少量?jī)?nèi)節(jié)點(diǎn)的順次分裂調(diào)整，以及與樹高相對(duì)應(yīng)的有限幾次根節(jié)點(diǎn)調(diào)整。 n 第二步，排序數(shù)據(jù)項(xiàng)；外部排序含數(shù)據(jù)項(xiàng)的E 個(gè)頁，保守估計(jì)需要3E次 I/Os（）。構(gòu)造以下幾種情況下的4階B樹，假定簡(jiǎn)單使用溢出頁處理重復(fù)鍵值情況。（3） gpa字段上的稠密B+樹索引，索引項(xiàng)為鍵值加記錄指針。這樣，可保證每個(gè)葉節(jié)點(diǎn)中的數(shù)據(jù)項(xiàng)都有不同的鍵值。（1） 解釋為什么需要全局位深度和局部位深度。一旦目錄項(xiàng)大小變化（翻倍增加或翻倍縮?。?，應(yīng)用到搜索鍵值的散列函數(shù)值需保留的有效位數(shù)也要隨之變化。當(dāng)一個(gè)被兩個(gè)或更多目錄項(xiàng)所共享的數(shù)據(jù)桶需要分裂時(shí)，并不會(huì)導(dǎo)致目錄項(xiàng)翻倍增加。如果恰好有一個(gè)數(shù)據(jù)項(xiàng)要從這兩個(gè)桶中的某個(gè)桶刪除，那么可能會(huì)導(dǎo)致兩個(gè)桶合并，但是否一定進(jìn)行桶合并，取決于具體的算法策略。（4）可擴(kuò)展散列并不保證僅用1次磁盤存取來完成記錄檢索。 可擴(kuò)展散列需要9個(gè)頁（包括目錄頁），而線性散列為10個(gè)頁。 （1） 從圖中，我們能否看出哪個(gè)是最后插入的項(xiàng)，為什么？（2） 若已知到目前為止沒有刪除發(fā)生，那么，從圖中我們能否看出哪個(gè)是最后插入的項(xiàng)？（3） 若已知到目前為止沒有刪除發(fā)生，那么，從圖中我們能否看出哪個(gè)是導(dǎo)致桶分裂的最后插入項(xiàng)？（4） 給出或標(biāo)示插入68*后的索引文件結(jié)構(gòu)圖。從當(dāng)前已有索引項(xiàng)中，我們通?？偰苷页龆鄠€(gè)以某個(gè)特別鍵作為最后插入項(xiàng)的插入刪除序列。（3） 首先，導(dǎo)致桶分裂的最后插入項(xiàng)不可能在桶C中，因?yàn)镃只能與跟它局部位深度也是2的B或D構(gòu)成分裂映象對(duì)，且C與B，或C與D的數(shù)據(jù)項(xiàng)數(shù)和都為4，少于最少要求的項(xiàng)數(shù)5。（1） 如果允許使用溢出頁，線性散列如何保證提供只比1多一點(diǎn)（）的等值搜索平均代價(jià)。即使一個(gè)桶有溢出頁，經(jīng)這樣的一輪分裂下來，每個(gè)桶增加的溢出頁長(zhǎng)度一般不會(huì)超過1（如果散列函數(shù)分布很好的話）。（3） (6)附圖。（4） 考慮如下鍵值序列： 0, 4, 1, 5, 2, 6, 3, 7。已知：每頁可容納10個(gè)元組；R按堆文件組織、記錄無序。（1） 檢索R的所有元組；（2） 檢索滿足a50的所有元組；（3） 找a＝50的所有元組。因此，選用B+樹索引是最理想的?！窘獯稹浚?）針對(duì)屬性a不是候選鍵的情況，檢索R所有元組是一樣的，掃描堆文件是最好的方式。（2）針對(duì)R是基于排序文件的的情況，由于索引是聚集的，檢索所有元組采用掃描堆文件最合理。（1） 假設(shè)有最理想的散列鍵值均勻分布，那么，在引起第一次桶分裂前，可被插入的最大數(shù)據(jù)項(xiàng)數(shù)和Next值分別是多少？請(qǐng)給出簡(jiǎn)要解釋。只要有溢出項(xiàng)發(fā)生，Next值就會(huì)變化，就會(huì)有分裂發(fā)生。（3）8項(xiàng)．首先，插入63引起第一次（也正好是第一個(gè)桶）分裂；插入41,73引起第二個(gè)桶分裂，因只有5被分到新分裂桶中，分裂后第二個(gè)桶仍是滿的。 ，給出基于可擴(kuò)展散列索引的存貯組織結(jié)構(gòu)圖。 （2）(b)所示。 （1）已知位圖編碼011000,000,01000,00100； 給出對(duì)應(yīng)的壓縮位圖編碼。作為m的函數(shù)，F(xiàn)的位圖索引有多少個(gè)字節(jié)？【解答】F的位圖索引有的字節(jié)數(shù)：1000000*m / 8 關(guān)于空間索引，簡(jiǎn)要回答以下問題。n 區(qū)域數(shù)據(jù)（region data）：區(qū)域數(shù)據(jù)是同時(shí)具有位置和邊界的空間延展。n 最鄰近點(diǎn)查詢(nearestneighbor query)：要求找出離指定點(diǎn)最近的對(duì)象。(4) B+樹索引只是一維索引，對(duì)二維或更高維空間點(diǎn)數(shù)據(jù)或區(qū)域數(shù)據(jù)查詢基本沒有作用。假設(shè)：① 每個(gè)頁可存放100個(gè)記錄點(diǎn)的數(shù)據(jù)，B樹的每個(gè)葉結(jié)點(diǎn)可容納200個(gè)鍵值－指針對(duì)；② x值落在[450,550]范圍內(nèi)的記錄點(diǎn)數(shù)約有10萬個(gè)， y也是如此；而x和y同時(shí)落在[450,550]范圍內(nèi)的記錄點(diǎn)數(shù)約有1萬個(gè)。 因此，檢索B+樹，獲得1萬個(gè)記錄指針，大約需要進(jìn)行1002次的I/O操作。（1）給出在按列表順序分別插入第4和5這些數(shù)據(jù)點(diǎn)后的網(wǎng)格文件。 對(duì)于范圍查詢，我們使用線性標(biāo)度識(shí)別要存取的網(wǎng)格目錄項(xiàng)組，然后分別檢查這組目錄項(xiàng)對(duì)應(yīng)的數(shù)據(jù)桶，來計(jì)算回答范圍查詢的結(jié)果。（1）標(biāo)示一個(gè)能插入R4，但不能插入R3的新對(duì)象邊界。（6）給出一個(gè)示例查詢，需要檢查R3和