數(shù)據(jù)存儲與組織管理演示文稿

數(shù)據(jù)存儲與組織管理演示文稿本文檔共39頁；當前第1頁；編輯于星期日\15點21分優(yōu)選數(shù)據(jù)存儲與組織管理本文檔共39頁；當前第2頁；編輯于星期日\15點21分第4章數(shù)據(jù)存儲和組織管理物理存儲介質(zhì)4.1磁盤空間管理4.2文件的頁組織4.3頁表示格式4.4記錄表示格式4.5DB元信息及其組織管理4.6DB緩沖區(qū)管理4.7本文檔共39頁；當前第3頁；編輯于星期日\15點21分4.1物理存儲介質(zhì)4.1.1存儲介質(zhì)的層次4.1.2磁盤的物理特性4.1.3磁盤故障及其處理策略4.1.4磁盤塊存取的優(yōu)化本文檔共39頁；當前第4頁；編輯于星期日\15點21分4.1.1存儲介質(zhì)的層次本文檔共39頁；當前第5頁；編輯于星期日\15點21分4.1.2磁盤的物理特性（1）磁盤結(jié)構(gòu)硬盤容量＝盤面數(shù)×每盤面磁道數(shù)×每磁道扇區(qū)數(shù)×每扇區(qū)字節(jié)數(shù)

本文檔共39頁；當前第6頁；編輯于星期日\15點21分4.1.2磁盤的物理特性（2）磁盤基本操作特性磁盤讀寫的最小單位是扇區(qū)。但在操作系統(tǒng)或DBMS系統(tǒng)層次，磁盤讀寫的基本單位是磁盤塊(block)。不同系統(tǒng)塊大小可能不同，大多數(shù)系統(tǒng)的塊取4KB。進行實際磁盤讀寫時，主存中必須有磁盤塊緩沖區(qū)；在磁盤和主存之間傳送一個磁盤塊稱為1次I/O操作。讀寫一個塊的時間:尋道時間＋旋轉(zhuǎn)延遲時間＋傳輸時間。本文檔共39頁；當前第7頁；編輯于星期日\15點21分例4.1

假設(shè)有一個含3個盤片的硬盤，共有4個記錄面，轉(zhuǎn)速為4500轉(zhuǎn)/分鐘，盤面有效記錄區(qū)域的外直徑為30cm，內(nèi)直徑為10cm，記錄位密度為250位/mm，磁道密度為8道/mm，每個磁道分16扇區(qū)，每扇區(qū)512字節(jié)。試計算：1）磁盤的總磁道數(shù)2）非格式化容量3）平均速度傳輸速率。本文檔共39頁；當前第8頁；編輯于星期日\15點21分例4.2

假設(shè)一種具有如下特性的硬盤：共有4個盤片，8個盤面；每個盤面有8192個磁道，每個磁道平均有256個扇區(qū)；每個扇區(qū)512個字節(jié)。試計算以下磁盤參數(shù)：1）磁盤格式化容量。2）若一個塊大小為4096字節(jié)，求每個磁道能存放的塊數(shù)。3）如果磁盤數(shù)據(jù)區(qū)外徑為3.5英寸、內(nèi)徑為1.5英寸，求磁盤的徑向密度。4）假定扇區(qū)間隙占磁道長度的10%，則磁盤最內(nèi)和最外磁道上的位密度分別是多少？5）若磁盤轉(zhuǎn)速為3840轉(zhuǎn)/分，即1/64秒轉(zhuǎn)一周。磁頭起落1次1毫秒，每移過500個磁道另加1毫秒，試計算讀寫一個塊的平均時間。本文檔共39頁；當前第9頁；編輯于星期日\15點21分4.1.3磁盤故障及其處理策略一、磁盤故障分類磁盤故障通常有以下幾種方式或類型：間斷性故障。寫故障。部分介質(zhì)損壞。磁盤崩潰。二、校驗和技術(shù)磁盤扇區(qū)通常會存儲一些冗余位，以可幫助識別從扇區(qū)讀出的內(nèi)容是否正確。最簡單的校驗和:是基于扇區(qū)內(nèi)所有位的奇偶性。通過增加奇偶位數(shù)，可降低檢不出錯誤的概率。若用n個位存儲校驗和,則漏檢錯誤的概率僅為1/2n

本文檔共39頁；當前第10頁；編輯于星期日\15點21分4.1.3磁盤故障及其處理策略一、磁盤故障分類二、校驗和技術(shù)三、穩(wěn)定存儲技術(shù)校驗和技術(shù)能幫助檢測讀寫故障或介質(zhì)故障，但不能幫助我們糾正錯誤?；诜€(wěn)定存儲(stablestorage)的多副本策略，可能幫助我們一定程度上解決這個問題。四、從崩潰的磁盤故障恢復(fù)：RAID技術(shù)磁盤冗余陣列的磁盤組織技術(shù)。RedundantArrayofInexpensiveDisks本文檔共39頁；當前第11頁；編輯于星期日\15點21分幾種常用的RAID級簡介

1．RAID0級(nonredundantstriping)把數(shù)據(jù)分拆到多塊磁盤并行存貯（位級拆分且沒有任何冗余）。在所有RAID級中，RAID0具有最好的寫性能，但安全性最低。2．RAID1級(mirroreddisks)為每一個磁盤配置一鏡像磁盤，適合于安全性要求很高場合。有效容量利用率只有50℅，成本較高。本文檔共39頁；當前第12頁；編輯于星期日\15點21分幾種常用的RAID級簡介

3．RAID2級(error-CorrectingCodes錯誤-校正碼)采用若干數(shù)據(jù)盤拆存字節(jié)中的位(bits)，并對每個字節(jié)計算奇偶校驗位，額外的校驗位存儲在冗余盤。對有D個數(shù)據(jù)盤的磁盤陣列中，一次讀寫傳輸最少是D個塊。較有利于傳輸數(shù)據(jù)量大的磁盤請求，不利于傳輸數(shù)據(jù)量小的磁盤請求。4.RAID3級(Bit-InterleavedParity位-奇偶交替)RAID2中因配置了較多的冗余校驗盤，能自動解決壞盤檢測問題，但也增大了代價。RAID3只使用一個冗余磁盤，即采用最低的安全性開銷。RAID2/3寫操作都需要一個read-modify-write的周期過程。本文檔共39頁；當前第13頁；編輯于星期日\15點21分幾種常用的RAID級簡介

5．RAID4級(block-InterleavedParity塊-奇偶交替)

拆存單位是一個磁盤塊。塊級分存優(yōu)點是能充分利用塊設(shè)備工作特性，且能適應(yīng)各種數(shù)據(jù)量傳輸?shù)拇疟P請求。不論有多少個數(shù)據(jù)磁盤，RAID4只用一個冗余盤存儲各數(shù)據(jù)盤中的奇偶校驗數(shù)據(jù)。6.RAID5級是RAID4的改進。RAID4中校驗數(shù)據(jù)塊總是用一個固定盤來存儲，而在RAID5中，校驗塊是交替分布在各磁盤上?！頡AID4磁盤讀寫過程讀塊過程：直接讀出相應(yīng)數(shù)據(jù)盤中的目標塊即可。寫塊過程：除了寫目標數(shù)據(jù)盤外，還要修改冗余盤上對應(yīng)塊數(shù)據(jù)。寫單個塊需要一個read-modify-write的周期過程。校驗盤對應(yīng)塊新數(shù)據(jù)＝(當前數(shù)據(jù)盤當前塊原數(shù)據(jù)

XOR當前數(shù)據(jù)盤當前塊新數(shù)據(jù))XOR校驗盤對應(yīng)塊原數(shù)據(jù)本文檔共39頁；當前第14頁；編輯于星期日\15點21分幾種常用的RAID級簡介

7．RAID6級(P+QRedundancy)使用RAID6的主要動機是：在很大的磁盤陣列中，僅能恢復(fù)一個壞盤顯得安全性不足；同時出現(xiàn)兩個壞盤，或在恢復(fù)過程中又出現(xiàn)壞盤的情況也必須考慮。RAID6一般采用基于Hamming-Code編碼的數(shù)據(jù)盤-校驗盤組合方案，使得能同時恢復(fù)兩個壞盤。RAID6的故障恢復(fù)步驟本文檔共39頁；當前第15頁；編輯于星期日\15點21分4.1.4磁盤塊存取的優(yōu)化在多數(shù)OS中，磁盤I/O請求是由文件系統(tǒng)和虛擬內(nèi)存管理器產(chǎn)生的。DB系統(tǒng)中，系統(tǒng)高層的頁請求通過磁盤空間管理器，也會產(chǎn)生基于磁盤塊的I/O請求。由于存取磁盤比存取主存要慢好幾個量級，所以，DB系統(tǒng)改善磁盤塊存取性能非常重要。

本文檔共39頁；當前第16頁；編輯于星期日\15點21分4.1.4磁盤塊存取的優(yōu)化一、磁頭調(diào)度技術(shù)先到先服務(wù)電梯算法例4.6

假設(shè)某磁盤的平均尋道時間、旋轉(zhuǎn)等待時間和塊傳輸時間分別為6.5、7.8和0.5毫秒。某一時刻存在著對柱面1000、3000、7000的塊訪問請求。初始時磁頭正位于1000柱面上而且是向上移動。此外，還有3個請求在稍后到來。

試用電梯調(diào)度和FIFO策略調(diào)度算法，分別計算完成各塊請求服務(wù)的時間。本文檔共39頁；當前第17頁；編輯于星期日\15點21分4.1.4磁盤塊存取的優(yōu)化一、磁頭調(diào)度技術(shù)先到先服務(wù)電梯算法二、采用特殊的文件組織方式按連續(xù)柱面存儲數(shù)據(jù)三、采用磁盤緩沖池技術(shù)基于“傳播控制層”的DB數(shù)據(jù)緩沖池技術(shù)磁盤預(yù)取技術(shù)雙緩沖技術(shù)本文檔共39頁；當前第18頁；編輯于星期日\15點21分4.2磁盤空間管理4.2.1磁盤空間管理器4.2.2利用OS管理磁盤空間4.2.3跟蹤自由塊本文檔共39頁；當前第19頁；編輯于星期日\15點21分磁盤空間管理器是DBMS體系結(jié)構(gòu)的最低層軟件模塊，隱藏了與磁盤有關(guān)的所有下層軟硬件操作細節(jié)，并支持以‘頁’為單位的數(shù)據(jù)管理。頁(page)的大小通常就是磁盤塊(block)大小，讀寫一個頁可通過一次磁盤塊I/O完成。允許高層軟件認為DB數(shù)據(jù)是一系列以頁為單位的磁盤數(shù)據(jù)集合。提供分配、釋放和讀寫頁的有關(guān)命令操作通過磁盤空間管理器，可將DB中的“關(guān)系”映射到“關(guān)系數(shù)據(jù)文件”.這種“文件”既可能是實際的OS文件，也可能只是一個虛擬的OS文件。本文檔共39頁；當前第20頁；編輯于星期日\15點21分4.3文件的頁組織4.3.1堆文件4.3.2排序文件4.3.3索引文件本節(jié)內(nèi)容安排

單個記錄文件所包含的記錄集，可能存儲在若干不同的頁上。高層DBMS代碼一般將“頁”視為容納多個記錄的對象，忽略頁中具體數(shù)據(jù)的表示方式或存儲細節(jié)。重點討論文件中有關(guān)頁的組織方式。記錄唯一標識符rid，可被用來識別記錄所屬的頁及記錄在頁內(nèi)的相對位置。本文檔共39頁；當前第21頁；編輯于星期日\15點21分4.3.1堆文件屬無序文件，文件中頁的大小相同。堆文件頁中的記錄是無序的，只能順序存取。每個記錄有唯一標識rid。堆文件管理支持創(chuàng)建/刪除堆文件;掃描文件;插入/刪除/檢索給定rid的記錄。不能直接幫助定位滿足指定查詢條件的有關(guān)記錄rids本文檔共39頁；當前第22頁；編輯于星期日\15點21分基于雙向頁鏈表的堆文件組織

將文件頁以雙鏈表方式鏈接在一起。缺點變長記錄情況下，可能所有頁都有空閑；檢索記錄可能需順序掃描多個頁

本文檔共39頁；當前第23頁；編輯于星期日\15點21分基于目錄頁的堆文件組織

組織結(jié)構(gòu)允許有多個目錄頁，不同的目錄頁通過指針鏈接在一起。目錄頁中包含多個目錄項，每個目錄項標識一個頁。優(yōu)點：有利于更有效搜索足夠容納新記錄的數(shù)據(jù)頁。本文檔共39頁；當前第24頁；編輯于星期日\15點21分4.3.2排序文件文件中記錄集按搜索鍵（searchkey）排序一般采用指針把記錄按順序鏈接起來。能支持按搜索鍵以順序或隨機方式快速獲取記錄，這對特定的排序查詢非常有用。為減少處理排序文件時頁請求的次數(shù)，需要盡可能地按搜索鍵順序來存儲記錄。但絕對維持記錄物理上的順序排序往往非常困難,代價非常高。更常見的做法是：刪記錄時僅做標記并留下空位，暫不移動其它記錄插入時，相應(yīng)位置即使沒有空，也暫時不移動其它記錄來騰出位置，而是引入溢出頁。必要時，系統(tǒng)重組文件（安排在相對空閑時間）本文檔共39頁；當前第25頁；編輯于星期日\15點21分4.3.3基于索引的文件組織利用輔助索引文件來幫助定位數(shù)據(jù)記錄。索引文件記錄:索引項<搜索鍵值,rid或rid_list>本文檔共39頁；當前第26頁；編輯于星期日\15點21分4.4頁表示格式4.4.1定長記錄4.4.2變長記錄在處理與I/O有關(guān)主題時，通常采用頁層次抽象已足夠。高層DBMS軟件將數(shù)據(jù)視為記錄集。為提高某些特殊應(yīng)用性能，系統(tǒng)也允許用戶指定數(shù)據(jù)文件存儲組織的一些選項參數(shù)。這需要進一步了解頁內(nèi)記錄的組織方式(即頁格式)。一般可將頁視為槽的集合，每個槽可容納一個記錄。記錄可通過使用rid：<id,slot-no>來標識定位。本文檔共39頁；當前第27頁；編輯于星期日\15點21分因所有記錄長度都相同，可在頁內(nèi)均勻、連續(xù)地安排記錄槽。4.4.1定長記錄本文檔共39頁；當前第28頁；編輯于星期日\15點21分DB系統(tǒng)中，變長記錄是很常見的：記錄類型中含有一個或多個變長字段；記錄中包含可重復(fù)的、數(shù)量不確定的字段；允許在一個頁中存儲多種記錄類型。對于變長記錄存儲，不能將頁簡單地劃分為均勻的槽集。必須仔細處理以下兩個問題：當插入一個記錄時，如何能找到一個恰好能容納新記錄的空間；如何跟蹤記錄刪除后空間。4.4.2變長記錄本文檔共39頁；當前第29頁；編輯于星期日\15點21分基于分槽式頁結(jié)構(gòu)表示變長記錄(圖4.10)

本文檔共39頁；當前第30頁；編輯于星期日\15點21分4.5記錄表示格式4.5.1定長記錄的字段表示4.5.2變長記錄的字段表示4.5.3跨頁記錄管理技術(shù)4.5.4巨型字段/對象管理技術(shù)4.5.5指針記錄管理技術(shù)－－指針混寫記錄首部信息DB中記錄除了存儲各字段信息外，通常還有一個記錄首部（記錄頭）。記錄頭中存儲記錄層次的一般管理信息，包括記錄長度、時間戳和指向記錄模式描述的指針等。記錄是否變長主要看它是否含變長字段。本節(jié)集中討論記錄中字段的表示問題。本文檔共39頁；當前第31頁；編輯于星期日\15點21分4.5記錄表示格式（圖4.11)4.5.1定長記錄的字段表示4.5.2變長記錄的字段表示（一）預(yù)留空間技術(shù)（二）采用特殊字符結(jié)尾來實現(xiàn)變長字段（三）采用偏移數(shù)組來實現(xiàn)變長字段本文檔共39頁；當前第32頁；編輯于星期日\15點21分4.5.3跨頁記錄管理技術(shù)跨頁記錄存在的原因至少有兩個：記錄中存在大型或巨型字段；出于節(jié)省存儲空間的需要。雖然記錄大小不超過1頁，但為了利用頁內(nèi)零頭空間，也會導(dǎo)致跨頁記錄?？珥撚涗洉环指畈⒎执娴蕉鄠€頁中，故需要在各頁中使用指針把它們鏈接在一起，形成單個記錄的頁鏈。本文檔共39頁；當前第33頁；編輯于星期日\15點21分4.5.4巨型字段/對象管理技術(shù)一些應(yīng)用可能包含非常大的巨型對象。例如，一個多媒體對象可能占用幾個MB的空間；一個視頻序列，可能達幾個GB。在RDB中，巨型字段也稱為長字段?？墒褂肂LOB等專門字段型來存儲巨型對象.ODB可以直接管理巨型對象。大多數(shù)RDB限制記錄的大小不超過1頁，以簡化緩沖區(qū)和空閑空間的管理。對超過一個頁的大對象或長字段，一般采用如下兩種管理方法：用跨頁記錄存儲技術(shù)；將它們單獨存儲在一些文件或文件集中。本文檔共39頁；當前第34頁；編輯于星期日\15點21分4.5.5指針字段管理技術(shù)：指針混寫（1）指針或地址經(jīng)常是記錄的一部分。當DB系統(tǒng)運行時，數(shù)據(jù)頁允許在主存和輔存之間移動，故指針所指向的目標頁/記錄，在特定時間，既可能在輔存，也可能在主存。相應(yīng)地，指針或地址也就有兩種形式：內(nèi)存地址數(shù)據(jù)庫地址，也稱持久化指針。是一種在輔存DB空間地址－－通常是一個邏輯地址。通過DB系統(tǒng)的“邏輯/物理地址映射表”，可將其映射為實際磁盤物理塊地址。本文檔共39頁；當前第35頁；編輯于星期日\15點21分4.5.5指針字段管理技術(shù)：指針混寫（2）根據(jù)給定的指針或地址尋找目標對象的過程，稱為解引用(dereference)。C++內(nèi)存指針引用語法：*指針名給定一個持久化指針，解引用一個對象需要額外的步驟：須通過“轉(zhuǎn)換表”查找持久化指針所代表對象在內(nèi)存中的實際位置。如對象不在內(nèi)存，則要從磁盤讀入，同時要修改轉(zhuǎn)換表，并將存放該持久指針的內(nèi)存單元，直接修改為目標對象的內(nèi)存位置指針。下一次同一持久化指針再次被解引用時，就可以直接使用內(nèi)存引用，從而可避免重復(fù)轉(zhuǎn)換內(nèi)存地址的過程開銷。當對象被寫回磁盤時，它所包含的任何被混寫