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

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

student_number:char(10);

student_name:char(8);

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

teacher_name:char(22);

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

course_capacity:int;endend

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

3210頁號(hào)：010槽號(hào)在物理上也按搜索碼順序存儲(chǔ)記錄，或盡可能地按照搜索碼順序物理存儲(chǔ)：①不同的頁之間：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ù)行在頁中的真實(shí)情況2/6/202353§7.8文件中記錄的組織簇集文件組織問題的提出：假設(shè)有兩個(gè)關(guān)系course和selecting，對(duì)于它們的自然連接運(yùn)算，用SQL表達(dá)如下：selectstudent_number,course_name,course_locationfromcourse,selectingwherecourse.course_name=selecting.course_name2/6/202354§7.8文件中記錄的組織簇集文件組織問題的解決：把相關(guān)記錄放在一個(gè)塊(或臨近塊)中存儲(chǔ)，一次讀塊操作就取得所有相關(guān)記錄；減少了磁盤I/O次數(shù)，提高了連接的性能。2/6/202355§7.8文件中記錄的組織簇集文件組織簇集的定義：把有關(guān)記錄按簇集鍵值集中在一個(gè)物理塊內(nèi)或物理上相鄰的區(qū)域內(nèi)，以提高某些查詢的速度。簇集的缺點(diǎn)：如果改用其他屬性或?qū)傩约龃丶I，將引起所有記錄的移動(dòng)；如果一個(gè)記錄的簇集鍵值修改了，則這個(gè)記錄也要做相應(yīng)的移動(dòng)；如果不是針對(duì)簇集設(shè)計(jì)的查詢，而