第4章-文件管理-文件系統(tǒng)(上)

• 初識(shí)文件管理

• 文件的屬性

• 操作系統(tǒng)向上提供的功能

• 從上往下看，文件應(yīng)如何存放在外存

• 文件的邏輯結(jié)構(gòu)

• 順序文件

• 索引文件

• 索引順序文件

• 多級索引順序文件

• 有結(jié)構(gòu)文件

• 文件目錄

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

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

• 多級目錄結(jié)構(gòu)（樹形目錄結(jié)構(gòu)）

• 無環(huán)圖目錄結(jié)構(gòu)

• 文件控制塊

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

• 索引結(jié)點(diǎn)（FCB改進(jìn)）

• 文件的物理結(jié)構(gòu)

• 連續(xù)分配

• 鏈接分配

• 索引分配

• 文件塊、磁盤塊

• 文件分配方式

第4章-文件管理-文件系統(tǒng)(上)

初識(shí)文件管理

文件的屬性

1. 文件名：由創(chuàng)建文件的用戶決定文件名，主要是為了方便用戶找到文件。同一目錄下不允許有重名文件

2. 標(biāo)識(shí)符：一個(gè)系統(tǒng)內(nèi)的各文件標(biāo)識(shí)符唯一，對用戶來說毫無可讀性，因此標(biāo)識(shí)符只是操作系統(tǒng)用于區(qū)分各個(gè)文件的一種內(nèi)部名稱

3. 類型：指明文件的類型

4. 位置：文件存放的路徑（讓用戶使用）、在外存中的地址（操作系統(tǒng)使用，對用戶不可見）

5. 大?。褐该魑募笮?/span>

6. 創(chuàng)建時(shí)間、上次修改時(shí)間、文件所有者信息

7. 保護(hù)信息：對文件進(jìn)行保護(hù)的訪問控制信息

無結(jié)構(gòu)文件（如文本文件）：由一些二進(jìn)制或字符流組成，又稱“流式文件”

有結(jié)構(gòu)文件（如數(shù)據(jù)庫表）：由一組相似的記錄組成，又稱“記錄式文件”

有結(jié)構(gòu)文件中，各個(gè)記錄間應(yīng)該如何組織的問題——應(yīng)該順序存放？還是用索引表來表示記錄間的順序？——這是“文件的邏輯結(jié)構(gòu)”重點(diǎn)要探討的問題

操作系統(tǒng)向上提供的功能

• 創(chuàng)建文件：點(diǎn)擊新建后，圖形化交互進(jìn)程在背后調(diào)用了create系統(tǒng)調(diào)用

• 讀文件：將文件數(shù)據(jù)讀入內(nèi)存，才能讓CPU處理（雙擊后，記事本應(yīng)用程序通過操作系統(tǒng)提供的“讀文件”功能，即read系統(tǒng)調(diào)用，將文件數(shù)據(jù)從外存讀入內(nèi)存，并顯示在屏幕上）

• 寫文件：將更改進(jìn)的文件數(shù)據(jù)寫回外存（在機(jī)身應(yīng)用程序中編輯文件內(nèi)容，點(diǎn)擊“保存”后，記事本應(yīng)用程序通過操作系統(tǒng)提供的寫文件功能，即write系統(tǒng)調(diào)用，將文件數(shù)據(jù)從內(nèi)存寫回外存

• 刪除文件：點(diǎn)了“刪除”之后，圖形化交互進(jìn)程通過操作系統(tǒng)提供的“刪除文件”功能，即delete系統(tǒng)調(diào)用，將文件數(shù)據(jù)從外存中刪除

• 打開文件：open系統(tǒng)調(diào)用

• 關(guān)閉文件：close系統(tǒng)調(diào)用

文件共享：使多個(gè)用戶可以共享使用同一個(gè)文件

文件保護(hù)：如何保證不同的用戶對文件有不同的操作權(quán)限

從上往下看，文件應(yīng)如何存放在外存

與內(nèi)存一樣，外存也是由一個(gè)個(gè)存儲(chǔ)單元組成的，每個(gè)存儲(chǔ)單元可以存儲(chǔ)一定量的數(shù)據(jù)（如1B），每個(gè)存儲(chǔ)單元對應(yīng)一個(gè)物理地址

類似于內(nèi)存分為一個(gè)個(gè)“內(nèi)存塊”，外存會(huì)分為一個(gè)個(gè)“塊/磁盤塊/物理塊”，每個(gè)磁盤塊的大小是相等的，每塊一般包含2的整數(shù)次冪個(gè)地址。同樣類似的是，文件的邏輯地址也可以分為（邏輯塊號，塊內(nèi)地址），操作系統(tǒng)同樣需要將邏輯地址轉(zhuǎn)為外存的物理地址（物理塊號，塊內(nèi)地址）的形式。塊內(nèi)地址的位數(shù)取決于磁盤塊的大小

操作系統(tǒng)以“塊”為單位為文件分配存儲(chǔ)空間，因此即使一個(gè)文件大小只有10B，但它依然需要占用1KB的磁盤塊。外存中的數(shù)據(jù)讀入內(nèi)存時(shí)同樣以塊為單位

文件的邏輯結(jié)構(gòu)

所謂的“邏輯結(jié)構(gòu)”，就是指在用戶看來，文件內(nèi)部的數(shù)據(jù)應(yīng)該是如何組織起來的。而“物理結(jié)構(gòu)”指的是在操作系統(tǒng)看來，文件的數(shù)據(jù)是如何存放在外存中的

類似于數(shù)據(jù)結(jié)構(gòu)的“邏輯結(jié)構(gòu)”和“物理結(jié)構(gòu)”。如“線性表”就是一種邏輯結(jié)構(gòu)，在用戶看來，線性表就是一組有先后關(guān)系的元素序列，如a,b,c,d,e…“線性表”這種邏輯結(jié)構(gòu)可以用不同的物理結(jié)構(gòu)實(shí)現(xiàn)，如順序表/鏈表。順序表的各個(gè)元素在邏輯上相鄰，在物理上頁相鄰；而鏈表的各個(gè)元素在物理上可以是不相鄰的。因此，順序表可以實(shí)現(xiàn)“隨機(jī)訪問”，而“鏈表”無法實(shí)現(xiàn)隨機(jī)訪問

可見，算法的具體實(shí)現(xiàn)都與邏輯結(jié)構(gòu)物理結(jié)構(gòu)有關(guān)（文件也一樣，文件的具體實(shí)現(xiàn)與文件的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)都有關(guān)）

有結(jié)構(gòu)文件

按文件是否有結(jié)構(gòu)分類，可以分為無結(jié)構(gòu)文件、有結(jié)構(gòu)文件兩種

• 無結(jié)構(gòu)文件：文件內(nèi)部的數(shù)據(jù)就是一系列二進(jìn)制流或字符流組成，又稱“流式文件”。如Windows操作系統(tǒng)的.txt文件

• 有結(jié)構(gòu)文件：由一組相似的記錄組成，又稱“記錄式文件”。每條記錄由若干個(gè)數(shù)據(jù)項(xiàng)組成。如數(shù)據(jù)庫表文件。一般來說，每條記錄有一個(gè)數(shù)據(jù)項(xiàng)可作為關(guān)鍵字（作為識(shí)別不同記錄的ID）。根據(jù)各條記錄的長度（占用的存儲(chǔ)空間）是否相等，又可分為定長記錄和可變長記錄兩種

順序文件

順序文件：文件中的記錄一個(gè)接一個(gè)地順序排列（邏輯上），記錄可以是定長的或者可變長的。各個(gè)記錄在物理上可以順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)

• 串結(jié)構(gòu)：記錄之間的順序與關(guān)鍵字無關(guān)（通常按記錄存入的時(shí)間決定記錄的順序）

• 順序結(jié)構(gòu)：記錄之間的順序按關(guān)鍵字順序排列

假設(shè)：已經(jīng)知道了文件的起始地址（也就是第一個(gè)記錄存放的位置）

1. 思考1：能否快速找到第i個(gè)記錄對應(yīng)的地址？（即能否實(shí)現(xiàn)隨機(jī)存?。?/span>

2. 思考2：能否快速找到某個(gè)關(guān)鍵字對應(yīng)的記錄存放的位置

• 順序存儲(chǔ)——邏輯上相鄰的記錄物理上也相鄰（類似于順序表）

• 若采用串結(jié)構(gòu)，無法快速找到某關(guān)鍵字對應(yīng)的記錄

• 若采用順序結(jié)構(gòu)，可以快速找到某關(guān)鍵字對應(yīng)的記錄（如折半查找）

• 可變長記錄：無法實(shí)現(xiàn)隨機(jī)存取，每次只能從第一個(gè)記錄開始往后查找

• 定長記錄：可實(shí)現(xiàn)隨機(jī)存取。記錄長度為L，則第i個(gè)記錄存放的相對位置是i*L。

• 鏈?zhǔn)酱鎯?chǔ)——邏輯上相鄰的記錄物理上不一定相鄰（類似于鏈表）無論是定長/可變長記錄，都無法實(shí)現(xiàn)隨機(jī)存取，每次只能從第一個(gè)記錄開始依次往后找

結(jié)論：定長記錄的順序文件，若物理上采用順序存儲(chǔ)，則可實(shí)現(xiàn)隨機(jī)存?。蝗粼倌鼙ＷC記錄的順序結(jié)構(gòu)，則可實(shí)現(xiàn)快速檢索（即根據(jù)關(guān)鍵字快速找到對應(yīng)記錄）

一般來說，考試題目中所說的“順序文件”指的是物理上順序存儲(chǔ)的順序文件。之后的講解中提到的順序文件也默認(rèn)如此。順序文件的缺點(diǎn)是增加/刪除一個(gè)記錄比較困難（如果是串結(jié)構(gòu)則相對簡單）

索引文件

對于可變長記錄文件，要找到第i個(gè)記錄，必須先順序地查找簽i-1條記錄，到那時(shí)很多應(yīng)用場景又必須使用可變長記錄，如何解決這個(gè)問題？

索引表本身是定長記錄的順序文件。因此可以快速找到第i個(gè)記錄對應(yīng)的索引項(xiàng)。

可將關(guān)鍵字作為索引號內(nèi)容，若按關(guān)鍵字順序排列，則還可以支持按照關(guān)鍵字折半查找。

每當(dāng)要增加/刪除一個(gè)記錄時(shí)，需要對索引表進(jìn)行修改。由于索引文件有很快的檢索速度，因此主要用于對信息處理的及時(shí)性要求比較高的場合。

另外，可以用不同的數(shù)據(jù)項(xiàng)建立多個(gè)索引表。如學(xué)生信息表中，可用關(guān)鍵字“學(xué)號”建立一張索引表，也可以用“姓名”建立一張索引表。這樣就可以根據(jù)“姓名”快速地檢索文件了。

索引順序文件

思考索引文件的缺點(diǎn)：每個(gè)記錄對應(yīng)一個(gè)索引表項(xiàng)，因此索引表可能會(huì)很大。比如：文件的每個(gè)記錄平均只占8B，而每個(gè)索引表項(xiàng)占32個(gè)字節(jié)，那么索引表都要比文件內(nèi)容本身大4倍，這樣對存儲(chǔ)空間的利用率就太低了

索引順序文件是索引文件和順序文件思想的結(jié)合。索引順序文件中，同樣會(huì)為文件建立一張索引表，但不同的是：并不是每個(gè)記錄對應(yīng)一個(gè)索引表項(xiàng)，而是一組記錄對應(yīng)一個(gè)索引表項(xiàng)

多級索引順序文件

為進(jìn)一步提高檢索效率，可以為順序文件建立多級索引表。例如，對一個(gè)含10^6個(gè)記錄的文件，可先為該文件建立一張低級索引表，每100個(gè)記錄分為一組，故低級索引表中共有10000個(gè)表項(xiàng)（即10000個(gè)定長記錄），再把這10000個(gè)定長記錄分組，每組100個(gè)，為建立其頂級索引表，故頂級索引表中共有100個(gè)表項(xiàng)

文件目錄

文件控制塊

目錄本身就是一種結(jié)構(gòu)文件，由一條條記錄組成。每條記錄對應(yīng)一個(gè)在該放在該目錄下的文件

目錄文件中的一條記錄就是一個(gè)“文件控制塊（FCB)”

FCB中包含了文件的基本信息（文件名、物理地址、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)等），存取控制信息（是否可讀/可寫、禁止訪問的用戶名單等），使用信息（如文件的建立時(shí)間、修改時(shí)間等）。最重要、最基本的還是文件名、文件存放的物理地址

FCB實(shí)現(xiàn)了文件名和文件之間的映射。使用戶（用戶程序）可以實(shí)現(xiàn)“按名存取”

需要對目錄進(jìn)行哪些操作？

1. 搜索：當(dāng)用戶要使用一個(gè)文件時(shí)，系統(tǒng)要根據(jù)文件名搜索目錄，找到該文件對應(yīng)的目錄項(xiàng)

2. 創(chuàng)建文件：創(chuàng)建一個(gè)新文件時(shí)，需要在其所屬的目錄中增加一個(gè)目錄項(xiàng)

3. 刪除文件：當(dāng)刪除一個(gè)文件時(shí)，需要在目錄中刪除相應(yīng)的目錄項(xiàng)

4. 顯示目錄：用戶可以請求顯示目錄的內(nèi)容，如顯示該目錄中的所有文件及相應(yīng)屬性

5. 修改目錄：某些文件屬性保存在目錄中，因此這些屬性變化時(shí)需要修改相應(yīng)的目錄項(xiàng)（如：文件重命名）

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

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

早期操作系統(tǒng)并不支持多級目錄，整個(gè)系統(tǒng)中只建立了一張目錄表，每個(gè)文件占一個(gè)目錄項(xiàng)。單機(jī)目錄實(shí)現(xiàn)了“按名存取”，但是不允許文件重命名

顯然，單級目錄結(jié)構(gòu)不適用于多用戶操作系統(tǒng)

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

早期的多用戶操作系統(tǒng)，采用兩級目錄結(jié)構(gòu)。分為主文件目錄（MFD，Master File Directory）和用戶文件目錄（UFD，User File Directory）

多級目錄結(jié)構(gòu)（樹形目錄結(jié)構(gòu)）

用戶（或用戶進(jìn)程）要訪問某個(gè)文件時(shí)要用文件路徑名標(biāo)識(shí)文件。文件路徑名是個(gè)字符串。各級目錄之間用"/"隔開。從根目錄出發(fā)的路徑稱為絕對路徑

從當(dāng)前目錄出發(fā)的稱為相對路徑。使用相對路徑訪問可以減少讀磁盤IO操作的次數(shù)

無環(huán)圖目錄結(jié)構(gòu)

在樹形目錄結(jié)構(gòu)的基礎(chǔ)上，增加一些指向同一節(jié)點(diǎn)的有向邊，使整個(gè)目錄成為一個(gè)有向無環(huán)圖，可以更方便地實(shí)現(xiàn)多個(gè)用戶間的文件共享

可以用不同的文件名指向同一個(gè)文件，甚至可以指向同一個(gè)目錄（共享同一目錄下的所有內(nèi)容）

需要為每個(gè)空閑節(jié)點(diǎn)設(shè)置一個(gè)共享計(jì)數(shù)器，用于記錄此時(shí)有多少個(gè)地方在共享該結(jié)點(diǎn)。用戶提出刪除結(jié)點(diǎn)的請求時(shí)，只是刪除該用戶的FCB，并使共享計(jì)數(shù)器減1，并不會(huì)直接刪除共享結(jié)點(diǎn)。只有共享計(jì)數(shù)器減為0時(shí)，才刪除結(jié)點(diǎn)

注意：共享文件不同于復(fù)制文件。在共享文件中，由于各用戶指向的是同一個(gè)文件，因此只要其中一個(gè)用戶修改了文件數(shù)據(jù)，那么所有用戶都可以看到文件數(shù)據(jù)的變化

索引結(jié)點(diǎn)（FCB改進(jìn)）

其實(shí)在查找各級目錄的過程中只要用到“文件名”這個(gè)信息，只有文件名匹配時(shí)，才需要讀出文件的其他信息，因此可以考慮讓目錄表“瘦身”來提升效率

當(dāng)找到文件名對應(yīng)的目錄項(xiàng)時(shí)，才需要將索引結(jié)點(diǎn)調(diào)入內(nèi)存。索引結(jié)點(diǎn)中記錄了文件的各種信息，包括文件在外存中的存放位置，根據(jù)“存放位置”即可找到文件

存放在外存中的索引結(jié)點(diǎn)稱為“磁盤索引結(jié)點(diǎn)”，當(dāng)索引結(jié)點(diǎn)放入內(nèi)存后稱為“內(nèi)存索引結(jié)點(diǎn)”。相比之下內(nèi)存索引結(jié)點(diǎn)中需要增加一些信息，比如：文件是否被修改、此時(shí)有幾個(gè)進(jìn)程正在訪問該文件等

文件的物理結(jié)構(gòu)

文件塊、磁盤塊

類似于內(nèi)存分頁，磁盤中的存儲(chǔ)單元也會(huì)被分為一個(gè)個(gè)“塊/磁盤塊/物理塊”，很多操作系統(tǒng)中，磁盤塊的大小與內(nèi)存塊、頁面的大小相同

內(nèi)存與磁盤之間的數(shù)據(jù)交換（即讀/寫操作、磁盤IO）都是以“塊”為單位進(jìn)行的。即每次讀入一塊，或每次寫出一塊

在內(nèi)存管理中，進(jìn)程的邏輯地址空間被分為一個(gè)一個(gè)頁面。同樣的，在外存管理中，為了方便對文件數(shù)據(jù)的管理，文件的邏輯地址空間也被分為了一個(gè)一個(gè)的文件“塊”。于是文件的邏輯地址也可以表示為（邏輯塊號，塊內(nèi)地址）的形式

文件分配方式

連續(xù)分配

連續(xù)分配方式要求每個(gè)文件在磁盤上占有一組連續(xù)的塊

用戶給出要訪問的邏輯塊號，操作系統(tǒng)找到該文件對應(yīng)的目錄項(xiàng)（FCB）

物理塊號=起始塊號+邏輯塊號

當(dāng)然，還需要檢查用戶提供的邏輯塊號是否合法（邏輯塊號\ge長度就不合法）

可以直接算出邏輯塊號對應(yīng)的物理塊號，因此連續(xù)分配支持順序訪問和直接訪問（即隨機(jī)訪問）

讀取某個(gè)磁盤塊時(shí)，需要移動(dòng)磁頭。訪問的兩個(gè)磁盤塊相隔越遠(yuǎn)，移動(dòng)磁頭所需時(shí)間久越長。因此連續(xù)分配的文件在順序讀/寫時(shí)速度最快

物理上采用連續(xù)分配的文件不方便拓展

物理上采用連續(xù)分配，存儲(chǔ)空間利用率低，會(huì)產(chǎn)生難以利用的磁盤碎片可以用緊湊來處理碎片，但是需要耗費(fèi)很大的時(shí)間代價(jià)

總結(jié)：

• 優(yōu)點(diǎn)：支持順序訪問和直接訪問（即隨機(jī)訪問）；連續(xù)分配的文件在順序訪問時(shí)速度最快

• 缺點(diǎn)：不方便文件拓展；存儲(chǔ)空間利用率低，會(huì)產(chǎn)生磁盤碎片

鏈接分配

鏈接分配采取離散分配的方式，可以為文件分配離散的磁盤塊，分為隱式鏈接和顯式鏈接兩種

• 隱式分配

目錄中記錄了文件存放的起始塊號和結(jié)束塊號。當(dāng)然也可以增加一個(gè)字段來表示文件的長度。除了文件的最后一個(gè)磁盤塊之外，每個(gè)磁盤塊中都會(huì)保存指向下一個(gè)盤塊的指針，這些指針對用戶是透明的。

如何實(shí)現(xiàn)文件的邏輯塊號到物理塊號的轉(zhuǎn)變？

用戶給出要訪問的邏輯塊號i，操作系統(tǒng)找到該文件對應(yīng)的目錄項(xiàng)（FCB）

從目錄項(xiàng)中找到起始塊號（即0號塊），將0號邏輯塊讀入內(nèi)存，由此知道1號邏輯塊存放的物理塊號，于是讀入1號邏輯塊，再找到2號邏輯塊的存放位置……以此類推因此，讀入i號邏輯塊，總共需要i+1次磁盤IO。

若此時(shí)要拓展文件，則可以隨便找一個(gè)空閑磁盤塊，掛到文件的磁盤塊鏈尾，并修改文件的FCB

結(jié)論：采用鏈?zhǔn)椒峙洌[式鏈接）方式的文件，只支持順序訪問，不支持隨機(jī)訪問，查找效率低。另外，指向下一個(gè)盤塊的指針也需要耗費(fèi)少量的存儲(chǔ)空間。很方便文件拓展。另外，所有的空閑磁盤塊都可以被利用，不會(huì)有碎片問題，外存利用率高

• 顯式鏈接

顯式鏈接：把用于鏈接文件各物理塊的指針顯式地存放在一張表中，即文件分配表（FAT，F(xiàn)ile Allocation Table）

注意：一個(gè)磁盤僅設(shè)置一張F(tuán)AT，開機(jī)時(shí)，將FAT讀入內(nèi)存，并常駐內(nèi)存。FAT的各個(gè)表項(xiàng)在物理上連續(xù)存儲(chǔ)，且每一個(gè)表項(xiàng)長度相同，因此“物理塊號”字段可以是隱含的。

如何實(shí)現(xiàn)文件的邏輯塊號到物理塊號的轉(zhuǎn)變？

用戶給出要訪問的邏輯塊號i，操作系統(tǒng)找到該文件對應(yīng)的目錄項(xiàng)FCB

從目錄項(xiàng)中找到起始塊號，若i>0，則查詢內(nèi)存中的文件分配表FAT，往后找到i號邏輯塊對應(yīng)的物理塊號。邏輯塊號轉(zhuǎn)換成物理塊號的過程不需要讀磁盤操作

結(jié)論：采用鏈?zhǔn)椒峙洌@式鏈接）方式的文件，支持順序訪問，也支持隨機(jī)訪問（想訪問i號邏輯塊時(shí)，并不需要依次訪問之前的0~i號邏輯塊），由于塊號的轉(zhuǎn)換過程并不需要訪問磁盤，因此相比于隱式鏈接方式來說，訪問速度快很多。顯式鏈接也不會(huì)產(chǎn)生外部碎片，可以很方便地對文件進(jìn)行拓展

索引分配

索引分配允許文件離散地分配在各個(gè)磁盤塊中，系統(tǒng)會(huì)為每個(gè)文件建立一張索引表，索引表中記錄了文件的各個(gè)邏輯塊對應(yīng)的物理塊（索引表的功能類似于內(nèi)存管理中的頁表——建立邏輯頁面到物理頁之間的映射關(guān)系）。索引表存放的磁盤塊稱為索引塊。文件數(shù)據(jù)存放的磁盤塊稱為數(shù)據(jù)塊。

在顯式鏈接的鏈?zhǔn)椒峙浞绞街?，文件分配表FAT是一個(gè)磁盤對應(yīng)一張。而索引分配方式中，索引表是一個(gè)文件對應(yīng)一張

如何實(shí)現(xiàn)文件的邏輯塊號到物理塊號的轉(zhuǎn)換？

用戶給出要訪問的邏輯塊號i，操作系統(tǒng)找到該文件的目錄項(xiàng)FCB，從目錄項(xiàng)FCB可知索引表存放位置，將索引表從外存讀入內(nèi)存，并查找索引表即可知i號邏輯塊在外存中的位置

可見，索引分配方式可以實(shí)現(xiàn)隨機(jī)訪問，文件拓展也很容易實(shí)現(xiàn)（只需要給文件分配一個(gè)空閑塊，并增加一個(gè)索引表項(xiàng)即可）

但是索引表需要占用一定的存儲(chǔ)空間

若每個(gè)磁盤塊1KB，一個(gè)索引表項(xiàng)4B，則一個(gè)磁盤塊只能存放256個(gè)索引項(xiàng)。如果一個(gè)文件的大小超過了256塊，那么一個(gè)磁盤塊時(shí)裝不下整個(gè)文件的索引表的，如何解決這個(gè)問題？

1. 鏈接方案：如果索引表太大，一個(gè)索引塊裝不下，那么可以將多個(gè)索引塊鏈接起來存放。缺點(diǎn)：若文件很大，索引表很長，就需要將很多個(gè)索引塊鏈接起來。想要找到i號索引塊，必須先依次讀入0~i-1號索引塊，這就導(dǎo)致磁盤IO次數(shù)過多，查找效率低下

2. 多層索引：建立多層索引（原理類似于多級列表）。使第一層索引塊指向第二層的索引塊。還可根據(jù)文件大小的要求再建第三層、第四層索引塊

   缺點(diǎn)：即使是小文件，訪問一個(gè)數(shù)據(jù)塊依然需要K+1次讀磁盤

3. 混合索引：多種索引分配方式的結(jié)合。例如，一個(gè)文件的頂級索引表中，既包含直接地址索引（直接指向數(shù)據(jù)塊），又包含一級間接索引（指向單層索引表），還包含兩級間接索引（指向兩層索引表）

   優(yōu)點(diǎn)：對于小文件來說，訪問一個(gè)數(shù)據(jù)塊所需的讀磁盤次數(shù)更少