不定長記錄

記錄是一組相關數據項的集合，用於描述一個對象在某方面的屬性。一個記錄應包含哪些數據項，取決於需要描述對象的哪個方面。而一個對象，由於他所處的環境不同可把他作為不同的對象。不定長記錄是指每個記錄含有信息長度不等，也可以稱之為變長記錄。變長記錄是由以下因素引起的，第一，多種記錄類型在一個文件中存儲；第二，記錄類型允許一個或多個字段是變長的；第三，記錄類型允許有可重複的字段。舉例如下：

type account-list = record 
　branch-name: char(22); 
　account-info: array[1..∞] of 
　record account-number: char(10); 
　balance: real; end end

在計算機科學中，記錄也稱為結構體或複合資料（Struct/record）是基本的數據結構，記錄是一些相關字段的聚集，它們可由不同的資料類型組成，通常是固定的數量和序列。記錄中的每個字段或稱為元素，但可能與集合的元素概念混淆不清。在面向對象編程中，記錄的字段也另外被稱為成員；依照慣例和具體的編程語言，多元組有可能會被認為是一個記錄，反之亦然。

譬如將日期儲存為一個記錄，則其中包含了數字的年份，以字串表示的月份和數字的日期等字段。而人事記錄可包含姓名，薪水和職級等字段。一個圓形的記錄可包含圓中心點和它的半徑－在這種情況下，圓中心點本身可能表示為x和y座標的點記錄。

記錄與陣列的區別在於，它們的字段數通常是固定的，每個字段都有一個名稱，而且每個字段可能有不同的類型。

一個記錄型別是描述其中字段所具有值和變量的資料類型。大多數現代計算機語言允許開發人員自由定義新的記錄型別。記錄型別的定義將會指定每個字段的資料類型和存取它的標識符（名稱或標籤）。

記錄可以存在於任何存儲介質中，包括主內存和大容量存儲裝置，如磁帶或硬盤。記錄是大多數數據結構的基本組成部分，特別是鏈接的數據結構。

許多計算機檔案是以邏輯記錄的陣列組成的，通常被分組成更大的實體記錄或區塊以提高存取效率。

函數或程序的參數通常當作是一個記錄變量其中的字段；而在呼叫該函數時，傳遞給它的參數可被視為將字段的值指派給該記錄變量。此外，通常用於實現程序調用的呼叫堆疊中，每個登錄即是一條啓動記錄或呼叫框頁，包含了程序參數和局部變量，返回位址和其它內部字段。

面嚮對象語言中的物件本質上是一個記錄，有如何處理該記錄的專用程序；而物件型別是對記錄類型的詳細描述。實際上在大多數面嚮對象語言中，記錄只是物件的特殊情況，並且被稱為普通舊數據結構（plain old data structures, PODS），與使用OO特徵的物件形成對比。

記錄是指同類信息中獨立的一部分數據，例如，電子郵箱中的一封信件，手機中的一條短信息等，都屬於一條記錄。應用程序在接收輸入信息時通常會將這些信息組織成為一條條的記錄的形式存放在存儲設備中。應用程序對這些生成的記錄需要採用一定的存儲方式存放在非易失類存儲設備中，以便於長期保存記錄。應用程序產生的記錄長度通常是不確定的，如一封信件，少則幾十個字節，多則幾百萬字節，如果採用統一大小的格式存儲，不僅存儲小記錄時浪費存儲空間，而且對大記錄也有長度限制，如果採用連續存儲的方式，則刪除的記錄所佔用的存儲空間無法被有效的再次利用，例如無法再存儲比刪除的記錄長度長的大記錄，因此執行刪除、修改等操作效率極低，不易管理而且浪費空間。

1、應用程序將記錄的存儲空間劃分為固定大小的數據塊，每個數據塊包括數據區和結構信息兩部分，數據塊的結構信息中包含有記錄ID、記錄長度、節點號、下一塊地址、數據塊狀態標記等信息；

2、應用程序按步驟a所劃分的數據塊的大小將記錄數據切分成若干個數據塊，並將每塊數據塊附加上結構信息；

3、長度不大於一個數據塊的記錄佔用一個數據塊，大於一個數據塊的記錄佔用多個數據塊，應用程序將同一記錄的數據塊採用鏈表形式組織前後關係，將同一記錄的數據塊的記錄ID號定為相同，在其結構信息中存放前後節點關係；

4、當刪除一條記錄時，應用程序將該記錄所屬的全部數據塊的狀態標記改寫為刪除；當寫記錄數據時，則從存儲空間最前面的刪除狀態的數據塊開始寫起，依次尋找下一個刪除狀態的數據塊，如無刪除狀態的數據塊，則寫入第一個空閒數據塊，寫數據塊時先寫入數據，最後將數據塊標記改寫為有效標記。 ^[2] 

不定長記錄（變長記錄）在文件中的存儲方法有以下幾種：字節流表示法、分槽的頁結構、定長表示法。

變長記錄在文件中的存儲方法之一就是採用字節流表示法：即在每個記錄的末尾都附加一個特殊的記錄終止符號(┴)，或者是在每個記錄的開頭存儲該記錄的長度，這樣就可以把每個記錄作為一個連續的字節流來存儲，如圖1所示。值得注意的有以下兩點：⑴　要想重新使用被刪除記錄曾經佔用的空間十分困難，很容易導致磁盤碎片；⑵　如果一個記錄變長了，該記錄就必須移動；如果一個記錄變短了，就造成磁盤碎片。而移動記錄的代價很高。

分槽的頁結構是基本字節流表示方法的一種改進形式，普遍用於物理塊內部的記錄組織，如圖2所示，分槽的頁結構由三部分組成：

⑴　塊頭部分：塊頭部分記錄了有關這一塊的詳細信息，包括塊中記錄個數、塊中空閒空間的末尾地址以及描述塊中每個記錄的大小和位置的數組；

⑵　塊尾部分：實際記錄從塊的尾部開始連續分配存儲空間；

⑶　塊中部分：塊中空閒空間是連續的，處在塊頭數組的最後一個條目和塊尾記錄的第一個條目之間，用於為新插入的記錄分配空間。

對於分槽的頁結構，如何實現記錄的插入和刪除呢？通常可以採用以下維護策略：

⑴　刪除一條記錄：該記錄所佔用的空間被釋放，同時塊中在被刪記錄之前的記錄都要移動。因此塊頭的相關部分都要進行修改，而空閒空間還是集中在塊中間；

⑵　插入一條記錄：在塊中空閒空間的尾部給這條記錄分配空間，同時修改塊頭的相關部分；

⑶　記錄的增長和縮短：該條記錄的末尾地址不變，而在此記錄之前的記錄都要移動，同時修改塊頭的相關部分。由於塊的大小是有限制的，因此塊內能存儲的記錄個數有限，這樣移動記錄的代價就不會太高。

變長記錄的定長表示法是用一個或多個定長記錄來表示一個變長記錄的方法。由於所採用的策略不同，變長記錄的定長表示法又分為以下幾種情況。

⑴　保留空間法：假設所有的變長記錄都不會超過某個長度，就為每個記錄都分配這樣長度的空間，具體情況如圖3所示：

對於保留空間法來説，值得注意的是：首先假設是不合理的，既然是變長記錄，記錄的長度就捉摸不定，我們又如何估計出所有記錄的最大長度呢？其次這樣的做法浪費了大量的存儲空間，在實際應用中不可取；

⑵　指針法：用一系列通過指針鏈接起來的定長記錄來表示一個變長記錄，如圖4所示：

變長記錄的指針鏈接法與表示定長記錄類似，在這裏變長記錄變成了一個鏈表，和保留空間法相比浪費的空間量較少，但引入了額外的結構，即指針列；

⑶　錨塊-溢出塊表示法：這是指針法的變形。在文件中使用兩種不同類型的物理塊：錨塊和溢出塊。其中錨塊是包含鏈表中第一個記錄的塊；而溢出塊是包含鏈表中除第一個記錄以外的其他記錄的塊。具體情形如圖5所示：

在錨塊-溢出塊表示法中文件裏包含不同的塊，而每個塊中的記錄都是定長的，所謂的變長記錄被表示成將不同塊中的記錄用指針鏈接起來的一個鏈表。 ^[3]