4. 文件组织（简单应用）

4.1 文件组织、文件系统的概念和文件系统的功能

文件组织：是数据组织的一部分，主要指数据记录在外设备上的组织。

文件系统：指计算机操作系统中的文件管理系统，实质上是一个管理和存取文件的软件系统，它由文件和管理文件的程序组成。

文件系统功能：它能定义需要的文件组织方式，并提供建立和存取数据的环境。

4.2 记录存入存储器的物理顺序和逻辑顺序的区别

两者并不一定完全一致，排好序的顺序文件是物理顺序和逻辑顺序一致的文件。

4.3 各种文件组织方式的特征

1） 顺序文件：存储在顺序存储器上时，只能按顺序扫描法存取；存储在随机存取存储器上时，还可以按分块查找法或折半查找法进行存取。

2） 索引文件：分为索引区和数据区，索引表的索引项按顺序排列，数据文件本身可以按顺序或不按顺序排列。

3） 直接存取文件

①直接地址法：存取机构动作简单，使用方便，不会产生重号；不易记忆。

②相对键法：搜索时间短，处理速度快；若有空号，造成空间浪费；需要占用一个连续的地址块，空间利用率低。

公式： （100为假设的记录长度，400为假设的文件存储起点地址）

③杂凑法公式：存取速度快，节约存储空间；不易找到一个良好的算法，有时碰撞现象发生过多时，会加长存取时间。

存储单元数： （N记录总数，n单位存储记录数）

质数除法公式： （K需要转变的键号，P接近存储单元的质数，INT表示取整）

4.4 在顺序存取存储器和随机存取存储器上顺序文件可以采用的查找方法

（见4.3）

4.5 索引文件的特点以及查找、删除、和插入操作过程

（见4.3）

4.6 实现直接存取文件组织的三种方法的原理

（见4.3）

4.7 杂凑函数的一种算法——质数除余数

（见4.3）

4.8 用溢流表法解决存储单元分配中碰撞现象的原理

（需要理解P30）

4.9 使用杂凑法的步骤，知道杂凑法的优缺点

1） 确定记录总数N；

2） 确定每一存储单元可以存放的记录数n；

3） 按公式计算应准备的单元数： ；

4） 找出一个杂凑函数。