在計算機世界中，文件是數(shù)據(jù)的抽象集合，它為用戶提供了一種直觀的方式來處理數(shù)據(jù)。而這些文件的數(shù)據(jù)最終必須存儲在具體的物理設(shè)備上，例如HDD、SSD 或是 USB。這些存儲設(shè)備通過設(shè)備控制器將他們的物理介質(zhì)映射為一個巨大的、可隨機尋址的地址空間，我們可以將其看作一個超大的數(shù)組。一個設(shè)備可以儲存多個文件，那么，如何將多個抽象的文件映射到這一巨大空間上，就是一個非常重要的問題。文件系統(tǒng)的設(shè)計在這里起著至關(guān)重要的作用，它必須以合理的方式將文件分布到物理存儲介質(zhì)上，以確保存儲和訪問的高效性。本文將為您介紹幾種經(jīng)典的文件分配方式及其優(yōu)缺點。

物理存儲的基本概念：塊與簇

當硬盤經(jīng)過設(shè)備控制器抽象為一個超大的數(shù)組后，對于設(shè)備來說，塊（block）通常是存儲介質(zhì)的最小單元。每個塊有固定的大小，例如 4KB，由存儲介質(zhì)本身決定。這些塊是存儲設(shè)備的最小分配和管理單位。而為了更好地利用空間并減少管理開銷，在系統(tǒng)中，塊可以進一步組合成更大的存儲單位，稱為簇（cluster），通常簇由幾個連續(xù)的塊組成。通常在格式化時可以指定簇大小，之后就不再改變，一簇至少包含一個塊，也可以設(shè)定為包含多個塊。

簇的大小直接影響到存儲效率和文件系統(tǒng)的性能。大簇（如32KB或64KB）意味著每個簇可以容納更多數(shù)據(jù)，從而減少文件系統(tǒng)管理這些簇的開銷，管理更容易且讀寫性能高，但會導致即使是 1 字節(jié)的文件也會占用一簇，造成小文件占用過多空間的情況，導致內(nèi)部碎片（internal fragmentation）。反之，小簇（如512字節(jié)或4KB）可以減少內(nèi)部碎片，但會增加管理簇的復雜性和處理開銷。因此，簇大小的選擇是權(quán)衡存儲效率與管理開銷的重要決策。

在格式化完成后，簇就成為文件系統(tǒng)視角下的最小分配單位，后文就不區(qū)分這兩個概念了。

連續(xù)分配：最簡單卻難以擴展的方案

存儲器已經(jīng)劃分為以簇編址的巨大數(shù)組，而文件也被劃分為幾簇，接下來我們要考慮怎樣為他們安排位置。

連續(xù)分配（Contiguous Allocation）是文件系統(tǒng)中最簡單的物理分配方式。它將文件存儲在一組連續(xù)的簇中。在文件記錄中，只需要存儲文件的起始位置和長度，這樣在訪問文件時，只需要從起始位置開始，讀取指定長度的數(shù)據(jù)即可。由于連續(xù)分配的文件在物理磁盤上是緊密排列的，因此它非常適合隨機訪問（random access），尤其是對大文件的順序訪問時，性能表現(xiàn)十分優(yōu)秀。當新增文件時，直接找到可容納下文件的連續(xù)塊插入即可。

然而，連續(xù)分配也有許多致命缺點：

1. 外部碎片（External Fragmentation）：隨著文件不斷地創(chuàng)建和刪除，磁盤空間會被割裂為許多不連續(xù)的小塊，導致碎片化，最終可能出現(xiàn)雖然總空間足夠，但無法找到足夠連續(xù)空間分配給新文件的情況。
2. 文件大小固定：由于文件必須存儲在連續(xù)的空間中，因此文件的大小在創(chuàng)建時就需要確定，且不能動態(tài)擴展。如果文件需要增長，就可能會覆蓋其他文件的數(shù)據(jù)。
3. 頻繁的數(shù)據(jù)移動：如果文件需要擴展而當前空間不足，就可能需要將文件移動到其他更大的連續(xù)區(qū)域，這將導致大量的數(shù)據(jù)移動（data movement），耗費性能。

這些缺點使得連續(xù)分配在現(xiàn)代操作系統(tǒng)中很少使用，尤其是在面對高頻率的文件操作時。然而，在某些特定情況下，例如對于磁帶這樣的順序訪問存儲介質(zhì)（sequential access storage medium），連續(xù)分配仍然是有效的選擇。

簡單鏈表分配：解決碎片問題的嘗試

為了解決外部碎片的問題，一種改進的方法是鏈表分配（Linked Allocation）。在鏈表分配中，文件被分為多個塊，每個塊通過一個指針鏈接到下一個塊，從而形成一個鏈表。文件記錄只需要存儲文件的第一個塊的地址（以及可能的最后一個塊地址），其余的塊通過鏈表指針進行訪問。這樣離散的分配方式也就不再有外部碎片。

然而，鏈表分配也有明顯的缺點：

1. 無法隨機訪問：由于塊之間通過指針鏈接，無法直接跳轉(zhuǎn)到某個特定塊，因此只能順序訪問（sequential access）文件的內(nèi)容。如果需要訪問文件的某個特定位置，必須從頭開始遍歷整個鏈表。
2. 可靠性問題：由于每個塊都通過指針鏈接，一旦某個塊的指針損壞，就會導致整個文件的剩余部分無法訪問。
3. 存儲開銷：每個塊需要額外存儲一個指針，這增加了存儲開銷，文件越小，這種額外開銷帶來的浪費越顯著。

鏈表分配解決了外部碎片的問題，但由于無法隨機訪問和存儲開銷大的缺點，使得它在現(xiàn)代操作系統(tǒng)中的應(yīng)用也較為有限。

顯式鏈表分配：文件分配表 (FAT)

在鏈表分配的基礎(chǔ)上，另一種改進方式是顯式鏈表分配（Explicit Linked Allocation），即將每個塊的指針信息集（即下一塊）中存儲在一個專門的表中（而非儲存到每個塊中），這就是文件分配表（File Allocation Table, FAT）。FAT 是一種將每一個簇和其后續(xù)簇的位置關(guān)系集中存儲的結(jié)構(gòu)，通過查找文件的起始簇，可以逐步找到文件的所有簇。

在 FAT 結(jié)構(gòu)下，文件記錄仍只需要存儲文件的起始塊位置，然后通過 FAT 來找到其他塊的位置。這樣的設(shè)計使得在文件內(nèi)進行塊間跳轉(zhuǎn)變得更加方便，雖然 FAT 仍然不能真正實現(xiàn)隨機訪問，但跳轉(zhuǎn)速度相較于簡單鏈表分配要快得多。為了提高訪問速度，操作系統(tǒng)通常將 FAT 緩存在內(nèi)存中，從而在文件訪問時減少對磁盤的頻繁讀取。

FAT 結(jié)構(gòu)具有如下特點：

1. 集中管理鏈表信息：通過將所有簇的信息集中管理，F(xiàn)AT 使得文件的管理更加簡單，整個文件系統(tǒng)只需要一張表，特別是在進行空間分配和回收時，能有效追蹤哪些簇是空閑的。
2. 提高訪問效率：由于 FAT 可以被緩存到內(nèi)存中，文件訪問的速度顯著提高，尤其是在文件內(nèi)部跳轉(zhuǎn)時。
3. 文件限制：簇大小和指針位數(shù)決定了單文件大小的上限。假設(shè)一個 FAT 文件系統(tǒng)使用 16 位指針來表示每個簇的位置，并且簇的大小為 4KB，那么可以表示的最大簇數(shù)是 2^16 = 65536 個簇。因此，該文件系統(tǒng)支持的最大文件大小為 65536 * 4KB = 256MB。

FAT 系列文件系統(tǒng)最早設(shè)計于 1977 年，歷經(jīng)多次演化，至今仍有應(yīng)用，特別是在嵌入式設(shè)備和閃存設(shè)備（如 USB 閃存）中。FAT 系列文件系統(tǒng)（如 FAT16、FAT32）由于其簡單性和廣泛兼容性，成為了很多嵌入式設(shè)備的首選。exFAT 是微軟在 2006 年引入的一種新的文件系統(tǒng)，專為閃存設(shè)備設(shè)計，主要目的是在 FAT32 的基礎(chǔ)上克服其局限性，相比上面介紹的原始版本拓展了很多功能，同時保持兼容性。

索引分配：真正實現(xiàn)隨機訪問

在離散存儲的基礎(chǔ)上，顯然不一定要使用鏈表。可以在文件記錄中以變長數(shù)組記錄每個塊的位置，這樣就可以實現(xiàn)真正的隨機訪問。這種數(shù)組叫做索引（index），這種分配方式稱為索引分配（Indexed Allocation）。在索引分配中，文件系統(tǒng)會為在每個文件的文件記錄里維護其索引塊，索引塊中存儲了文件各個數(shù)據(jù)塊的物理位置。通過查找這個索引塊，操作系統(tǒng)可以直接定位到文件的任意塊，從而實現(xiàn)快速的隨機訪問。簡單來說，索引用數(shù)組實現(xiàn)就可以，也可以選擇二叉樹或哈希表，這就不是本文的重點了。

單級索引（Single-Level Index）是最簡單的一種索引分配方式，其中每個文件都有一個單獨的索引塊，記錄文件的所有數(shù)據(jù)塊位置。這使得文件的訪問變得非常靈活，特別是對于需要頻繁隨機訪問的場景，索引分配具有顯著的優(yōu)勢。此外，由于索引塊集中存儲了所有的塊位置，文件的增刪也變得更加容易，只需更新索引塊即可，無需對物理塊進行復雜的移動操作。

例如，假設(shè)一個單級索引系統(tǒng)，每個索引塊的大小為 4KB，且每個指針占用 4 字節(jié)，那么一個索引塊最多可以容納 4KB / 4B = 1024 個指針。如果每個數(shù)據(jù)塊的大小也是 4KB，那么這個文件系統(tǒng)支持的最大文件大小為 1024 * 4KB = 4MB。

由此可以看出，單級索引適用于中小型文件。然而，索引塊的大小是有限的，這意味著單級索引的文件大小上限很低，只能用于較小的文件。對于非常大的文件，則需要使用其他的多級索引方案。

多級索引

由于文件記錄的大小通常是有限的，因此文件系統(tǒng)引入了多級索引（Multi-Level Indexing）的概念，也叫間接索引。多級索引通過使用多個層次的索引塊來管理文件的數(shù)據(jù)塊位置。例如，兩級索引（Two-Level Indexing）使用一個一級索引塊指向多個二級索引塊，而二級索引塊則記錄文件的數(shù)據(jù)塊位置。這種設(shè)計使得文件系統(tǒng)可以存儲比單級索引更大的文件。

以二級索引為例子，文件記錄中儲存的索引是一級索引，一級索引中指向的塊并非文件本身，而是其他索引塊，叫做二級索引，由二級索引記錄文件簇的物理位置。

混合索引：現(xiàn)代文件系統(tǒng)的主流

多級索引提高了單文件大小的上限，但是，如果文件記錄中全部使用多級索引，即使只有 1 字節(jié)的文件，也至少需要占用多級索引中每一級索引塊各一個。文件越小，索引本身帶來的開銷越大。

現(xiàn)代文件系統(tǒng)為了平衡小型文件和大型文件的存儲需求，引入了混合索引（Hybrid Indexing）的方式?；旌纤饕Y(jié)合了直接索引、間接索引和多級索引的優(yōu)點。例如，在某些文件系統(tǒng)中，文件記錄中包含了一些直接指向數(shù)據(jù)塊的指針（適用于小文件），以及間接指向索引塊的指針（適用于較大的文件）。這種設(shè)計使得文件系統(tǒng)能夠高效地處理各種不同大小的文件，既能減少小文件的管理開銷，又能支持大型文件的高效存取。

例如，假設(shè)一個文件系統(tǒng)使用混合索引的方式，每個 inode 包含 12 個直接指針、1 個一級間接指針、1 個二級間接指針以及 1 個三級間接指針。假設(shè)每個數(shù)據(jù)塊大小為 4KB，每個指針占用 4 字節(jié)。則：

• 直接指針：可以直接指向 12 個數(shù)據(jù)塊，存儲大小為 12 * 4KB = 48KB。即 48 KB 以下的文件只需要單級索引。
• 一級間接指針：即前文介紹的單級索引，指向一個索引塊，該索引塊包含 4KB / 4B = 1024 個指針，每個指針指向一個數(shù)據(jù)塊，因此可以存儲 1024 * 4KB = 4MB 的數(shù)據(jù)。即 4 MB + 48 KB 以下的文件只需要前兩級索引。
• 二級間接指針：指向一個索引塊，該索引塊中的每個指針又指向另一個索引塊，這樣可以指向 1024 * 1024 個數(shù)據(jù)塊，共計 1024 * 1024 * 4KB = 4GB 的數(shù)據(jù)。
• 三級間接指針：同樣道理，可以指向 1024 * 1024 * 1024 個數(shù)據(jù)塊，共計 1024 * 1024 * 1024 * 4KB = 4TB 的數(shù)據(jù)。

因此，該混合索引結(jié)構(gòu)支持的最大文件大小約為 48KB + 4MB + 4GB + 4TB。由此可以看出，混合索引的設(shè)計使得文件系統(tǒng)既能夠高效地處理小型文件，又可以支持非常大的文件。

混合索引方式被廣泛應(yīng)用于現(xiàn)代絕大多數(shù)文件系統(tǒng)中，例如：

• NTFS（New Technology File System）：是 Windows 操作系統(tǒng)的默認文件系統(tǒng)，使用了混合索引結(jié)構(gòu)來實現(xiàn)對文件的靈活管理。
• HFS+（Hierarchical File System Plus）：是 macOS 中曾經(jīng)使用的文件系統(tǒng)，通過索引節(jié)點和混合索引來管理文件。
• APFS（Apple File System）：是蘋果公司為 macOS、iOS 等設(shè)備開發(fā)的新一代文件系統(tǒng)，同樣使用了混合索引來提高文件訪問的效率和靈活性。
• ext4（Fourth Extended File System）：是 Linux 操作系統(tǒng)中的默認文件系統(tǒng)，使用了混合索引結(jié)構(gòu)，并通過擴展的多級索引和日志機制來提高文件的管理效率和可靠性。

混合索引結(jié)構(gòu)的優(yōu)勢在于其對小型文件和大型文件的適應(yīng)性，使得文件系統(tǒng)能夠在各種應(yīng)用場景下提供高效的存儲和訪問性能。因此，混合索引成為了現(xiàn)代文件系統(tǒng)設(shè)計的主流選擇。通過這種方式，文件系統(tǒng)不僅能夠高效管理存儲空間，還能夠提供靈活的隨機訪問能力，以滿足不同用戶和應(yīng)用程序的需求。

?作者Ofnoname 博客園https://www.cnblogs.com/ofnoname/p/18492168