非連續空間存放方式

我們已經對連續分配的方式有了一定的瞭解，並且也清楚了它存在的問題和局限性。為瞭解決這些問題，非連續存放的方式應運而生。非連續空間存儲大致可以分為兩種形式：鏈表形式和索引形式。

鏈式分配

鏈式分配是一種離散分配的方式，用於為文件分配非連續的磁碟塊。它有兩種分配方式：顯示鏈接和隱式鏈接。

隱式鏈接

隱式鏈表分配與我們已知的Java鏈表知識基本是一致的，都需要存儲下一個節點的指針。但為什麼稱之為隱式鏈接呢？因為我們不知道每個節點的指針是什麼，只有通過遍歷的方式從頭節點開始逐步獲取下一個節點的指針。每次操作都是相同的，指針並沒有存儲起來。在隱式鏈接分配中，目錄項只存儲了頭節點（磁碟塊）指針和尾節點（磁碟塊）指針。當需要分配新的磁碟塊時，我們使用最後一個磁碟塊中的指針指向新的磁碟塊，並將新的磁碟塊標記為最後一個磁碟塊。

現在讓我們考慮一個問題：使用隱式鏈接如何將邏輯塊號轉換為物理塊號？我們可以將其類比為Java中的鏈表如何找到相應的元素。

當用戶提供要訪問的邏輯塊號 i 時，操作系統需要找到所需訪問文件的文件控制塊（FCB）。從FCB中我們可以得知文件的起始塊號，然後將邏輯塊號 0 的數據讀入記憶體，通過這個可以知道邏輯塊號 1 的物理塊號，然後再讀入邏輯塊號 1 的數據進入記憶體，如此類推，最終可以找到用戶所需訪問的邏輯塊號 i。因此，訪問邏輯塊號 i 需要進行 i + 1 次磁碟 I/O 操作。隱式鏈接分配就像Java中的鏈表一樣只能按順序訪問，不支持隨機訪問，因此查找效率較低。

現在讓我們考慮另一個問題：使用隱式鏈接是否方便文件擴展？我們可以將其類比為Java中的鏈表是否方便進行擴容呢？

我們知道，目錄項中存儲了結束塊號的物理地址。因此，如果要擴展文件，我們只需要將新分配的磁碟塊掛載到結束塊號的後面。我們修改結束塊號的指針指向新分配的磁碟塊，並更新目錄項。隱式鏈接分配類似於Java中的鏈表，很方便進行文件擴展。所有的空閑磁碟塊都可以被利用，沒有碎片問題，存儲利用率較高。

顯式鏈接

有隱式連接那麼就有顯式鏈接，隱式鏈接我們說了沒有存儲各個節點指針所以每次都需要重新從頭結點來獲取下一指針節點，那麼顯示鏈接是把用於鏈接各個物理塊的指針顯式地存放在一張表中，該表稱為文件分配表（FAT，File Allocation Table）。

由於查找記錄的過程是在記憶體中進行的，從而顯著提高了檢索速度並減少了訪問磁碟的次數。但也正是整個表都存放在記憶體中的關係，它的主要的缺點是不適用於大磁碟。

舉個例子，假設有一個擁有200GB空間和1KB塊大小的磁碟。根據顯式鏈接的方式，需要在文件分配表中存儲2億項，每一項對應磁碟上的一個塊。如果每一項需要4個位元組的存儲空間，那麼文件分配表將占用800MB的記憶體。顯然，對於大磁碟而言，這種方式並不適合。

索引分配

理解索引分配之前，可以先想一下MySQL中的索引結構，這樣可以更好的理解索引分配的原理。

鏈表的方式解決了連續分配的磁碟碎片和文件動態擴展的問題，但是不能有效支持直接訪問（FAT除外）。為瞭解決這個問題，可以採用索引的方式。

索引的實現是為每個文件創建一個「索引數據塊」，裡面存放的是指向文件數據塊的指針列表，類似於書的目錄。通過查閱索引數據塊，可以快速找到對應的數據塊。

此外，文件頭還需要包含指向「索引數據塊」的指針。這樣可以通過文件頭知道索引數據塊的位置，然後通過索引數據塊里的索引信息找到對應的數據塊。

當創建文件時，索引塊的所有指針都被設置為空。當首次寫入第 i 塊時，從空閑空間中獲取一個塊，並將其地址寫入索引塊的第 i 個條目。這樣，通過文件頭中的指向索引數據塊的指針，可以知道索引數據塊的位置，並通過索引數據塊中的索引信息找到對應的數據塊。

索引分配的優點包括：

• 創建、增大和縮小文件都很方便；
• 沒有碎片問題；
• 支持順序讀寫和隨機讀寫。

然而，索引分配也有一些缺點。由於索引數據也需要存放在磁碟塊中，如果文件很小，實際上只需要一個塊就可以存放，但仍需要額外分配一個塊來存放索引數據，這會帶來額外的開銷。

如果文件很大，以至於一個索引數據塊無法容納全部的索引信息，我們可以採用組合的方式來處理大文件的存儲。

組合方式是鏈表 + 索引，也被稱為「鏈式索引塊」。在這種實現方式中，索引數據塊中會預留一個指針，用於存放下一個索引數據塊的地址。當一個索引數據塊的索引信息用完時，可以通過該指針找到下一個索引數據塊的信息。然而，這種方式也會面臨鏈表方式的問題，即如果某個指針損壞了，後續的數據將無法讀取。

為瞭解決這個問題，可以採用多級索引的方式。多級索引將一個大文件的索引信息分散到多個索引數據塊中，以減輕單個索引數據塊的負擔。類似於MySQL的B+樹索引結構，多級索引也在非葉子節點存儲了索引數據，而索引指針指向葉子節點的數據。儘管存在一些不同，但它們的邏輯是相似的。

總結

非連續空間存放方式是為瞭解決連續分配方式的問題和局限性而提出的。其中，鏈式分配方式包括隱式鏈接和顯式鏈接兩種形式。隱式鏈接通過存儲頭節點和尾節點指針的方式實現文件的非連續分配，但查找效率較低且不支持隨機訪問，但方便文件擴展且沒有碎片問題。顯式鏈接通過文件分配表存儲物理塊的指針，提高了檢索速度但不適用於大磁碟。

索引分配方式則通過為每個文件創建索引數據塊，併在文件頭和索引數據塊中存儲指針信息，實現了文件的非連續分配和直接訪問。索引分配的優點包括方便創建、擴展和縮小文件，沒有碎片問題，支持順序和隨機讀寫。然而，索引分配也存在一些缺點，如對小文件的額外開銷。

為瞭解決大文件存儲問題，可以採用鏈式索引塊和多級索引的組合方式。鏈式索引塊通過指針連接多個索引數據塊，但可能面臨指針損壞導致數據無法讀取的問題。多級索引將大文件的索引信息分散到多個索引數據塊中，提高了文件系統的性能和可靠性。通過這些優化，可以更好地處理大文件存儲，並提高文件系統的效率。