數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)02

1、第二章數(shù)據(jù)存儲(chǔ)1.存儲(chǔ)器層次2.磁盤3.第二級(jí)存儲(chǔ)器的有效使用4.改善第二級(jí)存儲(chǔ)器訪問(wèn)時(shí)間的策略5.磁盤故障6.磁盤恢復(fù)11.存儲(chǔ)器層次 高速緩沖存儲(chǔ)器主存儲(chǔ)器第二級(jí)存儲(chǔ)器(輔存,聯(lián)機(jī)存儲(chǔ))第三級(jí)存儲(chǔ)器(脫機(jī)存儲(chǔ))易失和非易失存儲(chǔ)器 在各級(jí)之間要解決的問(wèn)題: 1.速度瓶頸 2.容量瓶頸 如主存與輔存之間通過(guò)緩沖區(qū):第三級(jí)存儲(chǔ)器第二級(jí)存儲(chǔ)器(輔存)主存儲(chǔ)器高速緩沖存儲(chǔ)器價(jià)格及速度容量主存緩沖區(qū)輔存22.磁盤磁盤結(jié)構(gòu)磁盤控制器磁盤存儲(chǔ)特性磁盤訪問(wèn)特性塊的寫入塊的修改3磁盤結(jié)構(gòu) 1.磁盤組合: 2.磁頭組合:又分為移動(dòng)磁頭和固定磁頭(高速訪問(wèn),造價(jià)高) 3.磁道: 4.柱面:為討論提高數(shù)據(jù)訪問(wèn)速度

2、5.扇區(qū): 從磁盤讀出和寫入信息的最小單位,也是磁盤錯(cuò)誤的最小單位. 塊是OS或DBMS與磁盤進(jìn)行交換信息的邏輯單位,一般是扇區(qū)的整數(shù)倍4磁盤控制器 1.結(jié)構(gòu)圖: 總線 2.功能: 1)定位磁道(或柱面) 2)選盤面,并選扇區(qū) 3)讀數(shù)據(jù)傳送到主存(計(jì)算效驗(yàn)和數(shù)據(jù)并與讀出的效驗(yàn)和數(shù)據(jù)比較), 或從主存寫數(shù)據(jù)到所選扇區(qū)(包括效驗(yàn)和數(shù)據(jù))處理器主存磁盤控制器5磁盤存儲(chǔ)特性 1.磁盤組合的旋轉(zhuǎn)速度 2.每單元盤片數(shù) 3.每面磁道數(shù) 4.每個(gè)磁道字節(jié)數(shù)例:Megatron747有下列特性: 1.4個(gè)盤片,8個(gè)盤面 2.每個(gè)盤面有213個(gè)磁道(8192個(gè)磁道) 3.每個(gè)磁道平均有28個(gè)扇區(qū)(256個(gè))

3、4.每個(gè)扇區(qū)有29個(gè)字節(jié)(512個(gè))則磁盤容量如下: 23 * 213 * 28 * 29=231(8GB) 6磁盤訪問(wèn)特性 1.存取時(shí)間(access time): 從發(fā)出讀寫請(qǐng)求到數(shù)據(jù)開(kāi)始傳輸之間的時(shí)間 2.尋道時(shí)間(seek time),平均尋道時(shí)間(average seek time) 尋道時(shí)間 : 磁頭重定位的時(shí)間(230ms) 平均尋道時(shí)間 : 410ms 3.旋轉(zhuǎn)等待時(shí)間(rotational latency time),平均旋轉(zhuǎn)等待時(shí)間 旋轉(zhuǎn)等待時(shí)間:磁盤轉(zhuǎn)動(dòng)到被存取的扇區(qū)出現(xiàn)在磁頭下所用時(shí)間 平均旋轉(zhuǎn)等待時(shí)間: 4.數(shù)據(jù)傳輸率(data-transfer rate):從磁盤獲

4、取數(shù)據(jù)或者向磁盤存儲(chǔ)數(shù)據(jù) 的速率(25M40M/S) 5.平均故障時(shí)間(mean time to failure,MTTF):預(yù)期系統(tǒng)無(wú)故障連續(xù)運(yùn)行 的平均時(shí)間7塊的寫入與讀出: 1)磁頭定位(磁道) 2)扇區(qū)定位 3)讀或?qū)?塊的修改 1.過(guò)程: 1)將塊讀入主存 2)對(duì)主存中塊的副本進(jìn)行所要求的修改 3)將主存中塊的內(nèi)容寫回到磁盤 4)如果需要,檢查寫操作(對(duì)效驗(yàn)和進(jìn)行檢查) 2.所需時(shí)間: 1)讀的時(shí)間 2)在主存中更新的時(shí)間 3)寫的時(shí)間 4)進(jìn)行效驗(yàn)和判定的時(shí)間9磁盤數(shù)據(jù)組織與DBMS(或文件)數(shù)據(jù)組織的關(guān)系 物理概念 邏輯概念磁盤組合磁盤片盤面磁道扇區(qū)字節(jié)關(guān)系(包括數(shù)據(jù)字典,索引)

5、塊記錄字段柱面103.第二級(jí)存儲(chǔ)器的有效使用1.計(jì)算的I/O模型2.第二級(jí)存儲(chǔ)器中的數(shù)據(jù)排序3.歸并排序4.兩階段多路歸并排序5.擴(kuò)展多路歸并排序更大的關(guān)系111.計(jì)算的I/O模型: 在DBMS中,所有數(shù)據(jù)不在主存中,數(shù)據(jù)訪問(wèn)(或處理)的開(kāi)銷,CPU與I/O速度差,導(dǎo)致在考慮相關(guān)算法時(shí),只在乎磁盤塊訪問(wèn)(讀和寫)次數(shù)或所需時(shí)間,而CPU處理時(shí)間忽略不計(jì). 目標(biāo):為完成某項(xiàng)任務(wù),所實(shí)現(xiàn)的算法中,存儲(chǔ)器中的塊有最少的I/O次 數(shù) 122.第二級(jí)存儲(chǔ)器中的數(shù)據(jù)排序(也包括第二級(jí)/第三級(jí)) 討論:一個(gè)表的排序問(wèn)題,透視如何考慮以I/O開(kāi)銷為主的排序算法 1)小表(=DBMS(主存) 例:表=107行,

6、每行定長(zhǎng)=100字節(jié),DBMS(主存)=50M, 磁盤塊=4K(4096字節(jié)),每塊=40行,表=250000塊 DBMS(主存)=12800塊 1)歸并排序(書(shū)page31圖2-10,算法見(jiàn)書(shū)page32) 2)一階段兩路歸并排序 表大小= DBMS(主存) 3)多階段兩路歸并排序(淘汰賽)(I/O次數(shù)較多) 階段1:排序主存大小的數(shù)據(jù)片段 階段n:對(duì)階段n-1所排序的數(shù)據(jù)片段進(jìn)行兩兩歸并排序 4)兩階段多路歸并排序 階段1:排序主存大小的數(shù)據(jù)片段 階段2:對(duì)階段1所排序的數(shù)據(jù)片段的塊進(jìn)行多路歸并排序 5)多階段多路歸并排序 13模擬實(shí)現(xiàn)兩階段多路歸并排序(DBMS對(duì)大表某字段排序時(shí),所采用

7、)要求: 1)建立模擬所需的數(shù)據(jù)結(jié)構(gòu) 2)實(shí)現(xiàn)兩階段多路歸并排序的算法 3)測(cè)試或演示排序過(guò)程 4)顯示排序時(shí)間(時(shí)間開(kāi)銷)144.改善第二級(jí)存儲(chǔ)器訪問(wèn)時(shí)間的策略1.按柱面組織數(shù)據(jù): 將可能一起被訪問(wèn)的塊放在同一柱面上,可以減少訪問(wèn)時(shí)間 問(wèn)題:如何界定一起訪問(wèn),預(yù)留空間多大等2.使用多磁盤: 數(shù)據(jù)存儲(chǔ)在幾個(gè)獨(dú)立的磁盤上,而不是集中在一個(gè)較大的磁盤上 數(shù)據(jù)庫(kù)的存儲(chǔ)策略也是如此:數(shù)據(jù),索引,日志等最好是分布在獨(dú)立的 幾個(gè)磁盤上3.磁盤鏡像(mirror): 通過(guò)磁盤冗余,提高訪問(wèn)速度,同是也提高數(shù)據(jù)可靠性4.磁盤調(diào)度的電梯算法: 通過(guò)在OS,或在DBMS,或在磁盤控制器中采用有效的算法(如電梯算 法)5.預(yù)取和大規(guī)模緩沖: 預(yù)取將要使用的塊到主存中,盡可能地增加緩沖區(qū)的大小.6.各種策略及其優(yōu)缺點(diǎn)(略):(見(jiàn)書(shū)page43)155.磁盤故障 1.