清華大學(xué)數(shù)據(jù)庫access課件 第07章：存儲結(jié)構(gòu)和文件結(jié)構(gòu)

數(shù)據(jù)庫系統(tǒng)設(shè)計與原理第Ⅱ部分?jǐn)?shù)據(jù)存儲(第７章－第８章)2/6/20231第7章存儲結(jié)構(gòu)和文件結(jié)構(gòu)講課內(nèi)容：主要介紹數(shù)據(jù)庫系統(tǒng)的底層存儲。包括存儲介質(zhì)、數(shù)據(jù)庫文件的組織及結(jié)構(gòu)、文件中記錄的組織及結(jié)構(gòu)?！鑫锢泶鎯橘|(zhì)■文件結(jié)構(gòu)■磁盤■文件中記錄的組織■RAID■數(shù)據(jù)字典的存儲■第三級存儲■本章總結(jié)2/6/20232DBMS總體結(jié)構(gòu)回顧：磁盤存儲器用戶應(yīng)用界面索引統(tǒng)計數(shù)據(jù)數(shù)據(jù)文件數(shù)據(jù)字典應(yīng)用程序交互查詢數(shù)據(jù)庫模式應(yīng)用程序目標(biāo)碼嵌入式DML預(yù)編譯器DML編譯器DDL解釋器查詢計算引擎事務(wù)管理器緩沖區(qū)管理器文件管理器查詢處理器存儲管理器數(shù)據(jù)庫管理系統(tǒng)磁盤存儲器權(quán)限及完整性管理器日志2/6/20233§7.1物理存儲介質(zhì)認(rèn)識存儲介質(zhì)成本與速度隨機存取順序存取聯(lián)機與脫機存儲容量存儲易失性高速緩沖存儲器主存儲器磁盤光盤磁帶一級存儲三級存儲二級存儲閃存2/6/20234§7.2磁盤基本術(shù)語轉(zhuǎn)軸磁道扇區(qū)柱面盤片旋轉(zhuǎn)讀寫頭磁盤臂磁盤臂裝置2/6/20235§7.2磁盤磁盤的物理特性磁道：盤片的表面被邏輯地劃分為磁道。扇區(qū)：磁道又被邏輯地劃分為扇區(qū)；扇區(qū)是從磁盤讀出和寫入數(shù)據(jù)的最小單位，通常大小為512字節(jié)。物理塊：一個盤片的一條磁道內(nèi)幾個連續(xù)的扇區(qū)構(gòu)成的序列稱為物理塊,一般也簡稱塊；數(shù)據(jù)在磁盤和主存儲器之間以塊為單位傳輸。2/6/20236§7.2磁盤磁盤的塊存取磁盤的I/O請求指定了要存取的磁盤地址，這個地址是以塊號的形式提供的；數(shù)據(jù)庫的文件管理器將塊地址轉(zhuǎn)換成硬件層的柱面號、盤面號和扇區(qū)號。數(shù)據(jù)庫緩沖區(qū)數(shù)據(jù)庫的文件管理器只負(fù)責(zé)將包含用戶需要的數(shù)據(jù)所在的塊緩存到主存儲器里的數(shù)據(jù)庫緩沖區(qū)，或者執(zhí)行相反的操作；當(dāng)新的數(shù)據(jù)從磁盤到緩存時，根據(jù)緩沖區(qū)替換策略來安排數(shù)據(jù)的位置。2/6/20237§7.2磁盤磁盤質(zhì)量的度量標(biāo)準(zhǔn)容量大小存取時間：從發(fā)出讀寫請求到數(shù)據(jù)開始傳輸之間的時間；存取時間=尋道時間+旋轉(zhuǎn)等待時間。數(shù)據(jù)傳輸率：從磁盤獲得數(shù)據(jù)或者向磁盤存儲數(shù)據(jù)的速率，即I/O吞吐量。可靠性性價比2/6/20238§7.3RAID早期的RAID經(jīng)濟因素是主要原因，因此：RedundantArraysofInexpensiveDisks；中文稱為“廉價磁盤冗余陣列”?，F(xiàn)在的RAID價格已經(jīng)不是主要因素，而磁盤的性能(數(shù)據(jù)傳輸率)和可靠性是考慮的主要內(nèi)容，因此：RedundantArraysofIndependentDisks；中文稱為“獨立磁盤冗余陣列”。未來的RAID？真正的百年存儲……2/6/20239§7.3RAID如何提高磁盤的可靠性？引入冗余是解決可靠性問題的有效方法：存儲一些通常情況下不需要的額外信息，這些信息可在發(fā)生磁盤故障時用于重建丟失的信息。實現(xiàn)冗余的方法實現(xiàn)冗余最簡單、但最昂貴的方法：復(fù)制每一個磁盤，這種技術(shù)稱為磁盤鏡像或磁盤影像；一個邏輯上的磁盤由兩個物理磁盤組成，并且每一個寫操作都要在兩個磁盤上執(zhí)行。實現(xiàn)冗余的第二種方法是存儲奇偶校驗位。2/6/202310§7.3RAID如何提高磁盤的性能通過在多個磁盤上對數(shù)據(jù)進行拆分來提高傳輸率，原因是可以對多個磁盤并行存取。拆分的方法比特級拆分：數(shù)據(jù)拆分的最簡單形式是將每個字節(jié)按比特位分開，存儲到多個磁盤上。塊級拆分：在塊級拆分中，文件的塊被拆分存儲到多個磁盤上。如果有n個磁盤，則文件的第i塊被存儲到第(imodn)+1個磁盤上。2/6/202311§7.3RAIDRAID級別鏡像+拆分+奇偶校驗構(gòu)成了RAID的不同方案2/6/202312§7.3RAID如何正確選擇RAID級別由于RAID2和4被RAID3和5所包容，因此只需要在RAID0、1、3、5和6之間作出選擇：RAID0：用于可容忍數(shù)據(jù)丟失的高性能應(yīng)用；RAID1：用于存儲類似數(shù)據(jù)庫日志的應(yīng)用，因為它提供了最好的寫性能，同時又保證可靠性；RAID3：用于存儲大量數(shù)據(jù)，并提供高的數(shù)據(jù)傳輸率；RAID5：用于存儲大量數(shù)據(jù)，且隨機讀的效率很高。大多數(shù)數(shù)據(jù)庫系統(tǒng)都屬于這種情況；RAID6：提供比RAID5更高的可靠性，但很多RAID實現(xiàn)并不支持RAID6。2/6/202313§7.4第三級存儲傳統(tǒng)上，光盤和磁帶主要用于備份和歸檔數(shù)據(jù)，因此它們一般都是離線(off-line)的存儲介質(zhì)；隨著數(shù)據(jù)的不斷膨脹，數(shù)據(jù)越來越多，我們稱之為海量信息；在當(dāng)前，我們主要用光盤塔或磁帶庫來存儲海量信息，并且使它們變成近線(near-line)或在線(on-line)的存儲介質(zhì)。也就是說，跨過二級存儲設(shè)備在內(nèi)存和光盤或磁帶之間直接傳輸數(shù)據(jù)。2/6/202314§7.5DBMS的文件管理器DBMS的物理存儲綜述了解數(shù)據(jù)庫的存儲結(jié)構(gòu)就必須搞清楚：數(shù)據(jù)庫的文件組織：一個數(shù)據(jù)庫由幾個OS文件構(gòu)成？文件管理器：是DBMS的還是OS自身的？數(shù)據(jù)庫文件自身的結(jié)構(gòu)如何？為了能解析每條SQL語句，還必須進一步搞清楚：文件中記錄的存儲方式與結(jié)構(gòu)如何？文件中記錄的組織方式如何？2/6/202315§7.5DBMS的文件管理器數(shù)據(jù)庫與文件管理在小型關(guān)系數(shù)據(jù)庫系統(tǒng)中將各個關(guān)系存儲在一個個獨立的文件中。通常：文件中的記錄都是定長的，文件結(jié)構(gòu)簡單；充分利用了作為OS一部分的文件系統(tǒng)的好處。大型數(shù)據(jù)庫管理系統(tǒng)在文件管理方面并不直接依賴于操作系統(tǒng)。操作系統(tǒng)只分配給DBMS一個大的操作系統(tǒng)文件，所有關(guān)系都存儲在這個大文件中。它的好處是：有利于提高系統(tǒng)的性能；空間的分配與管理簡單、靈活，如簇集文件組織2/6/202316SQLSERVER2000的數(shù)據(jù)庫文件組織在MSSQLServer2000中，一個數(shù)據(jù)庫是由三個操作系統(tǒng)文件構(gòu)成的，它們分別是：主數(shù)據(jù)文件：*.MDF次數(shù)據(jù)文件：*.NDF日志文件：*.LDF這些信息都存放在SYSFILES系統(tǒng)表中SQLSERVER2000的數(shù)據(jù)庫文件管理上述數(shù)據(jù)庫文件的管理是由SQLServer自己負(fù)責(zé)的，而不是依賴于Windows的文件系統(tǒng)。SQLServer有自己的文件管理器。§7.5DBMS的文件管理器2/6/202317DBMS一般不用OS的文件管理器，而是獨立設(shè)計其數(shù)據(jù)庫文件的存儲結(jié)構(gòu)，有自己的文件管理器。這有以下5個方面的原因：更多功能與附加信息：DBMS為了實現(xiàn)其功能，須在文件目錄、文件描述塊、物理塊等部分附加一些信息；傳統(tǒng)的文件系統(tǒng)是不提供這些信息的批處理與即席訪問：傳統(tǒng)的文件系統(tǒng)主要面向批處理；而在DBMS中，往往要求即席訪問、動態(tài)修改：這就要求文件結(jié)構(gòu)能適應(yīng)數(shù)據(jù)的動態(tài)變化，提供快速訪問路徑?！?.5DBMS的文件管理器2/6/202318DBMS一般不用OS的文件管理器，而是獨立設(shè)計其存儲結(jié)構(gòu)，有自己的文件管理器。這有以下5個方面的原因：數(shù)據(jù)共享與并發(fā)控制：傳統(tǒng)的文件基本上是為某一用戶或某類用戶服務(wù)的，用途比較單一，共享的程度較低；數(shù)據(jù)庫文件是供所有用戶共享的，有些用途是不可預(yù)知的。這就要求數(shù)據(jù)庫文件的結(jié)構(gòu)能兼顧多方面的要求，提供多種訪問路徑，并在：并發(fā)控制故障恢復(fù)數(shù)據(jù)安全等§7.5DBMS的文件管理器2/6/202319DBMS一般不用OS的文件管理器，而是獨立設(shè)計其存儲結(jié)構(gòu)，有自己的文件管理器。這有以下5個方面的原因：可移植性與實現(xiàn)的可能性：如果采用操作系統(tǒng)的文件管理器作為DBMS的物理層實現(xiàn)的基礎(chǔ)，那么DBMS對操作系統(tǒng)的依賴性太大，不利于DBMS的移植；有些操作系統(tǒng)，如Unix，只提供字符流的存取功能，不提供各種文件結(jié)構(gòu)和存取路徑，這些只有靠DBMS自身來實現(xiàn)?！?.5DBMS的文件管理器2/6/202320DBMS一般不用OS的文件管理器，而是獨立設(shè)計其存儲結(jié)構(gòu)，有自己的文件管理器。這有以下5個方面的原因：數(shù)據(jù)的穩(wěn)定性與動態(tài)變化：傳統(tǒng)的文件一旦建立以后，數(shù)據(jù)量是比較穩(wěn)定的，而且一般只用于只讀的應(yīng)用；數(shù)據(jù)庫文件的數(shù)據(jù)量變化較大，有些文件在數(shù)據(jù)模式剛定義時幾乎是個空架子，隨著應(yīng)用的開發(fā)，數(shù)據(jù)也不斷地增長：數(shù)據(jù)庫文件的結(jié)構(gòu)應(yīng)能適應(yīng)這樣的變化；數(shù)據(jù)庫中的數(shù)據(jù)常常要求是可讀寫的?！?.5DBMS的文件管理器2/6/202321DBMS中文件的管理粒度DBMS的高層(邏輯層和視圖層)把數(shù)據(jù)看成是“記錄”的集合；DBMS的底層(物理層)在處理I/O問題時，把數(shù)據(jù)看成是“頁”的集合：具體地說，DBMS的文件管理器把數(shù)據(jù)看成是頁的集合，并且提供分配/回收頁和讀/寫頁的命令；通常以磁盤塊的大小作為頁的大小，以便在一次磁盤I/O中就能夠完成一頁的讀/寫。數(shù)據(jù)庫文件的頁結(jié)構(gòu)定長記錄方式變長記錄方式§7.5DBMS的文件管理器2/6/202322§7.6數(shù)據(jù)庫文件的結(jié)構(gòu)定長記錄方式記錄的移動引起記錄RID變化。如果有外部引用指向被移動的記錄，如索引，則……2/6/202323§7.6數(shù)據(jù)庫文件的結(jié)構(gòu)變長記錄方式刪除移動適應(yīng)性2/6/202324SQLSERVER2000的頁數(shù)據(jù)頁是表的所有非文本數(shù)據(jù)和圖形數(shù)據(jù)的存儲結(jié)構(gòu)；數(shù)據(jù)頁的固定大小為8KB，即8192字節(jié)，其中8096字節(jié)用于存儲數(shù)據(jù)，其余的96字節(jié)用于存儲頁結(jié)構(gòu)信息；數(shù)據(jù)頁由3個主要的部分組成：它們是……§7.6數(shù)據(jù)庫文件的結(jié)構(gòu)記錄不能跨頁存儲，它的最大長度是8060字節(jié)！2/6/202325SQLSERVER2000的文件結(jié)構(gòu)有一些特殊的元數(shù)據(jù)頁§7.6數(shù)據(jù)庫文件的結(jié)構(gòu)2/6/202326定長記錄首先考慮由有關(guān)student記錄組成的一個文件。該文件中的記錄定義如下：typestudent=record

student_number:char(10);

student_name:char(8);

department_name:char(22);end假設(shè)每個字符占一個字節(jié)，那么一個student記錄占40個字節(jié)?！?.7記錄的存儲與維護2/6/202327定長記錄的存儲用文件的頭40個字節(jié)存儲第一個記錄，接著的40個字節(jié)存儲第二個記錄，依次類推……這種結(jié)構(gòu)的問題是：刪除一條記錄時要么填充被刪空間要么標(biāo)記被刪記錄；除非塊的大小恰好是40的倍數(shù)，否則記錄會跨塊存儲?！?.7記錄的存儲與維護2/6/202328定長記錄的維護方案一：刪除一條記錄時，順序移動其后的所有記錄；插入一條記錄則始終在文件的尾部進行。方案二：刪除一條記錄時，移動最后一條記錄到此位置；而插入一條記錄則始終在文件的尾部進行?！?.7記錄的存儲與維護2/6/202329定長記錄的維護方案三：刪除一條記錄時，并不著急移動記錄，而是將其加入空閑記錄列表；當(dāng)要插入記錄時，使用空閑列表中的記錄空間；若沒有空閑空間就插入到文件的尾部。§7.7記錄的存儲與維護額外的結(jié)構(gòu)：文件頭指針列2/6/202330變長記錄造成變長記錄的原因：多種記錄類型在一個文件中存儲；記錄類型允許一個或多個字段是變長的；記錄類型允許可重復(fù)的字段。例如：typecourse_list=record

teacher_name:char(22);

course_info:array[1..∞]ofrecordcourse_name:char(30);

course_capacity:int;endend

定長部分變長部分§7.7記錄的存儲與維護2/6/202331變長記錄的存儲方法之一：字節(jié)流表示法在每個記錄的末尾都附加特殊的記錄終止符⊥；或者是在每個記錄的開頭存儲該記錄的長度。問題：磁盤碎片刪除一條記錄？記錄變長了？記錄變短了？方案：移動記錄的代價§7.7記錄的存儲與維護2/6/202332變長記錄的存儲方法之二：分槽的頁結(jié)構(gòu)用于物理塊內(nèi)部的記錄組織；塊頭部分：塊中記錄個數(shù)；塊中空閑空間的末尾地址；描述塊中每個記錄的大小和位置的數(shù)組；塊尾部分：實際記錄從塊的尾部開始連續(xù)存儲；塊中部分：塊中空閑空間是連續(xù)的。§7.7記錄的存儲與維護分槽頁結(jié)構(gòu)的實例？2/6/202333變長記錄的存儲方法之二：分槽頁結(jié)構(gòu)的維護刪除一條記錄：它所占用的空間被釋放；塊中在此之前的記錄都要移動；而空閑空間還是集中在塊中間。插入一條記錄：在塊中空閑空間的尾部給這條記錄分配空間。記錄的增長和縮短：該條記錄的末尾地址不變；在此記錄之前的記錄都要移動；塊的大小有限制，移動記錄的代價并不高?！?.7記錄的存儲與維護還要修改？2/6/202334變長記錄的存儲方法之三：定長表示法用一個或多個定長記錄來表示一個變長記錄。由于所采用的策略不同，定長表示法又分為以下幾類：方法之三(1)--保留空間法方法之三(2)--指針法方法之三(3)--錨塊-溢出塊表示法定長表示法在實際的DBMS當(dāng)中很少使用，為什么？但至少可以為我們解決其他問題開拓思路！§7.7記錄的存儲與維護2/6/202335變長記錄的存儲方法之三(1)：保留空間法假設(shè)所有的變長記錄都不會超過某個長度，就為每個記錄都分配這樣長度的空間；缺陷：假設(shè)不合理；浪費大量存儲空間§7.7記錄的存儲與維護2/6/202336變長記錄的存儲方法之三(2)：指針法用一系列通過指針鏈接起來的定長記錄來表示一個變長記錄；優(yōu)點：與定長記錄類似，變長記錄是一個鏈表；缺點：引入額外結(jié)構(gòu)，浪費存儲空間?！?.7記錄的存儲與維護2/6/202337變長記錄的存儲方法之三(3)：錨塊-溢出塊表示法指針法的變形；文件使用兩種不同的物理塊：錨塊：包含記錄的定長部分和變長部分的第一個分量的塊；溢出塊：包含記錄的變長部分除第一個分量以外的其他分量的塊?！?.7記錄的存儲與維護2/6/202338記錄的存儲結(jié)構(gòu)定長記錄記錄的字段數(shù)是固定的每個字段都是定長的應(yīng)存放在數(shù)據(jù)字典里偏移量§7.7記錄的存儲與維護2/6/202339記錄的存儲結(jié)構(gòu)變長記錄記錄的字段數(shù)是固定的某些字段是變長的基地址分槽頁結(jié)構(gòu)的偏移量1、如何定位某個字段？2、如何處理空值NULL？§7.7記錄的存儲與維護2/6/202340舉例SQLServer的數(shù)據(jù)行，即記錄的結(jié)構(gòu)定長記錄與變長記錄中字段組織方式的結(jié)合§7.7記錄的存儲與維護2/6/202341SQLServer的數(shù)據(jù)行結(jié)構(gòu)§7.7記錄的存儲與維護2/6/202342SQLServer的數(shù)據(jù)行結(jié)構(gòu)狀態(tài)位A，即TagA：位0：版本信息，在SQLServer2000中該位總是0。位1到位3：作為一個3位的值對待0表示該行是一個基本的記錄；1表示該行是一個轉(zhuǎn)向記錄；2表示該行是一個轉(zhuǎn)向存根；3表示該行是一個索引記錄；4表示該行是一塊碎片；5表示該行是一個幽靈索引記錄；6表示該行是一個幽靈數(shù)據(jù)記錄。§7.7記錄的存儲與維護2/6/202343SQLServer的數(shù)據(jù)行結(jié)構(gòu)狀態(tài)位A，即TagA：位4：表示NULL位圖的存在性；在SQLServer2000中，即使任何列都不允許NULL值，NULL位圖也總要出現(xiàn)；位4的值總為1；NULL位圖能有效地解決空值、空串的問題。位5：表示行中是否存在變長列。位6和位7：在SQLServer2000中未被使用?！?.7記錄的存儲與維護2/6/202344SQLServer的數(shù)據(jù)行結(jié)構(gòu)列偏移數(shù)組：一個兩字節(jié)的條目，表示變長列在行中結(jié)束的位置。在行的定長或變長數(shù)據(jù)塊內(nèi)，SQLServer按照創(chuàng)建表時定義的列順序來存儲數(shù)據(jù)；這個表的行的定長數(shù)據(jù)部分包括Col1的數(shù)據(jù)，后跟Col2和Col4的數(shù)據(jù)；行的變長數(shù)據(jù)部分包括Col3的數(shù)據(jù)，后跟Col5的數(shù)據(jù)?！?.7記錄的存儲與維護2/6/202345§7.8文件中記錄的組織在文件中組織記錄的常用方法堆積的方法排順的方法哈希的方法簇集的方法層次組織法(B樹類文件組織，下章索引介紹)堆文件組織一條記錄可以放在文件中的任何地方，只要那個地方有空間存放這條記錄；記錄是沒有順序的，是堆積起來的。2/6/202346§7.8文件中記錄的組織散列文件組織對文件中每個記錄的同一屬性或?qū)傩约枰嬎阋粋€散列(Hash)函數(shù)；散列函數(shù)的結(jié)果確定了記錄應(yīng)該存儲到文件的哪個物理塊中；記錄雖然沒有順序，但是有去向的！2/6/202347§7.8文件中記錄的組織順序文件組織根據(jù)搜索碼值的順序來邏輯存儲記錄；搜索碼是用于在文件中查找記錄的屬性或?qū)傩约?，與碼的概念完全不同！為了快速地按搜索碼獲取記錄，通過指針把記錄鏈接起來，每個記錄的指針都指向在搜索碼順序上的下一個記錄；同時，為了減少順序文件處理中物理塊的訪問次數(shù)，在物理上也按搜索碼值的順序存儲記錄，或盡可能地按照搜索碼值的順序來物理存儲。2/6/202348§7.8文件中記錄的組織順序文件組織順序文件組織的好處：結(jié)構(gòu)清晰，容易理解；對特定的查詢能快速處理。順序文件組織的問題：插入和刪除記錄后，首先要保證記錄按搜索碼的順序重新鏈接起來，但是維護記錄的物理順序則將十分困難；如果靠移動記錄的方式來維護記錄在物理上的順序，則代價十分昂貴！2/6/202349§7.8文件中記錄的組織順序文件的維護刪除記錄：用指針鏈表來管理刪除。插入記錄：首先定位要插入的記錄按搜索碼值排序時它前面那條記錄；如果該記錄所在的物理塊內(nèi)有空閑空間，就在這個塊中插入該記錄；否則，將插入到溢出塊中；如果溢出塊中的記錄不多，則這種方式還有效；但記錄的搜索碼順序和物理順序之間的一致性……這時，對記錄的順序處理將明顯變得效率低下（隨機I/O），需要對文件進行重組：時機和代價。2/6/202350SQLSERVER行偏移數(shù)組指出了頁中各記錄的邏輯順序；記錄的物理順序與其邏輯順序不必完全一致！§7.8文件中記錄的組織頁頭：96字節(jié)數(shù)據(jù)行，即記錄176行偏移數(shù)組095Mianus(96)Downtown(136)Brighton(176)Downtown(216)13621696

3210頁號：010槽號在物理上也按搜索碼順序存儲記錄，或盡可能地按照搜索碼順序物理存儲：①不同的頁之間：009（A）、010（B-M）、011（N-Z）；②同一頁之間；③溢出頁：012(A)。在SQLServer中搜索碼鏈表就是行偏移數(shù)組2/6/202351§7.8文件中記錄的組織行偏移數(shù)組可以表示行的邏輯順序，與行的物理順序不同；舉例：sp_helpstudentselect*fromstudentDBCCTRACEON(3604)GODBCCPAGE(DB_Teaching,1,132,1)GO2/6/202352§7.8文件中記錄的組織數(shù)據(jù)行在頁中的真實情況2/6/202353§7.8文件中記錄的組織簇集文件組織問題的提出：假設(shè)有兩個關(guān)系course和selecting，對于它們的自然連接運算，用SQL表達如下：selectstudent_number,course_name,course_locationfromcourse,selectingwherecourse.course_name=selecting.course_name2/6/202354§7.8文件中記錄的組織簇集文件組織問題的解決：把相關(guān)記錄放在一個塊(或臨近塊)中存儲，一次讀塊操作就取得所有相關(guān)記錄；減少了磁盤I/O次數(shù)，提高了連接的性能。2/6/202355§7.8文件中記錄的組織簇集文件組織簇集的定義：把有關(guān)記錄按簇集鍵值集中在一個物理塊內(nèi)或物理上相鄰的區(qū)域內(nèi)，以提高某些查詢的速度。簇集的缺點：如果改用其他屬性或?qū)傩约龃丶I，將引起所有記錄的移動；如果一個記錄的簇集鍵值修改了，則這個記錄也要做相應(yīng)的移動；如果不是針對簇集設(shè)計的查詢，而