文件組織

文件存取方法是由用戶使用文件的要求、存儲設備特徵來決定的，不僅要考慮到文件的邏輯結構，而且要考慮到文件物理結構。

當我們討論文件組織時，我們是在討論一個文件中記錄的排列，因為所有文件都是由記錄組成的。用戶給出的修改文件內容的命令其實就是一個訪問記錄的命令。

在每個文件裡面，記錄都應該具有同樣的格式——它們可以定長或者變長。不管其具體格式，這些記錄都可以是分塊或者未分塊。

定長記錄是最常見的，因為它們最容易直接訪問。這就是為什麼它們是理想的數據文件。定長記錄的關鍵是記錄的大小。如果太小，小過了記錄存儲的字元數，那麼多出的字元就要被截掉了。如果記錄大小太大了，大過了要存儲的字元數，就會有空間的浪費。

變長記錄不會有剩餘空間和截掉記錄，所以克服了定長的2個缺點。但儘管它也容易一個接一個讀取，但因為記錄的位置很難計算，所以直接讀取很困難。連續訪問的文件或者通過目錄查找的文件經常使用變長記錄格式。記錄的格式，它如何分塊，和其它相關信息都被保存在文件描述符里。

用來保存信息的空間根據系統各異，它由存儲介質的物理性質所限制。

一個文件的物理組織就是根據記錄的排列和存儲介質的特性來組織文件。

在一個磁介質的磁碟上，文件組織可以是下面3種方法中的一種：順序存儲，直接存儲，和順序索引。為了選擇最好的方法，程序員或者分析員必須要考慮下面特性的實際：

數據的揮發性——添加和刪除的頻率

文件的行為——在一個運行中，被處理的記錄的百分比

響應時間——完成操作之前用戶要等待的時間。這在交互環境中的查找和修改信息中尤其重要。

順序記錄組織是最容易實現的，因為記錄的存儲和得到都是順序的，一個接一個。為了找到一個記錄，文件要從頭開始查找直到找到這個記錄。

為了加速這個處理過程，一些優化特性被加入系統。一個就是選擇記錄的一個關鍵區域，然後在存儲記錄前都是根據這個區域分類記錄。然後當用戶需要一個記錄的時候，系統只是查找關鍵區域。當相匹配的記錄找到或者關鍵區域比最後一次比較的記錄小時，給出信息“沒找到記錄”，然後完成搜索。

儘管這個技術輔助查找處理過程，但因為當有記錄添加或者刪除的時候都要保存，它使得演演算法更複雜了。為了保存物理順序，文件必須在更改的時候完成回寫或者動態分類。

直接記錄組織使用直接訪問文件的方法，當然，只有在直接訪問存儲設備上才能實現。這些文件給用戶提供了以任何順序訪問任何記錄的靈活性，而不用從頭開始尋找。這也是一個隨機組織方法，其文件叫做隨機訪問文件。

記錄是由它們的相對地址——它們到文件開始的相對位置來確定的。它們的邏輯地址是當文件被存儲或者記錄恢復的時候計算出來的。

這個方法很直截了當。用戶通過記錄格式來確定一個區域（或者區域組合），並標記為鍵域，它唯一確定每一個記錄。程序通過一系列指令來保存數據，叫做散列演演算法，它將每一個鍵域編號，即記錄的邏輯地址。然後把這些交給信息管理器，它可以把邏輯地址通過幾步轉換成物理地址（簇，表面和記錄號）並保持文件組織，檢索記錄過程也是同樣的。

另外，直接訪問文件可以連續訪問，即從一個相對地址開始，然後增加地址來找到下一個記錄。

直接訪問文件比順序文件可以修改得更快，因為記錄可以很快回寫到它的原始地址。同時它也不需要保存記錄的順序，所以增加和刪除文件可以用更少的時間。

電話郵購公司用散列的方法來直接訪問客戶信息。假設你在訂貨，你詢問你的顧客號。（假設為152132727）。程序將從數據文件中按照散列演演算法的鍵值來計算出你的記錄的邏輯地址，（在348）。所以當服務員輸入152132727,熒幕很快顯示出同一個邏輯地址的顧客號。如果你在資料庫中，操作員會很快知道，如果不在，你會很快知道。

散列演演算法的問題在於，一些有唯一主鍵（比如顧客號）的記錄可能會有同一個邏輯地址——這裡將產生衝突。在文件管理存儲之前，它必須找到另一個邏輯地址。衝突的記錄將被存在一個溢出區域，它在文件的生成時就被附加上了。儘管程序做到了從溢出區域與記錄的邏輯地址的連接，文件管理還是要處理空間的分配問題。

文件的最大尺寸在它生成的時候就確立了。最終，文件可能會完全寫滿或者存儲在溢出區域的記錄數已經太多了，這將導致數據檢索的效率大大降低。在這兩種情況下，文件必須重新組織和重新寫入，這需要由編程者來干預。

索引順序記錄組織是順序和直接訪問的組合。它通過索引順序訪問方法(ISAM)來生成和維護記錄，它消除了編程者處理溢出和保存記錄順序的負擔。

這種組織方法避免了衝突，因為它沒有用哈希演演算法來生成一個記錄的地址。代替它的是，使用了該信息生成索引文件來實現記錄的查找。這種組織將順序的連續的文件分成了同等大小地塊。它的大小由文件管理器來決定，以充分利用物理存儲設備的優點並優化檢索策略。每一個索引文件的項目包括最高的記錄鍵和這個數據塊的物理位置，即這個記錄和記錄號最小的記錄的存儲位置。

因此，為訪問文件中的記錄，系統先搜索索引文件，然後進入物理位置。索引文件就像是一個數據的指示器。一個索引順序文件也有溢出區域，但是它會擴展到整個文件（可能是很少的記錄），所以已有的記錄也可以擴展，新的記錄可以生成在物理順序與邏輯順序最近的地方。另一個溢出區不在主要數據區域，而是只有在其它溢出區都充滿了才用。我們叫它為最後記錄的溢出區。

這個最後分配的溢出區可以在文件的有效時間內添加記錄。記錄是用軟體包來實現邏輯順序保存，而不用程序員投入太多的努力。當然，添加太多記錄時進程就會變慢，這是因為尋找一個記錄必須從目錄到主數據區最後才到溢出區。

當恢復時間變得太長，文件就需要重新組織。這個工作儘管不像組織一個直接訪問文件一樣枯燥，但通常仍要系統地分析員或者程序員來做。

對於大多數的動態文件，索引順序可以選擇，它允許直接訪問一小部分記錄和順序訪問很多記錄。一個索引順序文件的變體是B-tree。