存儲(chǔ)與文件結(jié)構(gòu)

1、Silberschatz, Korth and Sudarshan11.1Database System Conceptsn物理存儲(chǔ)介質(zhì)概述n磁盤(pán)nRAIDn第三級(jí)存儲(chǔ)器n存儲(chǔ)器訪問(wèn)n文件組織n文件中記錄組織n數(shù)據(jù)字典存儲(chǔ)n面向?qū)ο髷?shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)Silberschatz, Korth and Sudarshan11.2Database System Conceptsn數(shù)據(jù)庫(kù)文件被分割成若干定長(zhǎng)的存儲(chǔ)器單位(稱(chēng)為塊). 塊是存儲(chǔ)器分配和數(shù)據(jù)傳輸?shù)膯挝?n數(shù)據(jù)庫(kù)系統(tǒng)應(yīng)盡量減少磁盤(pán)與內(nèi)存間的塊傳輸次數(shù). 可以通過(guò)將盡可能多的塊保持在主存中來(lái)減少磁盤(pán)存取次數(shù).n緩沖區(qū)緩沖區(qū) 用于保存讀入的磁盤(pán)塊的主

2、存空間.n緩沖區(qū)管理器緩沖區(qū)管理器 負(fù)責(zé)分配緩沖區(qū)空間的子系統(tǒng).Silberschatz, Korth and Sudarshan11.3Database System Conceptsn當(dāng)程序請(qǐng)求某磁盤(pán)塊時(shí)即調(diào)用緩沖區(qū)管理器.1.如果該塊已經(jīng)在緩沖區(qū)中, 則程序得到該塊在主存中的地址2.如果該塊不在緩沖區(qū)中, 則1.緩沖區(qū)管理器為該塊分配緩沖區(qū)空間, 如果有必要需換出其他塊來(lái)為這個(gè)新塊騰出空間.2.如果被換出的塊自從最近一次寫(xiě)回磁盤(pán)或從磁盤(pán)讀入之后做過(guò)修改, 則需寫(xiě)回磁盤(pán). 否則直接替換.3.一旦在緩沖區(qū)中分配了空間, 緩沖區(qū)管理器就從磁盤(pán)將該塊讀入緩沖區(qū), 并將該塊在主存中的地址傳給請(qǐng)求者

3、. Silberschatz, Korth and Sudarshan11.4Database System Conceptsn多數(shù)操作系統(tǒng)采用最近未使用最近未使用(LRU)策略策略來(lái)替換塊nLRU背后的想法 利用過(guò)去的塊引用樣式來(lái)預(yù)測(cè)將來(lái)的引用n查詢(xún)有良定義的存取樣式(如順序掃描), 數(shù)據(jù)庫(kù)系統(tǒng)可利用用戶(hù)查詢(xún)中的信息來(lái)預(yù)測(cè)將來(lái)的引用HLRU 對(duì)某些涉及重復(fù)掃描數(shù)據(jù)的存取樣式來(lái)說(shuō)是很差的策略4例如當(dāng)用嵌套循環(huán)算法計(jì)算兩個(gè)關(guān)系 r 與s 的連接時(shí) for each tuple tr of r do for each tuple ts of s do if the tuples tr and ts

4、 match H由查詢(xún)優(yōu)化器提供的帶有替換策略指導(dǎo)線索的混合策略更可取Silberschatz, Korth and Sudarshan11.5Database System Conceptsn受制受制(Pinned)塊塊 不允許寫(xiě)回磁盤(pán)的內(nèi)存塊.n立即替換立即替換(Toss-immediate)策略 一旦塊中最后一條元組被處理完就釋放被該塊所占用的空間n最近使用最近使用(MRU) 策略策略 系統(tǒng)必須牽制(pin)當(dāng)前正被處理的塊. 當(dāng)處理完該塊的最后一條元組, 該塊被解除牽制(unpinned)并成為最近使用的塊.n緩沖區(qū)管理器可利用關(guān)于某請(qǐng)求會(huì)引用特定關(guān)系的概率的統(tǒng)計(jì)信息H例如, 數(shù)據(jù)字典

5、被頻繁存取. 啟示: 將數(shù)據(jù)字典塊保存在緩沖區(qū)中n為恢復(fù)目的, 緩沖區(qū)管理器還支持塊的強(qiáng)制輸出 (參見(jiàn)第17章)Silberschatz, Korth and Sudarshan11.6Database System Conceptsn數(shù)據(jù)庫(kù)保存為若干文件的集合. 文件是記錄的序列. 記錄是字段的序列.n一種方法:H記錄大小固定H每個(gè)文件中只有一種類(lèi)型的記錄H不同文件保存不同關(guān)系這種方法最容易實(shí)現(xiàn).Silberschatz, Korth and Sudarshan11.7Database System Conceptsn簡(jiǎn)單方法:H記錄i 從字節(jié)n (i 1)開(kāi)始存儲(chǔ), 其中n 是記錄大小.H

6、記錄存取簡(jiǎn)單, 但記錄可能跨塊4變化: 不允許記錄跨越塊邊界n刪除記錄i: 可選方法:H將記錄 i + 1, . . ., n 前移成 i, . . . , n 1H將記錄n前移成 iH不移動(dòng)記錄, 而是將所有自由 記錄鏈成一條自由鏈表Silberschatz, Korth and Sudarshan11.8Database System Conceptsn在文件頭中存儲(chǔ)第一條被刪記錄的地址.n在第一條被刪記錄中存儲(chǔ)第二條被刪記錄的地址, 等等n這些存儲(chǔ)的地址可視為指針, 因?yàn)樗鼈?“指向”記錄的位置.n是更有效利用空間的表示法: 重新利用自由記錄的正常字段空間來(lái)存儲(chǔ)指針. (使用中的記錄則不

7、存儲(chǔ)指針)Silberschatz, Korth and Sudarshan11.9Database System Conceptsn數(shù)據(jù)庫(kù)系統(tǒng)中在多種情況下需要變長(zhǎng)記錄:H一個(gè)文件中存儲(chǔ)多種記錄類(lèi)型H允許一個(gè)或多個(gè)變長(zhǎng)字段的記錄類(lèi)型H允許重復(fù)字段的記錄類(lèi)型 (用于某些老式數(shù)據(jù)模型).n字節(jié)串表示法H在每條記錄末尾附加控制字符end-of-record ()H難以刪除H難以增長(zhǎng)Silberschatz, Korth and Sudarshan11.10Database System ConceptsSilberschatz, Korth and Sudarshan11.11Database S

8、ystem ConceptsnSlotted page 頁(yè)頭包含:H記錄登記項(xiàng)數(shù)目H塊中自由空間末端H每條記錄的位置和大小n記錄可以在頁(yè)內(nèi)移動(dòng)以便保持記錄間的連續(xù)存儲(chǔ); 頁(yè)頭中的登記項(xiàng)必須更新.n指針不能直接指向記錄 而是應(yīng)該指向該記錄在頁(yè)頭中的登記項(xiàng).Silberschatz, Korth and Sudarshan11.12Database System Conceptsn定長(zhǎng)表示法: H預(yù)留空間法H指針?lè)╪預(yù)留空間法 利用具有已知最大長(zhǎng)度的定長(zhǎng)記錄; 較小記錄中的未用空間用null或 end-of-record 符號(hào)填充.Silberschatz, Korth and Sudarshan

9、11.13Database System Conceptsn指針?lè)℉變長(zhǎng)記錄用若干通過(guò)指針鏈在一起的定長(zhǎng)記錄表示.H即使最大記錄長(zhǎng)度未知也可用Silberschatz, Korth and Sudarshan11.14Database System Conceptsn指針結(jié)構(gòu)的缺點(diǎn): 除了鏈中首記錄, 其他所有記錄中都有浪費(fèi)空間.n解決方法是文件中采用兩種塊:H錨塊 包含鏈中的首記錄H溢出塊 包含鏈中其他記錄.Silberschatz, Korth and Sudarshan11.15Database System Conceptsn堆堆 記錄可置于文件中的任何有空間的地方n順序順序 記錄按順

10、序存儲(chǔ), 基于每條記錄在搜索鍵上的值n散列散列 對(duì)記錄的某屬性計(jì)算散列函數(shù); 計(jì)算結(jié)果決定該記錄應(yīng)該置于文件的哪個(gè)塊中n每個(gè)關(guān)系的記錄可存儲(chǔ)在單獨(dú)的文件中. 但在聚簇文件組織聚簇文件組織下, 多個(gè)關(guān)系的記錄可存儲(chǔ)于同一文件中H動(dòng)機(jī): 相關(guān)聯(lián)的記錄存儲(chǔ)在同一塊中可減少磁盤(pán) I/OSilberschatz, Korth and Sudarshan11.16Database System Conceptsn適用于需要順序處理整個(gè)文件的應(yīng)用n文件中的記錄按搜索鍵排序Silberschatz, Korth and Sudarshan11.17Database System Conceptsn刪除 利用指

11、針鏈n插入 確定待插入記錄的位置H若有自由空間則在該處插入H若無(wú)自由空間, 插入到溢出塊H兩種情況都要更新指針鏈n需要不時(shí)重組文件以恢復(fù)物理存儲(chǔ)順序Silberschatz, Korth and Sudarshan11.18Database System Conceptsn簡(jiǎn)單的文件結(jié)構(gòu)將每個(gè)關(guān)系存儲(chǔ)在一個(gè)單獨(dú)的文件中n利用聚簇文件組織可以將多個(gè)關(guān)系存儲(chǔ)在一個(gè)文件中n例如, customer 與depositor 的聚簇組織:H有利于涉及depositor customer的查詢(xún), 以及涉及單個(gè)客戶(hù)和他的賬戶(hù)的查詢(xún)H對(duì)只涉及customer的查詢(xún)不好(可用指針鏈, 見(jiàn)下圖)H導(dǎo)致變長(zhǎng)記錄Sil

12、berschatz, Korth and Sudarshan11.19Database System ConceptsSilberschatz, Korth and Sudarshan11.20Database System Conceptsn關(guān)系的信息H關(guān)系名H關(guān)系的屬性名和屬性類(lèi)型H視圖名及其定義H完整性約束n用戶(hù)及賬號(hào)信息, 包括口令n統(tǒng)計(jì)與描述數(shù)據(jù)H每個(gè)關(guān)系的元組數(shù)目n物理文件組織信息H關(guān)系如何存儲(chǔ) (順序/散列/)H關(guān)系的物理位置4操作系統(tǒng)文件名4包含關(guān)系記錄的磁盤(pán)塊地址n索引信息 數(shù)據(jù)字典(也稱(chēng)為系統(tǒng)目錄) 保存元數(shù)據(jù): 即關(guān)于數(shù)據(jù)的數(shù)據(jù),如Silberschatz, Korth

13、and Sudarshan11.21Database System Conceptsn目錄結(jié)構(gòu): 可采用H為高效存取而設(shè)計(jì)的專(zhuān)門(mén)的數(shù)據(jù)結(jié)構(gòu), 或者H關(guān)系集合, 利用現(xiàn)有系統(tǒng)特性保證高效存取通常采用后者n一種可能的目錄結(jié)構(gòu):Relation-metadata = (relation-name, number-of-attributes, storage-organization, location)Attribute-metadata = (attribute-name, relation-name, domain-type, position, length)User-metadata = (

14、user-name, encrypted-password, group)Index-metadata = (index-name, relation-name, index-type, index-attributes)View-metadata = (view-name, definition) Silberschatz, Korth and Sudarshan11.22Database System Conceptsn將對(duì)象映射到文件類(lèi)似于關(guān)系系統(tǒng)中的將元組映射到文件; 可以用文件結(jié)構(gòu)存儲(chǔ)對(duì)象數(shù)據(jù).nOO數(shù)據(jù)庫(kù)中的對(duì)象可能缺少一致性并可能非常大; 管理這種對(duì)象必須不同于管理關(guān)系系統(tǒng)中的記

15、錄.H只有少量元素的集合字段可以用鏈表之類(lèi)的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn). H具有大量元素的集合字段可以實(shí)現(xiàn)為數(shù)據(jù)庫(kù)中單獨(dú)的關(guān)系.H還可以通過(guò)規(guī)范化在存儲(chǔ)層消除集合字段.4類(lèi)似于E-R圖中的多值屬性轉(zhuǎn)換到關(guān)系Silberschatz, Korth and Sudarshan11.23Database System Conceptsn對(duì)象是通過(guò)對(duì)象標(biāo)識(shí)符(OID)來(lái)標(biāo)識(shí)的; 存儲(chǔ)系統(tǒng)需要一個(gè)機(jī)制來(lái)根據(jù)給定的OID定位對(duì)象 (此動(dòng)作稱(chēng)為解引用解引用).H邏輯標(biāo)識(shí)符邏輯標(biāo)識(shí)符不直接指明對(duì)象的物理位置; 必須維護(hù)一個(gè)索引將OID映射到對(duì)象的實(shí)際位置.H物理標(biāo)識(shí)符物理標(biāo)識(shí)符編碼了對(duì)象的位置信息, 因此可以直接找到對(duì)象.

16、 典型的物理OID由以下部分組成:1. 卷或文件標(biāo)識(shí)符2. 卷或文件內(nèi)的頁(yè)標(biāo)識(shí)符3. 頁(yè)內(nèi)偏移量Silberschatz, Korth and Sudarshan11.24Database System ConceptsnPhysical OIDs may be a unique identifier. This identifier is stored in the object also and is used to detect references via dangling pointers. Silberschatz, Korth and Sudarshan11.25Database

17、 System Conceptsn利用OID實(shí)現(xiàn)持久性指針; 持久性指針大大長(zhǎng)于內(nèi)存指針n指針swizzling減少了定位已經(jīng)在內(nèi)存中的持久性對(duì)象的代價(jià).n軟件swizzling (swizzling on pointer deference)H當(dāng)持久性指針第一次解引用(dereference)時(shí), 對(duì)象定位于內(nèi)存中之后, 指針被swizzle (用內(nèi)存指針替換).H隨后對(duì)同一指針的解引用就變得代價(jià)低廉.H如果有swizzled指針指向一個(gè)對(duì)象, 則要求它在內(nèi)存中的物理位置不能改變; 方法是釘住(pin)內(nèi)存頁(yè)H當(dāng)一個(gè)對(duì)象寫(xiě)回磁盤(pán)時(shí), 它所包含的所有swizzled指針需要 unswizzle

18、.Silberschatz, Korth and Sudarshan11.26Database System Conceptsn使用硬件swizzling時(shí), 對(duì)象中的持久性指針需要與內(nèi)存指針相同的空間量 使用對(duì)象外部的額外存儲(chǔ)空間來(lái)存儲(chǔ)指針的其他信息.n使用虛擬內(nèi)存翻譯機(jī)制來(lái)高效和透明地轉(zhuǎn)換持久性指針與內(nèi)存指針.n當(dāng)頁(yè)首次讀入內(nèi)存時(shí), 該頁(yè)內(nèi)的所有持久性指針都要被swizzled. H因此程序員只需要處理一種指針類(lèi)型, 即內(nèi)存指針.H某些swizzled指針可能指向暫時(shí)未分配實(shí)際內(nèi)存的虛擬內(nèi)存地址 (從而也未包含合法數(shù)據(jù)) Silberschatz, Korth and Sudarshan1

19、1.27Database System Conceptsn持久指針從概念上分為兩部分: 頁(yè)標(biāo)識(shí)和頁(yè)內(nèi)偏移.H指針中的頁(yè)標(biāo)識(shí)是一個(gè)短的間接指針: 每一頁(yè)都有一個(gè)轉(zhuǎn)換表提供從短的頁(yè)標(biāo)識(shí)到完整數(shù)據(jù)庫(kù)頁(yè)標(biāo)識(shí)的映射.H頁(yè)的轉(zhuǎn)換表較小 (4096字節(jié)的頁(yè)最多有1024 個(gè)4字節(jié)的指針)H頁(yè)中指向相同頁(yè)的多個(gè)指針共享轉(zhuǎn)換表中的同一表項(xiàng).Silberschatz, Korth and Sudarshan11.28Database System Conceptsnswizzling之前的頁(yè)映象之前的頁(yè)映象 (頁(yè)頁(yè)位于磁盤(pán)上位于磁盤(pán)上)Silberschatz, Korth and Sudarshan11.29D

20、atabase System Conceptsn當(dāng)系統(tǒng)將頁(yè)加載到內(nèi)存時(shí), 頁(yè)內(nèi)的持久指針的按如下方式進(jìn)行swizzling1.利用對(duì)象類(lèi)型信息定位頁(yè)內(nèi)每個(gè)對(duì)象中的持久指針2.對(duì)每個(gè)持久指針(pi, oi) 找到其完整頁(yè)標(biāo)識(shí) Pi 1.若 Pi 尚未被分配虛擬內(nèi)存頁(yè), 為Pi 分配虛擬內(nèi)存頁(yè)并讀保護(hù)該頁(yè)H注意: 這時(shí)虛擬內(nèi)存頁(yè)可以沒(méi)有分配任何物理空間 (在內(nèi)存中或在磁盤(pán)交換區(qū)中). 可以在訪問(wèn)Pi 時(shí)分配空間. 這時(shí)讀保護(hù)就不需要了.HAccessing a memory location in the page in the will result in a segmentation viol

21、ation, which is handled as described later 2.令 vi 是分配給Pi 的虛擬頁(yè)3.用(vi, oi)替換 (pi, oi)3.將轉(zhuǎn)換表中的每個(gè)表項(xiàng) (pi, Pi)替換成 (vi, Pi) Silberschatz, Korth and Sudarshan11.30Database System Conceptsn當(dāng)一個(gè)內(nèi)存指針被去引用, 如果操作系統(tǒng)發(fā)現(xiàn)它指向的頁(yè)尚未被分配存儲(chǔ)空間, 或者是讀保護(hù)的, 就發(fā)生了段越界段越界.nUnix中的mmap() 調(diào)用用來(lái)指定當(dāng)發(fā)生段越界時(shí)調(diào)用的函數(shù)n該函數(shù)被調(diào)用時(shí)做以下事情1.如果尚未為包含被引用地址的頁(yè)分配

22、就先分配存儲(chǔ)(交換區(qū)). 關(guān)閉讀保護(hù)2.從磁盤(pán)讀入該頁(yè)3.為該頁(yè)中每個(gè)持久指針執(zhí)行指針swizzlingSilberschatz, Korth and Sudarshan11.31Database System Conceptsn具有短頁(yè)標(biāo)識(shí)2395的頁(yè)被分配地址 5001. 注意指針和轉(zhuǎn)換表的變化.n具有短頁(yè)標(biāo)識(shí)4867的頁(yè)已被分配地址4867. 指針和轉(zhuǎn)換表沒(méi)有變化.swizzling之后的頁(yè)映象之后的頁(yè)映象Silberschatz, Korth and Sudarshan11.32Database System ConceptsnSwizzling之后, 所有短頁(yè)標(biāo)識(shí)指向分配給對(duì)應(yīng)頁(yè)的虛擬內(nèi)存地址H存取對(duì)象的函數(shù)甚至不知道它有持久指針, 不需要做任何變動(dòng)!H可以重用現(xiàn)有使用內(nèi)存指針的代碼和庫(kù)n此后, 觸發(fā)swizzling的指針解引用可以繼續(xù)n優(yōu)化:H若所有頁(yè)都分配與短頁(yè)標(biāo)識(shí)相同的地址, 則該頁(yè)不需要變動(dòng)!H不需要所謂deswizzling swizzled頁(yè)可以原樣保存到磁盤(pán)H一組頁(yè)