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

物理存儲(chǔ)的基本概念：塊與簇

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

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

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

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

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

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

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

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

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

簡(jiǎn)單鏈表分配：解決碎片問(wèn)題的嘗試

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

然而，鏈表分配也有明顯的缺點(diǎn)：

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

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

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

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

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

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

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

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

索引分配：真正實(shí)現(xiàn)隨機(jī)訪問(wèn)

在離散存儲(chǔ)的基礎(chǔ)上，顯然不一定要使用鏈表?？梢栽谖募涗浿幸宰冮L(zhǎng)數(shù)組記錄每個(gè)塊的位置，這樣就可以實(shí)現(xiàn)真正的隨機(jī)訪問(wèn)。這種數(shù)組叫做索引（index），這種分配方式稱(chēng)為索引分配（Indexed Allocation）。在索引分配中，文件系統(tǒng)會(huì)為在每個(gè)文件的文件記錄里維護(hù)其索引塊，索引塊中存儲(chǔ)了文件各個(gè)數(shù)據(jù)塊的物理位置。通過(guò)查找這個(gè)索引塊，操作系統(tǒng)可以直接定位到文件的任意塊，從而實(shí)現(xiàn)快速的隨機(jī)訪問(wèn)。簡(jiǎn)單來(lái)說(shuō)，索引用數(shù)組實(shí)現(xiàn)就可以，也可以選擇二叉樹(shù)或哈希表，這就不是本文的重點(diǎn)了。

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

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

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

多級(jí)索引

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

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

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

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

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

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

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

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

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

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

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

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