通过 filesystem 的 inode 设计，理解数组与链表

通过 filesystem 的 inode 设计，理解数组与链表

---

零、前言

通过讨论 inode 的设计，
理解 “ 数组 与 链表“ 在磁盘 “格式化文件系统技术“ 上的应用。

（记得看最后的总结）

---

一、inode 索引的本质

• inode 里面有一个大小为 60 字节的 i_block[] 数组，
• i_block[] 这个数组在 ext3 中被切割成单元大小为 4字节（32位的指针）的指针数组(len 为 15)。
• i_block[] 这个数组在 ext4 中被切割成单元大小为 12字节（32位的指针）的 entry 对象数组(len 为 5)。
• ext4 的 entry 对象可以是 ext4_extent_header、ext4_extent_idx 、 ext4_extent，这三个对象都是12字节，都可以认为是 entry.

---

二、ext3 和 ext4 的区别，一句话概括：

• ext3 和 ext4 都是一颗用叶子节点存放数据的多叉树。
• 区别：
• 1. 有无header (ext3的非叶子节点没有 header ，树的结构比较单一，一般都应该有个头， ext3 比较出格)
• 2.非叶子节点的分叉数（ext3 分叉数为 4K / 4 字节 = 1000个分叉， ext4 是 4K / 12字节 = 340 个分叉 ），
• 3. 【重点】叶子节点的大小 （ext3 一个节点大小为 1个block ，4K， 而 ext4 则是 128MB）。

【一句话概括】
ext4 与 ext3 相比最大的 进步 是：

提高了叶子节点的存储量，由 4K 升级到了 128MB.
(你可能会认为是 引入 ext4_extent_header， 但我觉得这不是本质提升)

---

三、inode 文件是一个block 链表 ( 理解为 “树” 也行 )

• 虽然磁盘大多是 以物理块block 4KB 提供存储的，但是 文件系统格式化后是以 inode 的形式来表示数据存储单位的【文件】（而 不是 block）。

• 优势呢？

• 文件可以理解为是一个 “block链表”，他更适合经常“增删查改”的 家庭用户读写数据的习惯。

• 而磁盘提供的 block 则更像是一个连续的数组，对于 家庭用户来说，这显得很原始。

---

四、inode位图（在数组中找空位）

• 说一说 block,

• 对于 block 使用，我们需要找到空位的 block, 找空位的办法？

• 日常生活中就两个步骤，（稍微冷静就能想到）：

• 1.找到所有已使用的block， 并做好标记到小本本上，

• 2.遍历所有block, 利用小本本检测遍历到的 block 是否被使用过，如果空闲，取而用之。

• 格式化后的文件系统也存在一个这样的小本本，叫 Block 位图。

• 但是，刚刚我们有讲过，格式化后的文件系统是以 inode 的形式给到用户读写，

• 那么自然而然，我们的小本本是 Inode 位图 （创建文件 的时候会用到）。
  （当 "读写文件" 内容的数据时才会涉及 “block 位图” ）

---

五、数组与位图

• 这里还有一个疑问：为什么要提供inode 位图？
• 难道 inode 在格式化后是以数组的形式提供分配给 用户 的么？
  （ 毕竟数组才需要位图管理，链表不需要 ），
• 答案是肯定。

---

六、 数组 和 对象池，谁更美？

• 为什么磁盘要这样设计呢？

• 我个人理解是简化实现，磁盘本身就是一个大数组，而不是对象池，数组管理inode 对象，比采用链表实现的池来管理对象显然简单很多，

• 毕竟简单才是美。

---

七、总结：

• inode 是存用户数据的地方。
• inode 用链表存放用户的数据。
• 磁盘是存放inode 的地方。
• 磁盘用数组存放 inode。
• inode 喜欢链表的灵活性。
• 磁盘喜欢数组的简单性。