1、第2部分 關系數據庫系統實現第4章 數據存放和組織管理高級數據庫系統及其應用數據存儲與組織管理第1頁第4章 數據存放和組織管理物理存放介質4.1磁盤空間管理4.2文件頁組織4.3頁表示格式4.4統計表示格式4.5DB元信息及其組織管理4.6DB緩沖區管理4.7數據存儲與組織管理第2頁4.1 物理存放介質4.1.1 存放介質層次 4.1.2 磁盤物理特征4.1.3 磁盤故障及其處理策略 4.1.4 磁盤塊存取優化數據存儲與組織管理第3頁4.1.1 存放介質層次數據存儲與組織管理第4頁4.1.2 磁盤物理特征（1）磁盤結構硬盤容量 盤面數每盤面磁道數每磁道扇區數每扇區字節數 數據存儲與組織管理第5

2、頁4.1.2 磁盤物理特征（2）磁盤基本操作特征磁盤讀寫最小單位是扇區。但在操作系統或DBMS系統層次，磁盤讀寫基本單位是磁盤塊(block)。不一樣系統塊大小可能不一樣，大多數系統塊取4KB。進行實際磁盤讀寫時，主存中必須有磁盤塊緩沖區；在磁盤和主存之間傳送一個磁盤塊稱為1次I/O操作。讀寫一個塊時間:尋道時間旋轉延遲時間傳輸時間。數據存儲與組織管理第6頁例4.1 假設有一個含3個盤片硬盤，共有4個統計面，轉速為4500轉/分鐘，盤面有效統計區域外直徑為30cm，內直徑為10cm，統計位密度為250位/mm，磁道密度為8道/mm，每個磁道分16扇區，每扇區512字節。試計算：1）磁盤總磁道數

3、2）非格式化容量3）平均速度傳輸速率。 數據存儲與組織管理第7頁例4.2 假設一個含有以下特征硬盤：共有4個盤片，8個盤面；每個盤面有8192個磁道，每個磁道平都有256個扇區；每個扇區512個字節。試計算以下磁盤參數：1）磁盤格式化容量。2）若一個塊大小為4096字節，求每個磁道能存放塊數。3）假如磁盤數據區外徑為3.5英寸、內徑為1.5英寸， 求磁盤徑向密度。4）假定扇區間隙占磁道長度10%，則磁盤最內和最外磁道上位密度分別是多少？ 5）若磁盤轉速為3840轉/分，即1/64秒轉一周。磁頭起落1次1毫秒，每移過500個磁道另加1毫秒，試計算讀寫一個塊平均時間。 數據存儲與組織管理第8頁4.

4、1.3 磁盤故障及其處理策略一、磁盤故障分類 磁盤故障通常有以下幾個方式或類型：間斷性故障。寫故障。部分介質損壞。磁盤瓦解。二、校驗和技術磁盤扇區通常會存放一些冗余位，以可幫助識別從扇區讀出內容是否正確。最簡單校驗和:是基于扇區內全部位奇偶性。經過增加奇偶位數，可降低檢不犯錯誤概率。若用n個位存放校驗和,則漏檢錯誤概率僅為1/2 n 數據存儲與組織管理第9頁4.1.3 磁盤故障及其處理策略一、磁盤故障分類二、校驗和技術三、穩定存放技術校驗和技術能幫助檢測讀寫故障或介質故障，但不能幫助我們糾正錯誤。基于穩定存放(stable storage)多副本策略，可能幫助我們一定程度上處理這個問題。四、從

5、瓦解磁盤故障恢復：RAID技術 磁盤冗余陣列 磁盤組織技術。Redundant Array of Inexpensive Disks數據存儲與組織管理第10頁幾個慣用RAID級介紹 1RAID0級(nonredundant striping)把數據分拆到多塊磁盤并行存貯（位級拆分且沒有任何冗余）。在全部RAID級中，RAID0含有最好寫性能，但安全性最低。2RAID1級(mirrored disks)為每一個磁盤配置一鏡像磁盤，適合于安全性要求很高場所。有效容量利用率只有50，成本較高。數據存儲與組織管理第11頁幾個慣用RAID級介紹 3RAID2級(error-Correcting Code

6、s錯誤-校正碼)采取若干數據盤拆存字節中位(bits)，并對每個字節計算奇偶校驗位，額外校驗位存放在冗余盤。對有D個數據盤磁盤陣列中，一次讀寫傳輸最少是D個塊。較有利于傳輸數據量大磁盤請求，不利于傳輸數據量小磁盤請求。4. RAID3級(Bit-Interleaved Parity位-奇偶交替) RAID2中因配置了較多冗余校驗盤，能自動處理壞盤檢測問題，但也增大了代價。RAID3只使用一個冗余磁盤，即采取最低安全性開銷。RAID2/3寫操作都需要一個read-modify-write 周期過程。 數據存儲與組織管理第12頁幾個慣用RAID級介紹 5RAID4級(block-Interleav

7、ed Parity塊-奇偶交替) 拆存單位是一個磁盤塊。塊級分存優點是能充分利用塊設備工作特征，且能適應各種數據量傳輸磁盤請求。不論有多少個數據磁盤，RAID4只用一個冗余盤存放各數據盤中奇偶校驗數據。6. RAID5級是RAID4改進。RAID4中校驗數據塊總是用一個固定盤來存放，而在RAID5中，校驗塊是交替分布在各磁盤上。 RAID4磁盤讀寫過程讀塊過程：直接讀出對應數據盤中目標塊即可。寫塊過程：除了寫目標數據盤外，還要修改冗余盤上對應塊數據。寫單個塊需要一個read- modify- write 周期過程。 校驗盤對應塊新數據(當前數據盤當前塊原數據 XOR 當前數據盤當前塊新數據 )

8、 XOR 校驗盤對應塊原數據數據存儲與組織管理第13頁幾個慣用RAID級介紹 7RAID6級(P+Q Redundancy)使用RAID6主要動機是：在很大磁盤陣列中，僅能恢復一個壞盤顯得安全性不足；同時出現兩個壞盤，或在恢復過程中又出現壞盤情況也必須考慮。RAID6普通采取基于Hamming-Code編碼數據盤-校驗盤組合方案，使得能同時恢復兩個壞盤。RAID6故障恢復步驟數據存儲與組織管理第14頁4.1.4 磁盤塊存取優化在多數OS中，磁盤I/O請求是由文件系統和虛擬內存管理器產生。DB系統中，系統高層頁請求經過磁盤空間管理器，也會產生基于磁盤塊I/O請求。因為存取磁盤比存取主存要慢好幾個

9、量級，所以，DB系統改進磁盤塊存取性能非常主要。 數據存儲與組織管理第15頁4.1.4 磁盤塊存取優化一、磁頭調度技術先到先服務電梯算法例4.6 假設某磁盤平均尋道時間、旋轉等候時間和塊傳輸時間分別為6.5、7.8和0.5毫秒。某一時刻存在著對柱面1000、3000、7000塊訪問請求。初始時磁頭正位于1000柱面上而且是向上移動。另外，還有3個請求在稍后到來。 試用電梯調度和FIFO策略調度算法，分別計算完成各塊請求服務時間。 數據存儲與組織管理第16頁4.1.4 磁盤塊存取優化一、磁頭調度技術先到先服務電梯算法二、采取特殊文件組織方式按連續柱面存放數據三、采取磁盤緩沖池技術基于“傳輸控制層

10、” DB數據緩沖池技術磁盤預取技術雙緩沖技術數據存儲與組織管理第17頁4.2 磁盤空間管理4.2.1 磁盤空間管理器 4.2.2 利用OS管理磁盤空間4.2.3 跟蹤自由塊 數據存儲與組織管理第18頁磁盤空間管理器是DBMS體系結構最低層軟件模塊，隱藏了與磁盤相關全部下層軟硬件操作細節，并支持以頁為單位數據管理。頁(page)大小通常就是磁盤塊(block)大小，讀寫一個頁可經過一次磁盤塊I/O完成。允許高層軟件認為DB數據是一系列以頁為單位磁盤數據集合。提供分配、釋放和讀寫頁相關命令操作經過磁盤空間管理器，可將DB中“關系”映射到 “關系數據文件”.這種“文件”既可能是實際OS文件，也可能只

11、是一個虛擬OS文件。數據存儲與組織管理第19頁4.3 文件頁組織4.3.1 堆文件 4.3.2 排序文件4.3.3 索引文件 本節內容安排 單個統計文件所包含統計集， 可能存放在若干不一樣頁上。 高層DBMS代碼普通將“頁”視為容納 多個統計對象，忽略頁中詳細數據 表示方式或存放細節。 重點討論文件中相關頁組織方式。統計唯一標識符rid，可被用來識別統計所屬頁及統計在頁內相對位置。數據存儲與組織管理第20頁4.3.1 堆文件屬無序文件，文件中頁大小相同。堆文件頁中統計是無序，只能次序存取。每個統計有唯一標識rid。 堆文件管理支持創建/刪除堆文件; 掃描文件; 插入/刪除/檢索給定rid統計。

12、不能直接幫助定位滿足指定查詢條件相關統計rids 數據存儲與組織管理第21頁基于雙向頁鏈表堆文件組織 將文件頁以雙鏈表方式鏈接在一起。缺點變長統計情況下，可能全部頁都有空閑；檢索統計可能需次序掃描多個頁 數據存儲與組織管理第22頁基于目錄頁堆文件組織 組織結構允許有多個目錄頁，不一樣目錄頁經過指針鏈接在一起。目錄頁中包含多個目錄項，每個目錄項標識一個頁。優點：有利于更有效搜索足夠容納新統計數據頁。 數據存儲與組織管理第23頁4.3.2 排序文件文件中統計集按搜索鍵（search key）排序普通采取指針把統計按次序鏈接起來。能支持按搜索鍵以次序或隨機方式快速獲取統計，這對特定排序查詢非常有用。

13、為降低處理排序文件時頁請求次數，需要盡可能地按搜索鍵次序來存放統計。但絕對維持統計物理上次序排序往往非常困難,代價非常高。更常見做法是：刪統計時僅做標識并留下空位，暫不移動其它統計插入時，對應位置即使沒有空，也暫時不移動其它統計來騰出位置，而是引入溢出頁。必要時，系統重組文件（安排在相對空閑時間）數據存儲與組織管理第24頁4.3.3 基于索引文件組織利用輔助索引文件來幫助定位數據統計。索引文件統計:索引項數據存儲與組織管理第25頁4.4 頁表示格式4.4.1 定長統計4.4.2 變長統計在處理與I/O相關主題時，通常采取頁層次抽象已足夠。高層DBMS軟件將數據視為統計集。為提升一些特殊應用性能

14、，系統也允許用戶指定數據文件存放組織一些選項參數。這需要深入了解頁內統計組織方式(即頁格式)。普通可將頁視為槽集合，每個槽可容納一個統計。統計可經過使用rid：來標識定位。數據存儲與組織管理第26頁因全部統計長度都相同，可在頁內均勻、連續地安排統計槽。4.4.1 定長統計數據存儲與組織管理第27頁DB系統中，變長統計是很常見：統計類型中含有一個或多個變長字段；統計中包含可重復、數量不確定字段；允許在一個頁中存放各種統計類型。對于變長統計存放，不能將頁簡單地劃分為均勻槽集。必須仔細處理以下兩個問題：當插入一個統計時，怎樣能找到一個恰好能容納新統計空間；怎樣跟蹤統計刪除后空間。 4.4.2 變長統

15、計數據存儲與組織管理第28頁基于分槽式頁結構表示變長統計(圖4.10) 數據存儲與組織管理第29頁4.5 統計表示格式4.5.1 定長統計字段表示 4.5.2 變長統計字段表示4.5.3 跨頁統計管理技術 4.5.4 巨型字段/對象管理技術4.5.5 指針統計管理技術指針混寫統計首部信息 DB中統計除了存放各字段信息外， 通常還有一個統計首部（統計頭）。統計頭中存放統計層次普通管理 信息，包含統計長度、時間戳和指向 統計模式描述指針等。統計是否變長主要看它是否含變長字段。本節集中討論統計中字段表示問題。數據存儲與組織管理第30頁4.5 統計表示格式（圖4.11)4.5.1 定長統計字段表示4.

16、5.2 變長統計字段表示（一）預留空間技術（二）采取特殊字符結尾來實現變長字段（三）采取偏移數組來實現變長字段數據存儲與組織管理第31頁4.5.3 跨頁統計管理技術跨頁統計存在原因最少有兩個：統計中存在大型或巨型字段；出于節約存放空間需要。即使統計大小不超出1頁，但為了利用頁內零頭空間，也會造成跨頁統計。跨頁統計會被分割并分存到多個頁中，故需要在各頁中使用指針把它們鏈接在一起，形成單個統計頁鏈。數據存儲與組織管理第32頁4.5.4 巨型字段/對象管理技術一些應用可能包含非常大巨型對象。比如，一個多媒體對象可能占用幾個MB空間；一個視頻序列，可能達幾個GB。在RDB中，巨型字段也稱為長字段。可使

17、用BLOB等專門字段型來存放巨型對象.ODB能夠直接管理巨型對象。大多數RDB限制統計大小不超出1頁，以簡化緩沖區和空閑空間管理。對超出一個頁大對象或長字段，普通采取以下兩種管理方法：用跨頁統計存放技術；將它們單獨存放在一些文件或文件集中。數據存儲與組織管理第33頁4.5.5 指針字段管理技術：指針混寫（1）指針或地址經常是統計一部分。當DB系統運行時，數據頁允許在主存和輔存之間移動，故指針所指向目標頁/統計，在特定時間，既可能在輔存，也可能在主存。對應地，指針或地址也就有兩種形式：內存地址數據庫地址，也稱持久化指針。是一個在輔存DB空間地址通常是一個邏輯地址。經過DB系統“邏輯/物理地址映射

18、表”，可將其映射為實際磁盤物理塊地址。數據存儲與組織管理第34頁4.5.5 指針字段管理技術：指針混寫（2）依據給定指針或地址尋找目標對象過程，稱為解引用(dereference)。C+內存指針引用語法：*指針名給定一個持久化指針，解引用一個對象需要額外步驟：須經過 “轉換表” 查找持久化指針所代表對象在內存中實際位置。如對象不在內存，則要從磁盤讀入，同時要修改轉換表，并將存放該持久指針內存單元，直接修改為目標對象內存位置指針。下一次同一持久化指針再次被解引用時，就能夠直接使用內存引用，從而可防止重復轉換內存地址過程開銷。當對象被寫回磁盤時，它所包含任何被混寫持久化指針必須執行反混寫，與內存指

19、針解引用相比，經過轉換表實現解引用仍是一個慢過程。 指針混寫時機選擇 自動混寫；按需混寫；不混寫；程序控制數據存儲與組織管理第35頁4.6 DB元信息及其存放管理在RDB系統，除了關系，還需要維護關于整個DB元描述數據，如關系模式等。這類元信息稱為數據字典(data dictionary)或系統目錄(system catalog)。系統需存放元信息類型有： 關系模式（關系名、每個屬性名字/類型/長度）。在DB上定義視圖名字和視圖定義。完整性約束。授權名、認證密碼等關于用戶帳戶信息。當前關系實例統計/描述數據。如每個關系中元組總數，或各字段取值統計直方圖信息等描述信息。實際上，全部這些信息組成了一個微型數據庫數據存儲與組織管理第36頁4.7 緩沖區管理4.7.1 DB緩沖池與緩