4.1_4_⽂件的物理结构（上）

专题讲解：文件系统

第200个文件块要经过哪一级指针

上一课页表把逻辑页映射到页框。文件系统 inode 也把文件逻辑块映射到磁盘块。设 inode 有4个直接指针和1个一级间接指针，块大小1 KiB、块号指针4 B。任务计算最大文件大小，并定位逻辑块号200（从0开始）。

def inode_layout(block_size,pointer_size,direct,logical_block):
    per_indirect=block_size//pointer_size
    max_blocks=direct+per_indirect
    if logical_block<direct:
        location=("direct",logical_block)
    elif logical_block<max_blocks:
        location=("single_indirect",logical_block-direct)
    else:
        location=("out_of_range",None)
    return max_blocks,max_blocks*block_size,location

assert inode_layout(1024,4,4,200)==(260,266240,("single_indirect",196))
assert inode_layout(1024,4,4,3)[2]==("direct",3)

一个间接块能放 1024/4=256 个块号，加4个直接块，共260个数据块，最大 260×1024=266240 B。逻辑块0～3走直接指针；块200 进入一级间接，索引 200-4=196。

为什么正确：直接指针各映射一个数据块；一级间接指针先指向一个“装块号的索引块”，其每个4字节条目再指向数据块。索引块本身不计入文件数据容量，却占磁盘空间和一次额外访问。

计算时间、空间 O(1)。目录把文件名映射到 inode 号，inode 保存元数据与块指针；打开文件后系统维护打开文件表和当前偏移。

典型错误：把间接索引块的1024字节也算作文件内容；逻辑块号从0起导致减 direct；硬链接共享 inode，符号链接保存路径；删除目录项后若仍有硬链接或打开引用，数据不一定立刻释放。

迁移答案：若再加一个二级间接指针，可额外覆盖 256² 个数据块；最大容量相应增加 256²×1024 B。

下一课关注这些磁盘块的实际访问顺序，用 SCAN 算法手工累计磁头移动距离。

专题讲解：多级索引文件容量

逻辑块5000要走二级索引的第3项、第892项

主章只算直接+一级。强化题 inode 有12个直接指针、一级/二级/三级间接各1个；块4 KiB、块号4 B。要求最大文件容量，并定位逻辑块5000（从0开始）。

def inode_capacity(block_size,pointer_size,direct):
    p=block_size//pointer_size
    blocks=direct+p+p**2+p**3
    return p,blocks,blocks*block_size

def locate(block,p,direct):
    if block<direct: return ("direct",block)
    block-=direct
    if block<p: return ("single",block)
    block-=p
    if block<p*p: return ("double",block//p,block%p)
    block-=p*p
    if block<p**3: return ("triple",block//(p*p),(block//p)%p,block%p)
    return ("out",)

p,blocks,size=inode_capacity(4096,4,12)
assert (p,blocks,size)==(1024,1074791436,4402345721856)
assert locate(5000,p,12)==("double",3,892)

每索引块可放 4096/4=1024 个块号。数据块总数 12+1024+1024²+1024³=1,074,791,436，最大字节数 4,402,345,721,856，约4 TiB（略大于4 TiB因还有低级块）。

定位5000：先跳过12个直接和1024个一级块，剩 5000-12-1024=3964；进入二级索引，第一层条目 3964//1024=3，第二层条目 3964%1024=892。

为什么正确：k级间接有 k 层、每层1024分支，可覆盖 1024^k 个数据块；定位就是把剩余逻辑块号按1024进制拆成各级索引。索引块本身占磁盘，但不计文件数据容量。

计算时间、空间 O(1)。错解反馈：逻辑块号从0开始；必须逐级减去前面覆盖范围；二级索引容量是 p² 而非 2p；题目若限制文件长度字段位数，实际上限取两者较小。

变式答案：逻辑块 12+1024+1024² 是三级间接覆盖的第一个块，对应三级索引 (0,0,0)。

本强化章结束。下一步进入组成原理与操作系统联合深挖，把页表、TLB、Cache、缺页与磁盘 I/O 放到一条完整访问链中。

专题讲解：文件索引、inode与最大文件长度

新困难：稀疏文件逻辑长度很大，磁盘只分配被写块和必要索引块

inode有12个直接指针、一级和二级间接指针，块4 KiB、块号4 B，每索引块1024项。对全新文件只在偏移 1 GiB 处写1字节。求逻辑块号、二级索引路径、文件逻辑长度和最少新分配块数（忽略inode自身）。

def sparse_write(offset,block_size=4096,pointers=1024,direct=12):
    logical_block,inside=divmod(offset,block_size)
    rest=logical_block-direct
    if rest<pointers: level='single'; path=(rest,); metadata=1
    else:
        rest-=pointers
        if rest>=pointers*pointers: raise ValueError('超出二级范围')
        level='double'; path=(rest//pointers,rest%pointers); metadata=2
    file_size=offset+1
    allocated_blocks=metadata+1
    return logical_block,inside,level,path,file_size,allocated_blocks

r=sparse_write(1*1024**3)
assert r==(262144,0,'double',(254,1012),1073741825,3)
assert r[-1]*4096==12288

陪算：1GiB/4KiB=262144，写入块内偏移0。跳过12个直接块和1024个一级覆盖块，剩 262144-12-1024=261108；二级第一层索引 261108//1024=254，第二层 261108%1024=1012。需分配一个二级根索引块、一个对应的下级索引块和一个数据块，共3块=12 KiB；文件长度却变为 1GiB+1 字节。

依据：未写的逻辑块是洞，不需要数据块；读取洞由文件系统返回零。索引树只为通向已分配数据块的路径按需建立。状态不变量是每个已分配数据块都有完整索引路径，而没有路径的范围不占数据块。

定位计算时间、空间 O(索引层数)；实际首次访问需读/写相应索引块。错误反馈：文件长度取最高写入偏移+写入长度；逻辑块号从0开始；索引块也占磁盘；洞不等于预先写满零的数据块；du与ls -l显示量可能不同。

迁移答案：若随后写同一二级下级索引覆盖范围内的另一数据块，只需再分配1个数据块，两个索引块可复用；若写到另一第一层条目，则再需一个下级索引块。

桥接：文件逻辑块最终转为磁盘请求；下一课比较 SCAN 与 LOOK 是否真的走到物理端点，完成整条I/O路径。