數(shù)據(jù)元素的表示

1、1第三章第三章 數(shù)據(jù)元素的表示數(shù)據(jù)元素的表示2Previousn磁盤結(jié)構(gòu)對(duì)性能的影響磁盤結(jié)構(gòu)對(duì)性能的影響nDBMS中的數(shù)據(jù)必須在內(nèi)存中操作中的數(shù)據(jù)必須在內(nèi)存中操作n磁盤和主存之間數(shù)據(jù)傳輸?shù)膯挝皇菈K，如果只需要塊上的磁盤和主存之間數(shù)據(jù)傳輸?shù)膯挝皇菈K，如果只需要塊上的某一項(xiàng)，也需要傳輸整個(gè)塊。讀某一項(xiàng)，也需要傳輸整個(gè)塊。讀/寫一個(gè)磁盤塊稱為一次寫一個(gè)磁盤塊稱為一次I/On讀讀/寫塊的時(shí)間依數(shù)據(jù)所在的位置而變化寫塊的時(shí)間依數(shù)據(jù)所在的位置而變化存取時(shí)間存取時(shí)間=尋道時(shí)間尋道時(shí)間S旋轉(zhuǎn)延遲旋轉(zhuǎn)延遲R傳輸時(shí)間傳輸時(shí)間T3n數(shù)據(jù)項(xiàng)的表示（數(shù)據(jù)項(xiàng)的表示（Data ItemsData Items）n記錄的表示（

2、記錄的表示（RecordsRecords）n記錄在塊中的組織（記錄在塊中的組織（BlockBlock）n記錄的修改記錄的修改n塊在文件中的組織塊在文件中的組織n緩沖區(qū)管理緩沖區(qū)管理主要內(nèi)容主要內(nèi)容4數(shù)據(jù)元素的表示層次數(shù)據(jù)元素的表示層次數(shù)據(jù)項(xiàng)記錄塊文件屬性值的物理組織元組的物理組織記錄的物理存放文件由磁盤塊構(gòu)成5一、數(shù)據(jù)項(xiàng)的表示一、數(shù)據(jù)項(xiàng)的表示n數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)n字節(jié)序列字節(jié)序列n表示關(guān)系數(shù)據(jù)庫(kù)中元組的屬性值表示關(guān)系數(shù)據(jù)庫(kù)中元組的屬性值61、數(shù)據(jù)項(xiàng)表示的內(nèi)容、數(shù)據(jù)項(xiàng)表示的內(nèi)容n表示什么？表示什么？n姓名姓名n年齡年齡n出生日期出生日期n照片照片nn用什么表示？用什么表示？nBytes72、數(shù)據(jù)項(xiàng)表示

3、方法：、數(shù)據(jù)項(xiàng)表示方法：SQL數(shù)據(jù)類型數(shù)據(jù)類型nInteger (short)n2 bytesn例如，例如，35 表示為表示為nReal，F(xiàn)loatn4 bytes （32 bits）nN bits表示小數(shù)，表示小數(shù)，M bits表示指數(shù)表示指數(shù) 000000000010001182、數(shù)據(jù)項(xiàng)表示方法：、數(shù)據(jù)項(xiàng)表示方法：SQL數(shù)據(jù)類型數(shù)據(jù)類型nChar(n) 或或 Character(n) 定長(zhǎng)字符串定長(zhǎng)字符串n小于小于n時(shí)使用特殊填充符時(shí)使用特殊填充符n例如，若屬性類型為例如，若屬性類型為Char(5)，則屬性值，則屬性值cat 表示為表示為 nVarchar(n) 變長(zhǎng)字符串變長(zhǎng)字符串nNU

4、LL終止符，例終止符，例 Varchar(5)n長(zhǎng)度長(zhǎng)度+內(nèi)容內(nèi)容 n定長(zhǎng)表示，定長(zhǎng)表示，n+1 bytesVarchar(4):cta ctacta3cta 92、數(shù)據(jù)項(xiàng)表示方法：、數(shù)據(jù)項(xiàng)表示方法：SQL數(shù)據(jù)類型數(shù)據(jù)類型nBooleannTRUEnFALSEn枚舉類型枚舉類型nRED,GREEN,YELLOWn整數(shù)表示整數(shù)表示nRED 1，GREEN 2，YELLOW 3n若用兩個(gè)字節(jié)的短整型來(lái)表示，則可以表示若用兩個(gè)字節(jié)的短整型來(lái)表示，則可以表示 216 個(gè)不同個(gè)不同值值1111 11110000 0000102、數(shù)據(jù)項(xiàng)表示方法：、數(shù)據(jù)項(xiàng)表示方法：SQL數(shù)據(jù)類型數(shù)據(jù)類型nDaten10字符

5、字符(SQL92)：YYYY-MM-DD字符串表示字符串表示n8字符：字符：YYYYMMDDn7字符：字符：YYYYDDD, NOT YYMMDD！nInteger，自，自1900-01-01以來(lái)的天數(shù)以來(lái)的天數(shù)nTimen8字符字符(SQL92)：HH:NN:SS 整數(shù)秒整數(shù)秒nVarchar(n)：HH:NN:SS.FF帶小數(shù)秒帶小數(shù)秒nInteger，自，自00:00:00以來(lái)的秒數(shù)以來(lái)的秒數(shù)112、數(shù)據(jù)項(xiàng)表示方法：、數(shù)據(jù)項(xiàng)表示方法：SQL數(shù)據(jù)類型數(shù)據(jù)類型nBitn帶長(zhǎng)度的二進(jìn)制位串帶長(zhǎng)度的二進(jìn)制位串n按字節(jié)表示，例如按字節(jié)表示，例如 010111110011LengthBits0101

6、111100110000123、兩種不同的數(shù)據(jù)項(xiàng)表示、兩種不同的數(shù)據(jù)項(xiàng)表示n定長(zhǎng)數(shù)據(jù)項(xiàng)定長(zhǎng)數(shù)據(jù)項(xiàng)n變長(zhǎng)數(shù)據(jù)項(xiàng)變長(zhǎng)數(shù)據(jù)項(xiàng)n帶長(zhǎng)度帶長(zhǎng)度 （常用常用!）nNull Terminated13數(shù)據(jù)項(xiàng)表示總結(jié)數(shù)據(jù)項(xiàng)表示總結(jié)類類 型型 表表 示示 方方 法法整數(shù)和實(shí)數(shù) 字節(jié)串字節(jié)串定長(zhǎng)字符串定長(zhǎng)字符串 n字節(jié)的數(shù)組字節(jié)的數(shù)組變長(zhǎng)字符串變長(zhǎng)字符串 VARCHAR(n) 用用n+ 1字節(jié)字節(jié) 長(zhǎng)度加內(nèi)容空值-終止字符串日期和時(shí)間 某種格式的定長(zhǎng)字符串 變長(zhǎng)值 整數(shù)二進(jìn)制位序列 長(zhǎng)度加內(nèi)容字節(jié)表示枚舉類型 使用整數(shù)編碼表示一個(gè)枚舉類型的值14Where are we?數(shù)據(jù)項(xiàng)記錄塊文件We are here！15

7、二、記錄的組織二、記錄的組織n記錄記錄n數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng) 字段，字段，F(xiàn)ields 的集合的集合E.g.: Employee record:name field,salary field,date-of-hire field, .161、記錄的類型、記錄的類型n固定格式固定格式 vs. 可變格式可變格式Fixed Format vs. Variable Formatn定長(zhǎng)定長(zhǎng) vs. 變長(zhǎng)變長(zhǎng)Fixed Length vs. Variable Length172、固定格式定長(zhǎng)記錄、固定格式定長(zhǎng)記錄n所有記錄具有相同的邏輯結(jié)構(gòu)（模式）所有記錄具有相同的邏輯結(jié)構(gòu)（模式）n記錄的模式（記錄的模式（Sch

8、ema）n# fieldsnName of each fieldnType of each fieldnOrder in recordnOffset of each field in the record18E.g. 固定格式定長(zhǎng)記錄固定格式定長(zhǎng)記錄Employee record(1) E#, 2 byte integer(2) Ename, 10 char. Schema(3) Dept, 2 byte code55s m i t h0283j o n e s01Records192、固定格式定長(zhǎng)記錄、固定格式定長(zhǎng)記錄n構(gòu)造構(gòu)造n不考慮尋址特點(diǎn)不考慮尋址特點(diǎn)202、固定格式定長(zhǎng)記錄、固定格式

9、定長(zhǎng)記錄n考慮尋址特點(diǎn)考慮尋址特點(diǎn)n假設(shè)記錄和字段的開(kāi)始地址必須是假設(shè)記錄和字段的開(kāi)始地址必須是4的倍數(shù)的倍數(shù)213、記錄首部、記錄首部n在記錄首部（在記錄首部（Head）的描述記錄的信息）的描述記錄的信息n記錄類型（模式信息）記錄類型（模式信息）n記錄長(zhǎng)度記錄長(zhǎng)度n時(shí)間戳?xí)r間戳n其它信息其它信息224、可變格式記錄、可變格式記錄n每個(gè)記錄的格式不同每個(gè)記錄的格式不同n記錄的格式存儲(chǔ)于記錄中記錄的格式存儲(chǔ)于記錄中23E.g. 可變格式變長(zhǎng)記錄表示可變格式變長(zhǎng)記錄表示4I524SDROF46 字段數(shù)字段數(shù)字段字段E標(biāo)識(shí)碼標(biāo)識(shí)碼Integer 類型類型字段字段 Ename標(biāo)識(shí)碼標(biāo)識(shí)碼String

10、類型類型長(zhǎng)度長(zhǎng)度Employee(E#, Ename)標(biāo)記字段(Tags)244、可變格式記錄、可變格式記錄n好處好處n靈活的記錄格式，適合靈活的記錄格式，適合“松散松散”記錄記錄n盡管一個(gè)記錄可能有大量字段，但某個(gè)記錄通常只有盡管一個(gè)記錄可能有大量字段，但某個(gè)記錄通常只有有限的幾個(gè)字段有限的幾個(gè)字段n例如，病人的檢驗(yàn)結(jié)果例如，病人的檢驗(yàn)結(jié)果n適合處理重復(fù)字段適合處理重復(fù)字段n適合記錄格式演變適合記錄格式演變n缺點(diǎn)缺點(diǎn)n浪費(fèi)存儲(chǔ)空間浪費(fèi)存儲(chǔ)空間256、變長(zhǎng)記錄表示、變長(zhǎng)記錄表示n首部指針?lè)ㄊ撞恐羔樂(lè)╪定長(zhǎng)字段在前，變長(zhǎng)字段在后定長(zhǎng)字段在前，變長(zhǎng)字段在后 name、address變長(zhǎng)變長(zhǎng)266、

11、變長(zhǎng)記錄表示、變長(zhǎng)記錄表示n混合格式：定長(zhǎng)記錄變長(zhǎng)記錄混合格式：定長(zhǎng)記錄變長(zhǎng)記錄27Where are we?數(shù)據(jù)項(xiàng)記錄塊文件We are here！28三、記錄在塊中的組織三、記錄在塊中的組織n假設(shè)假設(shè)n塊的大小固定塊的大小固定n記錄組織成單個(gè)文件記錄組織成單個(gè)文件assume fixedlength blocksassume a single file (for now)BlockA FileA Record29三、記錄在塊中的組織三、記錄在塊中的組織n定長(zhǎng)記錄的兩種塊內(nèi)組織定長(zhǎng)記錄的兩種塊內(nèi)組織n記錄地址記錄地址rid通常使用通常使用表示表示槽槽 1 1槽槽 N N槽槽 2 2N N1

12、0 1 0 1 M1 0 1 0 1 M槽槽 1 1槽槽 M M槽槽 2 2M M 3 2 1 3 2 1記錄數(shù)槽數(shù)空閑空間空閑空間塊頭塊頭30三、記錄在塊中的組織三、記錄在塊中的組織n變長(zhǎng)記錄在塊內(nèi)的組織變長(zhǎng)記錄在塊內(nèi)的組織N N242416162020第i塊rid=的記錄的記錄長(zhǎng)度24rid=rid=N N 4 3 2 1 4 3 2 1槽數(shù)槽數(shù)槽目錄槽目錄空閑空間數(shù)據(jù)區(qū)31三、記錄在塊中的組織三、記錄在塊中的組織n其他問(wèn)題其他問(wèn)題n記錄在塊中的分隔記錄在塊中的分隔 (separating records)n記錄跨塊記錄跨塊 vs.記錄不跨塊記錄不跨塊 (spanned vs. unspa

13、nned)n不同類型的記錄聚簇不同類型的記錄聚簇 (mixed record types clustering)n按序組織按序組織 (sequencing)n記錄的分裂記錄的分裂 (split records)n記錄地址記錄地址 (record address)n記錄的修改記錄的修改321、記錄在塊內(nèi)的分隔、記錄在塊內(nèi)的分隔n定長(zhǎng)記錄：不需分隔定長(zhǎng)記錄：不需分隔n使用特殊標(biāo)記使用特殊標(biāo)記n通過(guò)塊內(nèi)偏移量通過(guò)塊內(nèi)偏移量332、跨塊、跨塊 vs. 不跨塊不跨塊nUnspanned: 記錄必須在一個(gè)塊中存儲(chǔ)記錄必須在一個(gè)塊中存儲(chǔ)block 1 block 2 .nSpanned：記錄可跨塊存儲(chǔ)：記錄

14、可跨塊存儲(chǔ)block 1 block 2 .R1R2R1R3R4R5R2R3(a)R3(b)R6R5R4R7(a)342、跨塊、跨塊 vs. 不跨塊不跨塊n跨塊跨塊Whats the rest?From where?352、跨塊、跨塊 vs. 不可跨塊不可跨塊n比較比較nunspanned：實(shí)現(xiàn)簡(jiǎn)單，但空間浪費(fèi)：實(shí)現(xiàn)簡(jiǎn)單，但空間浪費(fèi)nspanned：有效利用空間，實(shí)現(xiàn)更復(fù)雜：有效利用空間，實(shí)現(xiàn)更復(fù)雜nBut nIf record size block size，MUST be spanned363、不同類型的記錄聚簇、不同類型的記錄聚簇n一個(gè)塊中存儲(chǔ)不同類型的記錄一個(gè)塊中存儲(chǔ)不同類型的記錄（對(duì)

15、于（對(duì)于RDB：多關(guān)系上的聚簇多關(guān)系上的聚簇）n好處好處聚簇聚簇 (clustering)n經(jīng)常一起訪問(wèn)的記錄存儲(chǔ)在同一塊或連續(xù)塊中經(jīng)常一起訪問(wèn)的記錄存儲(chǔ)在同一塊或連續(xù)塊中A Dept Record A Employee Record A Employee RecordA Block373、不同類型的記錄聚簇、不同類型的記錄聚簇學(xué)號(hào)學(xué)號(hào)s1其他列其他列學(xué)號(hào)學(xué)號(hào)S1S1s1其他列其他列課程號(hào)課程號(hào)C1C2c3學(xué)號(hào)學(xué)號(hào)s2其他列其他列學(xué)號(hào)學(xué)號(hào)S2S2s2其他列其他列課程號(hào)課程號(hào)C2C5c6學(xué)生表與課程學(xué)生表與課程表通過(guò)簇鍵表通過(guò)簇鍵“學(xué)號(hào)學(xué)號(hào)”聚簇聚簇Block383、不同類型的記錄聚簇、不同類型

16、的記錄聚簇Q1: select student.s#,ame from student s,sc where s.s# = sc.s# Q2: select * from studentn如果如果Q1經(jīng)常被查詢，則聚簇非常有效經(jīng)常被查詢，則聚簇非常有效n若若Q2經(jīng)常被查詢，則聚簇反而降低了效率經(jīng)常被查詢，則聚簇反而降低了效率STUDENT(STUDENT(s#s#,sname,age,sname,age) )SC(SC(s#s#, ,cnamecname,score,score) )394、在塊中按序存儲(chǔ)記錄、在塊中按序存儲(chǔ)記錄n另一種聚簇另一種聚簇 (對(duì)于對(duì)于RDB：?jiǎn)侮P(guān)系上的聚簇單關(guān)系上的

17、聚簇)n將記錄按某個(gè)字段順序排列在塊中將記錄按某個(gè)字段順序排列在塊中n好處好處n加快按排序字段查詢記錄時(shí)的效率加快按排序字段查詢記錄時(shí)的效率n利于歸并聯(lián)接利于歸并聯(lián)接 （will be discussed later）404、在塊中按序存儲(chǔ)記錄、在塊中按序存儲(chǔ)記錄化學(xué)系化學(xué)系化學(xué)系化學(xué)系化學(xué)系化學(xué)系化學(xué)系化學(xué)系物理系物理系物理系物理系物理系物理系中文系中文系化學(xué)系化學(xué)系物理系物理系物理系物理系化學(xué)系化學(xué)系中文系中文系化學(xué)系化學(xué)系物理系物理系化學(xué)系化學(xué)系按按Dept順序組織的順序組織的Student記錄記錄無(wú)序組織的無(wú)序組織的Student記錄記錄假設(shè)一個(gè)磁盤塊假設(shè)一個(gè)磁盤塊2條定長(zhǎng)記錄條定長(zhǎng)記

18、錄414、在塊中按序存儲(chǔ)記錄、在塊中按序存儲(chǔ)記錄n物理連續(xù)物理連續(xù)n指針連接指針連接Next (R1)R1R1R2Next(R1)425、記錄的分裂、記錄的分裂n適合于變長(zhǎng)記錄的混合格式表示適合于變長(zhǎng)記錄的混合格式表示n定長(zhǎng)部分存儲(chǔ)于某個(gè)塊中定長(zhǎng)部分存儲(chǔ)于某個(gè)塊中n變長(zhǎng)部分存儲(chǔ)于另一個(gè)塊中變長(zhǎng)部分存儲(chǔ)于另一個(gè)塊中n與與spanned存儲(chǔ)類似存儲(chǔ)類似436、記錄地址、記錄地址n物理地址物理地址n邏輯地址（間接地址）邏輯地址（間接地址）446、記錄地址、記錄地址n記錄的純物理地址記錄的純物理地址n主機(jī)標(biāo)識(shí)主機(jī)標(biāo)識(shí) n磁盤或其他設(shè)備標(biāo)識(shí)磁盤或其他設(shè)備標(biāo)識(shí)n柱面號(hào)柱面號(hào)n磁頭號(hào)（盤面號(hào)）磁頭號(hào)（盤面號(hào)

19、） n塊號(hào)塊號(hào) n塊內(nèi)的偏移量塊內(nèi)的偏移量塊地址456、記錄地址、記錄地址n記錄的純邏輯地址記錄的純邏輯地址物理地址物理地址邏輯地址邏輯地址映射表記錄地址純物理地址缺點(diǎn)訪問(wèn)代價(jià)增加：映射表占存儲(chǔ)空間；需要地址轉(zhuǎn)換好處?kù)`活性：刪除或移動(dòng)記錄時(shí)只要改變映射表項(xiàng)466、記錄地址、記錄地址記錄的純物理地址記錄的純邏輯地址tradeoff476、記錄地址、記錄地址n借助文件系統(tǒng)的邏輯塊地址借助文件系統(tǒng)的邏輯塊地址n文件號(hào)邏輯塊地址塊內(nèi)偏移文件號(hào)邏輯塊地址塊內(nèi)偏移文件系統(tǒng)映射File IDBlock(logical)Block(physical) + offset記錄地址48四、記錄的修改四、記錄的修改n

20、插入插入n刪除刪除491、插入、插入n記錄無(wú)序記錄無(wú)序n插入到任意塊的空閑空間中插入到任意塊的空閑空間中n或申請(qǐng)一個(gè)新塊（當(dāng)所有塊都已滿時(shí)）或申請(qǐng)一個(gè)新塊（當(dāng)所有塊都已滿時(shí)）n記錄變長(zhǎng)時(shí)，可使用偏移量表記錄變長(zhǎng)時(shí)，可使用偏移量表501、插入、插入n記錄有序記錄有序n找到記錄應(yīng)該放置的塊找到記錄應(yīng)該放置的塊n如果有空間，放入并調(diào)節(jié)記錄順序即可，否則有兩種方法：如果有空間，放入并調(diào)節(jié)記錄順序即可，否則有兩種方法：n在在“鄰近塊鄰近塊”中找空間中找空間 n創(chuàng)建溢出塊創(chuàng)建溢出塊 512、刪除、刪除n立即回收空間立即回收空間n例如，加到可用空間列表中例如，加到可用空間列表中n刪除記錄時(shí)處理溢出塊刪除記錄

21、時(shí)處理溢出塊n若刪除的記錄位于溢出塊鏈上，則刪除記錄后可對(duì)整個(gè)鏈若刪除的記錄位于溢出塊鏈上，則刪除記錄后可對(duì)整個(gè)鏈進(jìn)行重新組織以去除溢出塊進(jìn)行重新組織以去除溢出塊522、刪除、刪除n使用刪除標(biāo)記使用刪除標(biāo)記n若使用偏移表，則可以修改偏移表項(xiàng)指針，將其置空若使用偏移表，則可以修改偏移表項(xiàng)指針，將其置空n若使用邏輯物理地址映射表，則可以將物理地址置空若使用邏輯物理地址映射表，則可以將物理地址置空n可以在記錄首部預(yù)留一開(kāi)始位：可以在記錄首部預(yù)留一開(kāi)始位：0未刪除，未刪除，1已刪除已刪除1記錄10記錄253Where are we?數(shù)據(jù)項(xiàng)記錄塊文件We are here！54五、塊在文件中的組織五、塊

22、在文件中的組織n堆文件（堆文件（Heap File）n最基本、最簡(jiǎn)單的文件結(jié)構(gòu)最基本、最簡(jiǎn)單的文件結(jié)構(gòu)n記錄不以任何順序排序記錄不以任何順序排序n記錄可能存放在物理不鄰接的塊上記錄可能存放在物理不鄰接的塊上n插入容易，但查找和刪除代價(jià)高插入容易，但查找和刪除代價(jià)高551、鏈表式堆文件組織、鏈表式堆文件組織首塊數(shù)據(jù)塊數(shù)據(jù)塊數(shù)據(jù)塊數(shù)據(jù)塊數(shù)據(jù)塊數(shù)據(jù)塊含空閑空間的塊鏈表滿塊鏈表562、目錄式堆文件組織、目錄式堆文件組織數(shù)據(jù)塊1數(shù)據(jù)塊2數(shù)據(jù)塊N首塊57回顧：數(shù)據(jù)元素的表示層次回顧：數(shù)據(jù)元素的表示層次數(shù)據(jù)項(xiàng)記錄塊文件屬性值的物理組織元組的物理組織記錄的物理存放文件由磁盤塊構(gòu)成58六、六、SQL Serve

23、r的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)nSQL Server的數(shù)據(jù)庫(kù)文件是多個(gè)對(duì)象的集合，包括多個(gè)表、的數(shù)據(jù)庫(kù)文件是多個(gè)對(duì)象的集合，包括多個(gè)表、索引等索引等n參閱參閱SQL Server聯(lián)機(jī)叢書(shū)聯(lián)機(jī)叢書(shū)nSQL Server數(shù)據(jù)庫(kù)引擎數(shù)據(jù)庫(kù)引擎-高級(jí)數(shù)據(jù)庫(kù)引擎詳細(xì)信息高級(jí)數(shù)據(jù)庫(kù)引擎詳細(xì)信息591、頁(yè)、頁(yè)n在在SQL Server中，數(shù)據(jù)存儲(chǔ)的基本單位是頁(yè)。在中，數(shù)據(jù)存儲(chǔ)的基本單位是頁(yè)。在 SQL Server 2005 中，頁(yè)的大小是中，頁(yè)的大小是 8 KB。n每頁(yè)的開(kāi)頭每頁(yè)的開(kāi)頭 96 字節(jié)，用于存儲(chǔ)有關(guān)頁(yè)的系統(tǒng)信息，包括頁(yè)字節(jié)，用于存儲(chǔ)有關(guān)頁(yè)的系統(tǒng)信息，包括頁(yè)碼、頁(yè)類型、頁(yè)的可用空間以及擁有該頁(yè)的

24、對(duì)象的分配單元碼、頁(yè)類型、頁(yè)的可用空間以及擁有該頁(yè)的對(duì)象的分配單元 ID 9696字節(jié)字節(jié)單個(gè)數(shù)據(jù)行單個(gè)數(shù)據(jù)行最大最大80608060字節(jié)字節(jié)頁(yè)地址：數(shù)據(jù)行地址：602、區(qū)、區(qū)n區(qū)是管理空間的基本單位。一個(gè)區(qū)是八個(gè)物理上連續(xù)的頁(yè)（即區(qū)是管理空間的基本單位。一個(gè)區(qū)是八個(gè)物理上連續(xù)的頁(yè)（即 64 KB）。）。 n為了使空間分配更有效，為了使空間分配更有效，SQL Server 2005 對(duì)只含少量數(shù)據(jù)的表不分配對(duì)只含少量數(shù)據(jù)的表不分配完整的區(qū)。完整的區(qū)。SQL Server 2005 有兩種類型的擴(kuò)展盤區(qū)：有兩種類型的擴(kuò)展盤區(qū)： n統(tǒng)一區(qū)：由單個(gè)對(duì)象所有，區(qū)中的所有統(tǒng)一區(qū)：由單個(gè)對(duì)象所有，區(qū)中的所

25、有8頁(yè)只能由擁有該盤區(qū)的對(duì)象頁(yè)只能由擁有該盤區(qū)的對(duì)象使用。使用。n混合區(qū)：最多可由混合區(qū)：最多可由 8 個(gè)對(duì)象共享。個(gè)對(duì)象共享。 n通常從混合區(qū)中向新表或新索引分配頁(yè)。當(dāng)表或索引增長(zhǎng)到通常從混合區(qū)中向新表或新索引分配頁(yè)。當(dāng)表或索引增長(zhǎng)到 8 頁(yè)時(shí)，就頁(yè)時(shí)，就變成統(tǒng)一擴(kuò)展盤區(qū)。變成統(tǒng)一擴(kuò)展盤區(qū)。612、區(qū)、區(qū)n混合區(qū)和統(tǒng)一區(qū)混合區(qū)和統(tǒng)一區(qū)623、SQL Server文件組織文件組織nSQL Server 2005 數(shù)據(jù)庫(kù)有三種類型的文件：數(shù)據(jù)庫(kù)有三種類型的文件： n主要數(shù)據(jù)文件主要數(shù)據(jù)文件 n主要數(shù)據(jù)文件是數(shù)據(jù)庫(kù)的起點(diǎn)，指向數(shù)據(jù)庫(kù)中文件的其它部分。主要數(shù)據(jù)文件是數(shù)據(jù)庫(kù)的起點(diǎn)，指向數(shù)據(jù)庫(kù)中文件的其

26、它部分。每個(gè)數(shù)據(jù)庫(kù)都有一個(gè)主要數(shù)據(jù)文件。主要數(shù)據(jù)文件的推薦文件擴(kuò)每個(gè)數(shù)據(jù)庫(kù)都有一個(gè)主要數(shù)據(jù)文件。主要數(shù)據(jù)文件的推薦文件擴(kuò)展名是展名是 .mdf。n次要數(shù)據(jù)文件次要數(shù)據(jù)文件 n次要數(shù)據(jù)文件包含除主要數(shù)據(jù)文件外的所有數(shù)據(jù)文件。有些數(shù)據(jù)次要數(shù)據(jù)文件包含除主要數(shù)據(jù)文件外的所有數(shù)據(jù)文件。有些數(shù)據(jù)庫(kù)可能沒(méi)有次要數(shù)據(jù)文件，而有些數(shù)據(jù)庫(kù)則有多個(gè)次要數(shù)據(jù)文件。庫(kù)可能沒(méi)有次要數(shù)據(jù)文件，而有些數(shù)據(jù)庫(kù)則有多個(gè)次要數(shù)據(jù)文件。次要數(shù)據(jù)文件的推薦文件擴(kuò)展名是次要數(shù)據(jù)文件的推薦文件擴(kuò)展名是 .ndf。n日志文件日志文件 n日志文件包含恢復(fù)數(shù)據(jù)庫(kù)所需的所有日志信息。每個(gè)數(shù)據(jù)庫(kù)必須日志文件包含恢復(fù)數(shù)據(jù)庫(kù)所需的所有日志信息。每個(gè)數(shù)

27、據(jù)庫(kù)必須至少有一個(gè)日志文件，但可以不止一個(gè)。日志文件的推薦文件擴(kuò)至少有一個(gè)日志文件，但可以不止一個(gè)。日志文件的推薦文件擴(kuò)展名是展名是 .ldf。633、SQL Server文件組織文件組織643、SQL Server文件組織文件組織n數(shù)據(jù)文件頁(yè)數(shù)據(jù)文件頁(yè)n數(shù)據(jù)文件的頁(yè)按順序編號(hào)，文件首頁(yè)的頁(yè)碼是數(shù)據(jù)文件的頁(yè)按順序編號(hào)，文件首頁(yè)的頁(yè)碼是 0。每個(gè)文。每個(gè)文件都有一個(gè)文件件都有一個(gè)文件 ID 號(hào)。在數(shù)據(jù)庫(kù)中唯一標(biāo)識(shí)一頁(yè)需要同號(hào)。在數(shù)據(jù)庫(kù)中唯一標(biāo)識(shí)一頁(yè)需要同時(shí)使用文件時(shí)使用文件 ID 和頁(yè)碼。和頁(yè)碼。653、SQL Server文件組織文件組織n數(shù)據(jù)文件的起始結(jié)構(gòu)數(shù)據(jù)文件的起始結(jié)構(gòu)663、SQL S

28、erver文件組織文件組織n數(shù)據(jù)文件的起始結(jié)構(gòu)數(shù)據(jù)文件的起始結(jié)構(gòu)nPFS頁(yè)：頁(yè)可用空間頁(yè)：頁(yè)可用空間 (PFS) 頁(yè)記錄每頁(yè)的分配狀態(tài)，是否頁(yè)記錄每頁(yè)的分配狀態(tài)，是否已分配單個(gè)頁(yè)以及每頁(yè)的可用空間量。已分配單個(gè)頁(yè)以及每頁(yè)的可用空間量。PFS 對(duì)每頁(yè)都有對(duì)每頁(yè)都有一個(gè)字節(jié)，記錄該頁(yè)是否已分配。如果已分配，則記錄該一個(gè)字節(jié)，記錄該頁(yè)是否已分配。如果已分配，則記錄該頁(yè)是為空、已滿頁(yè)是為空、已滿 1% 到到 50%、已滿、已滿 51% 到到 80%、已滿、已滿 81% 到到 95% 還是已滿還是已滿 96% 到到 100%。 673、SQL Server文件組織文件組織n數(shù)據(jù)文件的起始結(jié)構(gòu)數(shù)據(jù)文件的起

29、始結(jié)構(gòu)nGAM頁(yè)：頁(yè)：全局分配映射表全局分配映射表 (GAM) 頁(yè)記錄已分配的區(qū)。每頁(yè)記錄已分配的區(qū)。每個(gè)個(gè) GAM 包含包含 64,000 個(gè)區(qū)，相當(dāng)于近個(gè)區(qū)，相當(dāng)于近 4 GB 的數(shù)據(jù)。的數(shù)據(jù)。GAM 用一個(gè)位來(lái)表示所涵蓋區(qū)間內(nèi)的每個(gè)區(qū)的狀態(tài)。如用一個(gè)位來(lái)表示所涵蓋區(qū)間內(nèi)的每個(gè)區(qū)的狀態(tài)。如果位為果位為 1，則區(qū)可用；如果位為，則區(qū)可用；如果位為 0，則區(qū)已分配。，則區(qū)已分配。683、SQL Server文件組織文件組織n數(shù)據(jù)文件的起始結(jié)構(gòu)數(shù)據(jù)文件的起始結(jié)構(gòu)nSGAM 頁(yè)：頁(yè)：共享全局分配映射表共享全局分配映射表 (SGAM)頁(yè)記錄當(dāng)前用頁(yè)記錄當(dāng)前用作混合區(qū)且至少有一個(gè)未使用的頁(yè)的區(qū)。每個(gè)作

30、混合區(qū)且至少有一個(gè)未使用的頁(yè)的區(qū)。每個(gè) SGAM 包包含含 64,000 個(gè)區(qū)，相當(dāng)于近個(gè)區(qū)，相當(dāng)于近 4 GB 的數(shù)據(jù)。的數(shù)據(jù)。SGAM 用一個(gè)用一個(gè)位來(lái)表示所涵蓋區(qū)間內(nèi)的每個(gè)區(qū)的狀態(tài)。如果位為位來(lái)表示所涵蓋區(qū)間內(nèi)的每個(gè)區(qū)的狀態(tài)。如果位為 1，則，則區(qū)正用作混合區(qū)且有可用頁(yè)。如果位為區(qū)正用作混合區(qū)且有可用頁(yè)。如果位為 0，則區(qū)未用作混，則區(qū)未用作混合區(qū)，或者雖然用作混合區(qū)但其所有頁(yè)均在使用中合區(qū)，或者雖然用作混合區(qū)但其所有頁(yè)均在使用中。693、SQL Server文件組織文件組織n數(shù)據(jù)文件的起始結(jié)構(gòu)數(shù)據(jù)文件的起始結(jié)構(gòu)1.1. 若要分配統(tǒng)一區(qū)，將在若要分配統(tǒng)一區(qū)，將在 GAM GAM 中搜索是

31、中搜索是 1 1 的位，然后將它設(shè)成的位，然后將它設(shè)成 0 0。2.2. 若要查找有可用頁(yè)的混合區(qū)，將在若要查找有可用頁(yè)的混合區(qū)，將在 SGAM SGAM 中搜索是中搜索是 1 1 的位。的位。3.3. 若要分配混合區(qū)，將在若要分配混合區(qū)，將在 GAM GAM 中搜索是中搜索是 1 1 的位，并將它設(shè)置為的位，并將它設(shè)置為 0 0，然后將，然后將 SGAM SGAM 中相應(yīng)的位也設(shè)置為中相應(yīng)的位也設(shè)置為 1 1。4.4. 若要釋放擴(kuò)展盤區(qū)，若要釋放擴(kuò)展盤區(qū)，SQL Server SQL Server 應(yīng)確保應(yīng)確保 GAM GAM 位設(shè)置為位設(shè)置為 1 1 而而且且 SGAM SGAM 位設(shè)置為

32、位設(shè)置為 0 0。703、SQL Server文件組織文件組織n表（表（Table）的組織）的組織索引分配映射表 (IAM) 頁(yè)記錄了分配給對(duì)象的區(qū)。713、SQL Server文件組織文件組織n表（表（Table）的組織）的組織nIAM 頁(yè)根據(jù)需要分配給每個(gè)對(duì)象，在文件中的位置也是隨機(jī)的。系統(tǒng)頁(yè)根據(jù)需要分配給每個(gè)對(duì)象，在文件中的位置也是隨機(jī)的。系統(tǒng)視圖視圖(sys.system_internals_allocation_units) 指向?qū)ο蟮牡谝粋€(gè)指向?qū)ο蟮牡谝粋€(gè) IAM 頁(yè)。該分配單元的所有頁(yè)。該分配單元的所有 IAM 頁(yè)都鏈接到一個(gè)鏈中。頁(yè)都鏈接到一個(gè)鏈中。 723、SQL Serve

33、r文件組織文件組織n表（表（Table）的組織）的組織nIAM 頁(yè)有一個(gè)標(biāo)頭，指明頁(yè)有一個(gè)標(biāo)頭，指明 IAM 頁(yè)所映射的區(qū)范圍的起始區(qū)。頁(yè)所映射的區(qū)范圍的起始區(qū)。IAM 頁(yè)頁(yè)中還有一個(gè)大位圖，其中每個(gè)位代表一個(gè)區(qū)。位圖中的第一個(gè)位代表中還有一個(gè)大位圖，其中每個(gè)位代表一個(gè)區(qū)。位圖中的第一個(gè)位代表范圍內(nèi)的第一個(gè)區(qū)，第二個(gè)位代表第二個(gè)區(qū)，依此類推。如果某個(gè)位范圍內(nèi)的第一個(gè)區(qū)，第二個(gè)位代表第二個(gè)區(qū)，依此類推。如果某個(gè)位是是 0，它所代表的區(qū)將不會(huì)分配給擁有該，它所代表的區(qū)將不會(huì)分配給擁有該 IAM 頁(yè)的分配單元。如果頁(yè)的分配單元。如果這個(gè)位是這個(gè)位是 1，它所代表的區(qū)將被分配給擁有該，它所代表的區(qū)將被

34、分配給擁有該 IAM 頁(yè)的分配單元。頁(yè)的分配單元。n當(dāng)當(dāng) 需要插入新行而當(dāng)前頁(yè)沒(méi)有可用空間時(shí)，需要插入新行而當(dāng)前頁(yè)沒(méi)有可用空間時(shí)，SQL Server 使用使用 IAM 頁(yè)查找分配給對(duì)象的區(qū)。對(duì)于每個(gè)區(qū)，頁(yè)查找分配給對(duì)象的區(qū)。對(duì)于每個(gè)區(qū)，SQL Server 搜索搜索 PFS 頁(yè)以頁(yè)以查看是否有一頁(yè)具有足夠的空間容納這一行。查看是否有一頁(yè)具有足夠的空間容納這一行。nIAM 和和 PFS 頁(yè)通常位于內(nèi)存中的頁(yè)通常位于內(nèi)存中的 SQL Server 緩沖池中緩沖池中73七、七、Oracle的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)nOracle數(shù)據(jù)庫(kù)空間的分配單位有數(shù)據(jù)塊（數(shù)據(jù)庫(kù)空間的分配單位有數(shù)據(jù)塊（Data

35、 Block），數(shù)），數(shù)據(jù)擴(kuò)展（據(jù)擴(kuò)展（Extent），和段（），和段（Segment）。）。 n參閱參閱Oracle Concepts741、塊（、塊（Block）n數(shù)據(jù)塊（數(shù)據(jù)塊（Data Blocks，也稱為頁(yè)）是，也稱為頁(yè)）是Oracle存儲(chǔ)數(shù)據(jù)的最小單位。數(shù)存儲(chǔ)數(shù)據(jù)的最小單位。數(shù)據(jù)庫(kù)中標(biāo)準(zhǔn)的數(shù)據(jù)塊（據(jù)庫(kù)中標(biāo)準(zhǔn)的數(shù)據(jù)塊（data block）容量是由初始化參數(shù)）容量是由初始化參數(shù) DB_BLOCK_SIZE 指定的，常見(jiàn)大?。褐付ǖ?，常見(jiàn)大小：2KB、4KB、8KB、16KB。如塊地址，段類型等數(shù)據(jù)塊的行目錄區(qū)（row directory）空間被使用后，即使數(shù)據(jù)行被刪除，行目錄區(qū)空間也

36、不會(huì)被回收。 如果數(shù)據(jù)塊屬于表或集群的數(shù)據(jù)段（data segment），或?qū)儆谒饕乃饕危╥ndex segment），其可用空間區(qū)中還可能會(huì)存儲(chǔ)事務(wù)條目。當(dāng)數(shù)據(jù)塊中的數(shù)據(jù)行正在由 INSERT，UPDATE，DELETE，及 SELECT.FOR UPDATE 語(yǔ)句訪問(wèn)，此數(shù)據(jù)塊中就需要保存事務(wù)條目。 751、擴(kuò)展區(qū)（、擴(kuò)展區(qū)（Extent）n擴(kuò)展區(qū)（擴(kuò)展區(qū)（extent）是由一組連續(xù)的數(shù)據(jù)塊構(gòu)成的數(shù)據(jù)庫(kù)邏輯）是由一組連續(xù)的數(shù)據(jù)塊構(gòu)成的數(shù)據(jù)庫(kù)邏輯存儲(chǔ)分配單位。存儲(chǔ)分配單位。n當(dāng)用戶創(chuàng)建數(shù)據(jù)表時(shí)，當(dāng)用戶創(chuàng)建數(shù)據(jù)表時(shí)，Oracle為此表的數(shù)據(jù)段（為此表的數(shù)據(jù)段（data segment）分配

37、一個(gè)包含若干數(shù)據(jù)塊（）分配一個(gè)包含若干數(shù)據(jù)塊（data block）的初始）的初始擴(kuò)展區(qū)（擴(kuò)展區(qū)（initial extent）。）。 761、段（、段（Segment）n段（段（segment）由一組擴(kuò)展區(qū)（）由一組擴(kuò)展區(qū)（extent）構(gòu)成。每個(gè)段的段）構(gòu)成。每個(gè)段的段頭（頭（header block）中包含一個(gè)記錄此段所有擴(kuò)展區(qū)）中包含一個(gè)記錄此段所有擴(kuò)展區(qū)（extent）的目錄。）的目錄。 n用戶使用用戶使用 CREATE 語(yǔ)句創(chuàng)建表或簇表時(shí)，語(yǔ)句創(chuàng)建表或簇表時(shí)，Oracle創(chuàng)建相應(yīng)創(chuàng)建相應(yīng)的數(shù)據(jù)段（的數(shù)據(jù)段（data segment）。）。 772、表空間（、表空間（tablespa

38、ce）nOracle中的數(shù)據(jù)邏輯上存儲(chǔ)于表空間（中的數(shù)據(jù)邏輯上存儲(chǔ)于表空間（tablespace）中，而物理上則存）中，而物理上則存儲(chǔ)于屬于表空間的數(shù)據(jù)文件（儲(chǔ)于屬于表空間的數(shù)據(jù)文件（datafile）中。）中。nOracle數(shù)據(jù)庫(kù)中每個(gè)表空間都是由一個(gè)或多個(gè)物理數(shù)據(jù)文件構(gòu)成的。一數(shù)據(jù)庫(kù)中每個(gè)表空間都是由一個(gè)或多個(gè)物理數(shù)據(jù)文件構(gòu)成的。一個(gè)數(shù)據(jù)文件只能由一個(gè)數(shù)據(jù)庫(kù)的一個(gè)表空間使用。個(gè)數(shù)據(jù)文件只能由一個(gè)數(shù)據(jù)庫(kù)的一個(gè)表空間使用。 782、表空間（、表空間（tablespace）n數(shù)據(jù)庫(kù)是由一個(gè)或多個(gè)被稱為表空間（數(shù)據(jù)庫(kù)是由一個(gè)或多個(gè)被稱為表空間（tablespace）的邏輯存儲(chǔ)單位構(gòu)）的邏輯存儲(chǔ)單位

39、構(gòu)成。表空間內(nèi)的邏輯存儲(chǔ)單位為段（成。表空間內(nèi)的邏輯存儲(chǔ)單位為段（segment），段又可以繼續(xù)劃分為），段又可以繼續(xù)劃分為數(shù)據(jù)擴(kuò)展（數(shù)據(jù)擴(kuò)展（extent）。而數(shù)據(jù)擴(kuò)展是由一組連續(xù)的數(shù)據(jù)塊（）。而數(shù)據(jù)擴(kuò)展是由一組連續(xù)的數(shù)據(jù)塊（data block）構(gòu)成。構(gòu)成。 793、表空間管理、表空間管理n數(shù)據(jù)字典管理（數(shù)據(jù)字典管理（dictionary managed）n用兩個(gè)數(shù)據(jù)字典來(lái)保存表空間的區(qū)間使用信息，用兩個(gè)數(shù)據(jù)字典來(lái)保存表空間的區(qū)間使用信息，UET$（已使用的區(qū)間）和（已使用的區(qū)間）和FET$（空閑空間）。（空閑空間）。nOracle 8i以前以前n本地管理（本地管理（locally man

40、aged）n將存儲(chǔ)信息保存在表空間頭部的位圖。將存儲(chǔ)信息保存在表空間頭部的位圖。Oracle在為新的數(shù)在為新的數(shù)據(jù)擴(kuò)展（據(jù)擴(kuò)展（extent）尋找可用空間時(shí)，首先選擇一個(gè)屬于此）尋找可用空間時(shí)，首先選擇一個(gè)屬于此表空間的數(shù)據(jù)文件（表空間的數(shù)據(jù)文件（datafile），再搜索此數(shù)據(jù)文件的位），再搜索此數(shù)據(jù)文件的位圖（圖（bitmap）查找連續(xù)的數(shù)據(jù)塊（）查找連續(xù)的數(shù)據(jù)塊（free block）。如果此）。如果此數(shù)據(jù)塊中沒(méi)有足夠的連續(xù)可用空間，數(shù)據(jù)塊中沒(méi)有足夠的連續(xù)可用空間，Oracle將查詢其他數(shù)將查詢其他數(shù)據(jù)文件。據(jù)文件。 80八、緩沖區(qū)管理器八、緩沖區(qū)管理器81八、緩沖區(qū)管理器八、緩沖區(qū)管理

41、器nBuffer PoolnFrame（Bucket）nBlockn is maintained.821、frame的參數(shù)的參數(shù)nDirtynFrame中的塊是否已經(jīng)被修改中的塊是否已經(jīng)被修改nPin-countnFrame的塊的已經(jīng)被請(qǐng)求并且還未釋放的計(jì)數(shù)，即當(dāng)前的的塊的已經(jīng)被請(qǐng)求并且還未釋放的計(jì)數(shù)，即當(dāng)前的用戶數(shù)用戶數(shù)n被釘住的塊（被釘住的塊（Pinned Blocks）不允許寫回磁盤）不允許寫回磁盤832、當(dāng)請(qǐng)求塊時(shí)、當(dāng)請(qǐng)求塊時(shí)nIf requested block is not in pool:nChoose a frame for replacementnIf frame is di

42、rty (some blocks are modified and havent been written to disk), write it to disknRead requested block into chosen framenPin (increment the pin-count of the frame) the block and return its address. If requests can be predicted (e.g., sequential scans) blocks can be pre-fetched several blocks at a tim

43、e!842、當(dāng)釋放塊時(shí)、當(dāng)釋放塊時(shí)nRequestor must unpin the frame containing the blocknRequestor must indicate whether block has been modified: ndirty bit is used for this.853、緩沖區(qū)替換策略、緩沖區(qū)替換策略nFrame is chosen for replacement by a replacement policy:nLeast-recently-used (LRU), Clock, FIFO, MRU (Most-recently-used) etc

44、.nOnly frames whose pin-count=0 are candidatesnPolicy can have big impact on # of I/Os; depends on the access pattern.863、緩沖區(qū)替換策略、緩沖區(qū)替換策略nLRU (Oracle, Sybase, Informix)n當(dāng)當(dāng)Pin-count為為0時(shí)，時(shí)，frame放入替換隊(duì)列放入替換隊(duì)列n選擇隊(duì)列頭的選擇隊(duì)列頭的frame替換替換nClock (MS SQL Server)nN個(gè)個(gè)frame組成環(huán)形，組成環(huán)形，current指針指向當(dāng)前指針指向當(dāng)前frame；每個(gè)；每個(gè)fra

45、me有一有一個(gè)個(gè)referenced位，它在位，它在pin-count=0時(shí)啟動(dòng)；時(shí)啟動(dòng)；n從從current開(kāi)始檢查，若開(kāi)始檢查，若pin-count0，current增加增加1；若；若referenced已啟動(dòng)，則關(guān)閉它并增加已啟動(dòng)，則關(guān)閉它并增加current（保證最近的不被替（保證最近的不被替換）；若換）；若pin-count=0并且并且referenced關(guān)閉，則替換關(guān)閉，則替換874、為何不使用、為何不使用OS緩沖區(qū)管理？緩沖區(qū)管理？nDBMS經(jīng)常能預(yù)測(cè)訪問(wèn)模式經(jīng)常能預(yù)測(cè)訪問(wèn)模式(Access Pattern)n可以使用更專門的緩沖區(qū)替換策略可以使用更專門的緩沖區(qū)替換策略n有利于有

46、利于pre-fetch策略的有效使用策略的有效使用nDBMS需要強(qiáng)制寫回磁盤能力（如需要強(qiáng)制寫回磁盤能力（如WAL），），OS的緩沖寫回的緩沖寫回一般通過(guò)記錄寫請(qǐng)求來(lái)實(shí)現(xiàn)（來(lái)自不同應(yīng)用），實(shí)際的磁盤一般通過(guò)記錄寫請(qǐng)求來(lái)實(shí)現(xiàn)（來(lái)自不同應(yīng)用），實(shí)際的磁盤修改推遲，因此不能保證寫順序修改推遲，因此不能保證寫順序885、錯(cuò)誤的記錄操作實(shí)現(xiàn)例子、錯(cuò)誤的記錄操作實(shí)現(xiàn)例子n例如，插入記錄例如，插入記錄 int insert_record(DBFILE*, DBRECORD)nnfopen()nfseek()nfwrite()nn沒(méi)有沒(méi)有DBMS自己的緩沖區(qū)管理和存儲(chǔ)管理自己的緩沖區(qū)管理和存儲(chǔ)管理n直接基于文

47、件系統(tǒng)，使用了直接基于文件系統(tǒng)，使用了FS的緩沖管理的緩沖管理n不能保證不能保證WALn不利于查詢優(yōu)化不利于查詢優(yōu)化n不適應(yīng)應(yīng)用需求不適應(yīng)應(yīng)用需求896、Block vs. Disk FilenDisk File文件存儲(chǔ)在磁盤上的物理形式是文件存儲(chǔ)在磁盤上的物理形式是bits/bytes，block是由是由OS或或DBMS軟件對(duì)文件所做的抽象，這一抽象是通過(guò)控制數(shù)據(jù)軟件對(duì)文件所做的抽象，這一抽象是通過(guò)控制數(shù)據(jù)在文件中的起止在文件中的起止offset來(lái)實(shí)現(xiàn)的來(lái)實(shí)現(xiàn)的0101001001001001011110100111010100101101111Block #1Block #2906、Buf

48、fer vs. Disk FileBufferset of framesFileset of pages緩沖區(qū)管理器存儲(chǔ)管理器page/blockframe通常，frame大小page大小CPUrefers to917、Buffer Sizen設(shè)計(jì)設(shè)計(jì)DBMS時(shí)應(yīng)是一個(gè)可變的輸入?yún)?shù)時(shí)應(yīng)是一個(gè)可變的輸入?yún)?shù)n通常通常DBMS允許用戶自行配置允許用戶自行配置928、Buffer的存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)nBuffer是一個(gè)是一個(gè)frame的列表，每個(gè)的列表，每個(gè)frame用于表示和存放一個(gè)用于表示和存放一個(gè)磁盤塊磁盤塊#define FRAMESIZE 4096struct bFrame Char f

49、ield FRAMESIZE ; #define BUFSIZE 1024 / frame數(shù)目bFrame bufBUFSIZE; /也可以是用戶配置的值Buffer的存儲(chǔ)結(jié)構(gòu)定義示例939、Page/block的一般存儲(chǔ)格式的一般存儲(chǔ)格式n對(duì)于定長(zhǎng)記錄對(duì)于定長(zhǎng)記錄n記錄地址記錄地址rid通常使用通常使用表示表示槽槽 1 1槽槽 N N槽槽 2 2N N1 0 1 0 1 M1 0 1 0 1 M槽槽 1 1槽槽 M M槽槽 2 2M M 3 2 1 3 2 1記錄數(shù)槽數(shù)空閑空間空閑空間塊頭塊頭949、Page/block的一般存儲(chǔ)格式的一般存儲(chǔ)格式nRecord的存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)struc

50、t Record int page_id; int slot_num; 9510、Buffer中的中的Frame存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)FrameMAX:BUFSIZE*FRAMESIZE9610、Buffer中的中的Frame存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)struct Frameint frame_id;int offset; ;9711、Buffer中中Frame的查找的查找n讀磁盤塊時(shí)：根據(jù)讀磁盤塊時(shí)：根據(jù)page_id確定在確定在Buffer中是否已經(jīng)存在中是否已經(jīng)存在framen寫磁盤塊時(shí)：要根據(jù)寫磁盤塊時(shí)：要根據(jù)frame_id快速找到文件中對(duì)應(yīng)的快速找到文件中對(duì)應(yīng)的page_id9811、Buffer中中Frame的查找的查找n首先，要維護(hù)首先，要維護(hù)Buffer中所有中所有frame的維護(hù)信息（的維護(hù)信息（Buffer Control Blocks），如），如struct BCB BCB(); int page_id; int frame_id; int count; int time; int dirty; BCB * next; 9911、Buffer中中Frame的查找的查找n建立建立frame-page之間的索引之間的索引n若用若用Hash