1、第5章 數(shù)據(jù)元素的表示,主要內(nèi)容,數(shù)據(jù)項(xiàng)的表示（Data Items） 記錄的表示（Records） 記錄在塊中的組織（Block） 記錄的修改 塊在文件中的組織 緩沖區(qū)管理,數(shù)據(jù)元素的表示層次,數(shù)據(jù)項(xiàng),記錄,塊,文件,屬性值的物理組織,元組的物理組織,記錄的物理存放,文件由磁盤塊構(gòu)成,一、數(shù)據(jù)項(xiàng)的表示,數(shù)據(jù)項(xiàng) 字節(jié)序列 表示關(guān)系數(shù)據(jù)庫(kù)中元組的屬性值,1、數(shù)據(jù)項(xiàng)表示的內(nèi)容,表示什么？ 姓名 年齡 出生日期 照片 用什么表示？ Bytes,2、數(shù)據(jù)項(xiàng)表示方法：SQL數(shù)據(jù)類型,Integer (short) 2 bytes 例如，35 表示為 Real，F(xiàn)loat 4 bytes （32 bits

2、） N bits表示小數(shù)，M bits表示指數(shù),00000000,00100011,2、數(shù)據(jù)項(xiàng)表示方法：SQL數(shù)據(jù)類型,Char(n) 或 Character(n) 定長(zhǎng)字符串 小于n時(shí)使用特殊填充符 例如，若屬性類型為Char(5)，則屬性值cat 表示為 Varchar(n) 變長(zhǎng)字符串 NULL終止符，例 Varchar(5) 帶長(zhǎng)度 定長(zhǎng)表示，n+1 bytesVarchar(4):,c,t,a,c,t,a,3,2、數(shù)據(jù)項(xiàng)表示方法：SQL數(shù)據(jù)類型,Boolean TRUE FALSE 枚舉類型 RED,GREEN,YELLOW 整數(shù)表示 RED 1，GREEN 2，YELLOW 3 若

3、用兩個(gè)字節(jié)的短整型來(lái)表示，則可以表示 216 個(gè)不同值,1111 1111,0000 0000,2、數(shù)據(jù)項(xiàng)表示方法：SQL數(shù)據(jù)類型,Date 10字符(SQL92)：YYYY-MM-DD字符串表示 8字符：YYYYMMDD 7字符：YYYYDDD, NOT YYMMDD！ Integer，自1900-01-01以來(lái)的天數(shù) Time 8字符(SQL92)：HH:NN:SS 整數(shù)秒 Varchar(n)：HH:NN:SS.FF帶小數(shù)秒 Integer，自00:00:00以來(lái)的秒數(shù),2、數(shù)據(jù)項(xiàng)表示方法：SQL數(shù)據(jù)類型,Bit 帶長(zhǎng)度的二進(jìn)制位串 按字節(jié)表示，例如 010111110011,Lengt

4、h,Bits,01011111,00110000,3、兩種不同的數(shù)據(jù)項(xiàng)表示,定長(zhǎng)數(shù)據(jù)項(xiàng) 變長(zhǎng)數(shù)據(jù)項(xiàng) 帶長(zhǎng)度 （常用!） Null Terminated,數(shù)據(jù)項(xiàng)表示總結(jié),Where are we?,數(shù)據(jù)項(xiàng),記錄,塊,文件,We are here！,二、記錄的組織,記錄 數(shù)據(jù)項(xiàng) 字段，F(xiàn)ields 的集合,E.g.: Employee record: name field, salary field, date-of-hire field, .,1、記錄的類型,固定格式 vs. 可變格式Fixed Format vs. Variable Format 定長(zhǎng) vs. 變長(zhǎng)Fixed Length v

5、s. Variable Length,2、固定格式定長(zhǎng)記錄,所有記錄具有相同的邏輯結(jié)構(gòu)（模式） 記錄的模式（Schema） # fields Name of each field Type of each field Order in record Offset of each field in the record,E.g. 固定格式定長(zhǎng)記錄,Employee record (1) E#, 2 byte integer (2) Ename, 10 char.Schema (3) Dept, 2 byte code,55,s m i t h,02,83,j o n e s,01,Records

6、,2、固定格式定長(zhǎng)記錄,構(gòu)造 不考慮尋址特點(diǎn),2、固定格式定長(zhǎng)記錄,考慮尋址特點(diǎn) 假設(shè)記錄和字段的開始地址必須是4的倍數(shù),3、記錄首部,在記錄首部（Head）的描述記錄的信息 記錄類型（模式信息） 記錄長(zhǎng)度 時(shí)間戳 其它信息,4、可變格式記錄,每個(gè)記錄的格式不同 記錄的格式存儲(chǔ)于記錄中,E.g. 可變格式變長(zhǎng)記錄表示,字段數(shù) 字段E標(biāo)識(shí)碼 Integer 類型 字段 Ename標(biāo)識(shí)碼 String 類型 長(zhǎng)度,Employee(E#, Ename),E.g. 固定格式變長(zhǎng)記錄表示,Key-Value 記錄都以“KEY+VALUE”方式表示 KEY與VALUE都以字節(jié)流（byte string）

7、存儲(chǔ)，如下：typedef struct void *data; /字節(jié)流指針 int size; /字節(jié)流長(zhǎng)度 DBT;,數(shù)據(jù)類型沒有限制 應(yīng)用與數(shù)據(jù)庫(kù)之間不需轉(zhuǎn)換數(shù)據(jù)格式 不提供KEY和VALUE的內(nèi)容和結(jié)構(gòu)信息 應(yīng)用必須知道所用的VALUE的含義,4、可變格式記錄,好處 靈活的記錄格式，適合“松散”記錄 盡管一個(gè)記錄可能有大量字段，但某個(gè)記錄通常只有有限的幾個(gè)字段 例如，病人的檢驗(yàn)結(jié)果 適合處理重復(fù)字段 適合記錄格式演變 缺點(diǎn) 浪費(fèi)存儲(chǔ)空間,6、變長(zhǎng)記錄表示,首部指針法 定長(zhǎng)字段在前，變長(zhǎng)字段在后 name、address變長(zhǎng),6、變長(zhǎng)記錄表示,混合格式：定長(zhǎng)記錄變長(zhǎng)記錄,Where a

8、re we?,數(shù)據(jù)項(xiàng),記錄,塊,文件,We are here！,三、記錄在塊中的組織,假設(shè) 塊的大小固定 記錄組織成單個(gè)文件,Block,A File,A Record,三、記錄在塊中的組織,定長(zhǎng)記錄的兩種塊內(nèi)組織 記錄地址rid通常使用表示,N,1 0 1 0 1 M,槽 1,槽 M,槽 2,M 3 2 1,記錄數(shù),槽數(shù),空閑空間,塊頭,三、記錄在塊中的組織,變長(zhǎng)記錄在塊內(nèi)的組織,三、記錄在塊中的組織,其他問題 記錄在塊中的分隔 (separating records) 記錄跨塊 vs.記錄不跨塊 (spanned vs. unspanned) 不同類型的記錄聚簇 (mixed record

9、 types clustering) 按序組織 (sequencing) 記錄的分裂 (split records) 記錄地址 (record address) 記錄的修改,1、記錄在塊內(nèi)的分隔,定長(zhǎng)記錄：不需分隔 使用特殊標(biāo)記 通過(guò)塊內(nèi)偏移量,2、跨塊 vs. 不跨塊,Unspanned: 記錄必須在一個(gè)塊中存儲(chǔ) block 1 block 2 . Spanned：記錄可跨塊存儲(chǔ) block 1 block 2 .,R1,R2,R1,R3,R4,R5,R2,R3 (a),R3 (b),R6,R5,R4,R7 (a),2、跨塊 vs. 不跨塊,跨塊,Whats the rest?,From w

10、here?,2、跨塊 vs. 不可跨塊,比較 unspanned：實(shí)現(xiàn)簡(jiǎn)單，但空間浪費(fèi) spanned：有效利用空間，實(shí)現(xiàn)更復(fù)雜 But If record size block size，MUST be spanned,3、不同類型的記錄聚簇,一個(gè)塊中存儲(chǔ)不同類型的記錄（對(duì)于RDB：多關(guān)系上的聚簇） 好處聚簇 (clustering) 經(jīng)常一起訪問的記錄存儲(chǔ)在同一塊或連續(xù)塊中,A Dept Record,A Employee Record,A Employee Record,A Block,3、不同類型的記錄聚簇,學(xué)號(hào) s1,其他列,學(xué)號(hào) S1 S1 s1,其他列,課程號(hào) C1 C2 c3,

11、學(xué)號(hào) s2,其他列,學(xué)號(hào) S2 S2 s2,其他列,課程號(hào) C2 C5 c6,學(xué)生表與課程表通過(guò)簇鍵“學(xué)號(hào)”聚簇,Block,3、不同類型的記錄聚簇,Q1: select student.s#,ame from student s,sc where s.s# = sc.s# Q2: select * from student,如果Q1經(jīng)常被查詢，則聚簇非常有效 若Q2經(jīng)常被查詢，則聚簇反而降低了效率,STUDENT(s#,sname,age) SC(s#,cname,score),4、在塊中按序存儲(chǔ)記錄,另一種聚簇 (對(duì)于RDB：?jiǎn)侮P(guān)系上的聚簇) 將記錄按某個(gè)字段順序排列在塊中 好處 加快按排

12、序字段查詢記錄時(shí)的效率 利于歸并聯(lián)接 （will be discussed later）,4、在塊中按序存儲(chǔ)記錄,按Dept順序組織的Student記錄,無(wú)序組織的Student記錄,假設(shè)一個(gè)磁盤塊2條定長(zhǎng)記錄,4、在塊中按序存儲(chǔ)記錄,物理連續(xù) 指針連接,Next (R1),R1,R1,R2,Next(R1),5、記錄的分裂,適合于變長(zhǎng)記錄的混合格式表示 定長(zhǎng)部分存儲(chǔ)于某個(gè)塊中 變長(zhǎng)部分存儲(chǔ)于另一個(gè)塊中 與spanned存儲(chǔ)類似,6、記錄地址,物理地址 邏輯地址（間接地址）,6、記錄地址,記錄的純物理地址 主機(jī)標(biāo)識(shí) 磁盤或其他設(shè)備標(biāo)識(shí) 柱面號(hào) 磁頭號(hào)（盤面號(hào)） 塊號(hào) 塊內(nèi)的偏移量,塊地址,6、

13、記錄地址,記錄的純邏輯地址,物理地址,邏輯地址,映射表,記錄地址,純物理地址,缺點(diǎn)訪問代價(jià)增加：映射表占存儲(chǔ)空間；需要地址轉(zhuǎn)換 好處?kù)`活性：刪除或移動(dòng)記錄時(shí)只要改變映射表項(xiàng),6、記錄地址,記錄的純物理地址,記錄的純邏輯地址,tradeoff,6、記錄地址,借助文件系統(tǒng)的邏輯塊地址 文件號(hào)邏輯塊地址塊內(nèi)偏移,文件系統(tǒng)映射,File ID Block(logical),Block(physical) + offset,記錄地址,四、記錄的修改,插入 刪除,1、插入,記錄無(wú)序 插入到任意塊的空閑空間中 或申請(qǐng)一個(gè)新塊（當(dāng)所有塊都已滿時(shí)） 記錄變長(zhǎng)時(shí)，可使用偏移量表,1、插入,記錄有序 找到記錄應(yīng)該放

14、置的塊 如果有空間，放入并調(diào)節(jié)記錄順序即可，否則有兩種方法： 在“鄰近塊”中找空間 創(chuàng)建溢出塊,基本塊,溢出塊,2、刪除,立即回收空間 例如，加到可用空間列表中 刪除記錄時(shí)處理溢出塊 若刪除的記錄位于溢出塊鏈上，則刪除記錄后可對(duì)整個(gè)鏈進(jìn)行重新組織以去除溢出塊,2、刪除,使用刪除標(biāo)記 若使用偏移表，則可以修改偏移表項(xiàng)指針，將其置空 若使用邏輯物理地址映射表，則可以將物理地址置空 可以在記錄首部預(yù)留一開始位：0未刪除，1已刪除,1,記錄1,0,記錄2,Where are we?,數(shù)據(jù)項(xiàng),記錄,塊,文件,We are here！,五、塊在文件中的組織,堆文件（Heap File） 最基本、最簡(jiǎn)單的文

15、件結(jié)構(gòu) 記錄不以任何順序排序 記錄可能存放在物理不鄰接的塊上 插入容易，但查找和刪除代價(jià)高,1、鏈表式堆文件組織,首塊,數(shù)據(jù)塊,數(shù)據(jù)塊,數(shù)據(jù)塊,數(shù)據(jù)塊,數(shù)據(jù)塊,數(shù)據(jù)塊,含空閑空間 的塊鏈表,滿塊鏈表,2、目錄式堆文件組織,數(shù)據(jù)塊1,數(shù)據(jù)塊2,數(shù)據(jù)塊N,首塊,回顧：數(shù)據(jù)元素的表示層次,數(shù)據(jù)項(xiàng),記錄,塊,文件,屬性值的物理組織,元組的物理組織,記錄的物理存放,文件由磁盤塊構(gòu)成,六、SQL Server的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu),SQL Server的數(shù)據(jù)庫(kù)文件是多個(gè)對(duì)象的集合，包括多個(gè)表、索引等,1、頁(yè),在SQL Server中，數(shù)據(jù)存儲(chǔ)的基本單位是頁(yè)。在 SQL Server 2000 中，頁(yè)的大小是 8

16、KB。,96字節(jié),單個(gè)數(shù)據(jù)行 最大8060字節(jié),頁(yè)地址： 數(shù)據(jù)行地址：,2、擴(kuò)展盤區(qū),擴(kuò)展盤區(qū)是一種基本單元，可將其中的空間分配給表和索引。一個(gè)擴(kuò)展盤區(qū)是 8 個(gè)鄰接的頁(yè)（或 64 KB）。 為了使空間分配更有效，SQL Server 2000 對(duì)只含少量數(shù)據(jù)的表不分配完整的擴(kuò)展盤區(qū)。SQL Server 2000 有兩種類型的擴(kuò)展盤區(qū)： 統(tǒng)一擴(kuò)展盤區(qū)：由單個(gè)對(duì)象所有，擴(kuò)展盤區(qū)中的所有八頁(yè)只能由擁有該盤區(qū)的對(duì)象使用。 混合擴(kuò)展盤區(qū)：最多可由 8 個(gè)對(duì)象共享。 通常從混合擴(kuò)展盤區(qū)中向新表或新索引分配頁(yè)。當(dāng)表或索引增長(zhǎng)到 8 頁(yè)時(shí)，就變成統(tǒng)一擴(kuò)展盤區(qū)。,2、擴(kuò)展盤區(qū),混合擴(kuò)展盤區(qū)和統(tǒng)一擴(kuò)展盤區(qū),3

17、、SQL Server文件組織,SQL Server 2000 數(shù)據(jù)庫(kù)有三種類型的文件： 主要數(shù)據(jù)文件 主要數(shù)據(jù)文件是數(shù)據(jù)庫(kù)的起點(diǎn)，指向數(shù)據(jù)庫(kù)中文件的其它部分。每個(gè)數(shù)據(jù)庫(kù)都有一個(gè)主要數(shù)據(jù)文件。主要數(shù)據(jù)文件的推薦文件擴(kuò)展名是 .mdf。 次要數(shù)據(jù)文件 次要數(shù)據(jù)文件包含除主要數(shù)據(jù)文件外的所有數(shù)據(jù)文件。有些數(shù)據(jù)庫(kù)可能沒有次要數(shù)據(jù)文件，而有些數(shù)據(jù)庫(kù)則有多個(gè)次要數(shù)據(jù)文件。次要數(shù)據(jù)文件的推薦文件擴(kuò)展名是 .ndf。 日志文件 日志文件包含恢復(fù)數(shù)據(jù)庫(kù)所需的所有日志信息。每個(gè)數(shù)據(jù)庫(kù)必須至少有一個(gè)日志文件，但可以不止一個(gè)。日志文件的推薦文件擴(kuò)展名是 .ldf。,3、SQL Server文件組織,3、SQL Se

18、rver文件組織,數(shù)據(jù)文件的頁(yè)按順序編號(hào)，文件首頁(yè)的頁(yè)碼是 0。每個(gè)文件都有一個(gè)文件 ID 號(hào)。在數(shù)據(jù)庫(kù)中唯一標(biāo)識(shí)一頁(yè)需要同時(shí)使用文件 ID 和頁(yè)碼。,3、SQL Server文件組織,數(shù)據(jù)文件的起始結(jié)構(gòu),3、SQL Server文件組織,數(shù)據(jù)文件的起始結(jié)構(gòu) PFS頁(yè)：給對(duì)象分配了擴(kuò)展盤區(qū)后，SQL Server 使用頁(yè)可用空間 (PFS) 頁(yè)記錄擴(kuò)展盤區(qū)的哪些頁(yè)已分配或可用，以及有多少可用的剩余空間。每個(gè) PFS 頁(yè)包含大約 8,000 頁(yè)。PFS 對(duì)每一頁(yè)都有一個(gè)相應(yīng)的位圖，該位圖記錄這一頁(yè)是空的、1-50% 已滿、51-80% 已滿、81-95% 已滿還是 96-100% 已滿。,3、S

19、QL Server文件組織,數(shù)據(jù)文件的起始結(jié)構(gòu) GAM頁(yè)：全局分配映射表 (GAM) 頁(yè)記錄已分配的擴(kuò)展盤區(qū)。每個(gè) GAM 包含 64,000 個(gè)擴(kuò)展盤區(qū)，將近 4 GB 的數(shù)據(jù)。GAM 對(duì)所涵蓋區(qū)間內(nèi)的每個(gè)擴(kuò)展盤區(qū)都有一位。如果這個(gè)位是 1，則擴(kuò)展盤區(qū)可用；如果這個(gè)位是 0，則擴(kuò)展盤區(qū)已分配。,3、SQL Server文件組織,數(shù)據(jù)文件的起始結(jié)構(gòu) SGAM 頁(yè)：共享全局分配映射表 (SGAM)頁(yè)記錄特定的擴(kuò)展盤區(qū)，這些盤區(qū)當(dāng)前用作混合擴(kuò)展盤區(qū)而且至少有一個(gè)未使用的頁(yè)。每個(gè) SGAM 包含 64,000 個(gè)擴(kuò)展盤區(qū)。SGAM 對(duì)所涵蓋區(qū)間內(nèi)的每個(gè)擴(kuò)展盤區(qū)都有一位。如果這個(gè)位是 1，則該擴(kuò)展盤區(qū)

20、就用作混合擴(kuò)展盤區(qū)且有可用的頁(yè)；如果這個(gè)位是 0，則該擴(kuò)展盤區(qū)不用作混合擴(kuò)展盤區(qū)，或者雖然用作混合擴(kuò)展盤區(qū)但其所有頁(yè)都正在使用中。,3、SQL Server文件組織,數(shù)據(jù)文件的起始結(jié)構(gòu),若要分配統(tǒng)一擴(kuò)展盤區(qū)，SQL Server 在 GAM 中搜索是 1 的位，然后將它設(shè)成 0。 若要查找有可用頁(yè)的混合擴(kuò)展盤區(qū)，SQL Server 在 SGAM 中搜索是 1 的位。 若要分配混合擴(kuò)展盤區(qū)，SQL Server 在 GAM 中搜索是 1 的位，并將它設(shè)置為 0，然后將 SGAM 中相應(yīng)的位也設(shè)置為 1。 若要釋放擴(kuò)展盤區(qū)，SQL Server 應(yīng)確保 GAM 位設(shè)置為 1 而且 SGAM 位設(shè)

21、置為 0。,3、SQL Server文件組織,表（Table）的組織,索引分配映射表 (IAM) 頁(yè)記錄了分配給對(duì)象的擴(kuò)展盤區(qū)。,3、SQL Server文件組織,表（Table）的組織,3、SQL Server文件組織,表（Table）的組織,數(shù)據(jù)頁(yè)沒有任何特定的順序，也不鏈接在一起。數(shù)據(jù)頁(yè)之間唯一的邏輯連接是記錄在 IAM 頁(yè)內(nèi)的連接。 服務(wù)器使用 IAM 頁(yè)查找數(shù)據(jù)頁(yè)集合內(nèi)的頁(yè)，進(jìn)行表掃描或串行讀。,3、SQL Server文件組織,表（Table）的組織 當(dāng) 需要插入新行而當(dāng)前頁(yè)沒有可用空間時(shí)，SQL Server 使用 IAM 頁(yè)查找分配給對(duì)象的擴(kuò)展盤區(qū)。對(duì)于每個(gè)擴(kuò)展盤區(qū)，SQL S

22、erver 搜索 PFS 頁(yè)以查看是否有一頁(yè)具有足夠的空間容納這一行。,3、SQL Server文件組織,create table student ( no char(3), name varchar(15), class varchar(5), address varchar(10), age smallint ),sysindexes表,0表示無(wú)索引， 是堆文件,IAM首頁(yè),4、SQL Server記錄結(jié)構(gòu),狀態(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ù),4、SQL Server記錄結(jié)構(gòu),create tabl

23、e Fixed ( col1 int, col2 char(5), col3 char(3), col4 float ),不包括列數(shù)和NULL位圖,sysindexes,Insert Into Fixed Values(123, ABCD, NULL, 45.6),已分配1個(gè)數(shù)據(jù)頁(yè) 00010000001E,文件號(hào)：1 頁(yè)號(hào)：30,4、SQL Server記錄結(jié)構(gòu),執(zhí)行DBCC PAGE(test,1,30,1)，4個(gè)字節(jié)一組顯示,定長(zhǎng)部分長(zhǎng)度24,定長(zhǎng)字段,列數(shù),NULL 位圖,00000100,Insert Into Fixed Values(123, ABCD, NULL, 45.6),

24、七、緩沖區(qū)管理器,七、緩沖區(qū)管理器,Buffer Pool Frame（Bucket） Block is maintained.,1、frame的參數(shù),Dirty Frame中的塊是否已經(jīng)被修改 Pin-count Frame的塊的已經(jīng)被請(qǐng)求并且還未釋放的計(jì)數(shù)，即當(dāng)前的用戶數(shù),2、當(dāng)請(qǐng)求塊時(shí),If requested block is not in pool: Choose a frame for replacement If frame is dirty (some blocks are modified and havent been written to disk), write it

25、to disk Read requested block into chosen frame Pin (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 time!,2、當(dāng)釋放塊時(shí),Requestor must unpin the frame containing the block Requestor

26、must indicate whether block has been modified: dirty bit is used for this.,3、緩沖區(qū)替換策略,Frame is chosen for replacement by a replacement policy: Least-recently-used (LRU), Clock, FIFO, MRU (Most-recently-used) etc. Only frames whose pin-count=0 are candidates Policy can have big impact on # of I/Os; de

27、pends on the access pattern.,3、緩沖區(qū)替換策略,LRU (Oracle, Sybase, Informix) 當(dāng)Pin-count為0時(shí)，frame放入替換隊(duì)列 選擇隊(duì)列頭的frame替換 Clock (MS SQL Server) N個(gè)frame組成環(huán)形，current指針指向當(dāng)前frame；每個(gè)frame有一個(gè)referenced位，它在pin-count=0時(shí)啟動(dòng)； 從current開始檢查，若pin-count0，current增加1；若referenced已啟動(dòng)，則關(guān)閉它并增加current（保證最近的不被替換）；若pin-count=0并且refere

28、nced關(guān)閉，則替換,4、為何不使用OS緩沖區(qū)管理？,DBMS經(jīng)常能預(yù)測(cè)訪問模式(Access Pattern) 可以使用更專門的緩沖區(qū)替換策略 有利于pre-fetch策略的有效使用 DBMS需要強(qiáng)制寫回磁盤能力（如WAL），OS的緩沖寫回一般通過(guò)記錄寫請(qǐng)求來(lái)實(shí)現(xiàn)（來(lái)自不同應(yīng)用），實(shí)際的磁盤修改推遲，因此不能保證寫順序,5、錯(cuò)誤的記錄操作實(shí)現(xiàn)例子,例如，插入記錄 int insert_record(DBFILE*, DBRECORD) fopen() fseek() fwrite() 沒有DBMS自己的緩沖區(qū)管理和存儲(chǔ)管理 直接基于文件系統(tǒng)，使用了FS的緩沖管理 不能保證WAL 不利于查詢優(yōu)

29、化 不適應(yīng)應(yīng)用需求,6、Block vs. Disk File,Disk File文件存儲(chǔ)在磁盤上的物理形式是bits/bytes，block是由OS或DBMS軟件對(duì)文件所做的抽象，這一抽象是通過(guò)控制數(shù)據(jù)在文件中的起止offset來(lái)實(shí)現(xiàn)的,0101001001001001011110100111010100101101111,Block #1,Block #2,6、Buffer vs. Disk File,Bufferset of frames,Fileset of pages,緩沖區(qū)管理器,存儲(chǔ)管理器,page/block,frame,通常， frame大小page大小,CPU,refers

30、 to,7、Buffer Size,設(shè)計(jì)DBMS時(shí)應(yīng)是一個(gè)可變的輸入?yún)?shù) 通常DBMS允許用戶自行配置,7、Buffer Size,配置實(shí)例,8、Buffer的存儲(chǔ)結(jié)構(gòu),Buffer是一個(gè)frame的列表，每個(gè)frame用于表示和存放一個(gè)磁盤塊,#define FRAMESIZE 4096 struct bFrame Char field FRAMESIZE ; ;,#define BUFSIZE 1024 / frame數(shù)目 bFrame bufBUFSIZE; /也可以是用戶配置的值,Buffer的存儲(chǔ)結(jié)構(gòu)定義示例,9、Page/block的一般存儲(chǔ)格式,對(duì)于定長(zhǎng)記錄 記錄地址rid通常使

31、用表示,N,1 0 1 0 1 M,槽 1,槽 M,槽 2,M 3 2 1,記錄數(shù),槽數(shù),空閑空間,塊頭,9、Page/block的一般存儲(chǔ)格式,Record的存儲(chǔ)結(jié)構(gòu),struct Record int page_id; int slot_num; ;,10、Buffer中的Frame存儲(chǔ)結(jié)構(gòu),Frame,MAX: BUFSIZE*FRAMESIZE,10、Buffer中的Frame存儲(chǔ)結(jié)構(gòu),struct Frame int frame_id; int offset; ;,11、Buffer中Frame的查找,讀磁盤塊時(shí)：根據(jù)page_id確定在Buffer中是否已經(jīng)存在frame 寫磁盤塊

32、時(shí)：要根據(jù)frame_id快速找到文件中對(duì)應(yīng)的page_id,11、Buffer中Frame的查找,首先，要維護(hù)Buffer中所有frame的維護(hù)信息（Buffer Control Blocks），如,struct BCB BCB(); int page_id; int frame_id; int count; int time; int dirty; BCB * next; ;,11、Buffer中Frame的查找,建立frame-page之間的索引 若用Hash Table，需要建立2個(gè) BCB hTableBufferSize /page 2 frame int hTableBuffer

33、Size /frame 2 page,一個(gè)簡(jiǎn)單的Hash Function例子 H(k)=(page_id)%(buffersize),12、Buffer Manager的基本功能,FixPage(int page_id) 將對(duì)應(yīng)page_id的page讀入到buffer中。如果buffer已滿，則需要選擇換出的frame。 FixNewPage() 在插入數(shù)據(jù)時(shí)申請(qǐng)一個(gè)新page并將其放在buffer中。 SelectVictim() 選擇換出的frame_id FindFrame(int page_id) 查找給定的page是否已經(jīng)在某個(gè)frame中了 SetDirty(int frame_id),13、數(shù)據(jù)庫(kù)文件的一般組成,數(shù)據(jù)文件 首塊在Insert_Record時(shí)創(chuàng)建（調(diào)用Buffer Manager的FixNewPage），一般塊號(hào)從0開始 系統(tǒng)目錄文件 首塊一般Creat