軟件學(xué)院高級(jí)數(shù)據(jù)庫(kù)考試攻略(金培權(quán)數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn))

1、University of Science and Technology of China 軟件學(xué)院2015級(jí)高級(jí)數(shù)據(jù)庫(kù)技術(shù)(金培權(quán)-數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn))Homework 1給定下面的關(guān)系：圖書(shū)（圖書(shū)號(hào)，書(shū)名，作者，單給定下面的關(guān)系：圖書(shū)（圖書(shū)號(hào)，書(shū)名，作者，單價(jià)，庫(kù)存量），讀者（讀者號(hào)，姓名，工作單位，價(jià)，庫(kù)存量），讀者（讀者號(hào)，姓名，工作單位，地址），借閱（圖書(shū)號(hào)，讀者號(hào)，借期，還期，備地址），借閱（圖書(shū)號(hào)，讀者號(hào)，借期，還期，備注）注） 注：還期為注：還期為NULL表示該書(shū)未還。表示該書(shū)未還。檢索讀者檢索讀者Rose的工作單位和地址的工作單位和地址工作單位，地址讀者姓名seRo檢索讀者檢索讀

2、者Rose所借閱讀書(shū)（包括已還和所借閱讀書(shū)（包括已還和未未還圖書(shū)）還圖書(shū)）的圖書(shū)名和借期的圖書(shū)名和借期書(shū)名，借期讀者借閱圖書(shū)姓名RoseHomework 1檢索未借閱圖書(shū)的讀者姓名檢索未借閱圖書(shū)的讀者姓名姓名姓名（讀者）（讀者 借閱)查詢(xún)語(yǔ)句結(jié)果可以計(jì)算如下：查詢(xún)語(yǔ)句結(jié)果可以計(jì)算如下：1. 取取FROM子句中列出的各個(gè)關(guān)系的元組的所有可能的組合子句中列出的各個(gè)關(guān)系的元組的所有可能的組合2. 將不符合將不符合WHERE子句中給出的條件的元組去掉子句中給出的條件的元組去掉3. 如果有如果有GROUP BY子句，則將剩下的元組按子句，則將剩下的元組按GROUP BY子句子句中給出的屬性值分組中給出的

3、屬性值分組4. 如果有如果有HAVING子句，則按照子句，則按照HAVING子句中給出的條件檢子句中給出的條件檢查每一組，去掉不符合條件的組查每一組，去掉不符合條件的組5. 按照按照SELECT子句的說(shuō)明，對(duì)于指定的屬性和屬性上的聚集子句的說(shuō)明，對(duì)于指定的屬性和屬性上的聚集（例如一組中的和）計(jì)算出結(jié)果元組（例如一組中的和）計(jì)算出結(jié)果元組6. 按照按照ORDER BY子句中的屬性列的值對(duì)結(jié)果元組進(jìn)行排序子句中的屬性列的值對(duì)結(jié)果元組進(jìn)行排序Homework 1檢索檢索Ullman所寫(xiě)的書(shū)的書(shū)名和單價(jià)所寫(xiě)的書(shū)的書(shū)名和單價(jià)SELECT 書(shū)名，單價(jià)書(shū)名，單價(jià)FROM 圖書(shū)圖書(shū)WHERE 作者作者=Ull

4、man檢索讀者檢索讀者“李林李林”借閱未還的圖書(shū)的圖書(shū)號(hào)和書(shū)名借閱未還的圖書(shū)的圖書(shū)號(hào)和書(shū)名SELECT 圖書(shū)號(hào)，書(shū)名圖書(shū)號(hào)，書(shū)名FROM圖書(shū)，讀者，借閱圖書(shū)，讀者，借閱WHERE 圖書(shū)圖書(shū).圖書(shū)號(hào)圖書(shū)號(hào) = 借閱借閱.圖書(shū)號(hào)圖書(shū)號(hào) AND 讀者讀者.讀者號(hào)讀者號(hào) = 借閱借閱.讀者號(hào)讀者號(hào)AND 讀者讀者.姓名姓名 = “李林李林” AND 借閱借閱.還期還期 = NULL；Homework 1檢索借閱圖書(shū)數(shù)目超過(guò)檢索借閱圖書(shū)數(shù)目超過(guò)3本的讀者姓名本的讀者姓名SELECT 姓名姓名FROM 讀者，借閱讀者，借閱WHERE 借閱借閱.讀者號(hào)讀者號(hào) = 讀者讀者.讀者號(hào)讀者號(hào)GROUP BY 讀者

5、號(hào)讀者號(hào)HAVING COUNT(*) 3;Homework 1檢索沒(méi)有借閱讀者檢索沒(méi)有借閱讀者“李林李林”所借的任何一本書(shū)的讀者所借的任何一本書(shū)的讀者姓名和讀者號(hào)姓名和讀者號(hào)SELECT 姓名，讀者號(hào)姓名，讀者號(hào)FROM 讀者，借閱讀者，借閱WHERE 借閱借閱.讀者號(hào)讀者號(hào) = 讀者讀者.讀者號(hào)讀者號(hào)AND借閱借閱.圖書(shū)號(hào)圖書(shū)號(hào)NOT IN (SELECT 圖書(shū)號(hào)圖書(shū)號(hào)FROM 借閱，讀者借閱，讀者WHERE 借閱借閱.讀者號(hào)讀者號(hào) = 讀者讀者.讀者號(hào)讀者號(hào)AND 讀者讀者.姓名姓名 = 李林李林);Homework 1檢索書(shū)名中包含檢索書(shū)名中包含“Oracle”的圖書(shū)書(shū)名及圖書(shū)號(hào)。的圖

6、書(shū)書(shū)名及圖書(shū)號(hào)。SELECT 圖書(shū)號(hào)，書(shū)名圖書(shū)號(hào)，書(shū)名FROM 圖書(shū)圖書(shū)WHERE 書(shū)名書(shū)名LIKE %Oracle%;Homework 1現(xiàn)有如下關(guān)系模式：現(xiàn)有如下關(guān)系模式： R(A，B，C，D，E，F(xiàn)，G)，R上存在的函數(shù)依賴(lài)有：上存在的函數(shù)依賴(lài)有：ABE，AB，BC，CD該關(guān)系模式滿(mǎn)足第幾范式嗎該關(guān)系模式滿(mǎn)足第幾范式嗎? 為什么為什么?滿(mǎn)足滿(mǎn)足1NF范式。因?yàn)槊恳粋€(gè)屬性值都只含有一個(gè)值，所以滿(mǎn)范式。因?yàn)槊恳粋€(gè)屬性值都只含有一個(gè)值，所以滿(mǎn)足足1NF。由于。由于R的候選碼為（的候選碼為（A,F,G），而），而B(niǎo)、C、D局部依賴(lài)于局部依賴(lài)于A，所以不滿(mǎn)足，所以不滿(mǎn)足2NF。如果將關(guān)系模式如果將

7、關(guān)系模式R分解為：分解為： R1(A，B，E) ，R2(B，C，D)，R3(A，F(xiàn)，G)，該數(shù)據(jù)庫(kù)模式最高滿(mǎn)足第幾范，該數(shù)據(jù)庫(kù)模式最高滿(mǎn)足第幾范式式?最高滿(mǎn)足最高滿(mǎn)足2NF范式。因?yàn)閷?duì)于模式范式。因?yàn)閷?duì)于模式R2， BC，CD，存在傳，存在傳遞依賴(lài)，遞依賴(lài)，所以不滿(mǎn)足所以不滿(mǎn)足3NF。Homework 1請(qǐng)將關(guān)系模式請(qǐng)將關(guān)系模式R無(wú)損連接并且保持函數(shù)依賴(lài)地分解無(wú)損連接并且保持函數(shù)依賴(lài)地分解到到3NF，要求給出具體步驟。，要求給出具體步驟。1.求求R上函數(shù)依賴(lài)集上函數(shù)依賴(lài)集F的最小的最小FD集合：集合： F = ABE,AB,BC,CD；U = A,B,C,D,E先先將將R保持函數(shù)依賴(lài)地分解到保

8、持函數(shù)依賴(lài)地分解到3NF。2.所有不在所有不在F中出現(xiàn)的屬性組成中出現(xiàn)的屬性組成R(F,G)Homework 13.對(duì)對(duì)F按相同的左部分組按相同的左部分組，并去除子集，得到：，并去除子集，得到：p = R1（A,B,E）；）；R2（B,C）；）；R3(C,D)；R(F,G)Homework 1無(wú)損連接且保持函數(shù)依賴(lài)地分解到無(wú)損連接且保持函數(shù)依賴(lài)地分解到3NFHomework 15.而而R是是R4的子集，所以從的子集，所以從p中去掉中去掉R（F,G）6.p=R1（A,B,E）,R2（B,C），），R3（C,D），），R4（A,F,G）為最終結(jié)果為最終結(jié)果Homework 1Megatron 77

9、7磁盤(pán)具有以下特性：磁盤(pán)具有以下特性：（1）有有10個(gè)盤(pán)面，每個(gè)盤(pán)面有個(gè)盤(pán)面，每個(gè)盤(pán)面有100000個(gè)磁道；個(gè)磁道；（2）磁道平均有磁道平均有1000個(gè)扇區(qū)，每個(gè)扇區(qū)為個(gè)扇區(qū)，每個(gè)扇區(qū)為1024字節(jié)；字節(jié)；（3）每個(gè)磁道的每個(gè)磁道的20%用于間隙；用于間隙；（4）磁盤(pán)旋轉(zhuǎn)為磁盤(pán)旋轉(zhuǎn)為10000轉(zhuǎn)轉(zhuǎn)/min；（5）磁頭移動(dòng)磁頭移動(dòng)n個(gè)磁道所需要的時(shí)間是個(gè)磁道所需要的時(shí)間是1+0.0002n ms磁盤(pán)的容量是多少？磁盤(pán)的容量是多少？Homework 1如果磁道是在直徑如果磁道是在直徑3.5英寸的圓面上，那么一個(gè)磁道英寸的圓面上，那么一個(gè)磁道的扇區(qū)中的平均位密度是多少？的扇區(qū)中的平均位密度是多少？我

10、們選取中間磁道來(lái)計(jì)算平均位密度，中間磁道的我們選取中間磁道來(lái)計(jì)算平均位密度，中間磁道的直徑為直徑為 3.5inch/2 ，該磁道的周長(zhǎng)為，該磁道的周長(zhǎng)為(3.5/2)inch，扇區(qū)所占的周長(zhǎng)是扇區(qū)所占的周長(zhǎng)是80%(3.5/2)inch。同時(shí)，每個(gè)。同時(shí)，每個(gè)磁道的容量是磁道的容量是100010248 bits所以一個(gè)磁道的扇區(qū)中的平均位密度是所以一個(gè)磁道的扇區(qū)中的平均位密度是（100010248）bits/(80%3.5/2)inch = 1861733.6 bpi最大尋道時(shí)間是多少？最大尋道時(shí)間是多少？最大尋道時(shí)間最大尋道時(shí)間 1 + 0.0002* 99 999 = 21msHomewo

11、rk 1最大旋轉(zhuǎn)等待時(shí)間是多少？最大旋轉(zhuǎn)等待時(shí)間是多少？最大旋轉(zhuǎn)等待時(shí)間：最大旋轉(zhuǎn)等待時(shí)間：60 x 1000ms /10 000 = 6ms如果一個(gè)塊是如果一個(gè)塊是65536字節(jié)（即字節(jié)（即64扇區(qū)），一個(gè)塊的扇區(qū)），一個(gè)塊的傳輸時(shí)間是多少？傳輸時(shí)間是多少？如果一個(gè)塊是如果一個(gè)塊是65536字節(jié)（即字節(jié)（即64扇區(qū)）扇區(qū)）,則磁頭必須則磁頭必須越過(guò)越過(guò)64個(gè)扇區(qū)以及扇區(qū)之間的個(gè)扇區(qū)以及扇區(qū)之間的63個(gè)間隙。需要的時(shí)個(gè)間隙。需要的時(shí)間為：間為：64（扇區(qū)（扇區(qū)+間隙）間隙）-1（間隙）（間隙）=64*（6/1000）-(6/1000)*0.2=0.3828msHomework 1平均尋道時(shí)間是

12、多少？平均尋道時(shí)間是多少？平均旋轉(zhuǎn)等待時(shí)間為：平均旋轉(zhuǎn)等待時(shí)間為：6ms/2=3ms平均旋轉(zhuǎn)等待時(shí)間是多少？平均旋轉(zhuǎn)等待時(shí)間是多少？1+0.0002*99999/3=7.67msHomework2假設(shè)一條記錄有如下順序的字段：一個(gè)長(zhǎng)度為假設(shè)一條記錄有如下順序的字段：一個(gè)長(zhǎng)度為23的的字符串，一個(gè)字符串，一個(gè)2字節(jié)整數(shù)，一個(gè)字節(jié)整數(shù)，一個(gè)SQL日期，一個(gè)日期，一個(gè)SQL時(shí)間（無(wú)小數(shù)點(diǎn)）。時(shí)間（無(wú)小數(shù)點(diǎn)）。字段可在任何字節(jié)處開(kāi)始？字段可在任何字節(jié)處開(kāi)始？一個(gè)一個(gè)SQL日期是日期是10個(gè)字節(jié)的字符串，一個(gè)個(gè)字節(jié)的字符串，一個(gè)SQL時(shí)間是時(shí)間是8個(gè)字節(jié)的字符串。個(gè)字節(jié)的字符串。因?yàn)槭侨魏巫止?jié)處開(kāi)始的，

13、所以記錄長(zhǎng)度需要因?yàn)槭侨魏巫止?jié)處開(kāi)始的，所以記錄長(zhǎng)度需要23+2+10+8=43字節(jié)。字節(jié)。Homework2字段必須在字段必須在8的倍數(shù)的字節(jié)處開(kāi)始？的倍數(shù)的字節(jié)處開(kāi)始？Homework2字段必須在字段必須在4的倍數(shù)的字節(jié)處開(kāi)始？的倍數(shù)的字節(jié)處開(kāi)始？因?yàn)楸仨毷且驗(yàn)楸仨毷?的倍數(shù)，而長(zhǎng)度為的倍數(shù)，而長(zhǎng)度為23的字符串需要分的字符串需要分配配24個(gè)字節(jié)，個(gè)字節(jié)，2字節(jié)的整數(shù)需要分配字節(jié)的整數(shù)需要分配4個(gè)字節(jié)，個(gè)字節(jié)，SQL日期需要分配日期需要分配12個(gè)字節(jié)，個(gè)字節(jié)，SQL時(shí)間需要分配時(shí)間需要分配8個(gè)字節(jié)個(gè)字節(jié)。所以：。所以：24+4+12+8=48字節(jié)。字節(jié)。Homework2假設(shè)我們有假設(shè)我們

14、有4096字節(jié)塊，塊中存儲(chǔ)字節(jié)塊，塊中存儲(chǔ)200字節(jié)長(zhǎng)的記字節(jié)長(zhǎng)的記錄。塊首部由一個(gè)偏移量表組成，它使用錄。塊首部由一個(gè)偏移量表組成，它使用2字節(jié)長(zhǎng)字節(jié)長(zhǎng)指針指向塊內(nèi)記錄。通常，每天向每塊插入兩條記指針指向塊內(nèi)記錄。通常，每天向每塊插入兩條記錄，刪除一條記錄。刪除記錄必須使用一個(gè)錄，刪除一條記錄。刪除記錄必須使用一個(gè)“刪除刪除標(biāo)記標(biāo)記”代替它的指針，因?yàn)榭赡軙?huì)有懸掛指針指向代替它的指針，因?yàn)榭赡軙?huì)有懸掛指針指向它。更明確地說(shuō)，假設(shè)任何一天刪除記錄總發(fā)生在它。更明確地說(shuō)，假設(shè)任何一天刪除記錄總發(fā)生在插入之前。如果剛開(kāi)始時(shí)塊是空的，多少天之后，插入之前。如果剛開(kāi)始時(shí)塊是空的，多少天之后，不再有插入

15、記錄的空間？不再有插入記錄的空間？第一天，只做插入操作，插入兩條記錄，同時(shí)使用第一天，只做插入操作，插入兩條記錄，同時(shí)使用2個(gè)指針指向記錄，總計(jì)增加了個(gè)指針指向記錄，總計(jì)增加了2（2+200） = 404字節(jié)。字節(jié)。Homework2之后的每一天都先刪除一條記錄再增加兩條記錄，之后的每一天都先刪除一條記錄再增加兩條記錄，凈增凈增404-200 = 204字節(jié)。由于（字節(jié)。由于（4096-404）/204 = 1820，即在，即在1+18 = 19天之后，塊中剩余空間為天之后，塊中剩余空間為20字節(jié)。字節(jié)。在第在第20天，先刪除一條記錄，余下天，先刪除一條記錄，余下200+20=220字節(jié)字節(jié)空

16、間，這時(shí)候只能夠再插入一條記錄（空間，這時(shí)候只能夠再插入一條記錄（202字節(jié)）字節(jié)）。Homework2 一個(gè)病人記錄包含以下定長(zhǎng)字段：一個(gè)病人記錄包含以下定長(zhǎng)字段：病人的出生日期病人的出生日期，社會(huì)保險(xiǎn)號(hào)碼社會(huì)保險(xiǎn)號(hào)碼，病人病人ID，每一個(gè)字段都是，每一個(gè)字段都是9字節(jié)長(zhǎng)字節(jié)長(zhǎng)。它還有下列變長(zhǎng)字段：。它還有下列變長(zhǎng)字段：姓名，住址和病史姓名，住址和病史。如果。如果記錄內(nèi)一個(gè)指針需要記錄內(nèi)一個(gè)指針需要8字節(jié)，記錄長(zhǎng)度是一個(gè)字節(jié)，記錄長(zhǎng)度是一個(gè)2字節(jié)字節(jié)整數(shù)，不包含變長(zhǎng)字段空間，這條記錄需要多少字整數(shù)，不包含變長(zhǎng)字段空間，這條記錄需要多少字節(jié)？你可以假設(shè)不需要對(duì)字節(jié)進(jìn)行對(duì)齊。節(jié)？你可以假設(shè)不需要

17、對(duì)字節(jié)進(jìn)行對(duì)齊。記記錄錄長(zhǎng)長(zhǎng)度度出生出生日期日期住住址址指指針針病病史史指指針針保險(xiǎn)保險(xiǎn)號(hào)碼號(hào)碼病人病人ID姓名姓名住址住址病史病史Homework2定長(zhǎng)字段有定長(zhǎng)字段有3個(gè)，每個(gè)有個(gè)，每個(gè)有9個(gè)字節(jié)長(zhǎng)，所以需要個(gè)字節(jié)長(zhǎng)，所以需要 39=27字節(jié)。字節(jié)。而記錄的首部需要寫(xiě)入記錄的長(zhǎng)度和指向所有除第而記錄的首部需要寫(xiě)入記錄的長(zhǎng)度和指向所有除第一個(gè)以外的變長(zhǎng)字段起始處的指針。而記錄長(zhǎng)度一個(gè)以外的變長(zhǎng)字段起始處的指針。而記錄長(zhǎng)度2字節(jié)，指向字節(jié)，指向“住址住址”的指針的指針8字節(jié)，指向字節(jié)，指向“病史病史”的指針的指針8字節(jié)。所以一共需要字節(jié)。所以一共需要27+2+8+8 = 45字節(jié)。字節(jié)。Hom

18、ework3 Homework3 T(W)/V(W,a) = 400/50 = 8T(Y)/V(Y,c) = 200/50 = 4Homework3 T(W)*T(Y)=400*200=80000T(Z)/3=100/3=33.3T(W)/V(W,a)*V(W,b)=400/(50*40)=0.2Homework3 T(W)/3*V(W,a)=400/（3*50）=2.67T(X)*T(Y)/3=300*200/3=20000Homework4如果如果R和和S都是非聚集的，似乎嵌套循環(huán)連將需要大約都是非聚集的，似乎嵌套循環(huán)連將需要大約T(R)T(S)/M次磁盤(pán)次磁盤(pán)I/O時(shí)間。時(shí)間。你怎樣做才

19、能明顯好于這個(gè)代價(jià)？你怎樣做才能明顯好于這個(gè)代價(jià)？假設(shè)假設(shè) S(R)=S(S),每次迭代時(shí)讀取每次迭代時(shí)讀取R的元組塞滿(mǎn)的元組塞滿(mǎn) M-1塊的塊的chunk,此時(shí)迭代次數(shù)為此時(shí)迭代次數(shù)為T(mén)(R)*S(R)/(M-1)，那么，那么總的磁盤(pán)總的磁盤(pán)I/O時(shí)間為時(shí)間為T(mén)(R)+T(R)*T(S)*S(R)/(M-1)。近近似為：似為： T(R)*T(S)*S(R)/M.例如：例如：1個(gè)個(gè)block中能存放中能存放10個(gè)元組個(gè)元組,即即S(R)=1/10*block，那么效率提高，那么效率提高10倍倍。Homework4如果如果R和和S中只有一個(gè)是非聚集的，你應(yīng)該怎樣執(zhí)行中只有一個(gè)是非聚集的，你應(yīng)該怎

20、樣執(zhí)行嵌套循環(huán)連接？考慮兩種情況：較大的關(guān)系是非聚嵌套循環(huán)連接？考慮兩種情況：較大的關(guān)系是非聚集的和較小的事非聚集的集的和較小的事非聚集的假定假定 R為較小關(guān)系，為較小關(guān)系，S為較大關(guān)系為較大關(guān)系（1）S是非聚集的：是非聚集的：方案方案1：For each loop:Read M -1 blocks of RRead all of S (using 1 block) + join代價(jià)為：代價(jià)為：B(R)+B(R)*T(S)/(M-1)Homework4方案方案2：Read M-1 blocks (M-1)1/S(S) tuples) of SRead all of R(using 1 bloc

21、k) + join代價(jià)為：代價(jià)為：T(S)+B(R)*T(S)*S(S)/(M-1)選擇代價(jià)最小的方案選擇代價(jià)最小的方案（2）R是非聚集的是非聚集的：方案方案1：For each loop:Read M-1 blocks (M-1)1/S（R）tuples) of RRead all of S (using 1 block)+ join代價(jià)為：代價(jià)為：T(R)+T(R)*B(S)*S(R)/(M-1)Homework4方案方案2：For each loop:Read M-1 blocks of SRead all of R(using 1 block)+ join代價(jià)為：代價(jià)為：B(S)+T(

22、R)*B(S)/(M-1)選擇代價(jià)最小的方案選擇代價(jià)最小的方案比較比較2種情況下的最優(yōu)代價(jià)種情況下的最優(yōu)代價(jià)Homework4假設(shè)這節(jié)中所描述算法的第二趟不需要所有的假設(shè)這節(jié)中所描述算法的第二趟不需要所有的M個(gè)緩個(gè)緩沖區(qū)，因?yàn)樽颖頂?shù)小于沖區(qū)，因?yàn)樽颖頂?shù)小于M。我們?cè)鯓油ㄟ^(guò)使用額外的。我們?cè)鯓油ㄟ^(guò)使用額外的緩沖區(qū)來(lái)節(jié)省磁盤(pán)緩沖區(qū)來(lái)節(jié)省磁盤(pán)I/O？原本我們需要將第一趟中得到的有序子表都寫(xiě)回磁原本我們需要將第一趟中得到的有序子表都寫(xiě)回磁盤(pán)，現(xiàn)在由于子表數(shù)小于盤(pán)，現(xiàn)在由于子表數(shù)小于M，可以將部分子表不寫(xiě)，可以將部分子表不寫(xiě)回，直接存儲(chǔ)在內(nèi)存緩沖區(qū)中，從而減少第二趟中回，直接存儲(chǔ)在內(nèi)存緩沖區(qū)中，從而減少

23、第二趟中的讀子表操作，對(duì)于這樣每塊我們節(jié)省了的讀子表操作，對(duì)于這樣每塊我們節(jié)省了 2 次次IO.Test 1假設(shè)某磁盤(pán)塊參數(shù)如下：容量假設(shè)某磁盤(pán)塊參數(shù)如下：容量36.7GB,傳輸速率傳輸速率45MB/S，旋轉(zhuǎn)一圈時(shí)間，旋轉(zhuǎn)一圈時(shí)間4ms，平均尋道時(shí)間，平均尋道時(shí)間5ms，最小尋道時(shí)，最小尋道時(shí)間間0.65ms，一個(gè)磁道大小，一個(gè)磁道大小180KB。如果磁盤(pán)塊大小。如果磁盤(pán)塊大小4KB,請(qǐng)回答下面問(wèn)題：請(qǐng)回答下面問(wèn)題：（1）隨機(jī)讀取）隨機(jī)讀取1000個(gè)磁盤(pán)塊需要多少時(shí)間（個(gè)磁盤(pán)塊需要多少時(shí)間（ms）？）？（2）假定（）假定（1）中的）中的1000個(gè)磁盤(pán)塊在單個(gè)磁道上連續(xù)個(gè)磁盤(pán)塊在單個(gè)磁道上連續(xù)存

24、儲(chǔ)，并且所有磁盤(pán)塊存儲(chǔ)在相鄰的磁道上，此時(shí)讀存儲(chǔ)，并且所有磁盤(pán)塊存儲(chǔ)在相鄰的磁道上，此時(shí)讀取這取這1000個(gè)磁盤(pán)塊需要多少時(shí)間？個(gè)磁盤(pán)塊需要多少時(shí)間？Test 1Test 1順序讀取順序讀取1000個(gè)塊個(gè)塊TestB+-Tree設(shè)定如下：設(shè)定如下：N: 記錄數(shù)記錄數(shù) n: B+-Tree的階，即節(jié)點(diǎn)所能容納的鍵數(shù)的階，即節(jié)點(diǎn)所能容納的鍵數(shù)R: 讀取一個(gè)磁盤(pán)塊的旋轉(zhuǎn)延遲讀取一個(gè)磁盤(pán)塊的旋轉(zhuǎn)延遲S: 讀取一個(gè)磁盤(pán)塊的尋道時(shí)間讀取一個(gè)磁盤(pán)塊的尋道時(shí)間T: 讀取一個(gè)磁盤(pán)塊的傳輸時(shí)間讀取一個(gè)磁盤(pán)塊的傳輸時(shí)間m: 在內(nèi)存的在內(nèi)存的m條記錄查找一條記錄的時(shí)間條記錄查找一條記錄的時(shí)間假設(shè)所有磁盤(pán)塊都不在內(nèi)存中

25、假設(shè)所有磁盤(pán)塊都不在內(nèi)存中現(xiàn)在考慮壓縮現(xiàn)在考慮壓縮B+-Tree，假設(shè)每個(gè)節(jié)點(diǎn)的鍵值壓縮，假設(shè)每個(gè)節(jié)點(diǎn)的鍵值壓縮1倍，即同樣空間可壓縮存儲(chǔ)倍，即同樣空間可壓縮存儲(chǔ)2n個(gè)鍵值和個(gè)鍵值和2n+1個(gè)指針個(gè)指針。額外代價(jià)是解壓縮，設(shè)每個(gè)壓縮鍵值的內(nèi)存解壓。額外代價(jià)是解壓縮，設(shè)每個(gè)壓縮鍵值的內(nèi)存解壓時(shí)間為時(shí)間為c，請(qǐng)問(wèn)在一棵滿(mǎn)的，請(qǐng)問(wèn)在一棵滿(mǎn)的n階壓縮階壓縮B+-Tree中查找給中查找給定記錄地址的時(shí)間多少？（定記錄地址的時(shí)間多少？（n+1可近似表示為可近似表示為n）Test2. 讀塊的時(shí)間讀塊的時(shí)間 = R + S + T3. 每塊有每塊有n條記錄，內(nèi)存查找時(shí)間為條記錄，內(nèi)存查找時(shí)間為 n6. 增加了

26、解壓時(shí)間增加了解壓時(shí)間2cn，內(nèi)存查找時(shí)間變?yōu)?，?nèi)存查找時(shí)間變?yōu)?nFinal Exam考試形式不同于往年，往年為開(kāi)卷考試，今年為閉卷考試，總共10個(gè)判斷題，及4個(gè)大題。10個(gè)判斷，30分，個(gè)人感覺(jué)不容易，考點(diǎn)比較細(xì)，都是一些概念的判斷，考的基本都是前三章的內(nèi)容，請(qǐng)大家仔細(xì)復(fù)習(xí)。（eg:ER圖是自下向頂設(shè)計(jì)的；關(guān)系模型中候選碼一定要存在；一個(gè)只有2個(gè)屬性的關(guān)系模式一定滿(mǎn)足第三范式嗎）第一個(gè)大題考的是PPT第七章的內(nèi)容，查詢(xún)優(yōu)化，老師上課講的PPT上不全，只要把書(shū)上P153頁(yè)5.4.3內(nèi)容掌握即可完美答題。題目難度：一顆星Final Exam第二個(gè)大題考的是PPT第十章的內(nèi)容，并發(fā)調(diào)度，考察沖突可串性及優(yōu)先圖的畫(huà)法，掌握PPT即可。題目難度：一顆星第三個(gè)大題考的是模糊查詢(xún)結(jié)合B+樹(shù)索引查詢(xún)（問(wèn)題是否能用B+樹(shù)索引查詢(xún)應(yīng)用于模糊查詢(xún)能否提高查詢(xún)效率），金老師上課基本沒(méi)提到模糊查詢(xún)，因此需