不定長記錄

檔案是由大量性質相同的記錄組成的集合。檔案可以按照記錄的一特性分成定長記錄檔案和不定長記錄檔案。若檔案中每個記錄含有的信息長度相同，則稱這類記錄為定長記錄。若檔案中每個記錄含有信息長度不等，則稱為不定長記錄。不定長記錄在各種檔案、應用程式中很常見。

基本介紹

• 中文名：不定長記錄
• 外文名：undefined length record
• 學科：計算機科學
• 定義：每個記錄含有信息長度不等
• 有關術語：定長記錄
• 領域：作業系統、應用程式、檔案系統

簡介

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

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、當刪除一條記錄時，應用程式將該記錄所屬的全部數據塊的狀態標記改寫為刪除；當寫記錄數據時，則從存儲空間最前面的刪除狀態的數據塊開始寫起，依次尋找下一個刪除狀態的數據塊，如無刪除狀態的數據塊，則寫入第一個空閒數據塊，寫數據塊時先寫入數據，最後將數據塊標記改寫為有效標記。

存儲方法

不定長記錄（變長記錄）在檔案中的存儲方法有以下幾種：位元組流表示法、分槽的頁結構、定長表示法。

位元組流表示法

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

分槽的頁結構

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

⑴　塊頭部分：塊頭部分記錄了有關這一塊的詳細信息，包括塊中記錄個數、塊中空閒空間的末尾地址以及描述塊中每個記錄的大小和位置的數組；
⑵　塊尾部分：實際記錄從塊的尾部開始連續分配存儲空間；
⑶　塊中部分：塊中空閒空間是連續的，處在塊頭數組的最後一個條目和塊尾記錄的第一個條目之間，用於為新插入的記錄分配空間。
對於分槽的頁結構，如何實現記錄的插入和刪除呢？通常可以採用以下維護策略：
⑴　刪除一條記錄：該記錄所占用的空間被釋放，同時塊中在被刪記錄之前的記錄都要移動。因此塊頭的相關部分都要進行修改，而空閒空間還是集中在塊中間；
⑵　插入一條記錄：在塊中空閒空間的尾部給這條記錄分配空間，同時修改塊頭的相關部分；
⑶　記錄的增長和縮短：該條記錄的末尾地址不變，而在此記錄之前的記錄都要移動，同時修改塊頭的相關部分。由於塊的大小是有限制的，因此塊內能存儲的記錄個數有限，這樣移動記錄的代價就不會太高。

定長表示法

變長記錄的定長表示法是用一個或多個定長記錄來表示一個變長記錄的方法。由於所採用的策略不同，變長記錄的定長表示法又分為以下幾種情況。
⑴　保留空間法：假設所有的變長記錄都不會超過某個長度，就為每個記錄都分配這樣長度的空間，具體情況如圖所示：

對於保留空間法來說，值得注意的是：首先假設是不合理的，既然是變長記錄，記錄的長度就捉摸不定，我們又如何估計出所有記錄的最大長度呢？其次這樣的做法浪費了大量的存儲空間，在實際套用中不可取；
⑵　指針法：用一系列通過指針連結起來的定長記錄來表示一個變長記錄，如圖所示：

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

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

在錨塊-溢出塊表示法中檔案里包含不同的塊，而每個塊中的記錄都是定長的，所謂的變長記錄被表示成將不同塊中的記錄用指針連結起來的一個鍊表。