4-9章習題解答_第1頁
4-9章習題解答_第2頁
4-9章習題解答_第3頁
4-9章習題解答_第4頁
4-9章習題解答_第5頁
已閱讀5頁,還剩48頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

第 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+樹檢索所有目標元組的代價

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論