科大-高級(jí)數(shù)據(jù)庫(kù)技術(shù)05

1、Advanced Database Technologies金培權(quán)（金培權(quán)（）2Advanced Database Technologies金培權(quán)（金培權(quán)（）n數(shù)據(jù)項(xiàng)的表示（數(shù)據(jù)項(xiàng)的表示（Data Items）n記錄的表示（記錄的表示（Records）n記錄在塊中的組織（記錄在塊中的組織（Block）n記錄的修改記錄的修改n塊在文件中的組織塊在文件中的組織n緩沖區(qū)管理緩沖區(qū)管理3Advanced Database Technologies金培權(quán)（金培權(quán)（）數(shù)據(jù)項(xiàng)記錄塊文件屬性值的物理組織元組的物理組織記錄的物理存放文件由磁盤塊構(gòu)成4Advanced Database Technologies金

2、培權(quán)（金培權(quán)（）n數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)字節(jié)序列字節(jié)序列表示關(guān)系數(shù)據(jù)庫(kù)中元組的屬性值表示關(guān)系數(shù)據(jù)庫(kù)中元組的屬性值5Advanced Database Technologies金培權(quán)（金培權(quán)（）n表示什么？表示什么？姓名姓名年齡年齡出生日期出生日期照片照片n用什么表示？用什么表示？Bytes6Advanced Database Technologies金培權(quán)（金培權(quán)（）nInteger (short)2 bytes例如，例如，35 表示為表示為nReal，F(xiàn)loat4 bytes （32 bits）N bits表示小數(shù)，表示小數(shù)，M bits表示指數(shù)表示指數(shù) 00000000001000117Advanc

3、ed Database Technologies金培權(quán)（金培權(quán)（）nChar(n) 或或 Character(n) 定長(zhǎng)字符串定長(zhǎng)字符串小于小于n時(shí)使用特殊填充符時(shí)使用特殊填充符例如，若屬性類型為例如，若屬性類型為Char(5)，則屬性值，則屬性值cat 表示為表示為 nVarchar(n) 變長(zhǎng)字符串變長(zhǎng)字符串NULL終止符，例終止符，例 Varchar(5)帶長(zhǎng)度帶長(zhǎng)度 定長(zhǎng)表示，定長(zhǎng)表示，n+1 bytesVarchar(4):cta ctacta3cta 8Advanced Database Technologies金培權(quán)（金培權(quán)（）nBooleanTRUEFALSEn枚舉類型枚舉類型

4、RED,GREEN,YELLOW整數(shù)表示整數(shù)表示RED 1，GREEN 2，YELLOW 3若用兩個(gè)字節(jié)的短整型來表示，則可以表示若用兩個(gè)字節(jié)的短整型來表示，則可以表示 216 個(gè)個(gè)不同值不同值1111 11110000 00009Advanced Database Technologies金培權(quán)（金培權(quán)（）nDate10字符字符(SQL92)：YYYY-MM-DD字符串表示字符串表示8字符：字符：YYYYMMDD7字符：字符：YYYYDDD, NOT YYMMDD！Integer，自，自1900-01-01以來的天數(shù)以來的天數(shù)nTime8字符字符(SQL92)：HH:NN:SS 整數(shù)秒整數(shù)秒

5、Varchar(n)：HH:NN:SS.FF帶小數(shù)秒帶小數(shù)秒Integer，自，自00:00:00以來的秒數(shù)以來的秒數(shù)10Advanced Database Technologies金培權(quán)（金培權(quán)（）nBit帶長(zhǎng)度的二進(jìn)制位串帶長(zhǎng)度的二進(jìn)制位串按字節(jié)表示，例如按字節(jié)表示，例如 010111110011LengthBits010111110011000011Advanced Database Technologies金培權(quán)（金培權(quán)（）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)帶長(zhǎng)度帶長(zhǎng)度 （常用常用!）Null Terminated12Advanced Database Technologie

6、s金培權(quán)（金培權(quán)（）類類 型型 表表 示示 方方 法法整數(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è)枚舉類型的值13Advanced Database Technologies金培權(quán)（金培權(quán)（）數(shù)據(jù)項(xiàng)記錄塊文件We are here！14Advanced Database Technologies金培權(quán)（金培權(quán)（）n記錄記錄數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng) 字段，字段，F(xiàn)ields 的集合的集合

7、E.g.: Employee record:name field,salary field,date-of-hire field, .15Advanced Database Technologies金培權(quán)（金培權(quán)（）n固定格式固定格式 vs. 可變格式可變格式Fixed Format vs. Variable Formatn定長(zhǎng)定長(zhǎng) vs. 變長(zhǎng)變長(zhǎng)Fixed Length vs. Variable Length16Advanced Database Technologies金培權(quán)（金培權(quán)（）n所有記錄具有相同的邏輯結(jié)構(gòu)（模式）所有記錄具有相同的邏輯結(jié)構(gòu)（模式）n記錄的模式（記錄的模式（Sch

8、ema）# fieldsName of each fieldType of each fieldOrder in recordOffset of each field in the record17Advanced Database Technologies金培權(quán)（金培權(quán)（）Employee record(1) E#, 2 byte integer(2) Ename, 10 char.Schema(3) Dept, 2 byte code55s m i t h0283j o n e s01Records18Advanced Database Technologies金培權(quán)（金培權(quán)（）n構(gòu)造構(gòu)造

9、n不考慮尋址特點(diǎn)不考慮尋址特點(diǎn)19Advanced Database Technologies金培權(quán)（金培權(quán)（）n考慮尋址特點(diǎn)考慮尋址特點(diǎn)假設(shè)記錄和字段的開始地址必須是假設(shè)記錄和字段的開始地址必須是4的倍數(shù)的倍數(shù)20Advanced Database Technologies金培權(quán)（金培權(quán)（）n在記錄首部（在記錄首部（Head）的描述記錄的信息）的描述記錄的信息記錄類型（模式信息）記錄類型（模式信息）記錄長(zhǎng)度記錄長(zhǎng)度時(shí)間戳?xí)r間戳其它信息其它信息21Advanced Database Technologies金培權(quán)（金培權(quán)（）n每個(gè)記錄的格式不同每個(gè)記錄的格式不同n記錄的格式存儲(chǔ)于記錄中記錄的格

10、式存儲(chǔ)于記錄中22Advanced Database Technologies金培權(quán)（金培權(quán)（）4I524SDROF46 字段數(shù)字段數(shù)字段字段E標(biāo)識(shí)碼標(biāo)識(shí)碼Integer 類型類型字段字段 Ename標(biāo)識(shí)碼標(biāo)識(shí)碼String 類型類型長(zhǎng)度長(zhǎng)度Employee(E#, Ename)標(biāo)記字段(Tags)23Advanced Database Technologies金培權(quán)（金培權(quán)（）n好處好處?kù)`活的記錄格式，適合靈活的記錄格式，適合“松散松散”記錄記錄盡管一個(gè)記錄可能有大量字段，但某個(gè)記錄通常只盡管一個(gè)記錄可能有大量字段，但某個(gè)記錄通常只有有限的幾個(gè)字段有有限的幾個(gè)字段例如，病人的檢驗(yàn)結(jié)果例如，病

11、人的檢驗(yàn)結(jié)果適合處理重復(fù)字段適合處理重復(fù)字段適合記錄格式演變適合記錄格式演變n缺點(diǎn)缺點(diǎn)浪費(fèi)存儲(chǔ)空間浪費(fèi)存儲(chǔ)空間24Advanced Database Technologies金培權(quán)（金培權(quán)（）n首部指針法首部指針法定長(zhǎng)字段在前，變長(zhǎng)字段在后定長(zhǎng)字段在前，變長(zhǎng)字段在后 name、address變長(zhǎng)變長(zhǎng)25Advanced Database Technologies金培權(quán)（金培權(quán)（）n混合格式：定長(zhǎng)記錄變長(zhǎng)記錄混合格式：定長(zhǎng)記錄變長(zhǎng)記錄26Advanced Database Technologies金培權(quán)（金培權(quán)（）數(shù)據(jù)項(xiàng)記錄塊文件We are here！27Advanced Database T

12、echnologies金培權(quán)（金培權(quán)（）n假設(shè)假設(shè)塊的大小固定塊的大小固定記錄組織成單個(gè)文件記錄組織成單個(gè)文件assume fixedlength blocksassume a single file (for now)BlockA FileA Record28Advanced Database Technologies金培權(quán)（金培權(quán)（）n定長(zhǎng)記錄的兩種塊內(nèi)組織定長(zhǎng)記錄的兩種塊內(nèi)組織記錄地址記錄地址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ù)空閑空

13、間空閑空間塊頭塊頭29Advanced Database Technologies金培權(quán)（金培權(quán)（）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ū)30Advanced Database Technologies金培權(quán)（金培權(quán)（）n其他問題其他問題記錄在塊中的分隔記錄在塊中的分隔 (separating records)記錄跨塊記錄跨塊 vs.記錄不跨塊記錄不跨塊 (spanned vs. unspanned)不同類型的記錄聚簇不同類型的記錄聚簇 (

14、mixed record types clustering)按序組織按序組織 (sequencing)記錄的分裂記錄的分裂 (split records)記錄地址記錄地址 (record address)記錄的修改記錄的修改31Advanced Database Technologies金培權(quán)（金培權(quán)（）n定長(zhǎng)記錄：不需分隔定長(zhǎng)記錄：不需分隔n使用特殊標(biāo)記使用特殊標(biāo)記n通過塊內(nèi)偏移量通過塊內(nèi)偏移量32Advanced Database Technologies金培權(quán)（金培權(quán)（）nUnspanned: 記錄必須在一個(gè)塊中存儲(chǔ)記錄必須在一個(gè)塊中存儲(chǔ)block 1 block 2 .nSpanned

15、：記錄可跨塊存儲(chǔ)：記錄可跨塊存儲(chǔ)block 1 block 2 .R1R2R1R3R4R5R2R3(a)R3(b)R6R5R4R7(a)33Advanced Database Technologies金培權(quán)（金培權(quán)（）n跨塊跨塊Whats the rest?From where?34Advanced Database Technologies金培權(quán)（金培權(quán)（）n比較比較unspanned：實(shí)現(xiàn)簡(jiǎn)單，但空間浪費(fèi)：實(shí)現(xiàn)簡(jiǎn)單，但空間浪費(fèi)spanned：有效利用空間，實(shí)現(xiàn)更復(fù)雜：有效利用空間，實(shí)現(xiàn)更復(fù)雜nBut If record size block size，MUST be spanned35Ad

16、vanced Database Technologies金培權(quán)（金培權(quán)（）n一個(gè)塊中存儲(chǔ)不同類型的記錄一個(gè)塊中存儲(chǔ)不同類型的記錄（對(duì)于（對(duì)于RDB：多關(guān)系上的聚簇多關(guān)系上的聚簇）n好處好處聚簇聚簇 (clustering)經(jīng)常一起訪問的記錄存儲(chǔ)在同一塊或連續(xù)塊經(jīng)常一起訪問的記錄存儲(chǔ)在同一塊或連續(xù)塊中中A Dept Record A Employee Record A Employee RecordA Block36Advanced Database Technologies金培權(quán)（金培權(quán)（）學(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其他列其他列

17、學(xué)號(hào)學(xué)號(hào)S2S2s2其他列其他列課程號(hào)課程號(hào)C2C5c6學(xué)生表與課程學(xué)生表與課程表通過簇鍵表通過簇鍵“學(xué)號(hào)學(xué)號(hào)”聚簇聚簇Block37Advanced Database Technologies金培權(quán)（金培權(quán)（）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

18、,age) )SC(SC(s#s#, ,cnamecname,score,score) )38Advanced Database Technologies金培權(quán)（金培權(quán)（）n另一種聚簇另一種聚簇 (對(duì)于對(duì)于RDB：?jiǎn)侮P(guān)系上的聚簇單關(guān)系上的聚簇)將記錄按某個(gè)字段順序排列在塊中將記錄按某個(gè)字段順序排列在塊中n好處好處加快按排序字段查詢記錄時(shí)的效率加快按排序字段查詢記錄時(shí)的效率利于歸并聯(lián)接利于歸并聯(lián)接 （will be discussed later）39Advanced Database Technologies金培權(quán)（金培權(quán)（）化學(xué)系化學(xué)系化學(xué)系化學(xué)系化學(xué)系化學(xué)系化學(xué)系化學(xué)系物理系物理系物理系物

19、理系物理系物理系中文系中文系化學(xué)系化學(xué)系物理系物理系物理系物理系化學(xué)系化學(xué)系中文系中文系化學(xué)系化學(xué)系物理系物理系化學(xué)系化學(xué)系按按Dept順序組織的順序組織的Student記錄記錄無序組織的無序組織的Student記錄記錄假設(shè)一個(gè)磁盤塊假設(shè)一個(gè)磁盤塊2條定長(zhǎng)記錄條定長(zhǎng)記錄40Advanced Database Technologies金培權(quán)（金培權(quán)（）n物理連續(xù)物理連續(xù)n指針連接指針連接Next (R1)R1R1R2Next(R1)41Advanced Database Technologies金培權(quán)（金培權(quán)（）n適合于變長(zhǎng)記錄的混合格式表示適合于變長(zhǎng)記錄的混合格式表示定長(zhǎng)部分存儲(chǔ)于某個(gè)塊中定長(zhǎng)

20、部分存儲(chǔ)于某個(gè)塊中變長(zhǎng)部分存儲(chǔ)于另一個(gè)塊中變長(zhǎng)部分存儲(chǔ)于另一個(gè)塊中與與spanned存儲(chǔ)類似存儲(chǔ)類似42Advanced Database Technologies金培權(quán)（金培權(quán)（）n物理地址物理地址n邏輯地址（間接地址）邏輯地址（間接地址）43Advanced Database Technologies金培權(quán)（金培權(quán)（）n記錄的純物理地址記錄的純物理地址主機(jī)標(biāo)識(shí)主機(jī)標(biāo)識(shí) 磁盤或其他設(shè)備標(biāo)識(shí)磁盤或其他設(shè)備標(biāo)識(shí)柱面號(hào)柱面號(hào)磁頭號(hào)（盤面號(hào)）磁頭號(hào)（盤面號(hào)） 塊號(hào)塊號(hào) 塊內(nèi)的偏移量塊內(nèi)的偏移量塊地址44Advanced Database Technologies金培權(quán)（金培權(quán)（）n記錄的純邏輯地址記

21、錄的純邏輯地址物理地址物理地址邏輯地址邏輯地址映射表記錄地址純物理地址缺點(diǎn)訪問代價(jià)增加：映射表占存儲(chǔ)空間；需要地址轉(zhuǎn)換好處?kù)`活性：刪除或移動(dòng)記錄時(shí)只要改變映射表項(xiàng)45Advanced Database Technologies金培權(quán)（金培權(quán)（）記錄的純物理地址記錄的純邏輯地址tradeoff46Advanced Database Technologies金培權(quán)（金培權(quán)（）n借助文件系統(tǒng)的邏輯塊地址借助文件系統(tǒng)的邏輯塊地址文件號(hào)邏輯塊地址塊內(nèi)偏移文件號(hào)邏輯塊地址塊內(nèi)偏移文件系統(tǒng)映射File IDBlock(logical)Block(physical) + offset記錄地址47Advance

22、d Database Technologies金培權(quán)（金培權(quán)（）n插入插入n刪除刪除48Advanced Database Technologies金培權(quán)（金培權(quán)（）n記錄無序記錄無序插入到任意塊的空閑空間中插入到任意塊的空閑空間中或申請(qǐng)一個(gè)新塊（當(dāng)所有塊都已滿時(shí)）或申請(qǐng)一個(gè)新塊（當(dāng)所有塊都已滿時(shí)）記錄變長(zhǎng)時(shí)，可使用偏移量表記錄變長(zhǎng)時(shí)，可使用偏移量表49Advanced Database Technologies金培權(quán)（金培權(quán)（）n記錄有序記錄有序找到記錄應(yīng)該放置的塊找到記錄應(yīng)該放置的塊如果有空間，放入并調(diào)節(jié)記錄順序即可，否如果有空間，放入并調(diào)節(jié)記錄順序即可，否則有兩種方法：則有兩種方法：在在

23、“鄰近塊鄰近塊”中找空間中找空間 創(chuàng)建溢出塊創(chuàng)建溢出塊 50Advanced Database Technologies金培權(quán)（金培權(quán)（）n立即回收空間立即回收空間例如，加到可用空間列表中例如，加到可用空間列表中n刪除記錄時(shí)處理溢出塊刪除記錄時(shí)處理溢出塊若刪除的記錄位于溢出塊鏈上，則刪除記錄若刪除的記錄位于溢出塊鏈上，則刪除記錄后可對(duì)整個(gè)鏈進(jìn)行重新組織以去除溢出塊后可對(duì)整個(gè)鏈進(jìn)行重新組織以去除溢出塊51Advanced Database Technologies金培權(quán)（金培權(quán)（）n使用刪除標(biāo)記使用刪除標(biāo)記若使用偏移表，則可以修改偏移表項(xiàng)指針，若使用偏移表，則可以修改偏移表項(xiàng)指針，將其置空將其置

24、空若使用邏輯物理地址映射表，則可以將物若使用邏輯物理地址映射表，則可以將物理地址置空理地址置空可以在記錄首部預(yù)留一開始位：可以在記錄首部預(yù)留一開始位：0未刪除，未刪除，1已刪除已刪除1記錄10記錄252Advanced Database Technologies金培權(quán)（金培權(quán)（）數(shù)據(jù)項(xiàng)記錄塊文件We are here！53Advanced Database Technologies金培權(quán)（金培權(quán)（）n堆文件（堆文件（Heap File）最基本、最簡(jiǎn)單的文件結(jié)構(gòu)最基本、最簡(jiǎn)單的文件結(jié)構(gòu)記錄不以任何順序排序記錄不以任何順序排序記錄可能存放在物理不鄰接的塊上記錄可能存放在物理不鄰接的塊上n插入容易，

25、但查找和刪除代價(jià)高插入容易，但查找和刪除代價(jià)高54Advanced Database Technologies金培權(quán)（金培權(quán)（）首塊數(shù)據(jù)塊數(shù)據(jù)塊數(shù)據(jù)塊數(shù)據(jù)塊數(shù)據(jù)塊數(shù)據(jù)塊含空閑空間的塊鏈表滿塊鏈表55Advanced Database Technologies金培權(quán)（金培權(quán)（）數(shù)據(jù)塊1數(shù)據(jù)塊2數(shù)據(jù)塊N首塊56Advanced Database Technologies金培權(quán)（金培權(quán)（）數(shù)據(jù)項(xiàng)記錄塊文件屬性值的物理組織元組的物理組織記錄的物理存放文件由磁盤塊構(gòu)成57Advanced Database Technologies金培權(quán)（金培權(quán)（）nSQL Server的數(shù)據(jù)庫(kù)文件是多個(gè)對(duì)象的的數(shù)據(jù)庫(kù)文

26、件是多個(gè)對(duì)象的集合，包括多個(gè)表、索引等集合，包括多個(gè)表、索引等58Advanced Database Technologies金培權(quán)（金培權(quán)（）n在在SQL Server中，數(shù)據(jù)存儲(chǔ)的基本單位中，數(shù)據(jù)存儲(chǔ)的基本單位是頁(yè)。在是頁(yè)。在 SQL Server 2000 中，頁(yè)的大中，頁(yè)的大小是小是 8 KB。9696字節(jié)字節(jié)單個(gè)數(shù)據(jù)行單個(gè)數(shù)據(jù)行最大最大80608060字節(jié)字節(jié)頁(yè)地址：數(shù)據(jù)行地址：59Advanced Database Technologies金培權(quán)（金培權(quán)（）n擴(kuò)展盤區(qū)是一種基本單元，可將其中的空間分配擴(kuò)展盤區(qū)是一種基本單元，可將其中的空間分配給表和索引。一個(gè)擴(kuò)展盤區(qū)是給表和索引。一

27、個(gè)擴(kuò)展盤區(qū)是 8 個(gè)鄰接的頁(yè)（個(gè)鄰接的頁(yè)（或或 64 KB）。）。n為了使空間分配更有效，為了使空間分配更有效，SQL Server 2000 對(duì)對(duì)只含少量數(shù)據(jù)的表不分配完整的擴(kuò)展盤區(qū)。只含少量數(shù)據(jù)的表不分配完整的擴(kuò)展盤區(qū)。SQL Server 2000 有兩種類型的擴(kuò)展盤區(qū)：有兩種類型的擴(kuò)展盤區(qū)： 統(tǒng)一擴(kuò)展盤區(qū)：由單個(gè)對(duì)象所有，擴(kuò)展盤區(qū)中的所有統(tǒng)一擴(kuò)展盤區(qū)：由單個(gè)對(duì)象所有，擴(kuò)展盤區(qū)中的所有八頁(yè)只能由擁有該盤區(qū)的對(duì)象使用。八頁(yè)只能由擁有該盤區(qū)的對(duì)象使用?；旌蠑U(kuò)展盤區(qū)：最多可由混合擴(kuò)展盤區(qū)：最多可由 8 個(gè)對(duì)象共享。個(gè)對(duì)象共享。 n通常從混合擴(kuò)展盤區(qū)中向新表或新索引分配頁(yè)。通常從混合擴(kuò)展盤區(qū)中向

28、新表或新索引分配頁(yè)。當(dāng)表或索引增長(zhǎng)到當(dāng)表或索引增長(zhǎng)到 8 頁(yè)時(shí)，就變成統(tǒng)一擴(kuò)展盤頁(yè)時(shí)，就變成統(tǒng)一擴(kuò)展盤區(qū)。區(qū)。60Advanced Database Technologies金培權(quán)（金培權(quán)（）n混合擴(kuò)展盤區(qū)和統(tǒng)一擴(kuò)展盤區(qū)混合擴(kuò)展盤區(qū)和統(tǒng)一擴(kuò)展盤區(qū)61Advanced Database Technologies金培權(quán)（金培權(quán)（）nSQL Server 2000 數(shù)據(jù)庫(kù)有三種類型的文件：數(shù)據(jù)庫(kù)有三種類型的文件： 主要數(shù)據(jù)文件主要數(shù)據(jù)文件 主要數(shù)據(jù)文件是數(shù)據(jù)庫(kù)的起點(diǎn)，指向數(shù)據(jù)庫(kù)中文件的其它部主要數(shù)據(jù)文件是數(shù)據(jù)庫(kù)的起點(diǎn)，指向數(shù)據(jù)庫(kù)中文件的其它部分。每個(gè)數(shù)據(jù)庫(kù)都有一個(gè)主要數(shù)據(jù)文件。主要數(shù)據(jù)文件的推分。每

29、個(gè)數(shù)據(jù)庫(kù)都有一個(gè)主要數(shù)據(jù)文件。主要數(shù)據(jù)文件的推薦文件擴(kuò)展名是薦文件擴(kuò)展名是 .mdf。次要數(shù)據(jù)文件次要數(shù)據(jù)文件 次要數(shù)據(jù)文件包含除主要數(shù)據(jù)文件外的所有數(shù)據(jù)文件。有些次要數(shù)據(jù)文件包含除主要數(shù)據(jù)文件外的所有數(shù)據(jù)文件。有些數(shù)據(jù)庫(kù)可能沒有次要數(shù)據(jù)文件，而有些數(shù)據(jù)庫(kù)則有多個(gè)次要數(shù)據(jù)庫(kù)可能沒有次要數(shù)據(jù)文件，而有些數(shù)據(jù)庫(kù)則有多個(gè)次要數(shù)據(jù)文件。次要數(shù)據(jù)文件的推薦文件擴(kuò)展名是數(shù)據(jù)文件。次要數(shù)據(jù)文件的推薦文件擴(kuò)展名是 .ndf。日志文件日志文件 日志文件包含恢復(fù)數(shù)據(jù)庫(kù)所需的所有日志信息。每個(gè)數(shù)據(jù)庫(kù)日志文件包含恢復(fù)數(shù)據(jù)庫(kù)所需的所有日志信息。每個(gè)數(shù)據(jù)庫(kù)必須至少有一個(gè)日志文件，但可以不止一個(gè)。日志文件的推必須至少有一個(gè)

30、日志文件，但可以不止一個(gè)。日志文件的推薦文件擴(kuò)展名是薦文件擴(kuò)展名是 .ldf。62Advanced Database Technologies金培權(quán)（金培權(quán)（）63Advanced Database Technologies金培權(quán)（金培權(quán)（）n數(shù)據(jù)文件的頁(yè)按順序編號(hào)，文件首頁(yè)的頁(yè)數(shù)據(jù)文件的頁(yè)按順序編號(hào)，文件首頁(yè)的頁(yè)碼是碼是 0。每個(gè)文件都有一個(gè)文件。每個(gè)文件都有一個(gè)文件 ID 號(hào)。在號(hào)。在數(shù)據(jù)庫(kù)中唯一標(biāo)識(shí)一頁(yè)需要同時(shí)使用文件數(shù)據(jù)庫(kù)中唯一標(biāo)識(shí)一頁(yè)需要同時(shí)使用文件 ID 和頁(yè)碼。和頁(yè)碼。64Advanced Database Technologies金培權(quán)（金培權(quán)（）n數(shù)據(jù)文件的起始結(jié)構(gòu)數(shù)據(jù)文件的

31、起始結(jié)構(gòu)65Advanced Database Technologies金培權(quán)（金培權(quán)（）n數(shù)據(jù)文件的起始結(jié)構(gòu)數(shù)據(jù)文件的起始結(jié)構(gòu)PFS頁(yè)：給對(duì)象分配了擴(kuò)展盤區(qū)后，頁(yè)：給對(duì)象分配了擴(kuò)展盤區(qū)后，SQL Server 使用使用頁(yè)可用空間頁(yè)可用空間 (PFS) 頁(yè)記錄擴(kuò)展盤頁(yè)記錄擴(kuò)展盤區(qū)的哪些頁(yè)已分配或可用，以及有多少可用區(qū)的哪些頁(yè)已分配或可用，以及有多少可用的剩余空間。每個(gè)的剩余空間。每個(gè) PFS 頁(yè)包含大約頁(yè)包含大約 8,000 頁(yè)頁(yè)。PFS 對(duì)每一頁(yè)都有一個(gè)相應(yīng)的位圖，該位對(duì)每一頁(yè)都有一個(gè)相應(yīng)的位圖，該位圖記錄這一頁(yè)是空的、圖記錄這一頁(yè)是空的、1-50% 已滿、已滿、51-80% 已滿、已滿、8

32、1-95% 已滿還是已滿還是 96-100% 已滿。已滿。66Advanced Database Technologies金培權(quán)（金培權(quán)（）n數(shù)據(jù)文件的起始結(jié)構(gòu)數(shù)據(jù)文件的起始結(jié)構(gòu)GAM頁(yè)：頁(yè)：全局分配映射表全局分配映射表 (GAM) 頁(yè)記錄已分頁(yè)記錄已分配的擴(kuò)展盤區(qū)。每個(gè)配的擴(kuò)展盤區(qū)。每個(gè) GAM 包含包含 64,000 個(gè)擴(kuò)個(gè)擴(kuò)展盤區(qū)，將近展盤區(qū)，將近 4 GB 的數(shù)據(jù)。的數(shù)據(jù)。GAM 對(duì)所涵蓋對(duì)所涵蓋區(qū)間內(nèi)的每個(gè)擴(kuò)展盤區(qū)都有一位。如果這個(gè)區(qū)間內(nèi)的每個(gè)擴(kuò)展盤區(qū)都有一位。如果這個(gè)位是位是 1，則擴(kuò)展盤區(qū)可用；如果這個(gè)位是，則擴(kuò)展盤區(qū)可用；如果這個(gè)位是 0，則擴(kuò)展盤區(qū)已分配。則擴(kuò)展盤區(qū)已分配。6

33、7Advanced Database Technologies金培權(quán)（金培權(quán)（）n數(shù)據(jù)文件的起始結(jié)構(gòu)數(shù)據(jù)文件的起始結(jié)構(gòu)SGAM 頁(yè)：頁(yè)：共享全局分配映射表共享全局分配映射表 (SGAM)頁(yè)頁(yè)記錄特定的擴(kuò)展盤區(qū)，這些盤區(qū)當(dāng)前用作混記錄特定的擴(kuò)展盤區(qū)，這些盤區(qū)當(dāng)前用作混合擴(kuò)展盤區(qū)而且至少有一個(gè)未使用的頁(yè)。合擴(kuò)展盤區(qū)而且至少有一個(gè)未使用的頁(yè)。每每個(gè)個(gè) SGAM 包含包含 64,000 個(gè)擴(kuò)展盤區(qū)。個(gè)擴(kuò)展盤區(qū)。SGAM 對(duì)所涵蓋區(qū)間內(nèi)的每個(gè)擴(kuò)展盤區(qū)都有一位。對(duì)所涵蓋區(qū)間內(nèi)的每個(gè)擴(kuò)展盤區(qū)都有一位。如果這個(gè)位是如果這個(gè)位是 1，則該擴(kuò)展盤區(qū)就用作混合擴(kuò)，則該擴(kuò)展盤區(qū)就用作混合擴(kuò)展盤區(qū)且有可用的頁(yè)；如果這個(gè)

34、位是展盤區(qū)且有可用的頁(yè)；如果這個(gè)位是 0，則該，則該擴(kuò)展盤區(qū)不用作混合擴(kuò)展盤區(qū)，或者雖然用擴(kuò)展盤區(qū)不用作混合擴(kuò)展盤區(qū)，或者雖然用作混合擴(kuò)展盤區(qū)但其所有頁(yè)都正在使用中。作混合擴(kuò)展盤區(qū)但其所有頁(yè)都正在使用中。68Advanced Database Technologies金培權(quán)（金培權(quán)（）n數(shù)據(jù)文件的起始結(jié)構(gòu)數(shù)據(jù)文件的起始結(jié)構(gòu)1.1. 若要分配統(tǒng)一擴(kuò)展盤區(qū)，若要分配統(tǒng)一擴(kuò)展盤區(qū)，SQL Server SQL Server 在在 GAM GAM 中搜索是中搜索是 1 1 的的位，然后將它設(shè)成位，然后將它設(shè)成 0 0。2.2. 若要查找有可用頁(yè)的混合擴(kuò)展盤區(qū)，若要查找有可用頁(yè)的混合擴(kuò)展盤區(qū)，SQL S

35、erver SQL Server 在在 SGAM SGAM 中中搜索是搜索是 1 1 的位。的位。3.3. 若要分配混合擴(kuò)展盤區(qū)，若要分配混合擴(kuò)展盤區(qū)，SQL Server SQL Server 在在 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è)置為位設(shè)置為 0 0。69Advanced Da

36、tabase Technologies金培權(quán)（金培權(quán)（）n表（表（Table）的組織）的組織索引分配映射表 (IAM) 頁(yè)記錄了分配給對(duì)象的擴(kuò)展盤區(qū)。70Advanced Database Technologies金培權(quán)（金培權(quán)（）n表（表（Table）的組織）的組織71Advanced Database Technologies金培權(quán)（金培權(quán)（）n表（表（Table）的組織）的組織數(shù)據(jù)頁(yè)沒有任何特定的順序，也不鏈接在一起。數(shù)據(jù)頁(yè)之間唯一的邏輯連接是記錄在 IAM 頁(yè)內(nèi)的連接。服務(wù)器使用 IAM 頁(yè)查找數(shù)據(jù)頁(yè)集合內(nèi)的頁(yè)，進(jìn)行表掃描或串行讀。72Advanced Database Technol

37、ogies金培權(quán)（金培權(quán)（）n表（表（Table）的組織）的組織當(dāng)當(dāng) 需要插入新行而當(dāng)前頁(yè)沒有可用空間時(shí)，需要插入新行而當(dāng)前頁(yè)沒有可用空間時(shí)，SQL Server 使用使用 IAM 頁(yè)查找分配給對(duì)象的頁(yè)查找分配給對(duì)象的擴(kuò)展盤區(qū)。對(duì)于每個(gè)擴(kuò)展盤區(qū)，擴(kuò)展盤區(qū)。對(duì)于每個(gè)擴(kuò)展盤區(qū)，SQL Server 搜索搜索 PFS 頁(yè)以查看是否有一頁(yè)具有足夠的空頁(yè)以查看是否有一頁(yè)具有足夠的空間容納這一行。間容納這一行。73Advanced Database Technologies金培權(quán)（金培權(quán)（）create table student( no char(3), name varchar(15), class

38、varchar(5), address varchar(10), age smallint ) sysindexes表0表示無索引，是堆文件IAM首頁(yè)74Advanced Database Technologies金培權(quán)（金培權(quán)（）1B1B2BnB2B 列數(shù)列數(shù)/8 2B2變長(zhǎng)列數(shù)變長(zhǎng)列數(shù)mB狀態(tài)位A狀態(tài)位B定長(zhǎng)部分長(zhǎng)度（不包括列數(shù)和NULL位圖字節(jié)）定長(zhǎng)數(shù)據(jù)列數(shù)NULL位圖變長(zhǎng)列數(shù)列偏移數(shù)組變長(zhǎng)數(shù)據(jù)75Advanced Database Technologies金培權(quán)（金培權(quán)（）create table Fixed( col1 int, col2 char(5), col3 char(3),

39、 col4 float ) 不包括列數(shù)和NULL位圖sysindexesInsert Into Fixed Values(123, ABCD, NULL, 45.6)已分配1個(gè)數(shù)據(jù)頁(yè)00010000001E文件號(hào)：1頁(yè)號(hào)：3076Advanced Database Technologies金培權(quán)（金培權(quán)（）執(zhí)行DBCC PAGE(test,1,30,1)，4個(gè)字節(jié)一組顯示100018007b0000004142434420000000cdcccccccccc4640040004定長(zhǎng)部分長(zhǎng)度24定長(zhǎng)字段列數(shù)NULL位圖00000100Insert Into Fixed Values(123, A

40、BCD, NULL, 45.6)77Advanced Database Technologies金培權(quán)（金培權(quán)（）78Advanced Database Technologies金培權(quán)（金培權(quán)（）Buffer PoolFrame（Bucket）Block is maintained.79Advanced Database Technologies金培權(quán)（金培權(quán)（）nDirtyFrame中的塊是否已經(jīng)被修改中的塊是否已經(jīng)被修改nPin-countFrame的塊的已經(jīng)被請(qǐng)求并且還未釋放的計(jì)的塊的已經(jīng)被請(qǐng)求并且還未釋放的計(jì)數(shù)，即當(dāng)前的用戶數(shù)數(shù)，即當(dāng)前的用戶數(shù)80Advanced Database T

41、echnologies金培權(quán)（金培權(quán)（）nIf requested block is not in pool:Choose a frame for replacementIf frame is dirty (some blocks are modified and havent been written to disk), write it to diskRead requested block into chosen framenPin (increment the pin-count of the frame) the block and return its address. If re

42、quests can be predicted (e.g., sequential scans) blocks can be pre-fetched several blocks at a time!81Advanced Database Technologies金培權(quán)（金培權(quán)（）nRequestor must unpin the frame containing the blocknRequestor must indicate whether block has been modified: dirty bit is used for this.82Advanced Database Te

43、chnologies金培權(quán)（金培權(quán)（）nFrame is chosen for replacement by a replacement policy:Least-recently-used (LRU), Clock, FIFO, MRU (Most-recently-used) etc.nOnly frames whose pin-count=0 are candidatesnPolicy can have big impact on # of I/Os; depends on the access pattern.83Advanced Database Technologies金培權(quán)（金培

44、權(quán)（）nLRU (Oracle, Sybase, Informix)當(dāng)當(dāng)Pin-count為為0時(shí)，時(shí)，frame放入替換隊(duì)列放入替換隊(duì)列選擇隊(duì)列頭的選擇隊(duì)列頭的frame替換替換nClock (MS SQL Server)N個(gè)個(gè)frame組成環(huán)形，組成環(huán)形，current指針指向當(dāng)前指針指向當(dāng)前frame；每個(gè)每個(gè)frame有一個(gè)有一個(gè)referenced位，它在位，它在pin-count=0時(shí)啟動(dòng)；時(shí)啟動(dòng)；從從current開始檢查，若開始檢查，若pin-count0，current增加增加1；若；若referenced已啟動(dòng)，則關(guān)閉它并增加已啟動(dòng)，則關(guān)閉它并增加current（保證最近的

45、不被替換）；若保證最近的不被替換）；若pin-count=0并且并且referenced關(guān)閉，則替換關(guān)閉，則替換84Advanced Database Technologies金培權(quán)（金培權(quán)（）nDBMS經(jīng)常能預(yù)測(cè)訪問模式經(jīng)常能預(yù)測(cè)訪問模式(Access Pattern)可以使用更專門的緩沖區(qū)替換策略可以使用更專門的緩沖區(qū)替換策略有利于有利于pre-fetch策略的有效使用策略的有效使用nDBMS需要強(qiáng)制寫回磁盤能力（如需要強(qiáng)制寫回磁盤能力（如WAL），OS的緩沖寫回一般通過記錄寫請(qǐng)求來的緩沖寫回一般通過記錄寫請(qǐng)求來實(shí)現(xiàn)（來自不同應(yīng)用），實(shí)際的磁盤修改實(shí)現(xiàn)（來自不同應(yīng)用），實(shí)際的磁盤修改推遲，

46、因此不能保證寫順序推遲，因此不能保證寫順序85Advanced Database Technologies金培權(quán)（金培權(quán)（）n例如，插入記錄例如，插入記錄 int insert_record(DBFILE*, DBRECORD)fopen()fseek()fwrite()n沒有沒有DBMS自己的緩沖區(qū)管理和存儲(chǔ)管理自己的緩沖區(qū)管理和存儲(chǔ)管理n直接基于文件系統(tǒng)，使用了直接基于文件系統(tǒng)，使用了FS的緩沖管理的緩沖管理不能保證不能保證WAL不利于查詢優(yōu)化不利于查詢優(yōu)化不適應(yīng)應(yīng)用需求不適應(yīng)應(yīng)用需求86Advanced Database Technologies金培權(quán)（金培權(quán)（）nDisk File文件

47、存儲(chǔ)在磁盤上的物理形式是文件存儲(chǔ)在磁盤上的物理形式是bits/bytes，block是由是由OS或或DBMS軟件軟件對(duì)文件所做的抽象，這一抽象是通過控制對(duì)文件所做的抽象，這一抽象是通過控制數(shù)據(jù)在文件中的起止數(shù)據(jù)在文件中的起止offset來實(shí)現(xiàn)的來實(shí)現(xiàn)的0101001001001001011110100111010100101101111Block #1Block #287Advanced Database Technologies金培權(quán)（金培權(quán)（）Bufferset of framesFileset of pages緩沖區(qū)管理器存儲(chǔ)管理器page/blockframe通常，frame大小pag

48、e大小CPUrefers to88Advanced Database Technologies金培權(quán)（金培權(quán)（）n設(shè)計(jì)設(shè)計(jì)DBMS時(shí)應(yīng)是一個(gè)可變的輸入?yún)?shù)時(shí)應(yīng)是一個(gè)可變的輸入?yún)?shù)n通常通常DBMS允許用戶自行配置允許用戶自行配置89Advanced Database Technologies金培權(quán)（金培權(quán)（）90Advanced Database Technologies金培權(quán)（金培權(quán)（）nBuffer是一個(gè)是一個(gè)frame的列表，每個(gè)的列表，每個(gè)frame用用于表示和存放一個(gè)磁盤塊于表示和存放一個(gè)磁盤塊#define FRAMESIZE 4096struct bFrame Char fiel

49、d FRAMESIZE ; #define BUFSIZE 1024 / frame數(shù)目bFrame bufBUFSIZE; /也可以是用戶配置的值Buffer的存儲(chǔ)結(jié)構(gòu)定義示例91Advanced Database Technologies金培權(quán)（金培權(quán)（）n對(duì)于定長(zhǎng)記錄對(duì)于定長(zhǎng)記錄記錄地址記錄地址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ù)空閑空間空閑空間塊頭塊頭92Advanced Database Technologies金培權(quán)（金培權(quán)（）

50、nRecord的存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)struct Record int page_id; int slot_num; 93Advanced Database Technologies金培權(quán)（金培權(quán)（）FrameMAX:BUFSIZE*FRAMESIZE94Advanced Database Technologies金培權(quán)（金培權(quán)（）struct Frameint frame_id;int offset; ;95Advanced Database Technologies金培權(quán)（金培權(quán)（）n讀磁盤塊時(shí)：根據(jù)讀磁盤塊時(shí)：根據(jù)page_id確定在確定在Buffer中是否已經(jīng)存在中是否已經(jīng)存在frame

51、n寫磁盤塊時(shí)：要根據(jù)寫磁盤塊時(shí)：要根據(jù)frame_id快速找到文快速找到文件中對(duì)應(yīng)的件中對(duì)應(yīng)的page_id96Advanced Database Technologies金培權(quán)（金培權(quán)（）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; 97Advanced Database Technologies金培權(quán)（金培權(quán)（）n建立建立frame-page之間的索引之間的索引n若用若用Hash Table，需要建立，需要建立2個(gè)個(gè)BCB hTableBufferSize /page 2 frame int hTableBufferSize /frame 2 page一個(gè)簡(jiǎn)單的Hash Function例子H(k)=(page_id)%(buffersize)98Advanced Database Technologies金培權(quán)（金培權(quán)（）nFixPage(int page_id)將對(duì)應(yīng)將對(duì)應(yīng)page_id的的page讀入到讀入到buffer中。如果中。如果buffer已滿，則需要選擇換出的已滿，則需要選擇換