硬盘
在介绍文件系统之前有必要先介绍下文件系统的物理媒介，硬盘在当下还是主流，就先学习下硬盘的组成吧。
文件是存储在具有磁性物质的磁盘上面，那么看下磁盘的格式。
-
磁區(Sector)為最小的物理儲存單位，每個磁區為 512 bytes；
-
將磁區組成一個圓，那就是磁柱(Cylinder)，磁柱是分割槽(partition)的最小單位；
-
第一個磁區最重要，裡面有：(1)主要開機區(Master boot record, MBR)及分割表(partition table)， 其中 MBR 佔有 446 bytes，而 partition table 則佔有 64 bytes。
因为分区表的大小限制，出现了主要(primary)分区与扩展(extended)分区（最多一个），扩展分区可再划分逻辑(logical)分区，见下图。
这些分区在Linux中的设备名称分别是（假设是SATA硬盘）：P1: /dev/hda1, P2: /dev/hda2, L1: /dev/hda5, L2: /dev/hda6, L3: /dev/hda7, L4: /dev/hda8, L5: /dev/hda9（逻辑分区是从5开始的）。
与分区有关的另一个重要概念是格式化。格式化是以分区为单位（已经有更小粒度的了？），将某个分区格式化成某种文件系统格式，例如将上述的/dev/hda1格式化成NTFS文件系统格式，或者格式化成Ext2文件系统格式（Linux下使用mkfs命令）。
接下来看一下第一个sector的另一部分，MBR。
上图要注意的是每个分区的第一个sector，按我的理解，分区被格式化之后，第一个sector用来存放什么信息应该是由文件系统决定的，例如下图所示Ext2的文件系统格式，第一个sector便是如上图所说的開機磁區。接下来我们展开来学习下Ext2。
Ext2
一般来说只有第一个BlockGroup有SuperBlock，SuperBlock：
- block 與 inode 的總量；
- 未使用與已使用的 inode / block 數量；
- block 與 inode 的大小 (block 為 1, 2, 4K，inode 為 128 bytes)；
- filesystem 的掛載時間、最近一次寫入資料的時間、最近一次檢驗磁碟 (fsck) 的時間等檔案系統的相關資訊；
-
一個 valid bit 數值，若此檔案系統已被掛載，則 valid bit 為 0 ，若未被掛載，則 valid bit 為 1 。
FileSystem Descriptor：這個區段可以描述每個 block group 的開始與結束的 block 號碼，以及說明每個區段 (superblock, bitmap, inodemap, data block) 分別介於哪一個 block 號碼之間。
BlockBitMap：记录每一个Block是否已被使用。
InodeBitMap：记录每一个Inode是否已被使用。
InodeTable：一个文件使用一个inode，inode存储的信息有：
- 該檔案的存取模式(read/write/excute)；
- 該檔案的擁有者與群組(owner/group)；
- 該檔案的容量；
- 該檔案建立或狀態改變的時間(ctime)；
- 最近一次的讀取時間(atime)；
- 最近修改的時間(mtime)；
- 定義檔案特性的旗標(flag)，如 SetUID...；
- 該檔案的資料所在的 block 號碼(pointer)；
-
每個檔案都僅會佔用一個 inode 而已，因此檔案系統能夠建立的檔案數量與 inode 的數量有關；
DataBlock：真正存儲数据的地方。Block大小为1/2/4K，这与Buddy Allocator方案类似。
使用dumpe2fs可以观察到这些信息：
[root@www ~]# dumpe2fs [-bh] 裝置檔名
選項與參數：
-b ：列出保留為壞軌的部分(一般用不到吧！？)
-h ：僅列出 superblock 的資料，不會列出其他的區段內容！
範例：找出我的根目錄磁碟檔名，並觀察檔案系統的相關資訊
[root@www ~]# df <==這個指令可以叫出目前掛載的裝置
Filesystem 1K-blocks Used Available Use% Mounted on
/dev/hdc2 9920624 3822848 5585708 41% / <==就是這個光！
/dev/hdc3 4956316 141376 4559108 4% /home
/dev/hdc1 101086 11126 84741 12% /boot
tmpfs 371332 0 371332 0% /dev/shm
[root@www ~]# dumpe2fs /dev/hdc2
dumpe2fs 1.39 (29-May-2006)
Filesystem volume name: /1 <==這個是檔案系統的名稱(Label)
Filesystem features: has_journal ext_attr resize_inode dir_index
filetype needs_recovery sparse_super large_file
Default mount options: user_xattr acl <==預設掛載的參數
Filesystem state: clean <==這個檔案系統是沒問題的(clean)
Errors behavior: Continue
Filesystem OS type: Linux
Inode count: 2560864 <==inode的總數
Block count: 2560359 <==block的總數
Free blocks: 1524760 <==還有多少個 block 可用
Free inodes: 2411225 <==還有多少個 inode 可用
First block: 0
Block size: 4096 <==每個 block 的大小啦！
Filesystem created: Fri Sep 5 01:49:20 2008
Last mount time: Mon Sep 22 12:09:30 2008
Last write time: Mon Sep 22 12:09:30 2008
Last checked: Fri Sep 5 01:49:20 2008
First inode: 11
Inode size: 128 <==每個 inode 的大小
Journal inode: 8 <==底下這三個與下一小節有關
Journal backup: inode blocks
Journal size: 128M
Group 0: (Blocks 0-32767) <==第一個 data group 內容, 包含 block 的啟始/結束號碼
Primary superblock at 0, Group descriptors at 1-1 <==超級區塊在 0 號 block
Reserved GDT blocks at 2-626
Block bitmap at 627 (+627), Inode bitmap at 628 (+628)
Inode table at 629-1641 (+629) <==inode table 所在的 block
0 free blocks, 32405 free inodes, 2 directories <==所有 block 都用完了！
Free blocks:
Free inodes: 12-32416 <==剩餘未使用的 inode 號碼
Group 1: (Blocks 32768-65535)
....(底下省略)....
可以看出除了DataBlock，其他部分也都是以Block为单位进行物理存储的（Block再由Sector组成）。SuperBlock在0号Block，FS Descriptor在1-626Block，BlockBitmap在627Block，InodeBitmap在628Block，InodeTable在629-1641Block，那么剩下的应该都是DataBlock了。
上面提到了由于inode大小将会限制所能指向的DataBlock的个数，为了解决这个问题，inode将pointer进行了分层（与增加逻辑分区相同思路），如下图，其中直接pointer有12个。这样便可以计算，假设DataBlock大小为1K，Block编号为整数，也就是占用4bytes，一个Block也就可以存储1K/4 = 256个Block编号，那么128bytes的inode所能指向的文件最大为（12 + 256 + 256*256 + 256*256*256）*1K = 16GB。
目录树
数据的快速读取，一般通过哈希或者树结构来支持。而文件系统则是通过目录树，所以需要先介绍下目录在Ext2里面是什么样的。
當我們在 Linux 下的 ext2 檔案系統建立一個目錄時， ext2 會分配一個 inode 與至少一塊 block 給該目錄。其中，inode 記錄該目錄的相關權限與屬性，並可記錄分配到的那塊 block 號碼； 而 block 則是記錄在這個目錄下的檔名與該檔名佔用的 inode 號碼資料。
可以说，目录树是文件系统的逻辑存储，分区是物理存储，两者之间则是通过mount操作关联。如下图，每个分区一定要mount到某个目录下面，这个目录将会作为读取这个分区物理存储的逻辑入口。df命令可以查看各个分区的mount信息。
最后，从搜索效率上来看目录树这样的数据结构，还有个问题需要思考下。如上图中，根目录下有etc, dev, bin等文件，假如我要读取/bin这个目录，那么是通过什么样的算法来快速找到bin的，总不能遍历吧？