【正文】 7, 14, 0, 65, 67, 98, 122, 124, 183, 199的順序依次查找 ， 并將數(shù)據(jù)輸入內(nèi)存 。 磁盤(pán)調(diào)度（ 2） ? SSTF（ 最短查找時(shí)間優(yōu)先 ） 調(diào)度 ? 考慮了各個(gè)請(qǐng)求之間的區(qū)別 ， 總是先執(zhí)行查找時(shí)間最短的那個(gè)請(qǐng)求 。 磁盤(pán)調(diào)度（ 1） ? FCFS（ 先來(lái)先服務(wù) ） 調(diào)度 先查找先進(jìn)入服務(wù)列隊(duì)的數(shù)據(jù) 。 單碟容量越高說(shuō)明單碟的磁道數(shù)越多 ， 磁道數(shù)的增加意味著磁道間距離的縮短 ， 而磁頭從一個(gè)磁道轉(zhuǎn)移到另一個(gè)磁道所需的就位時(shí)間就會(huì)縮短 ， 這將有助于隨機(jī)數(shù)據(jù)傳輸速度的提高 。 內(nèi)傳輸速率更能反映硬盤(pán)的實(shí)際表現(xiàn) ， 通常以每秒 MB為單位 。 因此緩存容量的加大可以容納更多的預(yù)讀數(shù)據(jù) ， 這樣大大縮短系統(tǒng)等待的時(shí)間 。 目前 ， 硬盤(pán)轉(zhuǎn)速大致有 4200RPM、5400RPM 、 7200RPM 、 10000RPM 和15000RPM。 硬盤(pán)的容量與碟片數(shù) 、 面密度關(guān)系密切 ，這兩項(xiàng)數(shù)值越大則容量越大 。 半徑方向單位長(zhǎng)度內(nèi)的磁道數(shù)目稱(chēng)為道密度 Dt， 沿圓周單位長(zhǎng)度上的信息比特?cái)?shù)稱(chēng)為位密度 Db， 道密度與位密度的乘積叫做面密度 Da， 即Da = Dt Db。 磁盤(pán) ? 磁盤(pán)性能度量 ? 訪(fǎng)問(wèn)時(shí)間：從發(fā)出讀寫(xiě)請(qǐng)求到數(shù)據(jù)開(kāi)始傳輸之間的時(shí)間 。 ? 磁道 （ track） 在同一個(gè)盤(pán)片上以同心圓方式排列的扇區(qū)構(gòu)成一個(gè)磁道 ， 磁道的扇區(qū)數(shù)隨同心圓的半徑而變化 ， 越靠外的磁道的扇區(qū)數(shù)越多 。提綱 ? 物理存儲(chǔ)介質(zhì) ? RAID ? 緩沖區(qū)管理 ? 索引 ? 數(shù)據(jù)庫(kù)文件 ? 存儲(chǔ)分配 物理存儲(chǔ)介質(zhì) 物理存儲(chǔ)介質(zhì) ? 高速緩沖存儲(chǔ)器 （ cache） ? 最快最昂貴的存儲(chǔ)介質(zhì) ? 很小 ， 由操作系統(tǒng)管理 ? 主存儲(chǔ)器 （ main memory） ? 存放可被處理的數(shù)據(jù)的存儲(chǔ)介質(zhì) ? 易失 ， 相對(duì)整個(gè)數(shù)據(jù)庫(kù)太小 ? 快閃存儲(chǔ)器 （ flash memory） ? 讀性能類(lèi)似主存 ， 寫(xiě)速度非常慢 ? 電子可擦除可編程只讀存儲(chǔ)器 (Electrically Erasable Programmable ReadOnly Memory) 物理存儲(chǔ)介質(zhì) ? 磁盤(pán)存儲(chǔ)器 （ Magicdisk storage） ? 直接讀取設(shè)備 ， 支持隨機(jī)讀取 ? 非易失聯(lián)機(jī)數(shù)據(jù)存儲(chǔ)設(shè)備 ? 訪(fǎng)問(wèn)數(shù)據(jù)時(shí) ， 磁盤(pán) ?內(nèi)存；修改后的數(shù)據(jù) ， 內(nèi)存 ?磁盤(pán) ? 光學(xué)存儲(chǔ)器 （ Optical storage） ? 只讀 (CDROM)、 一次寫(xiě)多次讀 (WORM)、 多次寫(xiě)(CDRW) ? 磁帶 （ tape） ? 順序訪(fǎng)問(wèn) ， 歸檔存儲(chǔ) ， 容量大 ， 價(jià)格便宜 磁盤(pán) 磁盤(pán) ? 基本構(gòu)成 ? 盤(pán)片 (platter)、 磁道 (track)、 扇區(qū) (sector)、 柱面(cylinder) ? 讀寫(xiě)頭 (readwrite head)：反轉(zhuǎn)磁性物質(zhì)磁化的方向 ? 磁盤(pán)臂 (disk arm) ? 磁盤(pán)控制器 (disk controller)：接受讀寫(xiě)扇區(qū)命令 ，定位讀寫(xiě)頭 。 ? 柱面 （ cylinder） 各盤(pán)片上位于同一位置的磁道構(gòu)成一個(gè)柱面 。 為到達(dá)指定扇區(qū) ， 需要先 移動(dòng) 磁盤(pán)臂 ，定位到正確的磁道 ， 然后 旋轉(zhuǎn) 磁盤(pán) ， 直到指定的扇區(qū)出現(xiàn)在讀寫(xiě)頭下方 ? 尋道時(shí)間 (seek time)：磁盤(pán)臂重定位時(shí)間 ， 取決于目標(biāo)磁道和磁盤(pán)臂當(dāng)前距離 ， 2~30毫秒 。 Da越大表明一個(gè)盤(pán)片上能存儲(chǔ)的信息量就越大 。 但是碟片數(shù)的增加會(huì)使硬盤(pán)體積增厚 ， 因此單碟容量的大小直接關(guān)系到整個(gè)硬盤(pán)容量的大小 ， 但隨著磁碟密度的提高 ， 磁頭就必須隨之越來(lái)越靈敏 。 磁盤(pán)的性能指標(biāo) ? （ 4） 緩存 ? 緩存也是磁盤(pán)相當(dāng)重要的一個(gè)參數(shù) ， 其大小也會(huì)直接影響到磁盤(pán)的整體性能 。 目前主流硬盤(pán)的緩存通常為 8MB和 16MB。 目前 ， 主流硬盤(pán)的傳輸速度通常為50~100MB/S。而磁道內(nèi)線(xiàn)性磁密度的增加則和硬盤(pán)的持續(xù)數(shù)據(jù)傳輸速度有著直接的聯(lián)系 ， 磁頭技術(shù)的發(fā)展確保了這個(gè)增長(zhǎng)不會(huì)因?yàn)榇蓬^的靈敏度的限制而放慢速度 。 例： 假設(shè)磁道數(shù)為 0——199， 我們申請(qǐng)調(diào)度的盤(pán)塊兒分別在 98, 183, 37, 122, 14, 124, 65, 67 磁道上 。 磁頭從 53號(hào)磁道開(kāi)始移動(dòng) ， 按照 65, 67, 37, 14, 98, 122, 124, 183 的順序依次查找 ， 并將數(shù)據(jù)輸入內(nèi)存 。 磁盤(pán)調(diào)度（ 4） ? CSCAN（ 環(huán)形掃描 ） 調(diào)度 ? 移動(dòng)臂總是從 0號(hào)柱面至最大號(hào)柱面順序掃描 ， 然后返回 0號(hào)柱面重復(fù)進(jìn)行 。 反方向查找服務(wù) 。 隨機(jī)數(shù)據(jù)寫(xiě)入 ，要求安全性高 ， 如服務(wù)器 、 數(shù)據(jù)庫(kù)存儲(chǔ)領(lǐng)域 。 在這里漢明碼都是以三個(gè)數(shù)據(jù)碼為基準(zhǔn)進(jìn)行編碼的 。P1+D8+D2+D1 的結(jié)果是奇數(shù) 3， 第二位糾錯(cuò)代碼為 1， 錯(cuò)誤 。 ? 4位數(shù)據(jù)需要 3位漢明碼 （ 23 ≥ 4+3+1） ， 64 位數(shù)據(jù)需要 7 位漢明碼 （ 27 ≥ 64+7+1 。 所以 RAID 2 中的硬盤(pán)數(shù)量取決于所設(shè)定的數(shù)據(jù)存儲(chǔ)寬度 。 ? RAID 2 是早期為了能進(jìn)行即時(shí)的數(shù)據(jù)校驗(yàn)而研制的一種技術(shù) ， 針對(duì)了當(dāng)時(shí)對(duì)數(shù)據(jù)即時(shí)性非常敏感的領(lǐng)域 ， 如 、 金融服務(wù)等 。 在數(shù)據(jù)存入時(shí) ， 數(shù)據(jù)陣列中處于同一等級(jí)的條帶的 XOR 校驗(yàn)編碼被即時(shí)寫(xiě)在校驗(yàn)盤(pán)相應(yīng)的位置 ， 所以彼此不會(huì)干擾混亂 。 直到更為先進(jìn)高效的 RAID 5 出現(xiàn)后 ， RAID 3 才開(kāi)始慢慢退出市場(chǎng) 。 按塊存儲(chǔ)可以保證塊的完整 ， 不受因分條帶存儲(chǔ)在其他硬盤(pán)上而可能產(chǎn)生的不利影響 （ 比如當(dāng)多個(gè)硬盤(pán)損壞 ） 。 ? RAID 4 在寫(xiě)入時(shí)要等一個(gè)硬盤(pán)寫(xiě)完后才能寫(xiě)一下個(gè) ， 還要寫(xiě)入校驗(yàn)數(shù)據(jù)所以寫(xiě)入效率比較差 ， 讀取時(shí)也是一個(gè)硬盤(pán)一個(gè)硬盤(pán)的讀 ， 但校驗(yàn)迅速 ，所以相對(duì)速度很快 。 ? RAID 3 被用在數(shù)據(jù)加強(qiáng)和加速單用戶(hù)對(duì)連續(xù)的長(zhǎng)記錄時(shí)的數(shù)據(jù)傳輸 。 它是由 Belady于 1966年提出的一種理論上的算法 。 ? FIFO：先進(jìn)先出置換算法 。 例 ? 在一個(gè)請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)中 ， 一個(gè)作業(yè)的頁(yè)面走向?yàn)? 5， 當(dāng)分配給該作業(yè)的物理塊數(shù)分別為 4時(shí) ， 試計(jì)算采用下述頁(yè)面淘汰算法時(shí)的缺頁(yè)次數(shù) (假設(shè)開(kāi)始執(zhí)行時(shí)主存中沒(méi)有頁(yè)面 )， 并比較所得結(jié)果 。該算法賦予每個(gè)頁(yè)面一個(gè)訪(fǎng)問(wèn)字段 ， 用來(lái)記錄一個(gè)頁(yè)面自上次被訪(fǎng)問(wèn)以來(lái)所經(jīng)歷的時(shí)間 t,， 當(dāng)須淘汰一個(gè)頁(yè)面時(shí) ， 選擇現(xiàn)有頁(yè)面中其 t值最大的 ， 即最近最久未使用的頁(yè)面予以淘汰 。 如果計(jì)數(shù)器為零 ， 則說(shuō)明這一緩沖區(qū)可回收使用 。 ? 對(duì)于緩沖區(qū)內(nèi)那些通過(guò)較高代價(jià)產(chǎn)生的對(duì)象 ， 系統(tǒng)使用具有較高參考價(jià)值的計(jì)數(shù)器 。 主索引禁止為產(chǎn)生索引關(guān)鍵字所指定字段或索引表達(dá)式中的重復(fù)值；因此 ， 主索引中每個(gè)索引關(guān)鍵字是唯一的 。 如果在任何包含重復(fù)數(shù)據(jù)的字段上指定主索引 ，將 產(chǎn)生一個(gè)錯(cuò)誤 。 我們認(rèn)為 NULL 值相互間不相等 。 我們沒(méi)有必要在唯一字段上建立索引 ， 那樣做只會(huì)重復(fù)建立自動(dòng)創(chuàng)建的索引 。 ? 聚集索引對(duì)于那些經(jīng)常要搜索范圍值的列特別有效 。 聚集索引 ? 當(dāng)索引值唯一時(shí) ， 使用聚集索引查找特定的行也很有效率 。Ota39。 這使非聚集索引成為精確匹配查詢(xún)的最佳方法 ， 因?yàn)樗饕枋霾樵?xún)所搜索的數(shù)據(jù)值在表中的精確位置的條目 。 ? 若未指定索引類(lèi)型 ， 則默認(rèn)為非聚集索引 ? 葉節(jié)點(diǎn)頁(yè)的次序和表的物理存儲(chǔ)次序不同 ? 每個(gè)表最多可以有 249個(gè)非聚集索引 ? 在非聚集索引創(chuàng)建之前創(chuàng)建聚集索引 (否則會(huì)引發(fā)索引重建 ) 非聚集索引 ? select * from employee where lname = 39。 ? 建議使用聚集索引的場(chǎng)合為： a. 此 列 包 含 有 限 數(shù) 目 的 不 同 值 ； b. 查 詢(xún) 的 結(jié) 果 返 回 一 個(gè) 區(qū) 間 的 值 ； c. 查詢(xún)的結(jié)果返回某值相同的大量結(jié)果集 。 何時(shí)使用聚集索引或非聚集索引 稠密索引 ? 文件中的每個(gè)搜索碼值都有一個(gè)索引記錄 稀疏索引 ? 只為搜索碼的某些值建立索引記錄 多層索引 ? 對(duì)索引建立索引 B+樹(shù) ? 樹(shù)結(jié)點(diǎn) ? Ki是搜索碼 ， Pi是指針 B+樹(shù) ? 每個(gè)非葉結(jié)點(diǎn)有 [n/2]到 n個(gè)子女 B+樹(shù) ? 插入導(dǎo)致結(jié)點(diǎn)分裂 插入 Clearview B+樹(shù) B+樹(shù) ? 刪除導(dǎo)致結(jié)點(diǎn)合并 刪除 Downtown B+樹(shù) 散列索引 ? 桶 (bucket) ? 存儲(chǔ)一條或多條記錄的存儲(chǔ)單元 ? 散列 (hash) ? K是搜索碼 ， B是桶地址 ， 散列函數(shù) h(K)=B ? 散列函數(shù) ? 分布是均勻的 ， 桶包含記錄的個(gè)數(shù)是均勻的 ? 分布是隨機(jī)的 ， 散列值不能與搜索碼的值呈現(xiàn)出相關(guān)性 ? 桶溢出 (bucket overflow) ? 桶不足 (insufficient bucket)+偏斜 (skew) 散列索引 散列索引 ? 溢出鏈 位圖索引 ? 針對(duì)一些特殊的列建立索引 ? 列中的每一個(gè)值對(duì)應(yīng)一個(gè)向量中的一位 ? 向量的長(zhǎng)度對(duì)應(yīng)與記錄的條數(shù) ? 不適合列中值的個(gè)數(shù)太多的情況 C u st R eg i o n T yp eC1 As ia R et ailC2 Europ e D ealerC3 As ia D ealerC4 Am eric a R et ailC5 Europ e D ealerR ecI D R etai l D eal er1 1 02 0 13 0 14 1 05 0 1R ec I D A si a Eu r o p e A m er i ca1 1 0 02 0 1 03 1 0 04 0 0 15 0 1 0Base table Index on Region Index on Type 位圖索引 ? 查詢(xún)： ? Select cust From BaseTable Where Region=‘Asia’ and Type=‘Dealer’； ? BitMap for Region(Asia): 10100 ? BitMap for Type(Dealer): 01101 ? 查詢(xún)結(jié)果：向量與操作： 00100 位圖索引 與 B樹(shù)的大小對(duì)比 位圖索引 ? 設(shè)表中有 10M個(gè)記錄 ， 每個(gè)記錄長(zhǎng) 800字節(jié) ， 每一頁(yè)16K字節(jié) ， 則掃描此表共需 50萬(wàn)次 I/O操作 “在美國(guó)加州有多少男性未申請(qǐng)保險(xiǎn)？” G e n d e r M M F M M 8 0 0 B y t e s / R o w 10M R O W S S t a t e NY CA CT MA CA 傳統(tǒng) R D B M S 作法 傳統(tǒng) R D B M S 做法 I n s u r e d Y Y N Y N 800 By tes x 1 0M R o w s 16K / P ag e = 5 0 0 ,0 0 0 I / O s ? ? 處理大量的數(shù)據(jù) ? ? 經(jīng)常進(jìn)行全表掃描 位圖索引 ? 對(duì)于 10M 個(gè)記錄建立三列的位圖索引共占（ 10Mbit*3列 /8)字節(jié)的空間 ， 每頁(yè) 16K， 則這些索引僅占 235頁(yè) ， 因此存取這些索引只要 235次 I/O操作 M Y CA M N CA F Y NY M N CA 1 2 4 3 G e n d e r I n s u r e d S ta te = 2 + + 1 1 0 1 1 1 0 1 0 1 0 1 10 M B i t s 10 M B i t s / 8 x 3 C o l s 16 K P a g e = 2 35 I/O s 位圖索引 RID Item Gender R1 a F R2 a M R3 b F R4 b F R5 b M R6 c F R7 c M R8 d M RID M F R1 0 1 R2 1 0 R3 0 1 R4 0 1 R5 1 0 R6 0 1 R7 1 0 R8 1 0 RID a b c d R1 1 0 0 0 R2 1 0 0 0 R3 0 1 0 0 R4 0 1 0 0 R5 0 1 0 0 R6 0 0 1 0 R7 0 0 1 0 R8 0 0 0 1 基本表 Item位圖索引