記錄及記錄集存儲結構的探討

2008-12-31 00:00:00王保志

中國校外教育(下旬) 2008年20期

[摘要]本文探討了數據庫管理系統中記錄及記錄集的存儲結構技術。

[關鍵詞]記錄記錄的存儲記錄集合的存儲

一、引言

數據庫中的數據是用來描述現實世界中具體事物的。在關系模型中，通常把那些描述事物所必需的屬性組合起來，構成一個元組，使得每一個元組正好表示現實世界中的一個事物。每一個元組對應著存儲結構中的一個數據記錄，每個邏輯頁面內可以存放若干個數據記錄。怎樣把一個元組描述成一個數據記錄呢？

二、記錄和記錄類型

數據通常都以記錄（record）的形式存儲的。每條記錄有相關的數據值或數據項匯集組成，其中每個值由一個或多個字節構成，并與記錄中的一個特定字段（field）相對應。記錄通常描述實體及其屬性。舉例來說，一個Employee記錄表示一個雇員實體，記錄中的各個字段值指定了該雇員的一些屬性，例如Name、Birthday、Salary等。字段名及其相應數據類型的匯集構成了一個記錄類型（record type）或記錄格式（record format）定義。與各字段相關的數據類型（data type）指定了此字段可取值的類型。

字段的數據類型通常是編程時使用的標準數據類型。其中包括數值型（整型、長整型或浮點型）、字符串（定長或變長字符串）、布爾型（只能取0和1或TRUE或FALSE這樣的值），有時還有專門編碼的日期和時間數據類型。對于給定的計算機系統，各數據類型所需的字節數是固定的。一個整型可能需要4個字節，一個長整型需要8個字節，一個實數型需要4個字節，一個布爾型需要1個字節，一個日期型需要10個字節（假設日期的模式是YYYY-MM-DD），k個字符組成的定長字符串需要k個字節，變長字符串需要的字節數等于各字段值中的字符數。例如，可以用C程序設計語言表示法將Employee的記錄類型定義為以下結構。

Struct employee{

Char name[30];

Char ssn[9];

Int salary;

Int job_code;

Char department[20];

};

三、文件、定長記錄和變長記錄

文件是記錄的序列。在許多情況下，一個文件中的所有記錄均屬于同一種記錄類型。如果文件中所有的記錄的長度均相等（以字節計），則稱這個文件是由定長記錄（fixed-length record）組成的。如果文件中的不同記錄的長度也不同，則稱這個文件是由變長記錄（variable-length record）組成的。文件之所以會有變長記錄是因為：

1．文件記錄均屬于同一記錄類型，但有一個或多個字段是變長的（變長字段）。例如，EMPLOYEE中的name字段就可能是變長字段。

2．文件記錄均屬于同一記錄類型，但有一個或多個字段對應的單個記錄有多個值，這樣的字段成為重復字段（repeating field），該字段的一組值通常稱為重復組（repeating group）。

3．文件記錄均屬于同一記錄類型，但有一個或多個字段是可選的（optional）。也就是說這個文件中有些記錄在該字段上有值，但并非該文件的所有記錄在該字段上都有值（可選字段）。

4．文件包含不同記錄類型的記錄，因此是變長的（混合文件）。如果不同類型的相關記錄在磁盤中聚簇存儲，就會出現這種情況。例如，某個學生的grade-report記錄可能緊跟在student記錄后面。

由此可以看出，不同記錄由于其屬性值的不同，存儲空間的大小也不相同，那么如何存儲元組就需要過細的考慮。

四、記錄的存儲

1．定長記錄的存儲

存儲記錄的一種最簡單的方法是固定長度的定長記錄法，即元組的屬性字段的數目是固定的，每個屬性字段的長度也是固定的，對屬性值長度不規整的取其最長的長度。如上述的employee關系可定義其記錄的存儲結構的長度為：

即每個記錄分配67B。所有記錄都有相同的屬性字段，且其字段長度是固定的，因此系統可以確定每個字段相對于該記錄的開始位置的起始字節位置。這有利于存取該文件的程序定位字段值。需要注意的是，這樣就有可能將一個邏輯上會有變長記錄的文件表示為定長記錄文件。例如，在記錄中有可選字段的情況下，我們可以將每個字段都包括在每個文件記錄中，但是如果某個字段沒有值，就這個字段中存儲一個特殊的NULL值。定長記錄法雖然簡單，但浪費存儲空間，另一個缺點是不夠靈活，不能應對新屬性的擴充和不需要的屬性的刪除。

2．變長記錄的存儲

對于有變長字段，每個記錄對于其中的每個字段都有一個值，不過我們不知道某些字段值的確切長度。為了確定一個特定記錄中各字段的字節數，可以使用特殊分隔符（separator）來結束變長字段，比如？、%、$，這些字符不會出現在任何字段中，如下圖1所示

（%為分隔符，其中Name和Department字段為變長字段）。

采用特殊分隔符的方法克服了上面定長記錄浪費空間的缺點，方法也簡單，但其缺點是不易于找到合適的保留字符，必須保證數據中都不會出現保留字符，特別對二進制數據就更困難。

變長記錄法的另外一種形式叫首部指針法，即在每個記錄的首部都設置若干個指針，分別指向第一個屬性值結束第二個屬性值開始，第二個屬性值結束第三個屬性值開始，…，倒數第二個屬性值結束倒數第一個屬性值開始的位置，如下圖2所示。

首部指針法中的指針可能占用較大空間，其改進的辦法是用屬性字段的長度來代替指針，此外，對于記錄中的定長屬性字段值，若每一記錄均用數字標明其長度，對于大量存儲的記錄也開銷太大，可以在目錄中將各定長屬性字段的長度予以記載，在存儲記錄時只指示變長屬性字段的長度。這樣可以節約大量的存儲空間。上面的例子可以如下圖3表示。其中，V表示變長屬性字段，F表示定長屬性字段。

這種把變長屬性字段的當前長度予以顯式指明的辦法還可以用于對關系中新屬性字段的擴充，擴充了新屬性的元組可將其新屬性和新屬性字段長度附加在記錄的尾部，從而無須更動原來的存儲結構而只需在目錄中稍加說明即可完成新屬性的擴充。

五、記錄集合的存儲

對于記錄的集合其存儲的結構也有多種方式。

1.記錄集順序存儲法（如下圖4所示）

它將一組記錄順序存儲，稱之為表（List），其優點是節省存儲空間，順序連續存取時效率最高。缺點是不靈活，只能表示記錄之間的一種關聯，一種順序，當存在其它關聯時則無法表示。再插入或刪除記錄時其存儲結構會發生變化。

2.鏈式存儲法（如下圖5所示）

這里的每個記錄都附有一個指針，指向下一個記錄的位置，因此在插入和刪除記錄時就很方便，只需將指針值改變即可。這種靈活性的代價是每個記錄多存儲一個指針。

3.變長指針法（如下圖6所示）

這種方式為指針集中鄰接存放，也較靈活，它的名字叫變長指針法，也叫指針陣列法（Pointer Array）。

4.指針鏈式存儲法（如下圖7所示）

這種存儲方法最為靈活，但存儲開銷和存取開銷也最大，查找一個記錄需要存取兩次。