1 概述
文件系統(tǒng)設(shè)計的關(guān)鍵要素是指將這些記錄構(gòu)成一個文件的方法，以及將一個文件存儲到外存上的方法啰扛。事實上璧坟，對于任何一個文件，都存在以下兩種形式的結(jié)構(gòu)：邏輯結(jié)構(gòu)與物理結(jié)構(gòu)
1.1 文件的邏輯結(jié)構(gòu)
這是從用戶觀點出發(fā)觀察到的文件組織形式讶隐，是用戶可以直接處理的數(shù)據(jù)及其結(jié)構(gòu)起胰，它獨立于文件的物理特性，又稱為文件組織巫延。
1.2 文件的物理結(jié)構(gòu)
又稱為文件的存儲結(jié)構(gòu)效五。是指文件在外存上的組織形式，這不僅與存儲介質(zhì)的存儲性能有關(guān)炉峰，而且與所采用的外存分配方式有關(guān)畏妖。
2 文件邏輯結(jié)構(gòu)的類型
有結(jié)構(gòu)文件指的是一個以及以上的記錄構(gòu)成的文件，故又把它稱為記錄式文件疼阔；無結(jié)構(gòu)文件是指字符流構(gòu)成的文件戒劫，故又稱為流式文件。
2.1 有結(jié)構(gòu)文件
在記錄式文件中婆廊，每個記錄都是用于描述實體集中的一個實體迅细，各記錄有著相同或不同數(shù)目的數(shù)據(jù)項。記錄長度可分為定長和不定長的兩類淘邻。
定長記錄
這是指文件中所有記錄的長度都是相同的們所有記錄中個數(shù)據(jù)項都是處在記錄相同的位置茵典，具有相同的順序和長度。廣泛用于數(shù)據(jù)處理中宾舅。不定長記錄
這是指文件中各記錄的長度不相同统阿。例如病例記錄中的病因彩倚、病史等。
有結(jié)構(gòu)文件按記錄的組織形式可以分為：順序結(jié)構(gòu)扶平、索引結(jié)構(gòu)帆离、索引順序結(jié)構(gòu)。
2.2 無結(jié)構(gòu)文件
如果說大量的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫是采用結(jié)構(gòu)的形式文件的話蜻直，則大量的源程序盯质、可執(zhí)行文件、庫函數(shù)等概而，所采用的則是無結(jié)構(gòu)的文件形式呼巷，即流式文件。
對流式文件的訪問是采用讀寫指針指出下一個要訪問的字符赎瑰⊥鹾罚可以把流式文件看做是記錄式文件的一個特例。
注意：在unix中餐曼，所有文件都被看做是流式文件压储，即使是記錄式（有結(jié)構(gòu)）文件也被視為流式文件，系統(tǒng)不對文件進(jìn)行格式處理源譬。
3 順序文件
文件中的記錄一個接一個地順序排列集惋，記錄可以是定長的或變長的，可以順序存儲或以鏈表形式存儲踩娘，在訪問時需要順序搜索文件刮刑。順序文件有以下兩種結(jié)構(gòu)：
- 串結(jié)構(gòu)
記錄之間的順序與關(guān)鍵字無關(guān)。通常的辦法是由時間決定养渴，即按存入時間的先后排列雷绢，最先存入的記錄作為第1個記錄，其次存入的為第2個記錄理卑，依此類推翘紊。 - 順序結(jié)構(gòu)
指文件中的所有記錄按關(guān)鍵字順序排列。
在對記錄進(jìn)行批量操作時藐唠，即每次要讀或?qū)懸淮笈涗浄保瑢樞蛭募男适撬羞壿嬑募凶罡叩?/em>；此外宇立，也只有順序文件才能存儲在磁帶上踪宠，并能有效地工作，但順序文件對查找泄伪、修改殴蓬、增加或刪除單個記錄的操作比較困難匿级。
可以為順序文件配置一個運行記錄文件（事務(wù)文件）蟋滴。把試圖增加染厅、刪除或修改的信息記錄其中，規(guī)定每隔一定時間津函，例如4小時肖粮，將運行記錄文件與原來的主文件加以合并，產(chǎn)生一個關(guān)鍵字排序的新文件尔苦。
4 索引文件
對于定長記錄文件涩馆，如果要查找第i個記錄，可直接根據(jù)下式計算來獲得第i個記錄相對于第一個記錄的地址：
然而允坚，對于可變長記錄的文件魂那，要查找第i個記錄時，必須順序地查找前i-1個記錄稠项，從而獲得相應(yīng)記錄的長度Li涯雅，然后才能按下式計算出第i個記錄的首址：
變長記錄文件只能順序查找，系統(tǒng)開銷較大展运。為此可以建立一張索引表以加快檢索速度活逆，索引表本身是定長記錄的順序文件。在記錄很多或是訪問要求高的文件中拗胜，需要引入索引以提供有效的訪問蔗候。實際中，通過索引可以成百上千倍地提高訪問速度埂软。
由于索引文件有較快的檢索速度锈遥，故它主要用于信息處理的及時性要求比較高的場合，例如飛機(jī)訂票系統(tǒng)仰美。
5 索引順序文件
索引順序文件是順序和索引兩種組織形式的結(jié)合迷殿。索引順序文件將順序文件中的所有記錄分為若干個組，為順序文件建立一張索引表咖杂，在索引表中為每組中的第一個記錄建立一個索引項庆寺，其中含有該記錄的關(guān)鍵字值和指向該記錄的指針。
對于含有N個記錄的順序文件诉字，查找某關(guān)鍵字值的記錄時平均需要查找N/2次懦尝。
在索引順序文件中，假設(shè)N個記錄分為N1/2組壤圃，索引表中有N1/2個表項陵霉，每組有N1/2個記錄，在查找某關(guān)鍵字值的記錄時伍绳，先順序查找索引表踊挠，需要查找(N1/2)/2次，然后再在主文件中對應(yīng)的組中順序查找，也需要查找(N1/2)/2次效床，這樣總共查找***(N1/2)/2+(N1/2)/2=N1/2次***睹酌。
顯然，索引順序文件提高了查找效率剩檀，如果記錄數(shù)很多憋沿，可以釆用兩級或多級索引。索引文件和索引順序文件都提高了存取的速度沪猴，但因為配置索引表而增加了存儲空間辐啄。
6 直接文件或散列文件(Hash File)
給定記錄的鍵值或通過Hash函數(shù)轉(zhuǎn)換的鍵值直接決定記錄的物理地址。這種映射結(jié)構(gòu)不同于順序文件或索引文件运嗜，沒有順序的特性壶辜。
散列文件有很高的存取速度，但是會引起沖突担租，即不同關(guān)鍵字的散列函數(shù)值相同士复。
