【正文】 成排序，相應(yīng)算法代價(jià)都為M+2T次I/Os。但嵌套循環(huán)連接算法不能避免枚舉叉積結(jié)果，它只是比簡(jiǎn)單嵌套循環(huán)連接算法更快（因?yàn)榭蓽p少掃描內(nèi)層關(guān)系的次數(shù)）。因此，可避免枚舉叉積結(jié)果。對(duì)兩個(gè)大小分別為M和N個(gè)頁(yè)的關(guān)系連接，頁(yè)嵌入連接算法的代價(jià)為M+ M*N，而塊嵌入連接算法的代價(jià)為N+ M*N/(B2)，其中，B為可用的主存緩存塊數(shù)。一個(gè)主項(xiàng)是指能匹配索引的那個(gè)合取子項(xiàng)。本質(zhì)上，它指在執(zhí)行查詢賦值期間需要存取的頁(yè)數(shù)最少的那個(gè)查詢存取路徑。（10） 通過(guò)一具體例子，說(shuō)明緩沖區(qū)置換策略會(huì)影響連接算法的性能。（7） 混合散列索引連接是如何改進(jìn)基本散列連接算法的？（8） 說(shuō)明可用全關(guān)系一趟算法實(shí)現(xiàn)的一元操作符、可用全關(guān)系一趟算法實(shí)現(xiàn)的二元操作符。（2） 什么情況下可認(rèn)為一個(gè)選擇條件能匹配選擇索引？對(duì)一個(gè)給定的索引，如何來(lái)區(qū)分選擇條件中的主項(xiàng)和非主項(xiàng)？ （3） “塊嵌入連接”算法是否肯定優(yōu)于“頁(yè)嵌入連接”算法？為什么？（4） 如何理解基于索引的嵌套循環(huán)連接可避免枚舉叉積結(jié)果？塊嵌入連接和排序歸并連接能避免枚舉叉積結(jié)果嗎？（5） 從代價(jià)、主存要求等方面，比較基于排序和基于散列的消除重復(fù)算法，說(shuō)明它們的優(yōu)缺點(diǎn)。第六章 關(guān)系操作符賦值。（4）由于R12與R16同時(shí)包含在R1與R2中，所以要檢索他們兩個(gè)數(shù)據(jù)項(xiàng)時(shí)，需要同時(shí)檢索R1和 R2子樹(shù)。NEW同時(shí)包含在R1與R6中，但是對(duì)于R1能完全覆蓋NEW，所以被插入到R1中。NEW同時(shí)包含在R1與R6中，但是對(duì)于R6能完全覆蓋NEW，所以被插入到R6中。NEW包含在R4中，但不包含在R3中，所以能插入R4，但不能插入R3。（6）給出一個(gè)示例查詢，需要檢查R3和R5，但不要檢查R4（如果沒(méi)有這樣的查詢，則給出解釋說(shuō)明）。（3）標(biāo)示一個(gè)能同時(shí)包含在R1和R6，但被插入R1的新對(duì)象邊界；該對(duì)象將被存放在哪個(gè)葉節(jié)點(diǎn)？（4）若搜索某對(duì)象時(shí)需要同時(shí)檢索R1和R2子樹(shù)，試給出該對(duì)象的一個(gè)例子。（1）標(biāo)示一個(gè)能插入R4，但不能插入R3的新對(duì)象邊界。如果該頁(yè)是空的，我們就使用線性標(biāo)度計(jì)算包含給定點(diǎn)分區(qū)之所有鄰近分區(qū)，檢查這些鄰近分區(qū)數(shù)據(jù)桶中的數(shù)據(jù)點(diǎn)，來(lái)確定最鄰近點(diǎn)。 對(duì)于范圍查詢，我們使用線性標(biāo)度識(shí)別要存取的網(wǎng)格目錄項(xiàng)組，然后分別檢查這組目錄項(xiàng)對(duì)應(yīng)的數(shù)據(jù)桶，來(lái)計(jì)算回答范圍查詢的結(jié)果。【解答】（1）。（1）給出在按列表順序分別插入第4和5這些數(shù)據(jù)點(diǎn)后的網(wǎng)格文件。這通常已超過(guò)數(shù)據(jù)文件本身的所有頁(yè)。 因此，檢索B+樹(shù)，獲得1萬(wàn)個(gè)記錄指針，大約需要進(jìn)行1002次的I/O操作?！窘獯稹堪袯＋樹(shù)的根保存在主存，且葉結(jié)點(diǎn)的指針已按照查找鍵排序；訪問(wèn)每一維的10萬(wàn)個(gè)指針，需要檢查一個(gè)B樹(shù)中間層結(jié)點(diǎn)和所有包含所需指針的葉結(jié)點(diǎn)。假設(shè)：① 每個(gè)頁(yè)可存放100個(gè)記錄點(diǎn)的數(shù)據(jù)，B樹(shù)的每個(gè)葉結(jié)點(diǎn)可容納200個(gè)鍵值－指針對(duì)；② x值落在[450,550]范圍內(nèi)的記錄點(diǎn)數(shù)約有10萬(wàn)個(gè)， y也是如此；而x和y同時(shí)落在[450,550]范圍內(nèi)的記錄點(diǎn)數(shù)約有1萬(wàn)個(gè)。其它情況，空間索引對(duì)于點(diǎn)數(shù)據(jù)的檢索都要好于B+樹(shù)索引。(4) B+樹(shù)索引只是一維索引，對(duì)二維或更高維空間點(diǎn)數(shù)據(jù)或區(qū)域數(shù)據(jù)查詢基本沒(méi)有作用。這類(lèi)查詢的典型例子包括“找相互間距離不超過(guò)200公里的城市組對(duì)”，“找靠近某區(qū)域（如一個(gè)湖泊）的所有城市”。n 最鄰近點(diǎn)查詢(nearestneighbor query)：要求找出離指定點(diǎn)最近的對(duì)象。（2）空間查詢的三種主要類(lèi)型：n 范圍查詢(range queries)：。n 區(qū)域數(shù)據(jù)（region data）：區(qū)域數(shù)據(jù)是同時(shí)具有位置和邊界的空間延展。（2） 描述空間查詢的三種主要類(lèi)型。作為m的函數(shù)，F(xiàn)的位圖索引有多少個(gè)字節(jié)？【解答】F的位圖索引有的字節(jié)數(shù)：1000000*m / 8 關(guān)于空間索引，簡(jiǎn)要回答以下問(wèn)題。 （3）已知壓縮編碼 1110100100110110011011； 給出對(duì)應(yīng)的位圖編碼。 （1）已知位圖編碼011000,000,01000,00100； 給出對(duì)應(yīng)的壓縮位圖編碼?？蓴U(kuò)展散列情況比較簡(jiǎn)單，讓每個(gè)溢出就可導(dǎo)致該桶分裂。 （2）(b)所示。（1）6項(xiàng)。 ，給出基于可擴(kuò)展散列索引的存貯組織結(jié)構(gòu)圖。最后，要導(dǎo)致第四次分裂――讓第三個(gè)個(gè)桶溢出，至少還需插入4個(gè)都進(jìn)入第三個(gè)桶的記錄項(xiàng)（如18, 34, 66, 130）。（3）8項(xiàng)．首先，插入63引起第一次（也正好是第一個(gè)桶）分裂；插入41,73引起第二個(gè)桶分裂，因只有5被分到新分裂桶中，分裂后第二個(gè)桶仍是滿的。（2）由于最后一個(gè)數(shù)據(jù)頁(yè)是滿的，只要插入一個(gè)屬于該桶的記錄項(xiàng)，就會(huì)發(fā)生溢出，引發(fā)桶分裂。只要有溢出項(xiàng)發(fā)生，Next值就會(huì)變化，就會(huì)有分裂發(fā)生。（3） 假設(shè)有最理想的散列鍵均勻分布，那么，會(huì)導(dǎo)致四個(gè)桶都發(fā)生分裂的最少需要插入數(shù)據(jù)項(xiàng)數(shù)及Next值分別是多少？請(qǐng)給出簡(jiǎn)要解釋。（1） 假設(shè)有最理想的散列鍵值均勻分布，那么，在引起第一次桶分裂前，可被插入的最大數(shù)據(jù)項(xiàng)數(shù)和Next值分別是多少？請(qǐng)給出簡(jiǎn)要解釋。對(duì)于a=50的檢索采用散列索引最合理。（2）針對(duì)R是基于排序文件的的情況，由于索引是聚集的，檢索所有元組采用掃描堆文件最合理。檢索a=50的元組也一樣，即使有散列索引，但由于非聚集，讀取數(shù)據(jù)文件所用的I/O數(shù)可能與滿足條件的記錄數(shù)一樣多?！窘獯稹浚?）針對(duì)屬性a不是候選鍵的情況，檢索R所有元組是一樣的，掃描堆文件是最好的方式。所以選用散列索引最合適。因此，選用B+樹(shù)索引是最理想的。利用索引反而是浪費(fèi)存取索引項(xiàng)的代價(jià)。（1） 檢索R的所有元組；（2） 檢索滿足a50的所有元組；（3） 找a＝50的所有元組。若有三種可能的存取路徑：1）掃描堆文件R；2) +樹(shù)索引；3）。已知：每頁(yè)可容納10個(gè)元組；R按堆文件組織、記錄無(wú)序。在這種情況下，可擴(kuò)展散列需要4個(gè)數(shù)據(jù)頁(yè)和1個(gè)目錄頁(yè)，而線性散列只需要正好4個(gè)頁(yè)。（4） 考慮如下鍵值序列： 0, 4, 1, 5, 2, 6, 3, 7。若規(guī)定每次當(dāng)需要增加一個(gè)溢出頁(yè)到桶0時(shí)，都會(huì)導(dǎo)致桶分裂。（3） (6)附圖。這是當(dāng)散列函數(shù)極度偏斜，所有鍵都被映射到同一個(gè)桶的情況。即使一個(gè)桶有溢出頁(yè)，經(jīng)這樣的一輪分裂下來(lái)，每個(gè)桶增加的溢出頁(yè)長(zhǎng)度一般不會(huì)超過(guò)1（如果散列函數(shù)分布很好的話）。【解答】（1） 在一個(gè)輪中，線性散列所有的桶將按順序依次分裂一次。（1） 如果允許使用溢出頁(yè)，線性散列如何保證提供只比1多一點(diǎn)（）的等值搜索平均代價(jià)。綜合以上分析，我們可得出結(jié)論：如果開(kāi)始時(shí)全局位深度位2，且沒(méi)有發(fā)生過(guò)刪除操作，那么導(dǎo)致桶分裂的最后插入項(xiàng)肯定在A與A2桶中。（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。顯然，對(duì)以任何一數(shù)據(jù)項(xiàng)做最后插入項(xiàng)，我們都總能找到一個(gè)或多個(gè)插入刪除序列。從當(dāng)前已有索引項(xiàng)中，我們通常總能找出多個(gè)以某個(gè)特別鍵作為最后插入項(xiàng)的插入刪除序列。（6） 給出或標(biāo)識(shí)刪除21*后的索引文件結(jié)構(gòu)圖。 （1） 從圖中，我們能否看出哪個(gè)是最后插入的項(xiàng)，為什么？（2） 若已知到目前為止沒(méi)有刪除發(fā)生，那么，從圖中我們能否看出哪個(gè)是最后插入的項(xiàng)？（3） 若已知到目前為止沒(méi)有刪除發(fā)生，那么，從圖中我們能否看出哪個(gè)是導(dǎo)致桶分裂的最后插入項(xiàng)？（4） 給出或標(biāo)示插入68*后的索引文件結(jié)構(gòu)圖。 。 可擴(kuò)展散列需要9個(gè)頁(yè)（包括目錄頁(yè)），而線性散列為10個(gè)頁(yè)。（5）如果散列函數(shù)在數(shù)據(jù)項(xiàng)上嚴(yán)重偏斜，那么，桶目錄大小和桶空間利用率都會(huì)很差。（4）可擴(kuò)展散列并不保證僅用1次磁盤(pán)存取來(lái)完成記錄檢索。（3）不需要。如果恰好有一個(gè)數(shù)據(jù)項(xiàng)要從這兩個(gè)桶中的某個(gè)桶刪除，那么可能會(huì)導(dǎo)致兩個(gè)桶合并，但是否一定進(jìn)行桶合并，取決于具體的算法策略。這個(gè)信息由局部位深度(local depth)指示。當(dāng)一個(gè)被兩個(gè)或更多目錄項(xiàng)所共享的數(shù)據(jù)桶需要分裂時(shí)，并不會(huì)導(dǎo)致目錄項(xiàng)翻倍增加。目錄大小的增加并不會(huì)導(dǎo)致每個(gè)新目錄項(xiàng)創(chuàng)建新數(shù)據(jù)桶。一旦目錄項(xiàng)大小變化（翻倍增加或翻倍縮?。?，應(yīng)用到搜索鍵值的散列函數(shù)值需保留的有效位數(shù)也要隨之變化。（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è)線性散列方法組織存儲(chǔ)需要的總頁(yè)數(shù)多于可擴(kuò)展散列存儲(chǔ)方法的具體例子。（1） 解釋為什么需要全局位深度和局部位深度。另一種方案是分別維護(hù)每個(gè)鍵值的重復(fù)項(xiàng)溢出鏈，但考慮到每個(gè)頁(yè)的容量限制，且一個(gè)給定鍵值的重復(fù)項(xiàng)數(shù)可能很少，故這個(gè)方案可能導(dǎo)致很差的空間利用率。這樣，可保證每個(gè)葉節(jié)點(diǎn)中的數(shù)據(jù)項(xiàng)都有不同的鍵值?！窘獯稹?（1）建立age上的稠密索引，（a）（2）建立age上的稀疏索引，（b）（3）建立gpa上的稠密B+樹(shù)索引，（c）注意，數(shù)據(jù)項(xiàng)未必按數(shù)據(jù)記錄同樣的順序存儲(chǔ)，因?yàn)樗鼈兛赡馨床煌捻樞虮徊迦氲紹+樹(shù)中。（3） gpa字段上的稠密B+樹(shù)索引，索引項(xiàng)為鍵值加記錄指針。（1） age字段上的稠密B+樹(shù)索引，索引項(xiàng)為數(shù)據(jù)項(xiàng)。構(gòu)造以下幾種情況下的4階B樹(shù)，假定簡(jiǎn)單使用溢出頁(yè)處理重復(fù)鍵值情況。因?yàn)榈诙街幸雅判驍?shù)據(jù)項(xiàng)的數(shù)據(jù)頁(yè)，可在它們從排序步輸出時(shí)，直接調(diào)用批量加載算法依次加入到新的B+樹(shù)中，因此，第三步的代價(jià)只是寫(xiě)出所有（內(nèi)節(jié)點(diǎn)）索引頁(yè)的代價(jià)。 n 第二步，排序數(shù)據(jù)項(xiàng)；外部排序含數(shù)據(jù)項(xiàng)的E 個(gè)頁(yè)，保守估計(jì)需要3E次 I/Os（）。該步包括掃描關(guān)系記錄集，并生成和寫(xiě)出相應(yīng)的數(shù)據(jù)項(xiàng)。（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)整?！窘獯稹浚?）利用標(biāo)準(zhǔn)的B+樹(shù)插入算法，逐項(xiàng)插入，這種方法可能代價(jià)非常昂貴，因?yàn)槊總€(gè)項(xiàng)加入都需要從根開(kāi)始到達(dá)合適的葉節(jié)點(diǎn)。指出該方案在性能和存儲(chǔ)利用率方面存在的問(wèn)題。 假定我們有一個(gè)排序文件，希望在該排序文件基礎(chǔ)上構(gòu)造一個(gè)稠密B+樹(shù)聚集索引。你能推測(cè)出這些子樹(shù)的內(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)致高度增加一層。（4） 給出一個(gè)插入時(shí)會(huì)導(dǎo)致樹(shù)高度增加的鍵值。（2） 給出插入109*后的B+樹(shù)?；卮鹨韵聠?wèn)題。刪除后的局部圖：(3) 可直接插入數(shù)據(jù)項(xiàng)46*。插入后的局部圖如下：（2）刪除8*后要跟前一個(gè)索引項(xiàng)重組，從根結(jié)點(diǎn)到兩個(gè)索引項(xiàng)要讀4個(gè)頁(yè)。由于索引項(xiàng)即數(shù)據(jù)文件本身，從根結(jié)點(diǎn)到索引項(xiàng)讀3個(gè)頁(yè)。（4） 給出在原樹(shù)中，依次刪除32*、39*、41*、45*和73*之后的B+樹(shù)。（2） 給出在原樹(shù)中刪除數(shù)據(jù)項(xiàng)8*之后的B+樹(shù)，并指出完成該操作需要讀多少個(gè)頁(yè)和寫(xiě)多少個(gè)頁(yè)。 =4的B+樹(shù)索引。 輔助索引：非主索引的索引文件。通常主碼索引往往也是聚集索引。 區(qū)別主(碼)索引與輔助索引 主索引或主碼索引：指搜索鍵恰好是主碼的索引。216。 聚集索引：指一種索引文件，這類(lèi)索引文件中索引項(xiàng)的排序方式和數(shù)據(jù)文件記錄的排序方式一致時(shí)。（4）216。③ 二級(jí)或二級(jí)以上索引肯定是稀疏索引，因?yàn)槿绻€是像稠密索引那樣一對(duì)一地建立二級(jí)索引的話，索引項(xiàng)或索引文件大小沒(méi)有實(shí)質(zhì)減少，沒(méi)有什么意義。② 只為搜索鍵的某些值建立索引項(xiàng)的索引稱(chēng)為稀疏索引，稀疏索引必須是聚集索引。如果每個(gè)索引鍵值都至少對(duì)應(yīng)有一個(gè)索引項(xiàng)，則稱(chēng)索引為稠密索引。（2）索引項(xiàng)的三種基本形式：索引項(xiàng)k*就是數(shù)據(jù)記錄本身，沒(méi)有另外單獨(dú)的索引文件。要頻繁執(zhí)行插入和掃描操作，應(yīng)該選用堆文件作為基本的文件組織方式。 （a） 聚簇文件與聚集索引；（b） 稠密索引與稀疏索引；（c） 主（碼）索引與輔助索引。②說(shuō)明稀疏索引的概念，稀疏索引肯定是聚集索引嗎？相應(yīng)的數(shù)據(jù)文件肯定是排序文件嗎？請(qǐng)解釋原因。那么，我們應(yīng)分別選擇基本文件組織方式中的哪一種？（2） 說(shuō)明索引項(xiàng)的三種基本形式。第五章 數(shù)據(jù)庫(kù)索引技術(shù) 簡(jiǎn)要回答以下問(wèn)題?！窘獯稹浚?）先用5號(hào)盤(pán)恢復(fù) 盤(pán)1的數(shù)據(jù)，再用4號(hào)盤(pán)恢復(fù) 盤(pán)7的數(shù)據(jù)?！窘獯稹浚?）01010110；（2）00110110 采用帶有7個(gè)磁盤(pán)的RAID6級(jí)方案,描述從下列故障中恢復(fù)所要采取的步驟 （1） 盤(pán)1＃和盤(pán)7＃。（1） 01010110, 11000000,00111011和11111011。 假設(shè)我們使用RAID4級(jí)方案，有4個(gè)數(shù)據(jù)盤(pán)和一個(gè)冗余盤(pán)。因?yàn)檫@種方法很容易導(dǎo)致保留過(guò)多的槽或槽不夠用情況，這是因?yàn)橄到y(tǒng)無(wú)法預(yù)測(cè)頁(yè)中存儲(chǔ)記錄的長(zhǎng)度。（3） 估算順序掃描該關(guān)系文件需要的總時(shí)間。給出贊成和反對(duì)該方法的理由。 考慮基于目錄槽變長(zhǎng)記錄頁(yè)格式。如果我們能以最好的方式在該磁盤(pán)上安排MPEG影片的塊，能實(shí)時(shí)播放該影片嗎？如果不能，則需要多少個(gè)該型磁盤(pán)？且應(yīng)如何在這些磁盤(pán)上安排塊，才能使影片在播放時(shí)有最小的延遲？【解答】 如果我們按連續(xù)柱面方式安排存儲(chǔ)塊，這樣可忽略尋道時(shí)間和旋轉(zhuǎn)等待時(shí)間，那么，傳送1GB字節(jié)至少需要時(shí)間為：（230/ 4096）=131s，約2分鐘。 。