第4章數(shù)據(jù)存儲(chǔ)與組織管理ppt課件

1、第2部分 關(guān)系數(shù)據(jù)庫系統(tǒng)實(shí)現(xiàn)第4章 數(shù)據(jù)存儲(chǔ)和組織管理高級(jí)數(shù)據(jù)庫系統(tǒng)及其運(yùn)用第4章 數(shù)據(jù)存儲(chǔ)和組織管理物理存儲(chǔ)介質(zhì)4.1磁盤空間管理4.2文件的頁組織4.3頁表示格式4.4記錄表示格式4.5DB元信息及其組織管理4.6DB緩沖區(qū)管理4.74.1 物理存儲(chǔ)介質(zhì)4.1.1 存儲(chǔ)介質(zhì)的層次 4.1.2 磁盤的物理特性4.1.3 磁盤缺點(diǎn)及其處置戰(zhàn)略 4.1.4 磁盤塊存取的優(yōu)化4.1.1 存儲(chǔ)介質(zhì)的層次4.1.2 磁盤的物理特性1磁盤構(gòu)造硬盤容量 盤面數(shù)每盤面磁道數(shù)每磁道扇區(qū)數(shù)每扇區(qū)字節(jié)數(shù) 4.1.2 磁盤的物理特性2磁盤根本操作特性磁盤讀寫的最小單位是扇區(qū)。但在操作系統(tǒng)

2、或DBMS系統(tǒng)層次，磁盤讀寫的根本單位是磁盤塊(block)。不同系統(tǒng)塊大小能夠不同，大多數(shù)系統(tǒng)的塊取4KB。進(jìn)展實(shí)踐磁盤讀寫時(shí)，主存中必需有磁盤塊緩沖區(qū)；在磁盤和主存之間傳送一個(gè)磁盤塊稱為1次I/O操作。讀寫一個(gè)塊的時(shí)間:尋道時(shí)間旋轉(zhuǎn)延遲時(shí)間傳輸時(shí)間。例4.1 假設(shè)有一個(gè)含3個(gè)盤片的硬盤，共有4個(gè)記錄面，轉(zhuǎn)速為4500轉(zhuǎn)/分鐘，盤面有效記錄區(qū)域的外直徑為30cm，內(nèi)直徑為10cm，記錄位密度為250位/mm，磁道密度為8道/mm，每個(gè)磁道分16扇區(qū)，每扇區(qū)512字節(jié)。試計(jì)算：1磁盤的總磁道數(shù)2非格式化容量3平均速度傳輸速率。 例4.2 假設(shè)一種具有如下特性的硬盤：共有4個(gè)盤片，8個(gè)盤面；每個(gè)

3、盤面有8192個(gè)磁道，每個(gè)磁道平均有256個(gè)扇區(qū)；每個(gè)扇區(qū)512個(gè)字節(jié)。試計(jì)算以下磁盤參數(shù)：1磁盤格式化容量。2假設(shè)一個(gè)塊大小為4096字節(jié)，求每個(gè)磁道能存放的塊數(shù)。3假設(shè)磁盤數(shù)據(jù)區(qū)外徑為3.5英寸、內(nèi)徑為1.5英寸， 求磁盤的徑向密度。4假定扇區(qū)間隙占磁道長(zhǎng)度的10%，那么磁盤最內(nèi)和最外磁道上的位密度分別是多少？ 5假設(shè)磁盤轉(zhuǎn)速為3840轉(zhuǎn)/分，即1/64秒轉(zhuǎn)一周。磁頭起落1次1毫秒，每移過500個(gè)磁道另加1毫秒，試計(jì)算讀寫一個(gè)塊的平均時(shí)間。 4.1.3 磁盤缺點(diǎn)及其處置戰(zhàn)略一、磁盤缺點(diǎn)分類 磁盤缺點(diǎn)通常有以下幾種方式或類型：延續(xù)性缺點(diǎn)。寫缺點(diǎn)。部分介質(zhì)損壞。磁盤解體。二、校驗(yàn)和技術(shù)磁盤扇區(qū)

4、通常會(huì)存儲(chǔ)一些冗余位，以可協(xié)助識(shí)別從扇區(qū)讀出的內(nèi)容能否正確。最簡(jiǎn)單的校驗(yàn)和:是基于扇區(qū)內(nèi)一切位的奇偶性。經(jīng)過添加奇偶位數(shù)，可降低檢不出錯(cuò)誤的概率。假設(shè)用n個(gè)位存儲(chǔ)校驗(yàn)和,那么漏檢錯(cuò)誤的概率僅為1/2 n 4.1.3 磁盤缺點(diǎn)及其處置戰(zhàn)略一、磁盤缺點(diǎn)分類二、校驗(yàn)和技術(shù)三、穩(wěn)定存儲(chǔ)技術(shù)校驗(yàn)和技術(shù)能協(xié)助檢測(cè)讀寫缺點(diǎn)或介質(zhì)缺點(diǎn)，但不能協(xié)助我們糾正錯(cuò)誤?；诜€(wěn)定存儲(chǔ)(stable storage)的多副本戰(zhàn)略，能夠協(xié)助我們一定程度上處理這個(gè)問題。四、從解體的磁盤缺點(diǎn)恢復(fù)：RAID技術(shù) 磁盤冗余陣列 的磁盤組織技術(shù)。Redundant Array of Inexpensive Disks幾種常用的RAID

5、級(jí)簡(jiǎn)介 1RAID0級(jí)(nonredundant striping)把數(shù)據(jù)分拆到多塊磁盤并行存貯位級(jí)拆分且沒有任何冗余。在一切RAID級(jí)中，RAID0具有最好的寫性能，但平安性最低。2RAID1級(jí)(mirrored disks)為每一個(gè)磁盤配置一鏡像磁盤，適宜于平安性要求很高場(chǎng)所。有效容量利用率只需50，本錢較高。幾種常用的RAID級(jí)簡(jiǎn)介 3RAID2級(jí)(error-Correcting Codes錯(cuò)誤-校正碼)采用假設(shè)干數(shù)據(jù)盤拆存字節(jié)中的位(bits)，并對(duì)每個(gè)字節(jié)計(jì)算奇偶校驗(yàn)位，額外的校驗(yàn)位存儲(chǔ)在冗余盤。對(duì)有D個(gè)數(shù)據(jù)盤的磁盤陣列中，一次讀寫傳輸最少是D個(gè)塊。較有利于傳輸數(shù)據(jù)量大的磁盤懇求，

6、不利于傳輸數(shù)據(jù)量小的磁盤懇求。4. RAID3級(jí)(Bit-Interleaved Parity位-奇偶交替) RAID2中因配置了較多的冗余校驗(yàn)盤，能自動(dòng)處理壞盤檢測(cè)問題，但也增大了代價(jià)。RAID3只運(yùn)用一個(gè)冗余磁盤，即采用最低的平安性開銷。RAID2/3寫操作都需求一個(gè)read-modify-write 的周期過程。 幾種常用的RAID級(jí)簡(jiǎn)介 5RAID4級(jí)(block-Interleaved Parity塊-奇偶交替) 拆存單位是一個(gè)磁盤塊。塊級(jí)分存優(yōu)點(diǎn)是能充分利用塊設(shè)備任務(wù)特性，且能順應(yīng)各種數(shù)據(jù)量傳輸?shù)拇疟P懇求。不論有多少個(gè)數(shù)據(jù)磁盤，RAID4只用一個(gè)冗余盤存儲(chǔ)各數(shù)據(jù)盤中的奇偶校驗(yàn)數(shù)據(jù)。

7、6. RAID5級(jí)是RAID4的改良。RAID4中校驗(yàn)數(shù)據(jù)塊總是用一個(gè)固定盤來存儲(chǔ)，而在RAID5中，校驗(yàn)塊是交替分布在各磁盤上。 RAID4磁盤讀寫過程讀塊過程：直接讀出相應(yīng)數(shù)據(jù)盤中的目的塊即可。寫塊過程：除了寫目的數(shù)據(jù)盤外，還要修正冗余盤上對(duì)應(yīng)塊數(shù)據(jù)。寫單個(gè)塊需求一個(gè)read- modify- write 的周期過程。 校驗(yàn)盤對(duì)應(yīng)塊新數(shù)據(jù)(當(dāng)前數(shù)據(jù)盤當(dāng)前塊原數(shù)據(jù) XOR 當(dāng)前數(shù)據(jù)盤當(dāng)前塊新數(shù)據(jù) ) XOR 校驗(yàn)盤對(duì)應(yīng)塊原數(shù)據(jù)幾種常用的RAID級(jí)簡(jiǎn)介 7RAID6級(jí)(P+Q Redundancy)運(yùn)用RAID6的主要?jiǎng)訖C(jī)是：在很大的磁盤陣列中，僅能恢復(fù)一個(gè)壞盤顯得平安性缺乏；同時(shí)出現(xiàn)兩個(gè)壞盤

8、，或在恢復(fù)過程中又出現(xiàn)壞盤的情況也必需思索。RAID6普通采用基于Hamming-Code編碼的數(shù)據(jù)盤-校驗(yàn)盤組合方案，使得能同時(shí)恢復(fù)兩個(gè)壞盤。RAID6的缺點(diǎn)恢復(fù)步驟4.1.4 磁盤塊存取的優(yōu)化在多數(shù)OS中，磁盤I/O懇求是由文件系統(tǒng)和虛擬內(nèi)存管理器產(chǎn)生的。DB系統(tǒng)中，系統(tǒng)高層的頁懇求經(jīng)過磁盤空間管理器，也會(huì)產(chǎn)生基于磁盤塊的I/O懇求。由于存取磁盤比存取主存要慢好幾個(gè)量級(jí)，所以，DB系統(tǒng)改善磁盤塊存取性能非常重要。 4.1.4 磁盤塊存取的優(yōu)化一、磁頭調(diào)度技術(shù)先到先效力電梯算法例4.6 假設(shè)某磁盤的平均尋道時(shí)間、旋轉(zhuǎn)等待時(shí)間和塊傳輸時(shí)間分別為6.5、7.8和0.5毫秒。某一時(shí)辰存在著對(duì)柱面1

9、000、3000、7000的塊訪問懇求。初始時(shí)磁頭正位于1000柱面上而且是向上挪動(dòng)。此外，還有3個(gè)懇求在稍后到來。 試用電梯調(diào)度和FIFO戰(zhàn)略調(diào)度算法，分別計(jì)算完成各塊懇求效力的時(shí)間。 4.1.4 磁盤塊存取的優(yōu)化一、磁頭調(diào)度技術(shù)先到先效力電梯算法二、采用特殊的文件組織方式按延續(xù)柱面存儲(chǔ)數(shù)據(jù)三、采用磁盤緩沖池技術(shù)基于“傳播控制層 的DB數(shù)據(jù)緩沖池技術(shù)磁盤預(yù)取技術(shù)雙緩沖技術(shù)4.2 磁盤空間管理4.2.1 磁盤空間管理器 4.2.2 利用OS管理磁盤空間4.2.3 跟蹤自在塊 磁盤空間管理器是DBMS體系構(gòu)造的最低層軟件模塊，隱藏了與磁盤有關(guān)的一切下層軟硬件操作細(xì)節(jié)，并支持以頁為單位的數(shù)據(jù)管理。

10、頁(page)的大小通常就是磁盤塊(block)大小，讀寫一個(gè)頁可經(jīng)過一次磁盤塊I/O完成。允許高層軟件以為DB數(shù)據(jù)是一系列以頁為單位的磁盤數(shù)據(jù)集合。提供分配、釋放和讀寫頁的有關(guān)命令操作經(jīng)過磁盤空間管理器，可將DB中的“關(guān)系映射到 “關(guān)系數(shù)據(jù)文件.這種“文件既能夠是實(shí)踐的OS文件，也能夠只是一個(gè)虛擬的OS文件。4.3 文件的頁組織4.3.1 堆文件 4.3.2 排序文件4.3.3 索引文件 本節(jié)內(nèi)容安排 單個(gè)記錄文件所包含的記錄集， 能夠存儲(chǔ)在假設(shè)干不同的頁上。 高層DBMS代碼普通將“頁視為包容 多個(gè)記錄的對(duì)象，忽略頁中詳細(xì)數(shù)據(jù) 的表示方式或存儲(chǔ)細(xì)節(jié)。 重點(diǎn)討論文件中有關(guān)頁的組織方式。記錄獨(dú)

11、一標(biāo)識(shí)符rid，可被用來識(shí)別記錄所屬的頁及記錄在頁內(nèi)的相對(duì)位置。4.3.1 堆文件屬無序文件，文件中頁的大小一樣。堆文件頁中的記錄是無序的，只能順序存取。每個(gè)記錄有獨(dú)一標(biāo)識(shí)rid。 堆文件管理支持創(chuàng)建/刪除堆文件; 掃描文件; 插入/刪除/檢索給定rid的記錄。不能直接協(xié)助定位滿足指定查詢條件的有關(guān)記錄rids 基于雙向頁鏈表的堆文件組織 將文件頁以雙鏈表方式鏈接在一同。缺陷變長(zhǎng)記錄情況下，能夠一切頁都有空閑；檢索記錄能夠需順序掃描多個(gè)頁 基于目錄頁的堆文件組織 組織構(gòu)造允許有多個(gè)目錄頁，不同的目錄頁經(jīng)過指針鏈接在一同。目錄頁中包含多個(gè)目錄項(xiàng)，每個(gè)目錄項(xiàng)標(biāo)識(shí)一個(gè)頁。優(yōu)點(diǎn)：有利于更有效搜索足夠包

12、容新記錄的數(shù)據(jù)頁。 4.3.2 排序文件文件中記錄集按搜索鍵search key排序普通采用指針把記錄按順序鏈接起來。能支持按搜索鍵以順序或隨機(jī)方式快速獲取記錄，這對(duì)特定的排序查詢非常有用。為減少處置排序文件時(shí)頁懇求的次數(shù)，需求盡能夠地按搜索鍵順序來存儲(chǔ)記錄。但絕對(duì)維持記錄物理上的順序排序往往非常困難,代價(jià)非常高。更常見的做法是：刪記錄時(shí)僅做標(biāo)志并留下空位，暫不挪動(dòng)其它記錄插入時(shí)，相應(yīng)位置即使沒有空，也暫時(shí)不挪動(dòng)其它記錄來騰出位置，而是引入溢出頁。必要時(shí)，系統(tǒng)重組文件安排在相對(duì)空閑時(shí)間4.3.3 基于索引的文件組織利用輔助索引文件來協(xié)助定位數(shù)據(jù)記錄。索引文件記錄:索引項(xiàng)4.4 頁表示格式4.4

13、.1 定長(zhǎng)記錄4.4.2 變長(zhǎng)記錄在處置與I/O有關(guān)主題時(shí)，通常采用頁層次籠統(tǒng)已足夠。高層DBMS軟件將數(shù)據(jù)視為記錄集。為提高某些特殊運(yùn)用性能，系統(tǒng)也允許用戶指定數(shù)據(jù)文件存儲(chǔ)組織的一些選項(xiàng)參數(shù)。這需求進(jìn)一步了解頁內(nèi)記錄的組織方式(即頁格式)。普通可將頁視為槽的集合，每個(gè)槽可包容一個(gè)記錄。記錄可經(jīng)過運(yùn)用rid：來標(biāo)識(shí)定位。因一切記錄長(zhǎng)度都一樣，可在頁內(nèi)均勻、延續(xù)地安排記錄槽。4.4.1 定長(zhǎng)記錄DB系統(tǒng)中，變長(zhǎng)記錄是很常見的：記錄類型中含有一個(gè)或多個(gè)變長(zhǎng)字段；記錄中包含可反復(fù)的、數(shù)量不確定的字段；允許在一個(gè)頁中存儲(chǔ)多種記錄類型。對(duì)于變長(zhǎng)記錄存儲(chǔ)，不能將頁簡(jiǎn)單地劃分為均勻的槽集。必需仔細(xì)處置以下兩

14、個(gè)問題：當(dāng)插入一個(gè)記錄時(shí)，如何能找到一個(gè)恰好能包容新記錄的空間；如何跟蹤記錄刪除后空間。 4.4.2 變長(zhǎng)記錄基于分槽式頁構(gòu)造表示變長(zhǎng)記錄(圖4.10) 4.5 記錄表示格式4.5.1 定長(zhǎng)記錄的字段表示 4.5.2 變長(zhǎng)記錄的字段表示4.5.3 跨頁記錄管理技術(shù) 4.5.4 巨型字段/對(duì)象管理技術(shù)4.5.5 指針記錄管理技術(shù)指針混寫記錄首部信息 DB中記錄除了存儲(chǔ)各字段信息外， 通常還有一個(gè)記錄首部記錄頭。記錄頭中存儲(chǔ)記錄層次的普通管理 信息，包括記錄長(zhǎng)度、時(shí)間戳和指向 記錄方式描畫的指針等。記錄能否變長(zhǎng)主要看它能否含變長(zhǎng)字段。本節(jié)集中討論記錄中字段的表示問題。4.5 記錄表示格式圖4.11

15、)4.5.1 定長(zhǎng)記錄的字段表示4.5.2 變長(zhǎng)記錄的字段表示一預(yù)留空間技術(shù)二采用特殊字符結(jié)尾來實(shí)現(xiàn)變長(zhǎng)字段三采用偏移數(shù)組來實(shí)現(xiàn)變長(zhǎng)字段4.5.3 跨頁記錄管理技術(shù)跨頁記錄存在的緣由至少有兩個(gè)：記錄中存在大型或巨型字段；出于節(jié)省存儲(chǔ)空間的需求。雖然記錄大小不超越1頁，但為了利用頁內(nèi)零頭空間，也會(huì)導(dǎo)致跨頁記錄?？珥撚涗洉?huì)被分割并分存到多個(gè)頁中，故需求在各頁中運(yùn)用指針把它們鏈接在一同，構(gòu)成單個(gè)記錄的頁鏈。4.5.4 巨型字段/對(duì)象管理技術(shù)一些運(yùn)用能夠包含非常大的巨型對(duì)象。例如，一個(gè)多媒體對(duì)象能夠占用幾個(gè)MB的空間；一個(gè)視頻序列，能夠達(dá)幾個(gè)GB。在RDB中，巨型字段也稱為長(zhǎng)字段。可運(yùn)用BLOB等專門

16、字段型來存儲(chǔ)巨型對(duì)象.ODB可以直接納理巨型對(duì)象。大多數(shù)RDB限制記錄的大小不超越1頁，以簡(jiǎn)化緩沖區(qū)和空閑空間的管理。對(duì)超越一個(gè)頁的大對(duì)象或長(zhǎng)字段，普通采用如下兩種管理方法：用跨頁記錄存儲(chǔ)技術(shù)；將它們單獨(dú)存儲(chǔ)在一些文件或文件集中。4.5.5 指針字段管理技術(shù)：指針混寫1指針或地址經(jīng)常是記錄的一部分。當(dāng)DB系統(tǒng)運(yùn)轉(zhuǎn)時(shí)，數(shù)據(jù)頁允許在主存和輔存之間挪動(dòng)，故指針?biāo)赶虻哪康捻?記錄，在特定時(shí)間，既能夠在輔存，也能夠在主存。相應(yīng)地，指針或地址也就有兩種方式：內(nèi)存地址數(shù)據(jù)庫地址，也稱耐久化指針。是一種在輔存DB空間地址通常是一個(gè)邏輯地址。經(jīng)過DB系統(tǒng)的“邏輯/物理地址映射表，可將其映射為實(shí)踐磁盤物理塊地址

17、。4.5.5 指針字段管理技術(shù)：指針混寫2根據(jù)給定的指針或地址尋覓目的對(duì)象的過程，稱為解援用(dereference)。C+內(nèi)存指針援用語法：*指針名給定一個(gè)耐久化指針，解援用一個(gè)對(duì)象需求額外的步驟：須經(jīng)過 “轉(zhuǎn)換表 查找耐久化指針?biāo)韺?duì)象在內(nèi)存中的實(shí)踐位置。如對(duì)象不在內(nèi)存，那么要從磁盤讀入，同時(shí)要修正轉(zhuǎn)換表，并將存放該耐久指針的內(nèi)存單元，直接修正為目的對(duì)象的內(nèi)存位置指針。下一次同一耐久化指針再次被解援用時(shí)，就可以直接運(yùn)用內(nèi)存援用，從而可防止反復(fù)轉(zhuǎn)換內(nèi)存地址的過程開銷。當(dāng)對(duì)象被寫回磁盤時(shí)，它所包含的任何被混寫耐久化指針必需執(zhí)行反混寫，與內(nèi)存指針解援用相比，經(jīng)過轉(zhuǎn)換表實(shí)現(xiàn)解援用仍是一個(gè)慢過程。

18、 指針混寫的時(shí)機(jī)選擇 自動(dòng)混寫；按需混寫；不混寫；程序控制4.6 DB元信息及其存儲(chǔ)管理在RDB系統(tǒng)，除了關(guān)系，還需求維護(hù)關(guān)于整個(gè)DB的元描畫數(shù)據(jù)，如關(guān)系的方式等。這類元信息稱為數(shù)據(jù)字典(data dictionary)或系統(tǒng)目錄(system catalog)。系統(tǒng)需存儲(chǔ)的元信息類型有： 關(guān)系的方式關(guān)系名、每個(gè)屬性名字/類型/長(zhǎng)度。在DB上定義的視圖名字和視圖定義。完好性約束。授權(quán)名、認(rèn)證密碼等關(guān)于用戶帳戶的信息。當(dāng)前關(guān)系實(shí)例的統(tǒng)計(jì)/描畫數(shù)據(jù)。如每個(gè)關(guān)系中的元組總數(shù)，或各字段取值的統(tǒng)計(jì)直方圖信息等描畫信息。實(shí)踐上，一切這些信息組成了一個(gè)微型數(shù)據(jù)庫4.7 緩沖區(qū)管理4.7.1 DB緩沖池與緩沖區(qū)管理器 4.7.2 緩沖區(qū)置換戰(zhàn)略4.7.3 DBMS與OS的緩沖區(qū)管理對(duì)比 DB緩沖池與緩沖區(qū)管理器DB緩沖池DBMS系統(tǒng)普通都擁有一個(gè)公用于處置頁讀寫的、稱為DB緩沖池的主存區(qū)。該主存區(qū)被按頁大小劃分為一個(gè)個(gè)頁槽簡(jiǎn)稱頁面框,frame) 。為表達(dá)方便，有時(shí)也常簡(jiǎn)單運(yùn)用可用主存、緩存、緩沖區(qū)、主存緩沖區(qū)等名詞稱謂DB緩沖池。緩沖區(qū)管理器指DBMS中專門擔(dān)任管理DB緩沖池的軟件模塊。緩沖區(qū)置換戰(zhàn)略當(dāng)新頁懇求發(fā)生且沒有空閑緩沖頁時(shí)，決議交換緩沖區(qū)哪些頁的戰(zhàn)略。緩沖區(qū)管理器呼應(yīng)高層頁懇求的根本過程檢查緩沖池中能否存在該頁，如不在，那么進(jìn)一步執(zhí)行以下一些操作?；谥脫Q戰(zhàn)略，選擇一個(gè)可被置換的f