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

1、LOGO高級(jí)數(shù)據(jù)庫(kù)系統(tǒng)及其應(yīng)用高級(jí)數(shù)據(jù)庫(kù)系統(tǒng)及其應(yīng)用第第4 4章章 數(shù)據(jù)存儲(chǔ)和組織管理數(shù)據(jù)存儲(chǔ)和組織管理物理存儲(chǔ)介質(zhì)物理存儲(chǔ)介質(zhì)4.1磁盤空間管理磁盤空間管理4.2文件的頁(yè)組織文件的頁(yè)組織4.3頁(yè)表示格式頁(yè)表示格式4.4記錄表示格式記錄表示格式4.5DB元信息及其組織管理元信息及其組織管理4.6DB緩沖區(qū)管理緩沖區(qū)管理4.74.1 物理存儲(chǔ)介質(zhì)物理存儲(chǔ)介質(zhì)4.1.1 存儲(chǔ)介質(zhì)的層次 4.1.2 磁盤的物理特性4.1.3 磁盤故障及其處理策略 4.1.4 磁盤塊存取的優(yōu)化4.1.1 存儲(chǔ)介質(zhì)的層次存儲(chǔ)介質(zhì)的層次4.1.2 磁盤的物理特性磁盤的物理特性（1）磁盤結(jié)構(gòu)）磁盤結(jié)構(gòu)硬盤容量硬盤容量 盤面

2、數(shù)盤面數(shù)每盤面磁道數(shù)每盤面磁道數(shù)每磁道扇區(qū)數(shù)每磁道扇區(qū)數(shù)每扇區(qū)字節(jié)數(shù)每扇區(qū)字節(jié)數(shù) 4.1.2 磁盤的物理特性磁盤的物理特性（2）磁盤基本操作特性）磁盤基本操作特性v磁盤讀寫的最小單位是扇區(qū)。但在操作系統(tǒng)或磁盤讀寫的最小單位是扇區(qū)。但在操作系統(tǒng)或DBMS系統(tǒng)層次，磁盤讀寫的基本單位是系統(tǒng)層次，磁盤讀寫的基本單位是磁盤塊磁盤塊(block)。 不同系統(tǒng)塊大小可能不同，大多數(shù)系統(tǒng)的塊取4KB。v進(jìn)行實(shí)際磁盤讀寫時(shí)，主存中必須有磁盤塊緩沖進(jìn)行實(shí)際磁盤讀寫時(shí)，主存中必須有磁盤塊緩沖區(qū)；在磁盤和主存之間傳送一個(gè)磁盤塊稱為區(qū)；在磁盤和主存之間傳送一個(gè)磁盤塊稱為1次次I/O操作。操作。v讀寫一個(gè)塊的時(shí)間讀寫一

3、個(gè)塊的時(shí)間: 尋道時(shí)間旋轉(zhuǎn)延遲時(shí)間傳輸時(shí)間。例例4.1 假設(shè)有一個(gè)含假設(shè)有一個(gè)含3個(gè)盤片的硬盤，共有個(gè)盤片的硬盤，共有4個(gè)個(gè)記錄面，轉(zhuǎn)速為記錄面，轉(zhuǎn)速為4500轉(zhuǎn)轉(zhuǎn)/分鐘，盤面有效分鐘，盤面有效記錄區(qū)域的外直徑為記錄區(qū)域的外直徑為30cm，內(nèi)直徑為，內(nèi)直徑為10cm，記錄位密度為，記錄位密度為250位位/mm，磁道，磁道密度為密度為8道道/mm，每個(gè)磁道分，每個(gè)磁道分16扇區(qū)，每扇區(qū)，每扇區(qū)扇區(qū)512字節(jié)。試計(jì)算：字節(jié)。試計(jì)算： 1）磁盤的總磁道數(shù) 2）非格式化容量 3）平均速度傳輸速率。 例例4.2 假設(shè)一種具有如下特性的硬盤：共有假設(shè)一種具有如下特性的硬盤：共有4個(gè)個(gè)盤片，盤片，8個(gè)盤面；

4、每個(gè)盤面有個(gè)盤面；每個(gè)盤面有8192個(gè)磁道，個(gè)磁道，每個(gè)磁道平均有每個(gè)磁道平均有256個(gè)扇區(qū)；每個(gè)扇區(qū)個(gè)扇區(qū)；每個(gè)扇區(qū)512個(gè)字節(jié)。試計(jì)算以下磁盤參數(shù)：個(gè)字節(jié)。試計(jì)算以下磁盤參數(shù)：v 1）磁盤格式化容量。）磁盤格式化容量。v 2）若一個(gè)塊大小為）若一個(gè)塊大小為4096字節(jié)，求每個(gè)磁道能存放的塊數(shù)。字節(jié)，求每個(gè)磁道能存放的塊數(shù)。v 3）如果磁盤數(shù)據(jù)區(qū)外徑為）如果磁盤數(shù)據(jù)區(qū)外徑為3.5英寸、內(nèi)徑為英寸、內(nèi)徑為1.5英寸，英寸， 求磁求磁盤的徑向密度。盤的徑向密度。v 4）假定扇區(qū)間隙占磁道長(zhǎng)度的）假定扇區(qū)間隙占磁道長(zhǎng)度的10%，則磁盤最內(nèi)和最外磁，則磁盤最內(nèi)和最外磁道上的位密度分別是多少？道上的位

5、密度分別是多少？ v 5）若磁盤轉(zhuǎn)速為）若磁盤轉(zhuǎn)速為3840轉(zhuǎn)轉(zhuǎn)/分，即分，即1/64秒轉(zhuǎn)一周。磁頭起秒轉(zhuǎn)一周。磁頭起落落1次次1毫秒，每移過(guò)毫秒，每移過(guò)500個(gè)磁道另加個(gè)磁道另加1毫秒，試計(jì)算讀寫一毫秒，試計(jì)算讀寫一個(gè)塊的平均時(shí)間。個(gè)塊的平均時(shí)間。 4.1.3 磁盤故障及其處理策略磁盤故障及其處理策略一、磁盤故障分類一、磁盤故障分類 磁盤故障通常有以下幾種方式或類型：磁盤故障通常有以下幾種方式或類型： 間斷性故障。間斷性故障。 寫故障。寫故障。 部分介質(zhì)損壞。部分介質(zhì)損壞。 磁盤崩潰。磁盤崩潰。二、校驗(yàn)和技術(shù)二、校驗(yàn)和技術(shù) 磁盤扇區(qū)通常會(huì)存儲(chǔ)一些冗余位，以可幫助識(shí)別從扇區(qū)讀出的內(nèi)容是否正確。

6、 最簡(jiǎn)單的校驗(yàn)和:是基于扇區(qū)內(nèi)所有位的奇偶性。 通過(guò)增加奇偶位數(shù)，可降低檢不出錯(cuò)誤的概率。 若用n個(gè)位存儲(chǔ)校驗(yàn)和,則漏檢錯(cuò)誤的概率僅為1/2 n 4.1.3 磁盤故障及其處理策略磁盤故障及其處理策略一、磁盤故障分類一、磁盤故障分類二、校驗(yàn)和技術(shù)二、校驗(yàn)和技術(shù)三、穩(wěn)定存儲(chǔ)技術(shù)三、穩(wěn)定存儲(chǔ)技術(shù) 校驗(yàn)和技術(shù)能幫助檢測(cè)讀寫故障或介質(zhì)故障，但不能幫助我們糾正錯(cuò)誤。 基于穩(wěn)定存儲(chǔ)(stable storage)的多副本策略，可能幫助我們一定程度上解決這個(gè)問(wèn)題。四、從崩潰的磁盤故障恢復(fù)：四、從崩潰的磁盤故障恢復(fù)：RAID技術(shù)技術(shù) 磁盤冗余陣列 的磁盤組織技術(shù)。 Redundant Array of Inex

7、pensive Disks幾種常用的幾種常用的RAID級(jí)簡(jiǎn)介級(jí)簡(jiǎn)介 1RAID0級(jí)級(jí)(nonredundant striping) 把數(shù)據(jù)分拆到多塊磁盤并行存貯（位級(jí)拆分且沒(méi)有任何冗余）。 在所有RAID級(jí)中，RAID0具有最好的寫性能，但安全性最低。2RAID1級(jí)級(jí)(mirrored disks) 為每一個(gè)磁盤配置一鏡像磁盤，適合于安全性要求很高場(chǎng)合。有效容量利用率只有50，成本較高。幾種常用的幾種常用的RAID級(jí)簡(jiǎn)介級(jí)簡(jiǎn)介 3RAID2級(jí)級(jí)(error-Correcting Codes錯(cuò)誤錯(cuò)誤-校正碼校正碼) 采用若干數(shù)據(jù)盤拆存字節(jié)中的位(bits)，并對(duì)每個(gè)字節(jié)計(jì)算奇偶校驗(yàn)位，額外的校驗(yàn)

8、位存儲(chǔ)在冗余盤。 對(duì)有D個(gè)數(shù)據(jù)盤的磁盤陣列中，一次讀寫傳輸最少是D個(gè)塊。較有利于傳輸數(shù)據(jù)量大的磁盤請(qǐng)求，不利于傳輸數(shù)據(jù)量小的磁盤請(qǐng)求。4. RAID3級(jí)級(jí)(Bit-Interleaved Parity位位-奇偶交替奇偶交替) RAID2中因配置了較多的冗余校驗(yàn)盤，能自動(dòng)解決壞盤檢測(cè)問(wèn)題，但也增大了代價(jià)。RAID3只使用一個(gè)冗余磁盤，即采用最低的安全性開(kāi)銷。 RAID2/3寫操作都需要一個(gè)read-modify-write 的周期過(guò)程。 幾種常用的幾種常用的RAID級(jí)簡(jiǎn)介級(jí)簡(jiǎn)介 5RAID4級(jí)級(jí)(block-Interleaved Parity塊塊-奇偶交替奇偶交替) 拆存單位是一個(gè)磁盤塊。塊級(jí)

9、分存優(yōu)點(diǎn)是能充分利用塊設(shè)備工作特性，且能適應(yīng)各種數(shù)據(jù)量傳輸?shù)拇疟P請(qǐng)求。 不論有多少個(gè)數(shù)據(jù)磁盤，RAID4只用一個(gè)冗余盤存儲(chǔ)各數(shù)據(jù)盤中的奇偶校驗(yàn)數(shù)據(jù)。6. RAID5級(jí)級(jí) 是RAID4的改進(jìn)。RAID4中校驗(yàn)數(shù)據(jù)塊總是用一個(gè)固定盤來(lái)存儲(chǔ)，而在RAID5中，校驗(yàn)塊是交替分布在各磁盤上。 RAID4磁盤讀寫過(guò)程磁盤讀寫過(guò)程 讀塊過(guò)程：直接讀出相應(yīng)數(shù)據(jù)盤中的目標(biāo)塊即可。 寫塊過(guò)程：除了寫目標(biāo)數(shù)據(jù)盤外，還要修改冗余盤上對(duì)應(yīng)塊數(shù)據(jù)。寫單個(gè)塊需要一個(gè)寫單個(gè)塊需要一個(gè)read- modify- write 的的周期過(guò)程周期過(guò)程。 校驗(yàn)盤對(duì)應(yīng)塊新數(shù)據(jù)校驗(yàn)盤對(duì)應(yīng)塊新數(shù)據(jù)(當(dāng)前數(shù)據(jù)盤當(dāng)前塊原數(shù)據(jù)當(dāng)前數(shù)據(jù)盤當(dāng)前塊原數(shù)

10、據(jù) XOR 當(dāng)前數(shù)據(jù)盤當(dāng)前塊新數(shù)據(jù)當(dāng)前數(shù)據(jù)盤當(dāng)前塊新數(shù)據(jù) ) XOR 校驗(yàn)盤對(duì)應(yīng)塊原數(shù)據(jù)校驗(yàn)盤對(duì)應(yīng)塊原數(shù)據(jù)幾種常用的幾種常用的RAID級(jí)簡(jiǎn)介級(jí)簡(jiǎn)介 7RAID6級(jí)級(jí)(P+Q Redundancy) 使用RAID6的主要?jiǎng)訖C(jī)是：在很大的磁盤陣列中，僅能恢復(fù)一個(gè)壞盤顯得安全性不足；同時(shí)出現(xiàn)兩個(gè)壞盤，或在恢復(fù)過(guò)程中又出現(xiàn)壞盤的情況也必須考慮。 RAID6一般采用基于Hamming-Code編碼的數(shù)據(jù)盤-校驗(yàn)盤組合方案，使得能同時(shí)恢復(fù)兩個(gè)壞盤。 RAID6的故障恢復(fù)步驟的故障恢復(fù)步驟4.1.4 磁盤塊存取的優(yōu)化磁盤塊存取的優(yōu)化v在多數(shù)在多數(shù)OS中，磁盤中，磁盤I/O請(qǐng)求是由文件系統(tǒng)請(qǐng)求是由文件系統(tǒng)和虛

11、擬內(nèi)存管理器產(chǎn)生的。和虛擬內(nèi)存管理器產(chǎn)生的。vDB系統(tǒng)中，系統(tǒng)高層的頁(yè)請(qǐng)求通過(guò)磁盤空系統(tǒng)中，系統(tǒng)高層的頁(yè)請(qǐng)求通過(guò)磁盤空間管理器，也會(huì)產(chǎn)生基于磁盤塊的間管理器，也會(huì)產(chǎn)生基于磁盤塊的I/O請(qǐng)請(qǐng)求。求。v由于存取磁盤比存取主存要慢好幾個(gè)量級(jí)，由于存取磁盤比存取主存要慢好幾個(gè)量級(jí)，所以，所以，DB系統(tǒng)改善磁盤塊存取性能非常重系統(tǒng)改善磁盤塊存取性能非常重要。要。 4.1.4 磁盤塊存取的優(yōu)化磁盤塊存取的優(yōu)化一、磁頭調(diào)度技術(shù)一、磁頭調(diào)度技術(shù) 先到先服務(wù)先到先服務(wù) 電梯算法電梯算法 例例4.6 假設(shè)某磁盤的平均尋道時(shí)間、旋轉(zhuǎn)等待假設(shè)某磁盤的平均尋道時(shí)間、旋轉(zhuǎn)等待時(shí)間和塊傳輸時(shí)間分別為時(shí)間和塊傳輸時(shí)間分別為6

12、.5、7.8和和0.5毫秒。某一時(shí)刻存在著對(duì)柱面毫秒。某一時(shí)刻存在著對(duì)柱面1000、3000、7000的塊訪問(wèn)請(qǐng)求。初始時(shí)磁頭的塊訪問(wèn)請(qǐng)求。初始時(shí)磁頭正位于正位于1000柱面上而且是向上移動(dòng)。此外，柱面上而且是向上移動(dòng)。此外，還有還有3個(gè)請(qǐng)求在稍后到來(lái)。個(gè)請(qǐng)求在稍后到來(lái)。 試用電梯調(diào)度和試用電梯調(diào)度和FIFO策略調(diào)度算法，分策略調(diào)度算法，分別計(jì)算完成各塊請(qǐng)求服務(wù)的時(shí)間。別計(jì)算完成各塊請(qǐng)求服務(wù)的時(shí)間。 4.1.4 磁盤塊存取的優(yōu)化磁盤塊存取的優(yōu)化一、磁頭調(diào)度技術(shù)一、磁頭調(diào)度技術(shù) 先到先服務(wù)先到先服務(wù) 電梯算法電梯算法二、采用特殊的文件組織方式二、采用特殊的文件組織方式 按連續(xù)柱面存儲(chǔ)數(shù)據(jù)按連續(xù)柱

13、面存儲(chǔ)數(shù)據(jù)三、采用磁盤緩沖池技術(shù)三、采用磁盤緩沖池技術(shù) 基于基于“傳播控制層傳播控制層” 的的DB數(shù)據(jù)緩沖池技術(shù)數(shù)據(jù)緩沖池技術(shù) 磁盤預(yù)取技術(shù)磁盤預(yù)取技術(shù) 雙緩沖技術(shù)雙緩沖技術(shù)4.2 磁盤空間管理磁盤空間管理4.2.1 磁盤空間管理器 4.2.2 利用OS管理磁盤空間4.2.3 跟蹤自由塊 磁盤空間管理器磁盤空間管理器v是是DBMS體系結(jié)構(gòu)的最低層軟件模塊，隱體系結(jié)構(gòu)的最低層軟件模塊，隱藏了與磁盤有關(guān)的所有下層軟硬件操作細(xì)藏了與磁盤有關(guān)的所有下層軟硬件操作細(xì)節(jié)，并支持以節(jié)，并支持以頁(yè)頁(yè)為單位的數(shù)據(jù)管理。為單位的數(shù)據(jù)管理。 頁(yè)頁(yè)(page)的大小通常就是磁盤塊的大小通常就是磁盤塊(block)大小

14、，大小，讀寫一個(gè)頁(yè)可通過(guò)一次磁盤塊讀寫一個(gè)頁(yè)可通過(guò)一次磁盤塊I/O完成。完成。 允許高層軟件認(rèn)為允許高層軟件認(rèn)為DB數(shù)據(jù)是一系列以頁(yè)為單數(shù)據(jù)是一系列以頁(yè)為單位的磁盤數(shù)據(jù)集合。位的磁盤數(shù)據(jù)集合。 提供分配、釋放和讀寫頁(yè)的有關(guān)命令操作提供分配、釋放和讀寫頁(yè)的有關(guān)命令操作v通過(guò)磁盤空間管理器，可將通過(guò)磁盤空間管理器，可將DB中的中的“關(guān)系關(guān)系”映映射到射到 “關(guān)系數(shù)據(jù)文件關(guān)系數(shù)據(jù)文件”. 這種這種“文件文件”既可能是實(shí)際的既可能是實(shí)際的OS文件，也可文件，也可能只是一個(gè)虛擬的能只是一個(gè)虛擬的OS文件。文件。4.3 文件的頁(yè)組織文件的頁(yè)組織4.3.1 堆文件 4.3.2 排序文件4.3.3 索引文件

15、u 單個(gè)記錄文件所包含的記錄集，單個(gè)記錄文件所包含的記錄集， 可能存儲(chǔ)在若干不同的頁(yè)上?？赡艽鎯?chǔ)在若干不同的頁(yè)上。u 高層高層DBMS代碼一般將代碼一般將“頁(yè)頁(yè)”視為容視為容納納 多個(gè)記錄的對(duì)象，忽略頁(yè)中具體數(shù)據(jù)多個(gè)記錄的對(duì)象，忽略頁(yè)中具體數(shù)據(jù) 的表示方式或存儲(chǔ)細(xì)節(jié)。的表示方式或存儲(chǔ)細(xì)節(jié)。u 重點(diǎn)討論文件中有關(guān)頁(yè)的組織方式。重點(diǎn)討論文件中有關(guān)頁(yè)的組織方式。記錄唯一標(biāo)識(shí)符記錄唯一標(biāo)識(shí)符rid，可被用來(lái)識(shí)別記錄所屬的頁(yè)及記錄在頁(yè)內(nèi)的相對(duì)位置。，可被用來(lái)識(shí)別記錄所屬的頁(yè)及記錄在頁(yè)內(nèi)的相對(duì)位置。4.3.1 堆文件堆文件v屬無(wú)序文件，文件中頁(yè)的大小相同。屬無(wú)序文件，文件中頁(yè)的大小相同。v堆文件頁(yè)中的記錄

16、是無(wú)序的，只能順序存取。每堆文件頁(yè)中的記錄是無(wú)序的，只能順序存取。每個(gè)記錄有唯一標(biāo)識(shí)個(gè)記錄有唯一標(biāo)識(shí)rid。 v堆文件管理支持堆文件管理支持 創(chuàng)建/刪除堆文件; 掃描掃描文件; 插入/刪除/檢索給定rid的記錄。 不能直接幫助定位滿足指定查詢條件的有關(guān)記錄rids 基于雙向頁(yè)鏈表的堆文件組織基于雙向頁(yè)鏈表的堆文件組織 v將文件頁(yè)以雙鏈表將文件頁(yè)以雙鏈表方式鏈接在一起。方式鏈接在一起。v缺點(diǎn)缺點(diǎn) 變長(zhǎng)記錄情況下，可能所有頁(yè)都有空閑；檢索記錄可能需順序掃描多個(gè)頁(yè) 基于目錄頁(yè)的堆文件組織基于目錄頁(yè)的堆文件組織 v 組織結(jié)構(gòu)組織結(jié)構(gòu) 允許有多個(gè)目錄頁(yè)，不同的目錄頁(yè)通過(guò)指針鏈接在一起。 目錄頁(yè)中包含多個(gè)

17、目錄項(xiàng)，每個(gè)目錄項(xiàng)標(biāo)識(shí)一個(gè)頁(yè)。v 優(yōu)點(diǎn)：優(yōu)點(diǎn)： 有利于更有效搜索足夠容納新記錄的數(shù)據(jù)頁(yè)。 4.3.2 排序文件排序文件v文件中記錄集按搜索鍵（文件中記錄集按搜索鍵（search key）排序）排序 一般采用指針把記錄按順序鏈接起來(lái)。 能支持按搜索鍵以順序或隨機(jī)方式快速獲取記錄，這對(duì)特定的排序查詢非常有用。v為減少處理排序文件時(shí)頁(yè)請(qǐng)求的次數(shù)，需要盡可為減少處理排序文件時(shí)頁(yè)請(qǐng)求的次數(shù)，需要盡可能地按搜索鍵順序來(lái)存儲(chǔ)記錄。能地按搜索鍵順序來(lái)存儲(chǔ)記錄。 但絕對(duì)維持記錄物理上的順序排序往往非常困難,代價(jià)非常高。更常見(jiàn)的做法是： 刪記錄時(shí)僅做標(biāo)記并留下空位，暫不移動(dòng)其它記錄 插入時(shí)，相應(yīng)位置即使沒(méi)有空，也

18、暫時(shí)不移動(dòng)其它記錄來(lái)騰出位置，而是引入溢出頁(yè)。 必要時(shí)，系統(tǒng)重組文件（安排在相對(duì)空閑時(shí)間）4.3.3 基于索引的文件組織基于索引的文件組織v 利用輔助索引文件來(lái)幫助定位數(shù)據(jù)記錄。利用輔助索引文件來(lái)幫助定位數(shù)據(jù)記錄。 索引文件記錄:索引項(xiàng)4.4 頁(yè)表示格式頁(yè)表示格式4.4.1 定長(zhǎng)記錄4.4.2 變長(zhǎng)記錄v 在處理與在處理與I/O有關(guān)主題時(shí)，通常采用頁(yè)層次抽象已足夠。有關(guān)主題時(shí)，通常采用頁(yè)層次抽象已足夠。v 高層高層DBMS軟件將數(shù)據(jù)視為記錄集。為提高某些特殊應(yīng)用軟件將數(shù)據(jù)視為記錄集。為提高某些特殊應(yīng)用性能，系統(tǒng)也允許用戶指定數(shù)據(jù)文件存儲(chǔ)組織的一些選項(xiàng)性能，系統(tǒng)也允許用戶指定數(shù)據(jù)文件存儲(chǔ)組織的一

19、些選項(xiàng)參數(shù)。參數(shù)。 這需要進(jìn)一步了解頁(yè)內(nèi)記錄的組織方式(即頁(yè)格式)。v 一般可將頁(yè)視為槽的集合，每個(gè)槽可容納一個(gè)記錄。一般可將頁(yè)視為槽的集合，每個(gè)槽可容納一個(gè)記錄。 記錄可通過(guò)使用rid：來(lái)標(biāo)識(shí)定位。v因所有記錄長(zhǎng)度都相同，可在頁(yè)內(nèi)均勻、因所有記錄長(zhǎng)度都相同，可在頁(yè)內(nèi)均勻、連續(xù)地安排記錄槽。連續(xù)地安排記錄槽。4.4.1 定長(zhǎng)記錄定長(zhǎng)記錄vDB系統(tǒng)中，變長(zhǎng)記錄是很常見(jiàn)的：系統(tǒng)中，變長(zhǎng)記錄是很常見(jiàn)的： 記錄類型中含有一個(gè)或多個(gè)變長(zhǎng)字段； 記錄中包含可重復(fù)的、數(shù)量不確定的字段； 允許在一個(gè)頁(yè)中存儲(chǔ)多種記錄類型。v對(duì)于變長(zhǎng)記錄存儲(chǔ)，不能將頁(yè)簡(jiǎn)單地劃分為均勻?qū)τ谧冮L(zhǎng)記錄存儲(chǔ)，不能將頁(yè)簡(jiǎn)單地劃分為均勻的槽

20、集。必須仔細(xì)處理以下兩個(gè)問(wèn)題：的槽集。必須仔細(xì)處理以下兩個(gè)問(wèn)題： 當(dāng)插入一個(gè)記錄時(shí)，如何能找到一個(gè)恰好能容納新記錄的空間； 如何跟蹤記錄刪除后空間。 4.4.2 變長(zhǎng)記錄變長(zhǎng)記錄基于分槽式頁(yè)結(jié)構(gòu)表示變長(zhǎng)記錄基于分槽式頁(yè)結(jié)構(gòu)表示變長(zhǎng)記錄(圖圖4.10) 4.5 4.5 記錄表示格式記錄表示格式4.5.1 定長(zhǎng)記錄的字段表示 4.5.2 變長(zhǎng)記錄的字段表示4.5.3 跨頁(yè)記錄管理技術(shù) 4.5.4 巨型字段/對(duì)象管理技術(shù)4.5.5 指針記錄管理技術(shù)指針混寫u DB中記錄除了存儲(chǔ)各字段信息外，中記錄除了存儲(chǔ)各字段信息外， 通常還有一個(gè)記錄首部（記錄頭）。通常還有一個(gè)記錄首部（記錄頭）。u記錄頭中存儲(chǔ)記

21、錄層次的一般管理記錄頭中存儲(chǔ)記錄層次的一般管理 信息，包括記錄長(zhǎng)度、時(shí)間戳和指向信息，包括記錄長(zhǎng)度、時(shí)間戳和指向 記錄模式描述的指針等。記錄模式描述的指針等。u記錄是否變長(zhǎng)主要看它是否含變長(zhǎng)字段。記錄是否變長(zhǎng)主要看它是否含變長(zhǎng)字段。u本節(jié)集中討論記錄中字段的表示問(wèn)題。本節(jié)集中討論記錄中字段的表示問(wèn)題。4.5 記錄表示格式記錄表示格式（圖（圖4.11)4.5.1 定長(zhǎng)記錄的字段表示定長(zhǎng)記錄的字段表示4.5.2 變長(zhǎng)記錄的字段表示變長(zhǎng)記錄的字段表示（一）預(yù)留空間技術(shù)（一）預(yù)留空間技術(shù)（二）采用特殊字符結(jié)尾來(lái)實(shí)現(xiàn)變長(zhǎng)字段（二）采用特殊字符結(jié)尾來(lái)實(shí)現(xiàn)變長(zhǎng)字段（三）采用偏移數(shù)組來(lái)實(shí)現(xiàn)變長(zhǎng)字段（三）采用偏

22、移數(shù)組來(lái)實(shí)現(xiàn)變長(zhǎng)字段4.5.3 跨頁(yè)記錄管理技術(shù)跨頁(yè)記錄管理技術(shù)v 跨頁(yè)記錄存在的原因至少有兩個(gè)：跨頁(yè)記錄存在的原因至少有兩個(gè)： 記錄中存在大型或巨型字段； 出于節(jié)省存儲(chǔ)空間的需要。雖然記錄大小不超過(guò)1頁(yè)，但為了利用頁(yè)內(nèi)零頭空間，也會(huì)導(dǎo)致跨頁(yè)記錄。v 跨頁(yè)記錄會(huì)被分割并分存到多個(gè)頁(yè)中，故需要在各頁(yè)中跨頁(yè)記錄會(huì)被分割并分存到多個(gè)頁(yè)中，故需要在各頁(yè)中使用指針把它們鏈接在一起，形成單個(gè)記錄的頁(yè)鏈。使用指針把它們鏈接在一起，形成單個(gè)記錄的頁(yè)鏈。4.5.4 巨型字段巨型字段/對(duì)象管理技術(shù)對(duì)象管理技術(shù)v一些應(yīng)用可能包含非常大的巨型對(duì)象。一些應(yīng)用可能包含非常大的巨型對(duì)象。 例如，一個(gè)多媒體對(duì)象可能占用幾個(gè)M

23、B的空間；一個(gè)視頻序列，可能達(dá)幾個(gè)GB。 在RDB中，巨型字段也稱為長(zhǎng)字段?？墒褂肂LOB等專門字段型來(lái)存儲(chǔ)巨型對(duì)象. ODB可以直接管理巨型對(duì)象。v大多數(shù)大多數(shù)RDB限制記錄的大小不超過(guò)限制記錄的大小不超過(guò)1頁(yè)，以簡(jiǎn)化頁(yè)，以簡(jiǎn)化緩沖區(qū)和空閑空間的管理。對(duì)超過(guò)一個(gè)頁(yè)的大對(duì)緩沖區(qū)和空閑空間的管理。對(duì)超過(guò)一個(gè)頁(yè)的大對(duì)象或長(zhǎng)字段，一般采用如下兩種管理方法：象或長(zhǎng)字段，一般采用如下兩種管理方法： 用跨頁(yè)記錄存儲(chǔ)技術(shù)； 將它們單獨(dú)存儲(chǔ)在一些文件或文件集中。4.5.5 指針字段管理技術(shù)：指針混寫（指針字段管理技術(shù)：指針混寫（1）v指針或地址經(jīng)常是記錄的一部分。指針或地址經(jīng)常是記錄的一部分。v當(dāng)當(dāng)DB系統(tǒng)運(yùn)

24、行時(shí)，數(shù)據(jù)頁(yè)允許在主存和輔存之間系統(tǒng)運(yùn)行時(shí)，數(shù)據(jù)頁(yè)允許在主存和輔存之間移動(dòng)，故指針?biāo)赶虻哪繕?biāo)頁(yè)移動(dòng)，故指針?biāo)赶虻哪繕?biāo)頁(yè)/記錄，在特定時(shí)間，記錄，在特定時(shí)間，既可能在輔存，也可能在主存。相應(yīng)地，指針或既可能在輔存，也可能在主存。相應(yīng)地，指針或地址也就有兩種形式：地址也就有兩種形式： 內(nèi)存地址內(nèi)存地址 數(shù)據(jù)庫(kù)地址，也稱持久化指針。是一種在輔存數(shù)據(jù)庫(kù)地址，也稱持久化指針。是一種在輔存DB空間地址通常是一個(gè)邏輯地址?？臻g地址通常是一個(gè)邏輯地址。v通過(guò)通過(guò)DB系統(tǒng)的系統(tǒng)的“邏輯邏輯/物理地址映射表物理地址映射表”，可將，可將其映射為實(shí)際磁盤物理塊地址。其映射為實(shí)際磁盤物理塊地址。4.5.5 指針字段

25、管理技術(shù)：指針混寫（指針字段管理技術(shù)：指針混寫（2）v 根據(jù)給定的指針或地址尋找目標(biāo)對(duì)象的過(guò)程，稱為解引用根據(jù)給定的指針或地址尋找目標(biāo)對(duì)象的過(guò)程，稱為解引用(dereference)。 C+內(nèi)存指針引用語(yǔ)法：內(nèi)存指針引用語(yǔ)法：*指針名指針名v 給定一個(gè)持久化指針，解引用一個(gè)對(duì)象需要額外的步驟：給定一個(gè)持久化指針，解引用一個(gè)對(duì)象需要額外的步驟： 須通過(guò)須通過(guò) “轉(zhuǎn)換表轉(zhuǎn)換表” 查找持久化指針?biāo)韺?duì)象在內(nèi)存查找持久化指針?biāo)韺?duì)象在內(nèi)存中的實(shí)際位置。中的實(shí)際位置。 如對(duì)象不在內(nèi)存，則要從磁盤讀入，同時(shí)要修改轉(zhuǎn)換表，并將如對(duì)象不在內(nèi)存，則要從磁盤讀入，同時(shí)要修改轉(zhuǎn)換表，并將存放該持久指針的內(nèi)存單元

26、，直接修改為存放該持久指針的內(nèi)存單元，直接修改為目標(biāo)對(duì)象目標(biāo)對(duì)象的內(nèi)存位置的內(nèi)存位置指針。指針。 下一次同一持久化指針再次被解引用時(shí)，就可以直接使用內(nèi)存下一次同一持久化指針再次被解引用時(shí)，就可以直接使用內(nèi)存引用，從而可避免重復(fù)轉(zhuǎn)換內(nèi)存地址的過(guò)程開(kāi)銷。引用，從而可避免重復(fù)轉(zhuǎn)換內(nèi)存地址的過(guò)程開(kāi)銷。 當(dāng)對(duì)象被寫回磁盤時(shí)，它所包含的任何被混寫持久化指針必須當(dāng)對(duì)象被寫回磁盤時(shí)，它所包含的任何被混寫持久化指針必須執(zhí)行反混寫，執(zhí)行反混寫，v 與內(nèi)存指針解引用相比，通過(guò)轉(zhuǎn)換表實(shí)現(xiàn)解引用仍是一個(gè)與內(nèi)存指針解引用相比，通過(guò)轉(zhuǎn)換表實(shí)現(xiàn)解引用仍是一個(gè)慢過(guò)程。慢過(guò)程。 v 指針混寫的時(shí)機(jī)選擇指針混寫的時(shí)機(jī)選擇 自動(dòng)混寫

27、；按需混寫；不混寫；程序控制4.6 DB元信息及其存儲(chǔ)管理元信息及其存儲(chǔ)管理v 在在RDB系統(tǒng)，除了關(guān)系，還需要維護(hù)關(guān)于整個(gè)系統(tǒng)，除了關(guān)系，還需要維護(hù)關(guān)于整個(gè)DB的元描的元描述數(shù)據(jù)，如關(guān)系的模式等。這類元信息稱為數(shù)據(jù)字典述數(shù)據(jù)，如關(guān)系的模式等。這類元信息稱為數(shù)據(jù)字典(data dictionary)或系統(tǒng)目錄或系統(tǒng)目錄(system catalog)。系統(tǒng)需存儲(chǔ)的元信息類型有：系統(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ì)直方圖信息等