數(shù)據(jù)庫原理與開發(fā)技術(shù) 課件 6.2 文件組織

6.2文件組織本章主要內(nèi)容：（1）存儲器的種類：高速緩沖存儲器、主存儲器、

二級存儲器（磁盤）、三級存儲器（2）文件組織：定長記錄、可變長記錄（4）文件中記錄的組織：堆文件組織、順序文件組織、散列文件組織6.2文件組織一個數(shù)據(jù)庫被保存在一個或多個物理文件中，這些文件由底層的操作系統(tǒng)（OS）來維護。一個文件（file）在邏輯上組織成為記錄的一個序列。在數(shù)據(jù)庫系統(tǒng)中，數(shù)據(jù)庫管理系統(tǒng)（DBMS）通過操作系統(tǒng)（OS），讀寫硬盤上的數(shù)據(jù)與內(nèi)存進行交互，是按最小單位：塊（Block）來進行的。一個塊可以包含多個扇區(qū)。數(shù)據(jù)庫系統(tǒng)所說的塊與操作系統(tǒng)所說的塊，本質(zhì)上是同一個含義，但塊的大小有所區(qū)別。大多數(shù)數(shù)據(jù)庫默認(rèn)使用4～8KB的塊大小，但是當(dāng)創(chuàng)建數(shù)據(jù)庫實例時，許多數(shù)據(jù)庫允許指定塊大小。6.2文件組織一個塊可能包含很多條記錄，一個塊所包含的記錄數(shù)是由使用的物理數(shù)據(jù)組織形式?jīng)Q定的。一般要求一條記錄包含在單個塊中，也就是說，沒有記錄是部分包含在一個塊中，部分包含在另一個塊中。當(dāng)然，數(shù)據(jù)庫中會有幾種大數(shù)據(jù)項，例如圖片，可能比一個塊要大，這種情況需要特殊處理。在磁盤中，數(shù)據(jù)庫以文件形式組織，而文件由記錄組成。文件結(jié)構(gòu)由操作系統(tǒng)的文件系統(tǒng)提供和管理。那么邏輯文件中的記錄在物理文件中將如何實現(xiàn)？這是本節(jié)要討論的問題。6.2文件組織一般，文件組織有兩種方式，一種是把記錄設(shè)計成定長格式，另一種是變長格式，下面分別討論。例6-1設(shè)關(guān)系數(shù)據(jù)庫系統(tǒng)定義了一張學(xué)生基本信息表如下：12345678CreateTableS(sNochar(8)

notnullprimarykey,

/*學(xué)號*/sNamevarchar(16)

notnull,

/*姓名*/Sexchar(1)notnulldefault‘M’,

/*性別*/

Ageintnotnulldefault0,/*年齡*/dtBirthDatedatetimenull

/*出生日期*/);一般保存一個整型字段（int）需要4個字節(jié)，保存一個日期型字段（datetime）需要8個字節(jié)，這樣，在磁盤上保存一個學(xué)生記錄，至少需要37個字節(jié)。6.2文件組織假如當(dāng)前學(xué)生關(guān)系中，有下列6條記錄：（‘18011201’，‘李明’，‘M’，21，‘2000-03-06’）（‘18011202’，‘張芳’，‘F’，20，‘2000-11-09’）（‘18011203’，‘劉燕’，‘F’，20，‘2001-02-16’）（‘18011204’，‘王二’，‘M’，22，‘1999-12-26’）（‘18011205’，‘袁三’，‘M’，21，‘2000-05-06’）（‘18011206’，‘姚小明’，‘M’，21，‘2000-07-12’）一個簡單方法是使用前37個字節(jié)來存儲第一條記錄，接下來的37個字節(jié)來存儲第二條記錄，以此類推。然而這種簡單的方法有兩個問題：6.2文件組織（1）除非塊的大小恰好是37的倍數(shù)（一般不太可能的），否則一些記錄會跨過塊的邊界，即一條記錄的一部分存儲在一個塊中，而另一部分存儲在另一塊中。于是，讀寫這樣的一條記錄需要兩次塊訪問。（2）刪除一條記錄非常困難。刪除的記錄所占據(jù)的空間必須移動文件中的其他記錄來填充。這顯然是難以接受的。因此，系統(tǒng)運行時，需要考慮3個問題：系統(tǒng)是如何插入一條記錄的？如何刪除一條記錄的？如何修改一條記錄的？

6.2.1定長記錄的表示方式這是最簡單的構(gòu)造記錄的方式。所有字段都按定義時的數(shù)據(jù)類型為定長，并按定義時的順序相連便可形成一條記錄。一個塊中只分配它能完整容納下的最大的記錄數(shù)，每個塊中余下的字節(jié)就不使用了。如圖6-3所示。偏移量：0824252937sNosNameSexAgedtBirthDate圖6-3關(guān)系S中的一條記錄（定長格式）

6.2.1定長記錄的表示方式1．刪除操作時的考慮：刪除一個記錄，有三種不同的方法（1）把被刪記錄后的記錄一次移上來例如在圖6-4（a）中，要刪除記錄2，那么要把記錄3～6依次移上來，如圖6-4（b）所示。這時刪除一個記錄平均要移動文件中的一半記錄。這種方法顯然是不可取的。記錄118011201李明M212000-03-06記錄218011203劉燕F202001-02-16記錄318011202張芳F202000-11-09記錄418011206姚小明M212000-07-12記錄518011204王二M221999-12-26記錄618011205袁三M212000-05-06記錄118011201李明M212000-03-06記錄318011202張芳F202000-11-09記錄418011206姚小明M212000-07-12記錄518011204王二M221999-12-26記錄618011205袁三M212000-05-06

6.2.1定長記錄的表示方式（2）把文件中最后一個記錄填補到被刪記錄位置，如圖6-5所示。這種方法也不可取。記錄118011201李明M212000-03-06記錄218011203劉燕F202001-02-16記錄318011202張芳F202000-11-09記錄418011206姚小明M212000-07-12記錄518011204王二M221999-12-26記錄618011205袁三M212000-05-06記錄118011201李明M212000-03-06記錄618011205袁三M212000-05-06記錄318011202張芳F202000-11-09記錄418011206姚小明M212000-07-12記錄518011204王二M221999-12-26圖6-5把最后一個記錄填補到被刪記錄位置

6.2.1定長記錄的表示方式（3）把被刪結(jié)點用指針鏈接起來。一個塊可以存放多條記錄，記錄之間通過界定符進行分隔。在每個記錄中增加一個指針，在文件中增設(shè)一個文件首部。文件首部包括文件的有關(guān)信息，其中有一個指針指向第一個被刪記錄位置，所有被刪結(jié)點用指針鏈接，構(gòu)成一個棧結(jié)構(gòu)的空閑記錄鏈表。例如，將圖6-4（a）中刪除記錄2、5后，文件如圖6-6所示。頭文件指針（塊地址）記錄118011201李明M212000-03-06記錄2記錄318011202張芳F202000-11-09記錄418011206姚小明M212000-07-12記錄5記錄618011205袁三M212000-05-06

6.2.1定長記錄的表示方式頭文件指針（塊地址）記錄118011201李明M212000-03-06記錄2記錄318011202張芳F202000-11-09記錄418011206姚小明M212000-07-12記錄5記錄618011205袁三M212000-05-06這種方式較好。但要注意，是否還有指針指向被刪記錄。在DB中，被指針指向的記錄稱為“被拴記錄”。如果不小心把被拴記錄刪掉，那么指向該記錄的指針成了“懸掛指針”。懸掛指針指向的空間稱為“垃圾”，即該空間別人無法使用而又被空閑著。

6.2.1定長記錄的表示方式

2．插入操作時的考慮如果采用把被刪記錄鏈接起來的方法，那么插入操作可采用下列方法：在空閑記錄鏈表的第一個空閑記錄中，填上插入記錄的值，同時使首部指針指向下一個空閑記錄；如果空閑記錄鏈表為空，那么只能把新記錄插到文件尾。如圖6-7所示。記錄118011201李明M212000-03-06011．008．001指針記錄218011203劉燕F202001-02-16011．018．021記錄318011202張芳F202000-11-09011．008．001記錄418011206姚小明M212000-07-12012．108．002記錄518011204王二M221999-12-26011．008．003記錄618011205袁三M212000-05-06011．008．001

6.2.1定長記錄的表示方式

3．修改操作時的考慮修改記錄時，先查找到被修改記錄在磁盤上的塊地址，直接釋放地址，再隨機插入要修改的記錄。定長記錄處理方式的特點是：簡單、方便。但如果記錄中有許多變長數(shù)據(jù)類型，比如姓名，全用16個字節(jié)表示，如果記錄數(shù)很多，就會浪費存儲空間。此時，一般采用變長記錄的方式處理。

6.2.2變長記錄的表示方式在數(shù)據(jù)庫的表或文件中，之所以會出現(xiàn)變長記錄，原因有下面幾點：（1）記錄中出現(xiàn)了一個或多個字段的數(shù)據(jù)類型是變長的。varchar(n)、text、圖片等都屬于變長數(shù)據(jù)類型。例如，例6-1中學(xué)生姓名sName的類型為varchar(16)，最長可為8個漢字，但也可以取2個、或3個漢字。（2）記錄中的非主屬性，其值可以為null。在這些為null字段上，有的記錄取了值，有的記錄沒有取值。例6-1中，學(xué)生的出生日期dtBirthDate，如果插入記錄時，不知道學(xué)生的出生日期，就可以不取值，即為null。

（3）記錄中出現(xiàn)了一個或多個字段的取值允許重復(fù)，這些字段稱為重復(fù)字段。例如，學(xué)生的性別Sex，值允許取“男”或“女”；銷售訂單主表的業(yè)務(wù)員編號EmplNo，這是一個外鍵，取值來自于公司的員工表的員工編號。

6.2.2變長記錄的表示方式變長記錄的存儲比較復(fù)雜，不同的數(shù)據(jù)庫系統(tǒng)有不同的技術(shù)。其中最常見的為“分槽式頁結(jié)構(gòu)”（SlottedStructure），如圖6-8所示。它一般是在每塊的開頭設(shè)置一個“塊首部”，塊首部中包含下列信息：

（1）塊中記錄的條數(shù)。

（2）指向塊中自由空間尾部的指針。

（3）登記每條記錄的開始位置和大小的信息。

6.2.2變長記錄的表示方式在一個物理塊中，實際記錄是從塊的尾部開始連續(xù)存儲的。塊中自由空間是連續(xù)的。如果要插入一條記錄，一般在自由空間的尾部給該記錄分配空間，同時將該記錄的大小和位置信息添加到塊頭部中。如果一條記錄被刪除，它的空間被釋放，它在塊頭部的信息被置為刪除標(biāo)志（比如被設(shè)為-1），同時它左邊的記錄全部依次往右移，以填補被刪記錄的空間。