3.2.2 文件的数据管理
本节主要介绍在文件系统中文件（目录）中的数据是如何被管理的。前文已经介绍了磁盘空间的管理方式，知道磁盘会被划分为多个文件块，文件块的大小可以是1KB、2KB或4KB等。但是一个文件可能会大于这些文件块的大小，如一个电影的大小约为1GB。这就涉及文件数据管理的问题。
对于文件系统来说，无论文件是什么格式，存储的是什么内容，它都不关心。文件就是一个线性空间，类似一个大数组。而且文件的空间被文件系统划分为与文件系统块一样大小的若干个逻辑块。文件系统要做的事情就是将文件的逻辑块与磁盘的物理块建立关系。这样当应用访问文件的数据时，文件系统可以找到具体的位置，进行相应的操作。
文件数据的位置通过文件的元数据进行描述，这些元数据描述了文件逻辑地址与磁盘物理地址的对应关系，如图3-21所示为文件逻辑块与磁盘数据的对应关系。
图3-21 文件逻辑块与磁盘数据的对应关系
以Linux为例，文件的起点是inode，文件数据的位置信息是存储在inode中的。这样就可以根据inode存储的关于文件数据的位置信息找到具体的数据。我们能想到的最直观的方式就是在inode中存储每一个块的位置信息。比如，在逻辑块大小为1KB的文件系统中有一个3KB的文件。那么在inode中有一个数组，前3项的值分别存储磁盘的地址信息，这样就可以根据数组的内容找到磁盘上存储的文件数据。
实际上，文件的数据管理方式大致如此，但又不完全是这样。不同的文件系统采用了不同的管理方式，下面就介绍一下文件数据的管理方式。
3.2.2.1 基于连续区域的文件数据管理
基于连续区域的文件数据管理方式是一次性为文件分配其所需要的空间，且空间在磁盘上是连续的。由于文件数据在磁盘上是连续存储的，因此只要知道文件的起始位置所对应的磁盘位置和文件的长度就可以知道文件数据在磁盘上是如何存储的。
举例说明，如图3-22所示，假设某个目录有3个文件，分别是test1、test2和test3，其中，每个文件数据在磁盘的位置及长度如图3-22所示（左侧）。每个文件的数据如图3-22所示（箭头的指向及深色方块处）。
图3-22 基于连续区域的文件数据管理
假设要访问test2文件，根据目录中记录的数据，可以知道文件起始位置对应磁盘第9个逻辑块，因此根据该信息和文件内部偏移就可以很容易地计算出文件任意偏移的数据在磁盘上的位置。
这种文件数据管理方式的最大缺点是不够灵活，特别是对文件进行追加写操作非常困难。如果该文件后面没有剩余磁盘空间，那么需要先将该文件移动到新的位置，然后才能追加写操作。如果整个磁盘的可用空间没有能够满足要求的空间，那么会导致写入失败。
除了追加写操作不够灵活，该文件数据管理方式还有另一个缺点就是容易形成碎片空间。由于文件需要占用连续的空间，因此很多小的可用空间就可能无法被使用，从而降低磁盘空间利用率。
鉴于上述缺点，在磁盘等需要经常修改数据的存储介质的文件系统通常都不采用基于连续区域的文件数据管理方式。该方式目前主要应用在光盘等存储介质的文件系统中，如ISOFS。
3.2.2.2 基于链表的文件数据管理
基于链表的文件数据管理方式将磁盘空间划分为大小相等的逻辑块。在目录项中包含文件名、数据的起始位置和终止位置。在每个数据块的后面用一个指针来指向下一个数据块，如图3-23所示。
图3-23 基于链表的文件数据管理
这种方式可以有效地解决连续区域的碎片问题，但是对文件的随机读/写却无能为力。这主要是因为在文件的元数据中没有足够的信息描述每块数据的位置。为了实现随机读/写，一些文件系统在具体实现时做了一些调整。
以FAT12文件系统为例，该文件系统其实使用的就是链表方式，但是FAT12又不完全使用的是链表方式。为了支持对文件的随机读/写，FAT12将文件的元数据抽取出来，而不是存储在数据块的结尾部分。这样，文件的元数据可以一次性加载到内存中，从而实现对随机访问的支持。
为了便于理解FAT12的原理，列举一个具体的实例，如图3-24所示。假设有一个file1.txt文件，我们根据目录文件项知道其起始的簇地址是0x05，这个是file1.txt文件第1个簇的位置，然后根据簇地址就能从文件分配表（FAT）中找到对应的表项，两者是一一对应的（图3-24中双向箭头处）。根据表项内容，我们可以知道下一个簇的位置，以此类推，就可以找到该文件的所有数据。
图3-24 FAT12文件数据管理示意图
如果简化一下这个结构，则整个关系就是一个单向链表的关系。我们可以将FAT表项理解为next指针，簇是data数据。只不过FAT表项和簇是通过地址偏移建立了两者之间的关系的。图3-24可以简化为图3-25。
图3-25 FAT12文件数据管理方式简化图
通过对比可以看出，FAT12本质上是基于链表数据管理方式的，但是由于文件分配表本身比较小，可以一次性加载到内存中，因此也是可以满足随机访问需求的。但是这种方式对随机访问的支持度还是不够的，毕竟内存中的链表访问也是相当低效的，特别是针对链表项比较多的情况。
3.2.2.3 基于索引的文件数据管理
索引方式的数据管理是指通过索引项来实现对文件内数据的管理。如图3-26所示，与文件名称对应的是索引块在磁盘的位置，索引块中存储的并非用户数据，而是索引列表。当读/写数据时，根据文件名可以找到索引块的位置，然后根据索引块中记录的索引项可以找到数据块的位置，并访问数据。
图3-26 基于索引的文件数据管理
上文只是对索引方式进行了非常简单的说明。在实际工程实现时会有各种差异，但本质上是一样的。接下来介绍两种常见的索引方式：一种是基于间接块的文件数据管理方式；另一种是基于Extent的文件数据管理方式。
1.基于间接块的文件数据管理
在索引方式中，最为直观、简单的就是对文件的每个逻辑块都有一个对应的索引项，并将索引项用一个数组进行管理，如图3-27所示。通过这种方式，文件的逻辑地址与上述数组的索引就会有一一对应的关系。因此，当想要访问文件某个位置的数据时，就可以根据该文件逻辑偏移计算出数组的索引值，然后根据数组的索引值找到索引项，进而找到磁盘上的数据。
图3-27 直接索引示意图
但是这种方式有个问题，就是对于大文件来说无法将索引数据一次性加载到内存中，形成索引用的数组。假设以32位数来表示位置信息，文件块大小是1KB，那么一个10GB的文件需要4MB的数组数据。因此，虽然这种实现方式非常直观、简单，但是并不实用。
在实际工程中通常会做一些变通。以Ext2文件系统为例，在实现索引时通过多级索引的方式实现对数据的管理，最终形成一个索引树。在索引树中，只有叶子节点存储的是用户数据，而中间节点存储的是索引数据。
Ext2文件系统在实现这个索引树时做了很多变通，这种变通可以对很多场景有优化的作用。对于Ext2文件系统，在inode中存储一个索引数组，该索引数组前12项存储着文件数据的物理地址，称为直接索引。这样对于小文件来说，可以实现一次检索就能找到数据。
当文件太大，超出直接索引的范围时会通过间接索引来管理。间接索引通过3棵独立的树来实现，分别是1级间接索引树、2级间接索引树和3级间接索引树。这里级数的含义是该树中中间节点的层数。
为了能够更清楚地理解Ext2文件系统是如何管理文件数据的，这里给出如图3-28所示的示意图。在图3-28中，block0～block11是直接索引，存储的是用户数据的物理地址。而block12～block14则是间接索引，存储的是索引块（或间接块，简写为IB）的物理地址，索引块中的数据并非用户数据，而是索引数据，是用于管理用户数据的。
以block13形成的索引树为例，这里会形成一个2级间接索引树，可以将block13理解为该索引树的树根。如果文件数据的逻辑地址在该树管理范围内，则需要经过2级检索才能找到用户数据。
当然，我们也可以将整个索引数组理解为一个树根，不同的逻辑地址由不同的子树进行管理。
图3-28 Ext2文件系统间接块数组组织形式
2.基于Extent的文件数据管理
使用间接块可以很好地管理文件的数据，但是其最大的缺点在于元数据与数据有一个固定的对应关系，也就是数据越多，需要的元数据越多。这种方式在某些场景下其实并不划算，如视频文件场景。
简单地表述上述问题，就是每个数据块都要有一个元数据指针来记录其位置。以32位指针，逻辑块大小为1KB的文件系统为例，在1级间接块中每1KB的数据都需要4字节的指针。而2级间接块除了每1KB的数据需要4字节的指针，每个2级间接块本身还需要指针来记录。
但是某些场景并不需要记录每个逻辑块的位置，最常见的就是视频文件或音频文件。以视频文件为例，通常文件比较大，而且是一次存入，基本不会出现修改。如果使用间接块的方式，则必须要有一定量的元数据。我们回忆一下前面介绍连续区域的文件数据管理方式就会发现这种方式非常适合此场景。
但是连续区域的文件数据管理方式最大的缺点是对追加写操作处理不好，容易形成存储空间的碎片化。于是，结合连续区域的文件数据管理方式和间接块的文件数据管理方式的优点就有了现在这种方式，也就是Extent文件数据管理的方式。在Extent文件数据管理方式中，每一个索引项记录的值不是一个数据块的地址，而是数据块的起始地址和长度，如图3-29所示。
图3-29 基于Extent的文件数据管理
在图3-29中，实例文件有两块数据，前一块数据存储在磁盘偏移为3的位置，大小是5个逻辑块；后一块数据存储在磁盘偏移为23的位置，大小是3个逻辑块。对比间接块的文件数据管理方式可以看出，使用Extent的文件数据管理方式可以有效减少元数据的相对数量。
对于Extent的文件数据管理方式，如果出现追加写数据的场景，则文件系统只需要分配一个新的Extent。因此该种方式并没有前文介绍的连续区域的文件数据管理方式的缺点。
虽然本书实例描述数据位置的信息在内存中，但实际情况是并不会全部在内存中。通常Extent是通过B+树的方式组织的，B+树的树根在inode初始化时被加载到内存中。而该树的中间节点则在磁盘上，会按需加载到内存中。由于B+树是一个有序的多叉树，因此基于B+树实现从文件逻辑地址到磁盘物理地址的映射还是比较快的。