文件管理、外排序

1、主存储器、辅助存储器

主存储器，main/primary memory，一般指随机访问存储器（RAM，Random Acess Memory）、高速缓存（cache）、视频存储器（video memory）。数据易失的（volatile），断电丢失，访问速度快。
辅助存储器，secondary/peripheral storage，一般指硬盘、软盘、磁带。数据永久（persistant），可移动，访问速度比主存慢100w倍。

2、磁盘

各个盘片的相同距离磁道形成柱面。
扇区是I/O基本单位，注意，扇区指的是一部分磁道，不是整个扇区内的全部磁道。就比如图中，箭头指向的是线上，一般1K~16K字节。
CD-ROM（光盘，碟子），单一的螺旋磁道，磁道数据均匀分布，I/O磁头向中心移动，必须减慢旋转速度，机制复杂且更慢。
硬盘读取数据过程：
1、寻道（seek），移动I/O磁头，定位到磁道，主要耗时。
2、磁头等待扇区到来（旋转延迟），磁盘转速3600、5400、7200转/min
3、读取一个扇区数据。
交错法：读取个扇区，计算机要处理固定时间t，这个时候磁盘已转了一段距离，所以数据最好不要连续存储，而是隔一段距离，可以让计算刚处理好数据后，下一个扇区刚好转到磁头下，这种扇区安排方法称为交错法（interleaving），逻辑上相邻的扇区之间的间隔称为交错因子（interleaving facotr）。如下图：
数字表示扇区的逻辑关系，就是连续的数据。1和2之间相差3，所以交错因子是3。

window文件：多个扇区集结成一个簇（cluster），它是文件最小分配单位，所以所有文件都是整数个cluster，大小由操作系统决定，文件管理器记录每个文件有哪些cluster。
UNIX文件：没有cluster，最小单位就是扇区（称为block，块），UNIX系统维护文件信息，记录文件有哪些block，称为索引节点。
逻辑上和物理上都相邻的cluster称为范围extent，就是同一个文件数据，而且连续地存储在磁盘上。

数据可能不会刚好铺满扇区，空出来的就是内部碎片（interal fragmentation）。

有扇区头、内部碎片，导致磁盘空间有“名义大小”和“实际大小”。

3、缓冲区、缓冲池

一般按扇区读取，如果只需要1byte数据又读取了一个扇区，这个扇区就作为“缓冲”存储在主存中。叫引用的局部性，这是计算机重要概念。
缓冲由磁盘控制器管理，独立于CPU，因为CPU比这快多了，别拖累。

把缓冲作为用户和中介的过程叫缓冲文件，一个缓冲区内的信息叫page（页），合起来叫缓冲池（buffer pool）。缓冲满了要决策抛弃哪些信息：
1、FIFO，缓冲区是一个队列，缓冲时间最长的被踢掉。
2、LFU，最不频繁使用，记录每个缓冲区的访问次数。
3、LRU，最近最少使用。缓冲区是链表，被访问一次就把信息放到表头。

虚拟存储

缓冲池抽象

//缓冲池抽象方法一：这个用起来简单安全，但是需要从缓冲区复制出来，不过主存的复制至少比磁盘的快得多。
class BufferPool{
public:
    //把space上pos开始的size个字节数据缓冲起来
    virtual void insert(void* space, int size, int pos) = 0;
    //从缓冲中pos开始读取size个字节到space中。
    virtual void* getbytes(void *space, int size, int pos) = 0;
}
//缓冲池抽象方法二：这个是直接提供缓冲访问权限，省了复制出来，但是用起来麻烦，而且危险，
class BufferPool{
public:
    //返回需要请求的block在缓冲中的指针
    virtual void* getbolck(int block) = 0;
    //缓冲区中block块已经被修改，缓冲池才能及时的更新到存储区中。
    virtual void dirtyblock(int block) = 0;
    //块大小，缓冲区大小。
    virtual int blocksize() = 0;
}

4、文件抽象 fstream

文件可以类比成线性表，当前访问位置就是“栅栏”位置，读取一次，访问位置移动。有两个“栅栏”：一个读入位置，一个写入位置。
C++操作二进制文件的工具。
open：打开文件
read：当前位置读入文件，read一次，“栅栏”会移动。
write：写入，类似read。
seekg、seekp：前者移动读入“栅栏”，后者移动写入“栅栏”，
close：关闭文件。

5、外部排序

记录数量太大，无法全部存储到主存。“大规模排序”。
磁盘访问要比CPU计算满得多，所以尽量少磁盘访问。
算法使用的块最好是扇区的整数倍。

索引文件index file

如果是直接读取数据记录，但就造成了大量的I/O操作，而且大部分信息又用不上，没必要。可以通过保存每条记录的关键码和指针（指向对应数据记录的文件位置）。这样排序算法只需对索引文件进行排序即可。可以用多个索引文件按照不同的关键码，如按照ID号排序，按照工资高低排序等。