數(shù)據庫系統(tǒng)設計與原理第Ⅱ部分數(shù)據存儲(第７章－第８章)1/15/20231第7章存儲結構和文件結構講課內容：主要介紹數(shù)據庫系統(tǒng)的底層存儲。包括存儲介質、數(shù)據庫文件的組織及結構、文件中記錄的組織及結構。■物理存儲介質■文件結構■磁盤■文件中記錄的組織■RAID

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

student_number:char(10);

student_name:char(8);

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

teacher_name:char(22);

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

course_capacity:int;endend

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