【9.2】 文件的逻辑结构

一、文件的逻辑结构

• 文件是记录的汇集
• 一个文件的各个记录按照某种次序排列起来， 各纪录间就自然地形成了一种线性关系
• 因而，文件可看成是一种线性结构

二、文件的组织和管理

• 逻辑文件( logical file )

• 对高级程序语言的编程人员而言

• 连续的字节构成记录，记录构成逻辑文件

• 物理文件( physical file )

• 成块地分布在整个磁盘中

• 文件管理器

• 操作系统或数据库系统的一部分。文件的记录无结构，数据库文件是结构型记录

• 把逻辑位置映射为磁盘中具体的物理位置

三、文件组织

• 文件逻辑组织有三种形式:

• 顺序结构的定长记录

• 顺序结构的变长记录

• 按关键码存取的记录

• 常见的物理组织结构:

• 顺序结构——顺序文件

• 计算寻址结构——散列文件

• 带索引的结构——带索引文件。 倒排是一种特殊的索引

四、文件上的操作

• 检索:在文件中寻找满足一定条件的记录
• 修改:是指对记录中某些数据值进行修改。若对关键码值进行修改，这相当于删除加插入
• 插入:向文件中增加一个新记录
• 删除:从文件中删去一个记录
• 排序:对指定好的数据项，按其值的大小把文 件中的记录排成序列，较常用的是按关键码值 的排序

五、C++ 的标准输入输出流类

• 标准输入输出流类

• istream 是通用输入流和其它输入流的基类，支持输入

• ostream 是通用输出流和其它输出流的基类，支持输出

• iostream 是通用输入输出流和其它输入输出流的基类，支持 输入输出

• 3个用于文件操作的文件类

• ifstream 类，从 istream 类派生，支持从磁盘文件的输入

• ofstream 类，从 ostream 类派生，支持向磁盘文件的输出

• fstream 类，从 iostream 类派生，支持对磁盘文件的输入 和输出

fstream类的主要成员函数

文件指针 定位;在当前文件指针位置 读取;向当前文件指针位置 写入

六、缓冲区和缓冲池

• 目的:减少磁盘访问次数的
• 方法:缓冲 ( buffering ) 或缓存( caching )
• 在内存中保留尽可能多的块
• 可以增加待访问的块已经在内存中的机会
• 存储在一个缓冲区中的信息经常称为一页 ( page )，往往是一次 I/O 的量
• 缓冲区合起来称为缓冲池( buffer pool )

替换缓冲区块的策略

• 新的页块申请缓冲区时，把最近最不可能 被再次引用的缓冲区释放来存放新页
• “先进先出”( FIFO )
• “最不频繁使用”( LFU )
• “最近最少使用”( LRU )

七、思考

1. 查询内存、硬盘、磁带、高速缓存等设 备每字节的价格

2. 查询当前主流硬盘的性能指标

• 容量(G)
• 磁盘旋转速度 ( rpm ) ‒ 交错因子
• 寻道时间
• 旋转延迟时间

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾