教學(xué)第6章-數(shù)據(jù)庫存儲(chǔ)技術(shù)課件

6.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)6.2文件組織6.3文件中記錄的組織6.4索引技術(shù)與散列技術(shù)第6章數(shù)據(jù)庫存儲(chǔ)技術(shù)6.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)第6章數(shù)據(jù)庫存儲(chǔ)技術(shù)6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)6.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)6.1數(shù)據(jù)庫的物理存儲(chǔ)介如圖6.1所示，計(jì)算機(jī)系統(tǒng)中的數(shù)據(jù)存儲(chǔ)是按照層次組織的。頂層是主存儲(chǔ)器，它是由高速緩存儲(chǔ)器和主存組合，提供數(shù)據(jù)的快速訪問；接下來是第二級(jí)存儲(chǔ)器，它是由磁盤等較慢的設(shè)備組成；第三級(jí)存儲(chǔ)器是最慢的存儲(chǔ)設(shè)備，如光盤和磁帶等。與同樣數(shù)量的磁盤相比，主存的價(jià)格昂貴得多，而磁帶卻比磁盤更便宜。因?yàn)閿?shù)據(jù)庫需要存儲(chǔ)大量的數(shù)據(jù)，所以像磁盤和磁帶這樣較慢的存儲(chǔ)設(shè)備在數(shù)據(jù)庫系統(tǒng)中具有重要地位。主要的存儲(chǔ)介質(zhì)有：6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)如圖6.1所示，計(jì)算機(jī)系統(tǒng)中的數(shù)據(jù)存儲(chǔ)是按照層次組織6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)CPU高速緩存主存磁帶磁盤數(shù)據(jù)請(qǐng)求滿足請(qǐng)求的數(shù)據(jù)主存儲(chǔ)器第二級(jí)存儲(chǔ)器第三級(jí)存儲(chǔ)器圖6.1存儲(chǔ)層次6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)CPU高速緩存主存磁帶磁盤1.高速緩存高速緩沖存儲(chǔ)器是最快最昂貴的存儲(chǔ)介質(zhì)。高速緩沖存儲(chǔ)器一般很小，它的使用由操作系統(tǒng)來管理。在數(shù)據(jù)庫系統(tǒng)中，我們將不考慮高速緩沖存儲(chǔ)器的存儲(chǔ)管理。2.主存主存又稱內(nèi)存或主存儲(chǔ)器，用于存放可被處理的數(shù)據(jù)，它是計(jì)算機(jī)機(jī)器指令執(zhí)行操作的地方。由于其存儲(chǔ)量?。ㄒ话阋訫B為單位）、成本高、存儲(chǔ)時(shí)間短，而且發(fā)生電源故障或者系統(tǒng)崩潰時(shí)，里面的內(nèi)容一般會(huì)丟失，因此它在數(shù)據(jù)庫中僅作為數(shù)據(jù)存儲(chǔ)的輔助實(shí)體，如作為工作區(qū)（workarea）(數(shù)據(jù)加工區(qū))、緩沖區(qū)（bufferarea）(磁盤與主存的交換區(qū))等。6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)1.高速緩存6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)3.快閃存儲(chǔ)器也叫電可擦可編程只讀存儲(chǔ)器（EEPROM）?？扉W存儲(chǔ)器不同于主存儲(chǔ)器的地方是在電源故障發(fā)生時(shí)數(shù)據(jù)可被保存下來。從快閃存儲(chǔ)器讀數(shù)據(jù)的時(shí)間小于100納秒，大致等于從主存儲(chǔ)器中讀數(shù)據(jù)的時(shí)間。然而，向快閃存儲(chǔ)器寫數(shù)據(jù)是非常復(fù)雜的——數(shù)據(jù)寫入一次，大約需要4~10微秒，而且數(shù)據(jù)不能被直接覆蓋。要想覆蓋已經(jīng)被寫過的快閃存儲(chǔ)器，必須一次性擦除整個(gè)快閃存儲(chǔ)器，然后它才可以再被寫入一次?？扉W存儲(chǔ)器的另一個(gè)缺點(diǎn)是它只支持有限的擦除次數(shù)，其范圍從10000~1百萬。在低成本計(jì)算機(jī)系統(tǒng)中，例如在嵌入至其他設(shè)備的計(jì)算機(jī)系統(tǒng)中，快閃存儲(chǔ)器作為磁盤的替代物來存儲(chǔ)少量數(shù)據(jù)（5MB~10MB）已經(jīng)非常流行。6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)3.快閃存儲(chǔ)器6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)4.磁盤磁盤存儲(chǔ)器又稱二級(jí)存儲(chǔ)器或次級(jí)存儲(chǔ)器。由于它存儲(chǔ)量大（一般以GB為單位），能長(zhǎng)期保存又有一定的存取速度且價(jià)格合理，因此早已成為數(shù)據(jù)庫真正存放數(shù)據(jù)的物理實(shí)體。通常整個(gè)數(shù)據(jù)庫都存儲(chǔ)在磁盤上。為了能夠訪問到數(shù)據(jù)，必須將數(shù)據(jù)從磁盤移到主存儲(chǔ)器。完成操作后，被修改的數(shù)據(jù)必須寫回磁盤。磁盤存儲(chǔ)器為直接存取存儲(chǔ)器，因?yàn)樵诖疟P上可以按任意順序讀取數(shù)據(jù)（與順序存取的存儲(chǔ)器不同）。在發(fā)生電源故障或者系統(tǒng)崩潰時(shí)，磁盤存儲(chǔ)器不會(huì)丟失數(shù)據(jù)。6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)4.磁盤6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)5.光盤光盤存儲(chǔ)器最流行的形式是只讀光盤（CD-ROM）。數(shù)據(jù)通過光學(xué)方法存儲(chǔ)在光盤上，并且可以被激光器讀取。用于CD-ROM存儲(chǔ)器的光盤是不可寫的，但是可以提供預(yù)先記錄的數(shù)據(jù)，并且可以裝入驅(qū)動(dòng)器或從驅(qū)動(dòng)器中移走。另一種光盤存儲(chǔ)器是“一次寫，多次讀”（WORM）光盤，它允許寫入數(shù)據(jù)一次，但是不允許擦除和重寫這些數(shù)據(jù)。這種介質(zhì)用于數(shù)據(jù)的歸檔存儲(chǔ)。此外還有磁光結(jié)合的存儲(chǔ)設(shè)備，可使用光學(xué)方法讀取以磁方法編碼的數(shù)據(jù)，并且允許對(duì)舊數(shù)據(jù)進(jìn)行覆蓋。6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)5.光盤6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)6.磁帶磁帶具有較大的容量（從GB到TB），價(jià)格便宜并可以脫機(jī)存放。因?yàn)榇艓П仨殢念^順序存取，是一種順序存取存儲(chǔ)器，因此數(shù)據(jù)存取也比磁盤慢的多。磁帶一般用于存儲(chǔ)磁盤或主存中的拷貝數(shù)據(jù)，它是一種輔助存儲(chǔ)設(shè)備，也稱為三級(jí)存儲(chǔ)器。6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)6.磁帶6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)由于磁盤是數(shù)據(jù)庫數(shù)據(jù)存儲(chǔ)的主要物理存儲(chǔ)體，因此本節(jié)主要介紹磁盤及其結(jié)構(gòu)。磁盤為現(xiàn)代計(jì)算機(jī)系統(tǒng)提供了大容量的輔助存儲(chǔ)，其存儲(chǔ)容量極大，大約在幾個(gè)GB到幾十個(gè)GB，甚至幾百個(gè)GB之間。一個(gè)典型的大型商業(yè)數(shù)據(jù)庫需要數(shù)百個(gè)磁盤。磁盤結(jié)構(gòu)如圖所示。6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)由于磁盤是數(shù)據(jù)庫數(shù)據(jù)6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)磁盤存儲(chǔ)器由磁盤盤片與磁盤驅(qū)動(dòng)器兩部分組成。1.磁盤盤片磁盤盤片是一種扁平的圓盤。它的兩個(gè)表面都覆蓋著磁性物質(zhì)，信息就記錄在表面上。盤片由硬金屬或玻璃制成，被磁性物質(zhì)覆蓋（通常是兩面）。盤片的表面被邏輯地劃分為磁道(track)，磁道又被劃分為扇區(qū)（sector），它又稱磁盤塊（block），磁盤塊是從磁盤讀出和寫入信息的最小單位。根據(jù)磁盤的不同類型，一個(gè)扇區(qū)的大小可從32~4096字節(jié)不等，但通常是512字節(jié)。每個(gè)磁道有4~32個(gè)扇區(qū)，每個(gè)盤片表面有20~1500個(gè)磁道。一個(gè)磁盤存儲(chǔ)器往往由若干個(gè)盤片（6~11片）組成一個(gè)盤片組，固定在一個(gè)主軸上，以每個(gè)盤片磁道為注視點(diǎn)可以構(gòu)成一個(gè)無形的同心圓柱體，從內(nèi)到外層層相套。每個(gè)圓柱體從上到下有若干個(gè)磁道圍繞其上。6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)磁盤存儲(chǔ)器由磁盤盤片與磁盤驅(qū)6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)2.磁盤驅(qū)動(dòng)器磁盤驅(qū)動(dòng)器由活動(dòng)臂、讀寫頭等組成。每個(gè)盤面有兩個(gè)臂，分別對(duì)應(yīng)上、下兩面，每個(gè)臂的盡頭是一個(gè)讀/寫頭（或稱磁頭），用它可以讀?。ɑ?qū)懭耄┍P片中的數(shù)據(jù)。一個(gè)由n個(gè)磁盤片所組成的盤片組對(duì)應(yīng)有2n個(gè)活動(dòng)臂，它們組合在一起構(gòu)成臂組合件，這種組合件可以自由伸縮活動(dòng)，它以磁道為單位向前推進(jìn)或向后退縮，用它可以對(duì)磁道定位，由于它是組合方式以全體活動(dòng)臂為單位作進(jìn)退，因此它的推進(jìn)或后退實(shí)際上是對(duì)圓柱體定位。6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)2.磁盤驅(qū)動(dòng)器6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)3.磁盤存儲(chǔ)器一個(gè)磁盤存儲(chǔ)器是由盤片組以及磁盤驅(qū)動(dòng)器組成，其中盤片組以軸為核心作不間斷的旋轉(zhuǎn)，速度以60、90、120或150轉(zhuǎn)不等，而活動(dòng)臂組合件則以圓柱體為單位做前進(jìn)或后退操作。這樣，一個(gè)磁盤存儲(chǔ)器上的任何一個(gè)磁盤塊都可由下面三個(gè)部分定位。（1）圓柱體號(hào)：確定圓柱體（由活動(dòng)臂移動(dòng)定位）。（2）讀/寫頭號(hào)：確定圓柱體中磁道（由選擇組合件中活動(dòng)臂定位）。（3）磁盤塊號(hào)：確定磁道中的盤塊號(hào)（由盤片組旋轉(zhuǎn)定位）。6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)3.磁盤存儲(chǔ)器6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)4.磁盤存儲(chǔ)器的I/O操作為進(jìn)行有效管理，系統(tǒng)對(duì)磁盤作統(tǒng)一編址，編址按圓柱體號(hào)、磁道號(hào)及盤塊號(hào)編碼，編碼規(guī)則如下：（1）圓柱體號(hào)：設(shè)有n個(gè)圓柱體，則編號(hào)自柱面的外層至內(nèi)層，從0~n-1。（2）磁道號(hào)：設(shè)一個(gè)圓柱體有m個(gè)磁道，則磁道號(hào)統(tǒng)一編碼從上到下順序編號(hào)，從0~nm-1個(gè)。（3）磁盤塊號(hào)：設(shè)一個(gè)磁道有r個(gè)盤塊，則磁盤塊號(hào)也是統(tǒng)一編碼，從0~nmr-1個(gè)。6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)4.磁盤存儲(chǔ)器的I/O操作6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)磁盤在投入使用前都要進(jìn)行格式化，目的是在各盤塊的頭部加注該塊地址，包括該塊所在的圓柱體號(hào)，讀/寫頭號(hào)，盤塊號(hào)以及某些狀態(tài)標(biāo)志。在具體操作時(shí)用戶給出磁盤地址，此時(shí)活動(dòng)臂組合件作機(jī)械運(yùn)動(dòng)并定位于指定圓柱體，同時(shí)系統(tǒng)選擇指定的讀/寫頭以確定磁道，最終讀/寫頭跟蹤旋轉(zhuǎn)的磁道，并讀出旋轉(zhuǎn)時(shí)每磁盤塊的地址。當(dāng)用戶給出的地址與磁盤地址一致時(shí)則表示地址已找到，此時(shí)系統(tǒng)就將該地址中的數(shù)據(jù)讀入內(nèi)存中的磁盤緩沖區(qū)（或從磁盤緩沖區(qū)將數(shù)據(jù)寫入指定磁盤地址），這就完成了一次磁盤讀/寫操作或稱I/O操作。6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)磁盤在投入使用前都要6.2.1文件的定長(zhǎng)記錄6.2.2文件的變長(zhǎng)記錄6.2文件組織6.2.1文件的定長(zhǎng)記錄6.2文件組織一般在文件中的記錄都是有固定長(zhǎng)度的，這種長(zhǎng)度一般都由文件記錄型確定。例如某個(gè)關(guān)系模式“物資編碼表”：Wzbmb（Wzbm，Wzmc，Xhgg，Jldw，Price），它可以設(shè)計(jì)成一個(gè)定長(zhǎng)文件。文件中的各個(gè)記錄定義如下：

TYPEWzbmb-TYPE=RECORDWzbm：VARCHAR2（6）；Wzmc：VARCHAR2（16）；Xhgg：VARCHAR2（16）；Jldw：VARCHAR2（6）；Price：NUMBER（8，2）；END

如果假設(shè)每個(gè)字符占1個(gè)字節(jié)，那么每個(gè)Wzbmb記錄定長(zhǎng)為52個(gè)字節(jié)。6.2.1文件的定長(zhǎng)記錄一般在文件中的記錄都是有固定長(zhǎng)度的，這種長(zhǎng)度一般都由文件中的記錄有時(shí)其長(zhǎng)度是可以變化的，變長(zhǎng)記錄出現(xiàn)在數(shù)據(jù)庫系統(tǒng)中的下述情況中：（1）多種記錄型在一個(gè)文件中存儲(chǔ)。（2）記錄型允許一個(gè)或多個(gè)字段是變長(zhǎng)的。（3）記錄型允許可重復(fù)的字段。6.2.2文件的變長(zhǎng)記錄文件中的記錄有時(shí)其長(zhǎng)度是可以變化的，變長(zhǎng)記錄出現(xiàn)在數(shù)

6.2.2文件的變長(zhǎng)記錄例如，把6.2.1中的關(guān)系模式作如下文件結(jié)構(gòu)定義：TYPEWzbmb-LIST=RECORDWzmc：VARCHAR2（16）；Wzbm-INFO：ARRAY[1，]OFRECORDWzbm：VARCHAR2（6）；Xhgg：VARCHAR2（16）；Jldw：VARCHAR2（6）；Price：NUMBER（8,2）；ENDEND

6.2.2文件的變長(zhǎng)記錄例如，把6.2.1中的關(guān)系模式作如變長(zhǎng)記錄的表示有兩種形式：（1）字節(jié)流實(shí)現(xiàn)變長(zhǎng)記錄的一個(gè)簡(jiǎn)單方法是在每個(gè)記錄的末尾附加一個(gè)特殊的記錄終止符號(hào)，這樣可以把每個(gè)記錄作為一個(gè)連續(xù)的字節(jié)流來存儲(chǔ)。另一種字節(jié)流表示方法是在每個(gè)記錄的開始處存儲(chǔ)記錄的長(zhǎng)度，而不再使用記錄終止符號(hào)。（2）定長(zhǎng)的表示方法另一種在文件系統(tǒng)中有效實(shí)現(xiàn)變長(zhǎng)記錄的方法是使用一個(gè)或多個(gè)定長(zhǎng)記錄來代表一個(gè)變長(zhǎng)記錄。6.2.2文件的變長(zhǎng)記錄變長(zhǎng)記錄的表示有兩種形式：6.2.2文件的變長(zhǎng)記錄使用定長(zhǎng)記錄實(shí)現(xiàn)變長(zhǎng)記錄文件的技術(shù)有兩種：①保留空間。如果設(shè)置一個(gè)永遠(yuǎn)不會(huì)被超過的最大記錄長(zhǎng)度，我們就可以使用長(zhǎng)度為這個(gè)最大記錄長(zhǎng)度的定長(zhǎng)記錄。如對(duì)那些比最大空間短的記錄，則未使用的空間用特殊的空值或記錄終結(jié)符號(hào)來填充。②指針。變長(zhǎng)記錄用一系列通過指針鏈接起來的定長(zhǎng)記錄來表示。在該形式中，每個(gè)定長(zhǎng)記錄后加一個(gè)指針字段，該字段指出是否有指針以及如果有指針則給出下一個(gè)定長(zhǎng)記錄的地址，這種方法即是用若干個(gè)定長(zhǎng)記錄來拼成一個(gè)變長(zhǎng)記錄。6.2.2文件的變長(zhǎng)記錄使用定長(zhǎng)記錄實(shí)現(xiàn)變長(zhǎng)記錄文件的技術(shù)有兩種：6.2.2文件的一般的記錄組織有如下幾種方式:1.堆文件組織（heapfile）在這種組織方式中，一條記錄可以放在文件中的任何地方，只要那個(gè)地方有空間存放這條記錄。記錄是沒有順序的。通常一個(gè)關(guān)系是一個(gè)單獨(dú)的文件。2.順序文件組織（sequentialfile）順序文件是為了高效處理按搜索碼排序的記錄而設(shè)計(jì)的。為了快速地按搜索碼獲取記錄，在這種文件中每個(gè)記錄增加一個(gè)指針字段，通過指針把記錄鏈接起來。每個(gè)記錄的指針指向在搜索碼順序上的下一個(gè)記錄。此外，為了減少順序文件處理中的塊訪問的次數(shù)，我們?cè)谖锢砩习此阉鞔a順序或盡可能的按搜索碼順序存儲(chǔ)記錄。6.3文件中記錄的組織一般的記錄組織有如下幾種方式:6.3文件中記錄的組3.散列文件組織（hashingfile）在這種組織方式中，對(duì)各個(gè)記錄的同一屬性計(jì)算一個(gè)散列函數(shù)。散列函數(shù)的結(jié)果作為記錄的存儲(chǔ)地址（即塊號(hào)）。4.聚集文件組織（clusteringfile）很多關(guān)系數(shù)據(jù)庫系統(tǒng)將各個(gè)關(guān)系存儲(chǔ)在一個(gè)個(gè)獨(dú)立的文件中，不同關(guān)系中有聯(lián)系的數(shù)據(jù)是通過關(guān)系間的聯(lián)接操作得到的，但是當(dāng)數(shù)據(jù)的數(shù)量比較大時(shí)，這種方法速度會(huì)很慢。而在聚集文件組織方式中，一個(gè)文件可以存儲(chǔ)多個(gè)關(guān)系的記錄，不同關(guān)系中有聯(lián)系的記錄存儲(chǔ)在一起可以提高查找速度。6.3文件中記錄的組織3.散列文件組織（hashingfile）6.3例如設(shè)物資管理系統(tǒng)中關(guān)系R1和R3中有下面的查詢：SELECTR1.Dwbm，R1.Dwmc，R3.Wzbm，R3.Qls，R3.SfsFROMR1，R3WHERER1.Dwbm=R3.Dwbm當(dāng)關(guān)系R1和R3數(shù)量很大時(shí)，要做聯(lián)接的查詢速度是比較慢的。但是如果把R1和R3放在一個(gè)聚集文件中，那么在讀單位信息時(shí)能夠同時(shí)把單位領(lǐng)料編碼以及領(lǐng)料數(shù)量一起讀入。圖6.4為一個(gè)聚集文件的例子。6.3文件中記錄的組織例如設(shè)物資管理系統(tǒng)中關(guān)系R1和R3中有下面的查詢：6.3文6.3文件中記錄的組織DwbmDwmcDwbmWzbmRqQlsSfs0101一分廠一車間01010201012002/12/01550102一分廠二車間01010104012002/12/011080221二分廠生產(chǎn)科01010101012002/12/02202001010201022002/12/025501010201012002/12/02101001020103012002/12/028801020201012002/12/023302210202012002/12/022015（a）關(guān)系R1（b）關(guān)系R36.3文件中記錄的組織DwbmDwmcDwbmWzbmRq6.3文件中記錄的組織0101一分廠一車間010101010101010101010201010104010101010201020201012002/12/012002/12/012002/12/022002/12/022002/12/025102051058205100102一分廠二車間010201020103010201012002/12/022002/12/0283830221二分廠生產(chǎn)科02210202012002/12/022015（c）聚集文件圖6.4聚集文件示例6.3文件中記錄的組織0101一分廠一車間010102016.4.1文件的定長(zhǎng)記錄6.4.2文件的變長(zhǎng)記錄6.4.3散列技術(shù)6.4索引技術(shù)與散列技術(shù)6.4.1文件的定長(zhǎng)記錄6.4索引技術(shù)與散列技術(shù)在索引技術(shù)中對(duì)文件（一般用順序文件）的查找采用類似書刊中目錄的方法，即對(duì)文件中記錄的指定項(xiàng)（稱索引項(xiàng)）的項(xiàng)值給出其記錄的地址，它們稱索引，索引一般也用文件表示，其結(jié)構(gòu)如圖6.4所示:6.4.1索引技術(shù)索引項(xiàng)值對(duì)應(yīng)記錄地址

因此，索引技術(shù)中一個(gè)索引文件一般由主文件與索引兩部分組成，其中主文件存放數(shù)據(jù)，而索引則存放數(shù)據(jù)地址。圖6.5索引結(jié)構(gòu)在索引技術(shù)中對(duì)文件（一般用順序文件）的查找采用類似書主索引主索引是索引中最常用的一種，它一般可以分為以下三類：（1）稠密索引所謂稠密索引（denseindex）是指對(duì)主文件索引項(xiàng)的每個(gè)“項(xiàng)值”建立一個(gè)索引項(xiàng)值，即索引記錄包括索引項(xiàng)中的所有項(xiàng)值以及指向該值的記錄鏈表中第一個(gè)記錄的指針，圖6.5給出了稠密索引的一個(gè)例子。6.4.1索引技術(shù)主索引主索引是索引中最常用的一種，它一般可以分為以下三類：（2）稀疏索引稀疏索引（sparseindex）是指只對(duì)主文件索引項(xiàng)的部分項(xiàng)值建立索引記錄，這些部分項(xiàng)值的選擇具有一定的稀疏特征，即每隔一定距離選擇一個(gè)。每個(gè)索引記錄也包括一個(gè)項(xiàng)值和指向該項(xiàng)值的第一個(gè)數(shù)據(jù)記錄的指針。（3）多級(jí)索引當(dāng)索引本身數(shù)量很大時(shí)，還有一種辦法是采用多級(jí)索引，即對(duì)索引本身采用索引。圖6.7給出了二級(jí)索引的例子。6.4.1索引技術(shù)（2）稀疏索引稀疏索引（sparseindex）是指只對(duì)主6.4.1索引技術(shù)

索引主文件圖6.5稠密索引示例

70Wzbm指針

WzbmWzmcJldwPrice010101010101鈹銅合金Kg010301010301鉛銻合金Kg010401010401鋯鎂合金Kg02010102010125銅管材根02010202010220銅管材根02020102020125鋁管材根02020202020210鋁管材根608090120010008006.4.1索引技術(shù)索引6.4.1索引技術(shù)6.4.1索引技術(shù)2.輔助索引由于主索引中具有相同索引項(xiàng)值的記錄在同一地址或相鄰地址中，因而查找速度慢，有時(shí)還需要使用輔助索引。采用輔助索引查找速度快，一般采用下面的方法：即仍采用索引記錄（索引項(xiàng)值與對(duì)應(yīng)的指針），不過此時(shí)指針指向的不是主文件記錄地址而是指向一個(gè)桶（bucket），桶內(nèi)存放指向具有同一索引項(xiàng)值的指針。如在前稀疏索引示例中，建立以Jldw為索引項(xiàng)的輔助索引。如圖6.8所示，在這種結(jié)構(gòu)中，以輔助索引為中介，可以通過二層指針方便地查到對(duì)應(yīng)的主文件地址。6.4.1索引技術(shù)2.輔助索引6.4.1索引技術(shù)1.B+樹的結(jié)構(gòu)B+樹索引是一個(gè)多級(jí)索引，但是其結(jié)構(gòu)不同于多級(jí)索引順序文件。B+樹的索引結(jié)構(gòu)是樹的形式，最上一級(jí)索引是樹的根結(jié)點(diǎn)，最下一級(jí)索引是樹的葉結(jié)點(diǎn)。該級(jí)索引指針指向主文件的記錄地址，一般采用稠密索引；而非葉的其他結(jié)點(diǎn)（包括根結(jié)點(diǎn)）的索引指向下一級(jí)結(jié)點(diǎn)的地址，一般為稀疏索引。6.4.2B+樹索引文件1.B+樹的結(jié)構(gòu)6.4.2B+樹索引文件6.4.2B+樹索引文件6.4.2B+樹索引文件6.4.2B+樹索引文件6.4.2B+樹索引文件典型的B+樹結(jié)點(diǎn)結(jié)構(gòu)如圖6.9所示，其中P為指針，K為索引項(xiàng)值，每個(gè)結(jié)點(diǎn)中的索引項(xiàng)值按次序存放，即如果i<j，那么Ki<Kj。6.4.2B+樹索引文件P1K1P2K2

…PiKi

…Pn-1Kn-1Pn圖6.9典型的B樹結(jié)點(diǎn)

各葉結(jié)點(diǎn)中值的范圍互不相交。因此，如果Li和Lj是兩個(gè)葉結(jié)點(diǎn)，且i<j，那么Li中所有的索引項(xiàng)值都小于Lj中的所有索引項(xiàng)值。既然葉結(jié)點(diǎn)指針指向主文件的記錄地址，因此如要使葉結(jié)點(diǎn)是稠密索引，則每個(gè)索引項(xiàng)值都必須出現(xiàn)在某個(gè)葉結(jié)點(diǎn)中。在葉結(jié)點(diǎn)中指針Pn的作用是把葉結(jié)點(diǎn)按索引項(xiàng)順序串在一起，即葉結(jié)點(diǎn)Li的Pn指向葉結(jié)點(diǎn)Li+1的第一個(gè)指針P1。典型的B+樹結(jié)點(diǎn)結(jié)構(gòu)如圖6.9所示，其中P為指針，K圖6.10給出了一個(gè)B+樹的例子，每個(gè)大寫字母代表索引項(xiàng)值。為簡(jiǎn)單起見，省略了空指針和指向主記錄的指針。6.4.2B+樹索引文件圖6.10給出了一個(gè)B+樹的例子，每個(gè)大寫字母代表索2.B樹上的查詢假設(shè)要查詢索引項(xiàng)值為K的所有記錄，查詢方法為：（1）檢查根結(jié)點(diǎn)，找到大于K的最小索引值，假設(shè)為K，那么順著P走到第二層結(jié)點(diǎn)。如果找不到這樣的值，就沿著P走到第二層結(jié)點(diǎn)。（2）在走到的第二層結(jié)點(diǎn)中用類似（1）的方法找到相應(yīng)指針并到達(dá)第三層。（3）如此重復(fù)，最終到達(dá)一個(gè)葉結(jié)點(diǎn)。如果該結(jié)點(diǎn)中有某個(gè)索引項(xiàng)值K等于K，那么指針P指向我們所需要的記錄，如果在該葉結(jié)點(diǎn)中找不到值K，則不存在索引項(xiàng)值為K的記錄。6.4.2B+樹索引文件2.B樹上的查詢6.4.2B+樹索引文件提高數(shù)據(jù)庫查找速度的另一種方法是散列（hash）技術(shù)。其基本原理是利用一種散列函數(shù)建立起主文件中指定項(xiàng)值與磁盤物理塊間的映射聯(lián)系，這樣只要給出指定項(xiàng)的值立即可通過散列函數(shù)得到其對(duì)應(yīng)的存儲(chǔ)物理塊地址。在對(duì)散列的描述中，將使用術(shù)語桶（bucket）來表示能存儲(chǔ)一條或多條記錄的一個(gè)存儲(chǔ)單位。通常一個(gè)桶就是一個(gè)磁盤塊，但也可能小于或者大于一個(gè)磁盤塊。形式化地，令K表示所有指定項(xiàng)值的集合，令B表示所有桶地址的集合，散列函數(shù)H就是一個(gè)從K到B的函數(shù)。我們用H表示散列函數(shù)。

6.4.3散列技術(shù)提高數(shù)據(jù)庫查找速度的另一種方法是散列（hash）技術(shù)散列技術(shù)的具體實(shí)現(xiàn)方法如下：（1）建立主文件的指定項(xiàng)K以及該項(xiàng)值的集合{K1，K2…Kn}。（2）建立磁盤物理存儲(chǔ)單位桶以及桶地址的集合{B1，B2…Bn}。（3）建立散列函數(shù)H（Ki），它建立主文件指定項(xiàng)的值與桶間的對(duì)應(yīng)關(guān)系，對(duì)應(yīng)一個(gè)Ki必通過H（Ki）找到惟一的一個(gè)桶地址。6.4.3散列技術(shù)散列技術(shù)的具體實(shí)現(xiàn)方法如下：6.4.3散列技術(shù)還可以將散列與索引相結(jié)合形成“散列索引”，從而使其效果更為有效。散列索引將索引項(xiàng)及相應(yīng)指針組織成散列文件結(jié)構(gòu)。散列索引的構(gòu)造如下：將散列函數(shù)作用于索引項(xiàng)以確定對(duì)應(yīng)的桶，然后將此索引項(xiàng)及相應(yīng)指針存入此桶中。例如，用圖6.6中的主文件建立散列索引。以Wzbm為指定項(xiàng)，首先建立索引記錄（見圖6.6），所用散列函數(shù)為Wzbm各位數(shù)字之和后模4。該散列索引有四個(gè)桶，每個(gè)桶大小為3（現(xiàn)實(shí)中索引的桶大小當(dāng)然會(huì)大的多）。經(jīng)計(jì)算建立起如圖6.12所示的一個(gè)散列索引。6.4.3散列技術(shù)還可以將散列與索引相結(jié)合形成“散列索引”，從而使其效6.4.3散列技術(shù)圖6.11索引散列示例6.4.3散列技術(shù)圖6.11索引散列示例6.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)6.2文件組織6.3文件中記錄的組織6.4索引技術(shù)與散列技術(shù)第6章數(shù)據(jù)庫存儲(chǔ)技術(shù)6.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)第6章數(shù)據(jù)庫存儲(chǔ)技術(shù)6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)6.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)6.1數(shù)據(jù)庫的物理存儲(chǔ)介如圖6.1所示，計(jì)算機(jī)系統(tǒng)中的數(shù)據(jù)存儲(chǔ)是按照層次組織的。頂層是主存儲(chǔ)器，它是由高速緩存儲(chǔ)器和主存組合，提供數(shù)據(jù)的快速訪問；接下來是第二級(jí)存儲(chǔ)器，它是由磁盤等較慢的設(shè)備組成；第三級(jí)存儲(chǔ)器是最慢的存儲(chǔ)設(shè)備，如光盤和磁帶等。與同樣數(shù)量的磁盤相比，主存的價(jià)格昂貴得多，而磁帶卻比磁盤更便宜。因?yàn)閿?shù)據(jù)庫需要存儲(chǔ)大量的數(shù)據(jù)，所以像磁盤和磁帶這樣較慢的存儲(chǔ)設(shè)備在數(shù)據(jù)庫系統(tǒng)中具有重要地位。主要的存儲(chǔ)介質(zhì)有：6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)如圖6.1所示，計(jì)算機(jī)系統(tǒng)中的數(shù)據(jù)存儲(chǔ)是按照層次組織6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)CPU高速緩存主存磁帶磁盤數(shù)據(jù)請(qǐng)求滿足請(qǐng)求的數(shù)據(jù)主存儲(chǔ)器第二級(jí)存儲(chǔ)器第三級(jí)存儲(chǔ)器圖6.1存儲(chǔ)層次6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)CPU高速緩存主存磁帶磁盤1.高速緩存高速緩沖存儲(chǔ)器是最快最昂貴的存儲(chǔ)介質(zhì)。高速緩沖存儲(chǔ)器一般很小，它的使用由操作系統(tǒng)來管理。在數(shù)據(jù)庫系統(tǒng)中，我們將不考慮高速緩沖存儲(chǔ)器的存儲(chǔ)管理。2.主存主存又稱內(nèi)存或主存儲(chǔ)器，用于存放可被處理的數(shù)據(jù)，它是計(jì)算機(jī)機(jī)器指令執(zhí)行操作的地方。由于其存儲(chǔ)量?。ㄒ话阋訫B為單位）、成本高、存儲(chǔ)時(shí)間短，而且發(fā)生電源故障或者系統(tǒng)崩潰時(shí)，里面的內(nèi)容一般會(huì)丟失，因此它在數(shù)據(jù)庫中僅作為數(shù)據(jù)存儲(chǔ)的輔助實(shí)體，如作為工作區(qū)（workarea）(數(shù)據(jù)加工區(qū))、緩沖區(qū)（bufferarea）(磁盤與主存的交換區(qū))等。6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)1.高速緩存6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)3.快閃存儲(chǔ)器也叫電可擦可編程只讀存儲(chǔ)器（EEPROM）?？扉W存儲(chǔ)器不同于主存儲(chǔ)器的地方是在電源故障發(fā)生時(shí)數(shù)據(jù)可被保存下來。從快閃存儲(chǔ)器讀數(shù)據(jù)的時(shí)間小于100納秒，大致等于從主存儲(chǔ)器中讀數(shù)據(jù)的時(shí)間。然而，向快閃存儲(chǔ)器寫數(shù)據(jù)是非常復(fù)雜的——數(shù)據(jù)寫入一次，大約需要4~10微秒，而且數(shù)據(jù)不能被直接覆蓋。要想覆蓋已經(jīng)被寫過的快閃存儲(chǔ)器，必須一次性擦除整個(gè)快閃存儲(chǔ)器，然后它才可以再被寫入一次?？扉W存儲(chǔ)器的另一個(gè)缺點(diǎn)是它只支持有限的擦除次數(shù)，其范圍從10000~1百萬。在低成本計(jì)算機(jī)系統(tǒng)中，例如在嵌入至其他設(shè)備的計(jì)算機(jī)系統(tǒng)中，快閃存儲(chǔ)器作為磁盤的替代物來存儲(chǔ)少量數(shù)據(jù)（5MB~10MB）已經(jīng)非常流行。6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)3.快閃存儲(chǔ)器6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)4.磁盤磁盤存儲(chǔ)器又稱二級(jí)存儲(chǔ)器或次級(jí)存儲(chǔ)器。由于它存儲(chǔ)量大（一般以GB為單位），能長(zhǎng)期保存又有一定的存取速度且價(jià)格合理，因此早已成為數(shù)據(jù)庫真正存放數(shù)據(jù)的物理實(shí)體。通常整個(gè)數(shù)據(jù)庫都存儲(chǔ)在磁盤上。為了能夠訪問到數(shù)據(jù)，必須將數(shù)據(jù)從磁盤移到主存儲(chǔ)器。完成操作后，被修改的數(shù)據(jù)必須寫回磁盤。磁盤存儲(chǔ)器為直接存取存儲(chǔ)器，因?yàn)樵诖疟P上可以按任意順序讀取數(shù)據(jù)（與順序存取的存儲(chǔ)器不同）。在發(fā)生電源故障或者系統(tǒng)崩潰時(shí)，磁盤存儲(chǔ)器不會(huì)丟失數(shù)據(jù)。6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)4.磁盤6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)5.光盤光盤存儲(chǔ)器最流行的形式是只讀光盤（CD-ROM）。數(shù)據(jù)通過光學(xué)方法存儲(chǔ)在光盤上，并且可以被激光器讀取。用于CD-ROM存儲(chǔ)器的光盤是不可寫的，但是可以提供預(yù)先記錄的數(shù)據(jù)，并且可以裝入驅(qū)動(dòng)器或從驅(qū)動(dòng)器中移走。另一種光盤存儲(chǔ)器是“一次寫，多次讀”（WORM）光盤，它允許寫入數(shù)據(jù)一次，但是不允許擦除和重寫這些數(shù)據(jù)。這種介質(zhì)用于數(shù)據(jù)的歸檔存儲(chǔ)。此外還有磁光結(jié)合的存儲(chǔ)設(shè)備，可使用光學(xué)方法讀取以磁方法編碼的數(shù)據(jù)，并且允許對(duì)舊數(shù)據(jù)進(jìn)行覆蓋。6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)5.光盤6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)6.磁帶磁帶具有較大的容量（從GB到TB），價(jià)格便宜并可以脫機(jī)存放。因?yàn)榇艓П仨殢念^順序存取，是一種順序存取存儲(chǔ)器，因此數(shù)據(jù)存取也比磁盤慢的多。磁帶一般用于存儲(chǔ)磁盤或主存中的拷貝數(shù)據(jù)，它是一種輔助存儲(chǔ)設(shè)備，也稱為三級(jí)存儲(chǔ)器。6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)6.磁帶6.1.1數(shù)據(jù)庫的物理存儲(chǔ)介質(zhì)6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)由于磁盤是數(shù)據(jù)庫數(shù)據(jù)存儲(chǔ)的主要物理存儲(chǔ)體，因此本節(jié)主要介紹磁盤及其結(jié)構(gòu)。磁盤為現(xiàn)代計(jì)算機(jī)系統(tǒng)提供了大容量的輔助存儲(chǔ)，其存儲(chǔ)容量極大，大約在幾個(gè)GB到幾十個(gè)GB，甚至幾百個(gè)GB之間。一個(gè)典型的大型商業(yè)數(shù)據(jù)庫需要數(shù)百個(gè)磁盤。磁盤結(jié)構(gòu)如圖所示。6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)由于磁盤是數(shù)據(jù)庫數(shù)據(jù)6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)磁盤存儲(chǔ)器由磁盤盤片與磁盤驅(qū)動(dòng)器兩部分組成。1.磁盤盤片磁盤盤片是一種扁平的圓盤。它的兩個(gè)表面都覆蓋著磁性物質(zhì)，信息就記錄在表面上。盤片由硬金屬或玻璃制成，被磁性物質(zhì)覆蓋（通常是兩面）。盤片的表面被邏輯地劃分為磁道(track)，磁道又被劃分為扇區(qū)（sector），它又稱磁盤塊（block），磁盤塊是從磁盤讀出和寫入信息的最小單位。根據(jù)磁盤的不同類型，一個(gè)扇區(qū)的大小可從32~4096字節(jié)不等，但通常是512字節(jié)。每個(gè)磁道有4~32個(gè)扇區(qū)，每個(gè)盤片表面有20~1500個(gè)磁道。一個(gè)磁盤存儲(chǔ)器往往由若干個(gè)盤片（6~11片）組成一個(gè)盤片組，固定在一個(gè)主軸上，以每個(gè)盤片磁道為注視點(diǎn)可以構(gòu)成一個(gè)無形的同心圓柱體，從內(nèi)到外層層相套。每個(gè)圓柱體從上到下有若干個(gè)磁道圍繞其上。6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)磁盤存儲(chǔ)器由磁盤盤片與磁盤驅(qū)6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)2.磁盤驅(qū)動(dòng)器磁盤驅(qū)動(dòng)器由活動(dòng)臂、讀寫頭等組成。每個(gè)盤面有兩個(gè)臂，分別對(duì)應(yīng)上、下兩面，每個(gè)臂的盡頭是一個(gè)讀/寫頭（或稱磁頭），用它可以讀?。ɑ?qū)懭耄┍P片中的數(shù)據(jù)。一個(gè)由n個(gè)磁盤片所組成的盤片組對(duì)應(yīng)有2n個(gè)活動(dòng)臂，它們組合在一起構(gòu)成臂組合件，這種組合件可以自由伸縮活動(dòng)，它以磁道為單位向前推進(jìn)或向后退縮，用它可以對(duì)磁道定位，由于它是組合方式以全體活動(dòng)臂為單位作進(jìn)退，因此它的推進(jìn)或后退實(shí)際上是對(duì)圓柱體定位。6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)2.磁盤驅(qū)動(dòng)器6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)3.磁盤存儲(chǔ)器一個(gè)磁盤存儲(chǔ)器是由盤片組以及磁盤驅(qū)動(dòng)器組成，其中盤片組以軸為核心作不間斷的旋轉(zhuǎn)，速度以60、90、120或150轉(zhuǎn)不等，而活動(dòng)臂組合件則以圓柱體為單位做前進(jìn)或后退操作。這樣，一個(gè)磁盤存儲(chǔ)器上的任何一個(gè)磁盤塊都可由下面三個(gè)部分定位。（1）圓柱體號(hào)：確定圓柱體（由活動(dòng)臂移動(dòng)定位）。（2）讀/寫頭號(hào)：確定圓柱體中磁道（由選擇組合件中活動(dòng)臂定位）。（3）磁盤塊號(hào)：確定磁道中的盤塊號(hào)（由盤片組旋轉(zhuǎn)定位）。6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)3.磁盤存儲(chǔ)器6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)4.磁盤存儲(chǔ)器的I/O操作為進(jìn)行有效管理，系統(tǒng)對(duì)磁盤作統(tǒng)一編址，編址按圓柱體號(hào)、磁道號(hào)及盤塊號(hào)編碼，編碼規(guī)則如下：（1）圓柱體號(hào)：設(shè)有n個(gè)圓柱體，則編號(hào)自柱面的外層至內(nèi)層，從0~n-1。（2）磁道號(hào)：設(shè)一個(gè)圓柱體有m個(gè)磁道，則磁道號(hào)統(tǒng)一編碼從上到下順序編號(hào)，從0~nm-1個(gè)。（3）磁盤塊號(hào)：設(shè)一個(gè)磁道有r個(gè)盤塊，則磁盤塊號(hào)也是統(tǒng)一編碼，從0~nmr-1個(gè)。6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)4.磁盤存儲(chǔ)器的I/O操作6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)磁盤在投入使用前都要進(jìn)行格式化，目的是在各盤塊的頭部加注該塊地址，包括該塊所在的圓柱體號(hào)，讀/寫頭號(hào)，盤塊號(hào)以及某些狀態(tài)標(biāo)志。在具體操作時(shí)用戶給出磁盤地址，此時(shí)活動(dòng)臂組合件作機(jī)械運(yùn)動(dòng)并定位于指定圓柱體，同時(shí)系統(tǒng)選擇指定的讀/寫頭以確定磁道，最終讀/寫頭跟蹤旋轉(zhuǎn)的磁道，并讀出旋轉(zhuǎn)時(shí)每磁盤塊的地址。當(dāng)用戶給出的地址與磁盤地址一致時(shí)則表示地址已找到，此時(shí)系統(tǒng)就將該地址中的數(shù)據(jù)讀入內(nèi)存中的磁盤緩沖區(qū)（或從磁盤緩沖區(qū)將數(shù)據(jù)寫入指定磁盤地址），這就完成了一次磁盤讀/寫操作或稱I/O操作。6.1.2磁盤存儲(chǔ)器及其結(jié)構(gòu)磁盤在投入使用前都要6.2.1文件的定長(zhǎng)記錄6.2.2文件的變長(zhǎng)記錄6.2文件組織6.2.1文件的定長(zhǎng)記錄6.2文件組織一般在文件中的記錄都是有固定長(zhǎng)度的，這種長(zhǎng)度一般都由文件記錄型確定。例如某個(gè)關(guān)系模式“物資編碼表”：Wzbmb（Wzbm，Wzmc，Xhgg，Jldw，Price），它可以設(shè)計(jì)成一個(gè)定長(zhǎng)文件。文件中的各個(gè)記錄定義如下：

TYPEWzbmb-TYPE=RECORDWzbm：VARCHAR2（6）；Wzmc：VARCHAR2（16）；Xhgg：VARCHAR2（16）；Jldw：VARCHAR2（6）；Price：NUMBER（8，2）；END

如果假設(shè)每個(gè)字符占1個(gè)字節(jié)，那么每個(gè)Wzbmb記錄定長(zhǎng)為52個(gè)字節(jié)。6.2.1文件的定長(zhǎng)記錄一般在文件中的記錄都是有固定長(zhǎng)度的，這種長(zhǎng)度一般都由文件中的記錄有時(shí)其長(zhǎng)度是可以變化的，變長(zhǎng)記錄出現(xiàn)在數(shù)據(jù)庫系統(tǒng)中的下述情況中：（1）多種記錄型在一個(gè)文件中存儲(chǔ)。（2）記錄型允許一個(gè)或多個(gè)字段是變長(zhǎng)的。（3）記錄型允許可重復(fù)的字段。6.2.2文件的變長(zhǎng)記錄文件中的記錄有時(shí)其長(zhǎng)度是可以變化的，變長(zhǎng)記錄出現(xiàn)在數(shù)

6.2.2文件的變長(zhǎng)記錄例如，把6.2.1中的關(guān)系模式作如下文件結(jié)構(gòu)定義：TYPEWzbmb-LIST=RECORDWzmc：VARCHAR2（16）；Wzbm-INFO：ARRAY[1，]OFRECORDWzbm：VARCHAR2（6）；Xhgg：VARCHAR2（16）；Jldw：VARCHAR2（6）；Price：NUMBER（8,2）；ENDEND

6.2.2文件的變長(zhǎng)記錄例如，把6.2.1中的關(guān)系模式作如變長(zhǎng)記錄的表示有兩種形式：（1）字節(jié)流實(shí)現(xiàn)變長(zhǎng)記錄的一個(gè)簡(jiǎn)單方法是在每個(gè)記錄的末尾附加一個(gè)特殊的記錄終止符號(hào)，這樣可以把每個(gè)記錄作為一個(gè)連續(xù)的字節(jié)流來存儲(chǔ)。另一種字節(jié)流表示方法是在每個(gè)記錄的開始處存儲(chǔ)記錄的長(zhǎng)度，而不再使用記錄終止符號(hào)。（2）定長(zhǎng)的表示方法另一種在文件系統(tǒng)中有效實(shí)現(xiàn)變長(zhǎng)記錄的方法是使用一個(gè)或多個(gè)定長(zhǎng)記錄來代表一個(gè)變長(zhǎng)記錄。6.2.2文件的變長(zhǎng)記錄變長(zhǎng)記錄的表示有兩種形式：6.2.2文件的變長(zhǎng)記錄使用定長(zhǎng)記錄實(shí)現(xiàn)變長(zhǎng)記錄文件的技術(shù)有兩種：①保留空間。如果設(shè)置一個(gè)永遠(yuǎn)不會(huì)被超過的最大記錄長(zhǎng)度，我們就可以使用長(zhǎng)度為這個(gè)最大記錄長(zhǎng)度的定長(zhǎng)記錄。如對(duì)那些比最大空間短的記錄，則未使用的空間用特殊的空值或記錄終結(jié)符號(hào)來填充。②指針。變長(zhǎng)記錄用一系列通過指針鏈接起來的定長(zhǎng)記錄來表示。在該形式中，每個(gè)定長(zhǎng)記錄后加一個(gè)指針字段，該字段指出是否有指針以及如果有指針則給出下一個(gè)定長(zhǎng)記錄的地址，這種方法即是用若干個(gè)定長(zhǎng)記錄來拼成一個(gè)變長(zhǎng)記錄。6.2.2文件的變長(zhǎng)記錄使用定長(zhǎng)記錄實(shí)現(xiàn)變長(zhǎng)記錄文件的技術(shù)有兩種：6.2.2文件的一般的記錄組織有如下幾種方式:1.堆文件組織（heapfile）在這種組織方式中，一條記錄可以放在文件中的任何地方，只要那個(gè)地方有空間存放這條記錄。記錄是沒有順序的。通常一個(gè)關(guān)系是一個(gè)單獨(dú)的文件。2.順序文件組織（sequentialfile）順序文件是為了高效處理按搜索碼排序的記錄而設(shè)計(jì)的。為了快速地按搜索碼獲取記錄，在這種文件中每個(gè)記錄增加一個(gè)指針字段，通過指針把記錄鏈接起來。每個(gè)記錄的指針指向在搜索碼順序上的下一個(gè)記錄。此外，為了減少順序文件處理中的塊訪問的次數(shù)，我們?cè)谖锢砩习此阉鞔a順序或盡可能的按搜索碼順序存儲(chǔ)記錄。6.3文件中記錄的組織一般的記錄組織有如下幾種方式:6.3文件中記錄的組3.散列文件組織（hashingfile）在這種組織方式中，對(duì)各個(gè)記錄的同一屬性計(jì)算一個(gè)散列函數(shù)。散列函數(shù)的結(jié)果作為記錄的存儲(chǔ)地址（即塊號(hào)）。4.聚集文件組織（clusteringfile）很多關(guān)系數(shù)據(jù)庫系統(tǒng)將各個(gè)關(guān)系存儲(chǔ)在一個(gè)個(gè)獨(dú)立的文件中，不同關(guān)系中有聯(lián)系的數(shù)據(jù)是通過關(guān)系間的聯(lián)接操作得到的，但是當(dāng)數(shù)據(jù)的數(shù)量比較大時(shí)，這種方法速度會(huì)很慢。而在聚集文件組織方式中，一個(gè)文件可以存儲(chǔ)多個(gè)關(guān)系的記錄，不同關(guān)系中有聯(lián)系的記錄存儲(chǔ)在一起可以提高查找速度。6.3文件中記錄的組織3.散列文件組織（hashingfile）6.3例如設(shè)物資管理系統(tǒng)中關(guān)系R1和R3中有下面的查詢：SELECTR1.Dwbm，R1.Dwmc，R3.Wzbm，R3.Qls，R3.SfsFROMR1，R3WHERER1.Dwbm=R3.Dwbm當(dāng)關(guān)系R1和R3數(shù)量很大時(shí)，要做聯(lián)接的查詢速度是比較慢的。但是如果把R1和R3放在一個(gè)聚集文件中，那么在讀單位信息時(shí)能夠同時(shí)把單位領(lǐng)料編碼以及領(lǐng)料數(shù)量一起讀入。圖6.4為一個(gè)聚集文件的例子。6.3文件中記錄的組織例如設(shè)物資管理系統(tǒng)中關(guān)系R1和R3中有下面的查詢：6.3文6.3文件中記錄的組織DwbmDwmcDwbmWzbmRqQlsSfs0101一分廠一車間01010201012002/12/01550102一分廠二車間01010104012002/12/011080221二分廠生產(chǎn)科01010101012002/12/02202001010201022002/12/025501010201012002/12/02101001020103012002/12/028801020201012002/12/023302210202012002/12/022015（a）關(guān)系R1（b）關(guān)系R36.3文件中記錄的組織DwbmDwmcDwbmWzbmRq6.3文件中記錄的組織0101一分廠一車間010101010101010101010201010104010101010201020201012002/12/012002/12/012002/12/022002/12/022002/12/025102051058205100102一分廠二車間010201020103010201012002/12/022002/12/0283830221二分廠生產(chǎn)科02210202012002/12/022015（c）聚集文件圖6.4聚集文件示例6.3文件中記錄的組織0101一分廠一車間010102016.4.1文件的定長(zhǎng)記錄6.4.2文件的變長(zhǎng)記錄6.4.3散列技術(shù)6.4索引技術(shù)與散列技術(shù)6.4.1文件的定長(zhǎng)記錄6.4索引技術(shù)與散列技術(shù)在索引技術(shù)中對(duì)文件（一般用順序文件）的查找采用類似書刊中目錄的方法，即對(duì)文件中記錄的指定項(xiàng)（稱索引項(xiàng)）的項(xiàng)值給出其記錄的地址，它們稱索引，索引一般也用文件表示，其結(jié)構(gòu)如圖6.4所示:6.4.1索引技術(shù)索引項(xiàng)值對(duì)應(yīng)記錄地址

因此，索引技術(shù)中一個(gè)索引文件一般由主文件與索引兩部分組成，其中主文件存放數(shù)據(jù)，而索引則存放數(shù)據(jù)地址。圖6.5索引結(jié)構(gòu)在索引技術(shù)中對(duì)文件（一般用順序文件）的查找采用類似書主索引主索引是索引中最常用的一種，它一般可以分為以下三類：（1）稠密索引所謂稠密索引（denseindex）是指對(duì)主文件索引項(xiàng)的每個(gè)“項(xiàng)值”建立一個(gè)索引項(xiàng)值，即索引記錄包括索引項(xiàng)中的所有項(xiàng)值以及指向該值的記錄鏈表中第一個(gè)記錄的指針，圖6.5給出了稠密索引的一個(gè)例子。6.4.1索引技術(shù)主索引主索引是索引中最常用的一種，它一般可以分為以下三類：（2）稀疏索引稀疏索引（sparseindex）是指只對(duì)主文件索引項(xiàng)的部分項(xiàng)值建立索引記錄，這些部分項(xiàng)值的選擇具有一定的稀疏特征，即每隔一定距離選擇一個(gè)。每個(gè)索引記錄也包括一個(gè)項(xiàng)值和指向該項(xiàng)值的第一個(gè)數(shù)據(jù)記錄的指針。（3）多級(jí)索引當(dāng)索引本身數(shù)量很大時(shí)，還有一種辦法是采用多級(jí)索引，即對(duì)索引本身采用索引。圖6.7給出了二級(jí)索引的例子。6.4.1索引技術(shù)（2）稀疏索引稀疏索引（sparseindex）是指只對(duì)主6.4.1索引技術(shù)

索引主文件圖6.5稠密索引示例

70Wzbm指針

WzbmWzmcJldwPrice010101010101鈹銅合金Kg010301010301鉛銻合金Kg010401010401鋯鎂合金Kg02010102010125銅管材根02010202010220銅管材根02020102020125鋁管材根02020202020210鋁管材根608090120010008006.4.1索引技術(shù)索引6.4.1索引技術(shù)6.4.1索引技術(shù)2.輔助索引由于主索引中具有相同索引項(xiàng)值的記錄在同一地址或相鄰地址中，因而查找速度慢，有時(shí)還需要使用輔助索引。采用輔助索引查找速度快，一般采用下面的方法：即仍采用索引記錄（索引項(xiàng)值與對(duì)應(yīng)的指針），不過此時(shí)指針指向的不是主文件記錄地址而是指向一