非連續空間存放方式

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

鏈式分配

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

隱式連結

隱式連結串列分配與我們已知的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+樹索引結構，多級索引也在非葉子節點儲存了索引資料，而索引指標指向葉子節點的資料。儘管存在一些不同，但它們的邏輯是相似的。

總結

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

索引分配方式則通過為每個檔案建立索引資料塊，並在檔案頭和索引資料塊中儲存指標資訊，實現了檔案的非連續分配和直接存取。索引分配的優點包括方便建立、擴充套件和縮小檔案，沒有碎片問題，支援順序和隨機讀寫。然而，索引分配也存在一些缺點，如對小檔案的額外開銷。

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