为什么引入文件索引节点能大大加快目录检索速度

一般来说&＃xff0c;面试不会问 inode 。但是 inode 是一个重要概念&＃xff0c;是理解 Unix/Linux 文件系统和硬盘储存的基础。
理解inode&＃xff0c;要从文件储存说起。

文件储存在硬盘上&＃xff0c;硬盘的最小存储单位叫做"扇区"&＃xff08;Sector&＃xff09;。每个扇区储存512字节&＃xff08;相当于0.5KB&＃xff09;。

操作系统读取硬盘的时候&＃xff0c;不会一个个扇区地读取&＃xff0c;这样效率太低&＃xff0c;而是一次性连续读取多个扇区&＃xff0c;即一次性读取一个"块"&＃xff08;block&＃xff09;。这种由多个扇区组成的"块"&＃xff0c;是文件存取的最小单位。"块"的大小&＃xff0c;最常见的是4KB&＃xff0c;即连续八个 sector组成一个 block。

文件数据都储存在"块"中&＃xff0c;那么很显然&＃xff0c;我们还必须找到一个地方储存文件的元信息&＃xff0c;比如文件的创建者、文件的创建日期、文件的大小等等。这种储存文件元信息的区域就叫做inode&＃xff0c;中文译名为"索引节点"。

每一个文件都有对应的inode&＃xff0c;里面包含了与该文件有关的一些信息

这一过程也是操作系统从文件的逻辑地址&＃xff08;逻辑上连续存放&＃xff0c;表现为索引节点的磁盘地址表中的数据是连续存放的&＃xff09;转换到物理地址&＃xff08;物理上离散存放&＃xff09;的过程。
首先os会使用应用程序给定的路径&＃xff08;包含所要查找的文件名&＃xff09;&＃xff0c;一次一次的将对应级别的目录调到内存中来&＃xff0c;直到找到文件对应的目录项(FCB)&＃xff0c;这时有两种情况&＃xff1a;

• 如果应用了索引结点&＃xff0c;则一个FCB中只存放了文件名和一个指向文件索引结点的指针&＃xff0c; 然后再根据这个指针&＃xff0c;将这个64B的
  索引结点调入内存&＃xff0c;然后定位至索引节点中的磁盘地址表&＃xff0c;依据顺序取得文件数据存放的磁盘地址并且将相应的存放文件的磁盘数据调入内存中

• 如果没有应用索引结点&＃xff0c;则磁盘地址会拿到FCB后会直接从FCB中拿到相应的磁盘地址表&＃xff0c;然后再依据这个磁盘地址表将磁盘中的数据依次调入内存中。

以上的步骤中是否给人一种加了索引结点后&＃xff0c;反而os还要多一个步骤才能找到文件中的数据&＃xff0c;实际上并非如此&＃xff0c;请看以下的解析

为什么引入文件索引节点能大大加快检索速度

首先现代操作系统&＃xff0c;比如linux采用的树形目录结构&＃xff0c;其中的一个文件目录项由一个FCB(File Control Block)即文件控制块组成&＃xff0c;每一个FCB即每一个目录项中包含了文件名&＃xff0c;该目录文件在磁盘中的位置&＃xff0c;文件的类型&＃xff0c;文件的开放权限&＃xff0c;文件的大小等等信息&＃xff0c;其中最重要的是第一个属性&＃xff0c;其次是第二个属性。

缺点&＃xff1a;
当一个FCB很大时&＃xff0c;则会导致磁盘I/O次过多&＃xff0c;检索速度慢&＃xff0c;为什么这么说&＃xff0c;请看例一&＃xff1a;

假如一个FCB有64B大小&＃xff0c;一个文件夹中有640个目录项&＃xff0c;一个页面大小为1KB&＃xff0c;则一个页面只能存储1KB / 64B &＃61; 16个目录项&＃xff0c;那么就需要 64B * 640 / 1 KB &＃61; 40 个磁盘块才能存放这些FCB&＃xff0c;所以&＃xff0c;如果按照文件名检索&＃xff0c;即顺序检索&＃xff0c;则平均需要查询320个目录项&＃xff0c;因为每个盘块能存放16个目录项&＃xff0c;所以评分需要读磁盘(读磁盘是指将磁盘中的需要的数据调入内存) 320 / 16 &＃61; 20 (次)

从以上例子中可以看出&＃xff0c;当FCB越小&＃xff0c;一个磁盘块中能存放的FCB也越多&＃xff0c;从而减少磁盘I/O次数

1. 因为一个FCB中包含的信息太多&＃xff0c;导致一个FCB会很大&＃xff0c;不利于磁盘IO和检索&＃xff0c;所以我们需要对其进行改进
2. 我们知道一个文件目录项中最重要的是文件名(实现文件的按名存取必然需要文件名)&＃xff0c;所以我们可以把FCB中不重要的信息放到一个索引结点当中&＃xff0c;让一个FCB只有两个分量组成,分别是文件名和指向该索引结点的指针&＃xff0c;因此一个FCB占用的空间会小很多&＃xff0c;会大大加快磁盘I/O速度

例二&＃xff1a;

如果使用索引结点机制&＃xff0c;一个FCB的只有两个分量&＃xff0c;假设文件名占用14B&＃xff0c;索引结点指针占2B&＃xff0c;也就是说一个目录项占用16B&＃xff0c;当一个磁盘块大小是1KB&＃xff0c;则一个磁盘块能存放 1KB / 16B &＃61; 64个 FCB&＃xff0c;如果一个文件中有640个目录项&＃xff0c;则需要640 / 64 &＃61; 10个磁盘块存储&＃xff0c;按文件名顺序查找&＃xff0c;平均查找320次&＃xff0c;因为每一个盘块能存放64个FCB&＃xff0c;因此平均情况下&＃xff0c;只需要进行5次磁盘I/O就能找到所需要检索的文件目录项。

显然&＃xff0c;引入索引结点能大大提升文件检索速度

3.1 为什么一个FCB中需要记录该目录文件在磁盘中的位置&＃xff1f;

答&＃xff1a;因为一个目录文件中也存放了多个子目录文件(也称为子FCB)&＃xff0c;而一个正常的目录项中不包含子FCB(因为一个目录文件中可能包含了几十个FCB&＃xff0c;那样的话就不利于顺序读取)&＃xff0c;而是把他隐藏起来放到了磁盘中&＃xff0c;然后在FCB中添加一个指向该文件位置的指针。

3.2 关于FCB索引结点的特别说明

当找到文件名对应的目录项时&＃xff0c;才需要将索引结点调入内存&＃xff0c;索引结点中记录了文件的各种信息&＃xff0c;包括文件在外存中的存放位置&＃xff0c;根据“存放位置”即可找到文件。
存放在外存中的索引结点称为“磁盘索引结点”&＃xff0c;当索引结点放入内存后称为“内存索引结点”。
相比之下内存索引结点中需要增加一些信息&＃xff0c;比如:文件是否被修改、此时有几个进程正在访问该文件等。