【正文】 存儲管理系統(tǒng)中 ， 一個作業(yè)的頁面走向為 5， 當分配給該作業(yè)的物理塊數(shù)分別為 4時 ， 試計算采用下述頁面淘汰算法時的缺頁次數(shù) (假設開始執(zhí)行時主存中沒有頁面 )， 并比較所得結果 。 它是由 Belady于 1966年提出的一種理論上的算法 。 ? RAID 4 在寫入時要等一個硬盤寫完后才能寫一下個 ， 還要寫入校驗數(shù)據(jù)所以寫入效率比較差 ， 讀取時也是一個硬盤一個硬盤的讀 ， 但校驗迅速 ，所以相對速度很快 。 直到更為先進高效的 RAID 5 出現(xiàn)后 ， RAID 3 才開始慢慢退出市場 。 ? RAID 2 是早期為了能進行即時的數(shù)據(jù)校驗而研制的一種技術 ， 針對了當時對數(shù)據(jù)即時性非常敏感的領域 ， 如 、 金融服務等 。 ? 4位數(shù)據(jù)需要 3位漢明碼 （ 23 ≥ 4+3+1） ， 64 位數(shù)據(jù)需要 7 位漢明碼 （ 27 ≥ 64+7+1 。 在這里漢明碼都是以三個數(shù)據(jù)碼為基準進行編碼的 。 反方向查找服務 。 磁頭從 53號磁道開始移動 ， 按照 65, 67, 37, 14, 98, 122, 124, 183 的順序依次查找 ， 并將數(shù)據(jù)輸入內(nèi)存 。而磁道內(nèi)線性磁密度的增加則和硬盤的持續(xù)數(shù)據(jù)傳輸速度有著直接的聯(lián)系 ， 磁頭技術的發(fā)展確保了這個增長不會因為磁頭的靈敏度的限制而放慢速度 。 目前主流硬盤的緩存通常為 8MB和 16MB。 但是碟片數(shù)的增加會使硬盤體積增厚 ， 因此單碟容量的大小直接關系到整個硬盤容量的大小 ， 但隨著磁碟密度的提高 ， 磁頭就必須隨之越來越靈敏 。 為到達指定扇區(qū) ， 需要先 移動 磁盤臂 ，定位到正確的磁道 ， 然后 旋轉 磁盤 ， 直到指定的扇區(qū)出現(xiàn)在讀寫頭下方 ? 尋道時間 (seek time)：磁盤臂重定位時間 ， 取決于目標磁道和磁盤臂當前距離 ， 2~30毫秒 。提綱 ? 物理存儲介質(zhì) ? RAID ? 緩沖區(qū)管理 ? 索引 ? 數(shù)據(jù)庫文件 ? 存儲分配 物理存儲介質(zhì) 物理存儲介質(zhì) ? 高速緩沖存儲器 （ cache） ? 最快最昂貴的存儲介質(zhì) ? 很小 ， 由操作系統(tǒng)管理 ? 主存儲器 （ main memory） ? 存放可被處理的數(shù)據(jù)的存儲介質(zhì) ? 易失 ， 相對整個數(shù)據(jù)庫太小 ? 快閃存儲器 （ flash memory） ? 讀性能類似主存 ， 寫速度非常慢 ? 電子可擦除可編程只讀存儲器 (Electrically Erasable Programmable ReadOnly Memory) 物理存儲介質(zhì) ? 磁盤存儲器 （ Magicdisk storage） ? 直接讀取設備 ， 支持隨機讀取 ? 非易失聯(lián)機數(shù)據(jù)存儲設備 ? 訪問數(shù)據(jù)時 ， 磁盤 ?內(nèi)存；修改后的數(shù)據(jù) ， 內(nèi)存 ?磁盤 ? 光學存儲器 （ Optical storage） ? 只讀 (CDROM)、 一次寫多次讀 (WORM)、 多次寫(CDRW) ? 磁帶 （ tape） ? 順序訪問 ， 歸檔存儲 ， 容量大 ， 價格便宜 磁盤 磁盤 ? 基本構成 ? 盤片 (platter)、 磁道 (track)、 扇區(qū) (sector)、 柱面(cylinder) ? 讀寫頭 (readwrite head)：反轉磁性物質(zhì)磁化的方向 ? 磁盤臂 (disk arm) ? 磁盤控制器 (disk controller)：接受讀寫扇區(qū)命令 ，定位讀寫頭 。 磁盤 ? 磁盤性能度量 ? 訪問時間：從發(fā)出讀寫請求到數(shù)據(jù)開始傳輸之間的時間 。 硬盤的容量與碟片數(shù) 、 面密度關系密切 ，這兩項數(shù)值越大則容量越大 。 因此緩存容量的加大可以容納更多的預讀數(shù)據(jù) ， 這樣大大縮短系統(tǒng)等待的時間 。 單碟容量越高說明單碟的磁道數(shù)越多 ， 磁道數(shù)的增加意味著磁道間距離的縮短 ， 而磁頭從一個磁道轉移到另一個磁道所需的就位時間就會縮短 ， 這將有助于隨機數(shù)據(jù)傳輸速度的提高 。 磁盤調(diào)度（ 2） ? SSTF（ 最短查找時間優(yōu)先 ） 調(diào)度 ? 考慮了各個請求之間的區(qū)別 ， 總是先執(zhí)行查找時間最短的那個請求 。 磁臂僅移動到請求的最外道就回轉 。 ? 參照位置表 ， 漢明碼處理的結果就是 1010101 。 漢明碼 ? 漢明碼的數(shù)量與數(shù)據(jù)位的數(shù)量之間的關系 :2P≥P+D+1 ， 其中 P 代表漢明碼的個數(shù) ， D 代表數(shù)據(jù)位的個數(shù) 。 但由于數(shù)據(jù)是以位為單位并行傳輸 ， 所以傳輸率也相當快 。 ? RAID 3 在 RAID 2 基礎上成功地進行結構與運算的簡化 ， 曾受到廣泛的歡迎 ， 并大量應用 。 因此即使是當前硬盤上的數(shù)據(jù)塊損壞 ， 也可以通過 XOR 校驗值和其他硬盤上的同級數(shù)據(jù)進行恢復 。 ? RAID 10 集良好的可靠性和高性能于一身 . 選擇合適的 RAID級別 ? RAID 0 ? 無冗余拆分 ? RAID 1 ? 鏡像 ? RAID 5 ? 拆分＋校驗碼 ? RAID 10 ? 拆分＋鏡像 選擇合適的 RAID級別 R e a d I n t e n s i v e020220400006000080000So ftR A I D 5R A I D 5 R A I D 0 R A I D 1 0 R A I D 1 Si n g l eD i s kThroughput (tuples/sec)選擇合適的 RAID級別 Wri te Int e nsiv e04080120160So ftR A I D 5R A I D 5 R A I D 0 R A I D 1 0 R A I D 1 Si n g l eD i s kThroughput (tuples/sec)選擇合適的 RAID級別 ? 日志文件 ? RAID 1 ? 容錯 ， 高寫輸出率 ? 臨時文件 ? RAID 0 is appropriate. ? 無容錯 ， 高吞吐率 ? 數(shù)據(jù)以及索引文件 ? RAID 5適合于讀為主的應用 ? RAID 10適合于寫為主的應用 磁盤還是內(nèi)存 ? 保持常用數(shù)據(jù)在內(nèi)存 ， 可以減少磁盤 I/O， 但增加內(nèi)存代價 ? 若一個頁面每秒被訪問 n次 ， 將它駐留在內(nèi)存節(jié)省 ? 保持一個頁面在內(nèi)存的代價 n * priceperdiskdrive accessespersecondperdisk priceperMBofmemory pagesperMBofmemory 磁盤還是內(nèi)存 ? 5minute rule： 如果一個被隨機訪問的頁面的使用頻率超過每 5分鐘一次 ， 那么它應該被駐留在內(nèi)存 ? 1minute rule： 如果被順序訪問的頁面的使用頻率超過每 1分鐘一次 ， 那么它應該被駐留在內(nèi)存 priceperdiskdrive=2022$/disk accessespersecondperdisk=64accesses/second/disk priceperMBofmemory=15$/MB_RAM pagesperMBofmemory=128pages/MB 2022 * 128/15/64/=266 緩沖區(qū)管理 ? 當需要訪問一個磁盤塊時 ? 如果該塊已經(jīng)在緩沖區(qū)中 ， 返回塊在內(nèi)存中的地址 ? 如果塊不在緩沖區(qū)中 ? 緩沖區(qū)管理器為該塊在緩沖區(qū)中分配空間 ， 如果有必要 ，替換緩沖區(qū)中的其他塊 ? 如果被替換的塊被修改過 ， 則將其寫回磁盤 ? 將所需的塊調(diào)入緩沖區(qū) ， 返回其在緩沖區(qū)的地址 緩沖區(qū)管理 ? 被釘住的塊 (pinned blocks) ? 不允許寫回磁盤的塊 ? 當一個塊上的更新正在進行時 ， 不允許寫回磁盤 ? 釘住被頻繁訪問的小表 ? 塊的強制輸出 (forced output of blocks) ? 先寫日志原則 ? 檢查點 ? 提交事務的日志記錄 緩沖區(qū)管理 ：替換策略 ? LRU(最近最少使用 ) ? 如果必須替換一個塊 ， 則替換最近最少使用的塊 ? MRU(最近最常使用 ) ? 如果必須替換一個塊 ， 則替換最近最常使用的塊 SR ??對于 R中的每條元組 tr 對于 S中的每條元組 ts …… ? 一旦 R中的一個元組處理完 ， 就不會再使用它了 ， 應該立即丟棄 (toss immediate) ? 當 S 中的一個元組被處理完 ， 只 有 其 他 S中的元組都被處理完后才會再用到它 ， 應該采用 MRU 替換策略 ? 當使用者第一次向數(shù)據(jù)庫發(fā)出查詢數(shù)據(jù)的請求時 ， 數(shù)據(jù)庫會先在緩沖區(qū)中查找該數(shù)據(jù) ,如果要訪問的數(shù)據(jù)恰好已經(jīng)在緩沖區(qū)中 (稱之為Cache Hit),那么就直接用緩沖區(qū)中讀取該數(shù)據(jù) . ? 反之如果緩沖區(qū)中沒有使用者要查詢的數(shù)據(jù)稱之為 Cache Miss,這種情況下數(shù)據(jù)庫就會先從磁盤上讀取使用者要的數(shù)據(jù)放入緩沖區(qū) ,使用者再從緩沖區(qū)讀取該數(shù)據(jù) . ? 很顯然 Cache Hit會比 Cache Miss時存取速度快 . OPTIMAL/FIFO ? OPTIMAL：最佳置換算法 。 該算法實現(xiàn)簡單只需把一個進程已調(diào)入內(nèi)存的頁面 ， 按先后次序鏈接成一個隊列 ， 并設置一個指針 ， 稱為替換指針 ， 使它總是指向最老的頁面 。 它為每個緩沖區(qū)設置一個計數(shù)器 ， 每隔一段時間則順序掃描緩沖池里的每一個緩沖區(qū) ， 檢查計數(shù)器 。 索引 ? 順序索引 ? 基于值的順序排序 ? 散列索引 ? 基于將值平均分布到若干散列桶中 ? 索引評價指標 ? 訪問類型 ? 訪問時間 ? 插入時間 ? 刪除時間 ? 空間開銷 主索引和輔助索引 ? 主索引 (primary index)、 輔助索引 (secondary index)；聚集索引 (cluster index)、 非聚集索引(noncluster index) branch_name balance 主索引 ? 主索引包含表中每條記錄的索引關鍵字并且當未指定任何其他索引作為表主索引時的默認索引 。 ? 如果索引聲明為唯一的 ， 那么就不允許出現(xiàn)多個索引值相同的行 。 但該索引可以包含多個列 （ 組合索引 ） 。 ? 也可以在 lname（ 姓氏 ） 列和 fname（ 名字 ）列上創(chuàng)建聚集索引 ， 因為雇員記錄常常是按姓名而不是按雇員 ID 分組和查詢的 聚集索引 ? 聚集索引的葉節(jié)點就是實際的數(shù)據(jù)頁 ? 在數(shù)據(jù)頁中數(shù)據(jù)按照索引順序存儲 ? 行的物理位置和行在索引中的位置是相同的 ? 每個表只能有一個聚集索引 ? 聚集索引的平均大小大約為表大小的 5%左右 聚集索引 ? select * from table where firstName = 39。 非聚集索引 ? 非聚集索引的頁 ， 不是數(shù)據(jù) ， 而是指向數(shù)據(jù)頁的頁 。 ? 建議使用非聚集索引的場合為： ? ； ； c. order by 子句中使用了該列 。 其中 LcdPt 域和 RcdPt域分別表示指向左孩子結點和右孩子結點的指針； Xcoord 和 Ycoord 各自保存數(shù)據(jù)點 X 和 Y 的坐標值或?qū)傩灾担?NAME 域用來保存結點描述信息 ， 即屬性 ( 例如薪水 )；Disc域表示結點識別的坐標名 (也就是比較坐標名 ) 。 ? 為實現(xiàn)一個插入 ， 首先要查找 ， 定位到葉結點 ，如果葉結點的塊中還有空間 ， 就把新的數(shù)據(jù)點放在那里 ， 如果沒有空間 ， 就把塊分裂成兩塊 。 該內(nèi)結點的左邊只有一個記錄 (25， 400)， 而右邊是有另外兩個記錄的葉結點塊 。 在左子結點 ， 只需往左走 ，在右子結點 ,只需考慮它的右子樹 。四叉樹索引有滿四叉樹索引和一般四叉樹索引 。 R樹 ? RTree是一種空間索引數(shù)據(jù)結構 ， 下面做簡要介紹： ? （ 1） RTree是 n 叉樹 ， n稱為 RTree的扇 （ fan） 。 樹上有兩類結點：葉子結點和非葉子結點 。 每個結點所能擁有的子結點數(shù)目有上 、 下限 ， 下限保證對磁盤空間的有效利用 ，上限保證每個結點對應一個磁盤頁 ， 當插入新的結點導致某結點要求的空間大于一個磁盤頁時 ， 該結點一分為二 。 設 M和 m( m≤ M)為 R樹結點中單元個數(shù)的上限和下限 ， 當新的空間要素的插入使葉子結點中的單元個數(shù)超過 M時 ， 需要進行結點的分裂操作 。 查找到該空間要素所在的葉子結點后 ， 刪除其對應的單元 。 但是用什么樣的規(guī)則來衡量空間要素的聚集 ， 是一個非常復雜的問題 。 ? R樹空間索引具有其他索引方法無法比擬的優(yōu)勢： ? 它按數(shù)據(jù)來組織索引結構 。 當有多個數(shù)據(jù)庫