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

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

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

notnullprimarykey,

/*學(xué)號(hào)*/sNamevarchar(16)

notnull,

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

/*性別*/

Ageintnotnulldefault0,/*年齡*/dtBirthDatedatetimenull

/*出生日期*/);一般保存一個(gè)整型字段（int）需要4個(gè)字節(jié)，保存一個(gè)日期型字段（datetime）需要8個(gè)字節(jié)，這樣，在磁盤上保存一個(gè)學(xué)生記錄，至少需要37個(gè)字節(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’）一個(gè)簡(jiǎn)單方法是使用前37個(gè)字節(jié)來(lái)存儲(chǔ)第一條記錄，接下來(lái)的37個(gè)字節(jié)來(lái)存儲(chǔ)第二條記錄，以此類推。然而這種簡(jiǎn)單的方法有兩個(gè)問(wèn)題：6.2文件組織（1）除非塊的大小恰好是37的倍數(shù)（一般不太可能的），否則一些記錄會(huì)跨過(guò)塊的邊界，即一條記錄的一部分存儲(chǔ)在一個(gè)塊中，而另一部分存儲(chǔ)在另一塊中。于是，讀寫這樣的一條記錄需要兩次塊訪問(wèn)。（2）刪除一條記錄非常困難。刪除的記錄所占據(jù)的空間必須移動(dòng)文件中的其他記錄來(lái)填充。這顯然是難以接受的。因此，系統(tǒng)運(yùn)行時(shí)，需要考慮3個(gè)問(wèn)題：系統(tǒng)是如何插入一條記錄的？如何刪除一條記錄的？如何修改一條記錄的？

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

6.2.1定長(zhǎng)記錄的表示方式1．刪除操作時(shí)的考慮：刪除一個(gè)記錄，有三種不同的方法（1）把被刪記錄后的記錄一次移上來(lái)例如在圖6-4（a）中，要?jiǎng)h除記錄2，那么要把記錄3～6依次移上來(lái)，如圖6-4（b）所示。這時(shí)刪除一個(gè)記錄平均要移動(dòng)文件中的一半記錄。這種方法顯然是不可取的。記錄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定長(zhǎng)記錄的表示方式（2）把文件中最后一個(gè)記錄填補(bǔ)到被刪記錄位置，如圖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把最后一個(gè)記錄填補(bǔ)到被刪記錄位置

6.2.1定長(zhǎng)記錄的表示方式（3）把被刪結(jié)點(diǎn)用指針鏈接起來(lái)。一個(gè)塊可以存放多條記錄，記錄之間通過(guò)界定符進(jìn)行分隔。在每個(gè)記錄中增加一個(gè)指針，在文件中增設(shè)一個(gè)文件首部。文件首部包括文件的有關(guān)信息，其中有一個(gè)指針指向第一個(gè)被刪記錄位置，所有被刪結(jié)點(diǎn)用指針鏈接，構(gòu)成一個(gè)棧結(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定長(zhǎng)記錄的表示方式頭文件指針（塊地址）記錄118011201李明M212000-03-06記錄2記錄318011202張芳F202000-11-09記錄418011206姚小明M212000-07-12記錄5記錄618011205袁三M212000-05-06這種方式較好。但要注意，是否還有指針指向被刪記錄。在DB中，被指針指向的記錄稱為“被拴記錄”。如果不小心把被拴記錄刪掉，那么指向該記錄的指針成了“懸掛指針”。懸掛指針指向的空間稱為“垃圾”，即該空間別人無(wú)法使用而又被空閑著。

6.2.1定長(zhǎng)記錄的表示方式

2．插入操作時(shí)的考慮如果采用把被刪記錄鏈接起來(lái)的方法，那么插入操作可采用下列方法：在空閑記錄鏈表的第一個(gè)空閑記錄中，填上插入記錄的值，同時(shí)使首部指針指向下一個(gè)空閑記錄；如果空閑記錄鏈表為空，那么只能把新記錄插到文件尾。如圖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定長(zhǎng)記錄的表示方式

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

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

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

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

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

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

（3）登記每條記錄的開(kāi)始位置和大小的信息。

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