操作系统4.1.2 文件的逻辑结构

落日映苍穹つ 2023-02-23 12:23 5阅读 0赞

### 一、按文件结构分 ###

**1、无结构文件（流式文件）**

文件内部数据由一系列二进制流或字符流组成

**2、有结构文件（记录式文件）**

文件内部数据由 一组相似记录组成，每条记录由若干个数据项组成，每条记录有一个数据项可作为关键字

记录：分为定长记录和可变长记录（常用）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70][]

## ##

### 二、按组织形式分 ###

**1、顺序文件**

文件中的记录一个接一个地按顺序排列(逻辑上)，记录可以是定长的或可变长的。

各个记录在物理上可以顺序存储或链式存储。

**1）顺序文件的排列方式**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 1][]

**2）顺序文件的特性及优缺点**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 2][]

**2、索引文件**

索引表本身是定长记录的顺序文件。因此可以快速找到第 i 个记录对应的索引项。  
可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。  
每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。

另外，可以用不同的数据项建立多个索引表。如：学生信息表中，可用关键字“学号”建立一张索引表。也可用“姓名”建立一张索引表。这样就可以根据“姓名”快速地检索文件了。(Eg:SQL 就支持根据某个数据项建立索引的功能)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 3][]

**3、索引顺序文件**

**1）索引顺序文件**

索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是：并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 4][]

映射、索引、段页很多都是折半查找。

若一个顺序文件有 10000 个记录，则根据关键字检索文件，只能从头开始顺序查找(这里指的并不是定长记，录、顺序结构的顺序文件)，平均须查找 5000 个记录。

若采用索引顺序文件结构，可把 10000 个记录分为 V10000=100 组，每组 100 个记录。则需要先顺序查找索引表找到分组(共 100 个分组，因此索引表长度为 100，平均需要查 50 次)，找到分组后，再在分组中顺序查找记录(每个分组 100 个记录，因此平均需要查 50 次)。可见，采用索引顺序文件结构后，平均查找次数减少为 50+50=100 次。

同理，若文件共有 106 个记录，则可分为 1000 个分组，每个分组 1000 个记录。根据关键字检索一个记录，平均需要查找 500+500=1000 次。这个查找次数依然很多，如何解决呢？

**2）多级索引顺序文件**

为了进一步提高检索效率，可以为顺序文件建立多级索引表。例如，对于一个含 106 个记录的文件，可先为该文件建立一张低级索引表， 每 100 个记录为一组，故低级索引表中共有 10000 个表项( 即 10000 个定长记录)，再把这 10000 个定长记录分组，每组 100 个， 为其建立顶级索引表，故顶级索引表中共有 100 个表。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 5][]

### 三、总结 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 6][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200707173530237.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200707173422898.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200707173724822.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200707174811810.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200707175128734.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200707175541694.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200707175641418.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R5d182NjY2NjY=,size_16,color_FFFFFF,t_70