現(xiàn)代計算機(jī)系統(tǒng)主要通過文件目錄對其大量存儲的文件進(jìn)行有效的管理州邢。文件目錄是一種數(shù)據(jù)結(jié)構(gòu)鉴腻，用于標(biāo)識系統(tǒng)中的文件及其物理地址这嚣，供檢索時使用。

目錄管理的要求如下：

• 實(shí)現(xiàn)“按名存取”瑟蜈，用戶能通過文件名字能快速準(zhǔn)確找到指定文件在外存上的存儲位置烟逊。

• 提高對目錄的檢索速度。通過合理地組織目錄結(jié)構(gòu)方法铺根，加快目錄檢索速度宪躯，進(jìn)而提高文件存取速度。

• 文件共享位迂。在多用戶系統(tǒng)中访雪，應(yīng)允許多個用戶共享一個文件。在外存中只保留一份該文件副本掂林，以節(jié)省大量存儲空間冬阳。

• 允許文件重名系統(tǒng)應(yīng)允許不同用戶對不同文件采用相同的名字，便于用戶按照自己習(xí)慣使用文件党饮。

1 文件控制塊

為了能對文件進(jìn)行正確的存取，必須為文件設(shè)置用于描述和控制文件的數(shù)據(jù)結(jié)構(gòu)驳庭，稱之為文件控制塊FCB刑顺。文件管理程序可借助于文件控制塊中的信息，對文件施加各種操作饲常，文件與文件控制塊一一對應(yīng)蹲堂。

人們把文件控制塊的有序集合稱為文件目錄，一個文件控制塊就是一個文件目錄項(xiàng)贝淤。通常柒竞，一個文件目錄也可被看成是一個文件，稱為目錄文件播聪。

為了能對系統(tǒng)中大量文件進(jìn)行有效的管理朽基，通常文件控制塊應(yīng)包含以下三方面信息：

• 基本信息類
  文件名布隔、物理地址位置（文件長度）、文件邏輯結(jié)構(gòu)稼虎、文件物理結(jié)構(gòu)衅檀。

• 存取控制信息類
  文件主的存取權(quán)限、準(zhǔn)核用戶的存取權(quán)限以及一般用戶的存取權(quán)限霎俩。

• 使用信息類
  文件的建立日期哀军、上次修改日期、當(dāng)前使用信息（打開該文件的進(jìn)程數(shù)打却、是否被鎖定杉适、文件在內(nèi)存中是否已被修改單尚未拷貝到盤上）

2 索引結(jié)點(diǎn)

文件目錄通常是存放在磁盤上的，當(dāng)文件很多時柳击，文件目錄可能要占用大量的盤塊猿推。

稍加分析可發(fā)現(xiàn)，在檢索目錄文件時腻暮，只用到了文件名彤守，僅當(dāng)找到一個目錄項(xiàng)時，才從該目錄中讀取該文件的物理地址哭靖。顯然具垫，對文件進(jìn)行的描述信息在檢索目錄時一概不用調(diào)入內(nèi)存。

為此试幽，在有的系統(tǒng)中筝蚕，如UNIX系統(tǒng)，便采用了把文件名和文件描述信息分開的方法铺坞，使文件描述信息單獨(dú)形成一個稱為索引結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)起宽，簡稱為i結(jié)點(diǎn)（iNode），在文件目錄中的每個目錄項(xiàng)由文件名和指向該文件i結(jié)點(diǎn)的指針所構(gòu)成济榨。

2.1 磁盤索引結(jié)點(diǎn)

每個文件都有唯一的磁盤索引結(jié)點(diǎn)（磁盤索引結(jié)點(diǎn)信息與文件名等信息一起構(gòu)成了FCB）坯沪，其主要包括內(nèi)容如下：

• 1. 文件主標(biāo)識符，即擁有該文件的個人或小組的標(biāo)識符擒滑。
• 2. 文件類型腐晾，包括正規(guī)文件、目錄文件或特別文件丐一。
• 3. 文件存取權(quán)限藻糖，指各類用戶對該文件的存取權(quán)限。
• 4. 文件物理地址库车，每個索引結(jié)點(diǎn)中含有13個地址項(xiàng)（混合索引方式）巨柒，他們以直接或間接的方式給出數(shù)據(jù)文件所在的盤塊的編號。
• 5. 文件長度，指以字節(jié)為單位的文件長度洋满。
• 6. 文件連接計數(shù)晶乔，表明在本文件系統(tǒng)中所有指向該文件名的指針計數(shù)。
• 7. 文件存取時間芦岂，指本文件最近被進(jìn)程存取的時間瘪弓、最近被修改的時間及索引結(jié)點(diǎn)最近被修改的時間。

當(dāng)文件被打開時禽最，要將磁盤索引結(jié)點(diǎn)拷貝到內(nèi)存索引結(jié)點(diǎn)中腺怯，便于以后使用，在內(nèi)存索引結(jié)點(diǎn)中又增加了以下內(nèi)容：

• 1. 索引結(jié)點(diǎn)編號川无，用于標(biāo)識內(nèi)存索引結(jié)點(diǎn)呛占。
• 2. 狀態(tài)，指示i結(jié)點(diǎn)是否上鎖或被修改懦趋。
• 3. 訪問計數(shù)晾虑，每當(dāng)有進(jìn)程要訪問此i結(jié)點(diǎn)時，將訪問計數(shù)加1仅叫，訪問完再減1帜篇。
• 4. 文件所屬文件系統(tǒng)的邏輯設(shè)備號。
• 5. 鏈接指針诫咱，設(shè)置有分別指向空閑鏈表和散列隊(duì)列的指針笙隙。

3 目錄結(jié)構(gòu)

目錄結(jié)構(gòu)的組織，關(guān)系到文件系統(tǒng)的存取速度坎缭，也關(guān)系到文件的共享性和安全性竟痰，目前常用的目錄結(jié)構(gòu)形式有單級目錄、兩級目錄掏呼、多級目錄坏快。

3.1 單級目錄結(jié)構(gòu)

在整個系統(tǒng)中只建立一張目錄表，每個文件占一個目錄項(xiàng)憎夷，目錄項(xiàng)中含文件名莽鸿、文件擴(kuò)展名、文件長度拾给、文件類型富拗、文件物理地址、狀態(tài)位（表示目錄項(xiàng)是否空閑）等鸣戴。

每當(dāng)要建立一個新文件時，必須先檢查所有的目錄項(xiàng)粘拾，以保證新文件名在目錄中是唯一的窄锅，然后再從目錄表中找到一個空白目錄項(xiàng)，填入新文件名及其他說明信息，并置狀態(tài)為1入偷。

刪除文件時追驴，先從目錄中找到該文件的目錄項(xiàng)，回收該文件所占用的存儲空間疏之，然后再清除該目錄項(xiàng)殿雪。

優(yōu)點(diǎn)

• 簡單并且能夠?qū)崿F(xiàn)目錄管理的基本功能-按名存取。

缺點(diǎn)

• 查找速度慢
  查找具有N個目錄項(xiàng)的單級目錄平均要使用N/2次查找锋爪。

• 不允許重名
  在一個目錄表中的所有文件丙曙，都不能與另一個文件有相同的名字，這是難以避免的

• 不便于實(shí)現(xiàn)文件共享
  每一個用戶都有自己的名字空間或命名習(xí)慣其骄，因此亏镰，應(yīng)該允許不同用戶使用不同的文件名來訪問同一個文件

3.2 兩級目錄結(jié)構(gòu)

兩級目錄結(jié)構(gòu)，為每個用戶建立一個單獨(dú)的用戶文件目錄UFD（User File Directory）拯爽，這些文件目錄具有相似的結(jié)構(gòu)索抓，由用戶所有文件的文件控制塊組成。

系統(tǒng)中還有一個主文件目錄MFD（Master File Directory）毯炮，在主文件目錄中逼肯，每個用戶目錄文件都占有一個目錄項(xiàng)，其目錄項(xiàng)包括用戶名和指向用戶目錄文件的指針桃煎。

優(yōu)點(diǎn)

兩級目錄結(jié)構(gòu)克服了單級目錄的缺點(diǎn)篮幢，具有如下優(yōu)點(diǎn)：

• 提高了檢索目錄的速度
  如果在主目錄中有n個子目錄，每個用戶目錄最多為m個目錄項(xiàng)备禀，則為查找一指定的目錄項(xiàng)洲拇，最多只需要檢索n+m個目錄項(xiàng)。

• 在不同的用戶目錄中曲尸，可以使用相同的文件名
  只要在用戶自己的UFD中赋续，每個文件名都是唯一的，不同用戶可以有文件名相同的文件另患。不同用戶還可使用不同的文件名來訪問系統(tǒng)中同一個共享文件纽乱。

缺點(diǎn)

• 在多個用戶需要合作完成一個大任務(wù)時，不便于用戶之間共享文件昆箕。

3.3 多級目錄結(jié)構(gòu)

對于大型文件系統(tǒng)鸦列，通常采用三級或三級以上的目錄結(jié)構(gòu)，以提高對目錄的檢索速度和文件系統(tǒng)的性能鹏倘。多級目錄結(jié)構(gòu)又稱為樹形目錄結(jié)構(gòu)薯嗤，主目錄被稱為根目錄，把數(shù)據(jù)文件稱為樹葉纤泵，其他的目錄均作為樹的結(jié)點(diǎn)骆姐。

目錄結(jié)構(gòu)

方框代表目錄文件，圓圈代表數(shù)據(jù)文件，主目錄中有三個用戶總目錄A玻褪、B肉渴、C。在B用戶的總目錄B中带射，又包括三個分目錄F同规、E、D窟社，其中每個分目錄中又包含多個文件券勺。

為提高系統(tǒng)的靈活性，應(yīng)允許在一個目錄文件中的目錄項(xiàng)既是作為目錄文件的FCB桥爽，又是數(shù)據(jù)文件的FCB朱灿，這一信息可用目錄項(xiàng)中的一位來指示。如用戶A總目錄中钠四，目錄項(xiàng)A是目錄文件FCB盗扒，而目錄項(xiàng)B和D則是數(shù)據(jù)文件的FCB。

路徑名

在樹形目錄結(jié)構(gòu)中，從根目錄到任何數(shù)據(jù)文件，都只有一條唯一的通路驶沼，在該路徑上從樹的根開始建瘫，把全部目錄文件名和數(shù)據(jù)文件名依次用"/"連接起來假丧，即構(gòu)成該數(shù)據(jù)文件的路徑名。

為避免每訪問一個文件，都要使用從樹根開始直到樹葉（數(shù)據(jù)文件）的全路徑名，可為每個進(jìn)程設(shè)置一個當(dāng)前目錄（工作目錄）凡怎，進(jìn)程對各文件的訪問都相對于當(dāng)前目錄而進(jìn)行的。

把從當(dāng)前目錄開始值得數(shù)據(jù)文件為止所構(gòu)成的路徑名稱為相對路徑名赊抖，而把從樹根開始的路徑名稱為絕對路徑名统倒。

3.4 增加和刪除目錄

增加

在樹形目錄結(jié)構(gòu)中，用戶可為自己建立UFD氛雪，并可再創(chuàng)建子目錄房匆。

在用戶要創(chuàng)建一個新文件時，只需要查看自己的UFD及其子目錄中有無與新建文件相同的文件名报亩，若無浴鸿，便可在UFD或其某個子目錄中增加一個新目錄項(xiàng)。

刪除

在樹形目錄中弦追，如何刪除一個目錄岳链，應(yīng)該視情況而定，若要刪除的目錄為空劲件，則簡單地將其刪除宠页，使它在其上一級目錄中所對應(yīng)的目錄項(xiàng)為空左胞，若不為空，可采用如下方法：

• 不刪除非空目錄
  當(dāng)目錄不為空時举户，為了刪除一個非空目錄，必須先刪除目錄中所有的文件遍烦，使之稱為空目錄俭嘁，然后再刪除，如果目錄中包含有子目錄服猪，則應(yīng)該遞歸調(diào)用方式刪除

• 可刪除非空目錄
  將目錄中的所有文件和子目錄同時刪除供填。

4 目錄查詢技術(shù)

當(dāng)訪問一個已存在的文件時：

• 首先，利用文件名在目錄中找出該文件的文件控制塊或?qū)?yīng)索引結(jié)點(diǎn)
• 然后罢猪，根據(jù)FCB或索引結(jié)點(diǎn)中所記錄的文件物理地址（盤塊號）近她，換算出文件在磁盤上的物理位置
• 最后，再通過磁盤驅(qū)動程序膳帕，將所需文件讀入內(nèi)存粘捎。

目前常用的方式有線性檢索法和Hash方法。

4.1 線性檢索法

其又稱為順序檢索法危彩，在樹形目錄中攒磨，用戶提供的文件名是由多個文件分量名組成的路徑名，此時須對多級目錄進(jìn)行查找汤徽，假定用戶給定的文件路徑名為/usr/ast/mbox娩缰，則查找過程如下。

• 在根目錄中谒府，由usr找到結(jié)點(diǎn)6拼坎，定位到132；
• 在usr目錄中完疫，由ast找到26泰鸡，定位到496；
• 在ast目錄中趋惨，由mbox找到60鸟顺，查詢結(jié)束。

如果查詢失敗器虾，則返回“文件未找到”讯嫂。

4.2 Hash方法

系統(tǒng)利用用戶提供的文件名并將它轉(zhuǎn)換為文件目錄的索引值，再利用該索引值到目錄中去查找兆沙，這將顯著提高檢索速度欧芽。

注意：通配符無法進(jìn)行Hash目錄檢索。