# 2. 文件的逻辑结构

**逻辑结构：**&#x6587;件内部的数据应该如何组织起来

## 1. 无结构文件

文件内部的数据就是一系列二进制流或字符流组成，又称**流式文件**

## 2. 有结构文件

由一组相似的记录组成，又称**记录式文件**。每条记录又有若干个数据项组成。如：数据库表文件。一般来说，每条记录有一个数据项可作为**关键字**（作为识别不同记录的 ID）

根据每条记录**是否等长**，又可分为**定长记录**和**可变长记录**

有结构文件的[逻辑结构](2.-wen-jian-de-luo-ji-jie-gou)可分为三种，顺序文件、索引文件、索引顺序文件

## 3. 逻辑结构

### 3.1 顺序文件

文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。各个记录在物理上可以**顺序存储**或**链式存储**

* 顺序存储：逻辑上相邻，物理上也相邻
* 链式存储：逻辑上相邻，物理上不相邻

顺序文件的结构：

* **串结构：**&#x8BB0;录之间的顺序与关键字无关（通常按照记录存入的时间决定记录的顺序）
* **顺序结构：**&#x8BB0;录之间的顺序按关键字顺序排列

**顺序文件可与数据结构中的线性表类比**

* 对于链式存储：无论是定长还是可变长记录，都无法实现随机存取，每次只能从第一个记录开始依次从前往后查找
* 对于顺序存储：
  * 定长：可实现随机存取。记录长度为 L，则第 i 个记录存放的相对位置是 i \* L
  * 变长：无法实现随机存取。每次只能从头往后开始依次查找

### 3.2 索引文件

**索引文件主要就是解决可变长记录无法随机存取的问题**

**思路：**&#x4E3A;每一个文件建立一个索引表【索引号、长度 m、指针 ptr】，其中指针指向文件中的每个记录项的起始位置，长度为每个记录项的长度。索引表中的每个索引项的长度都是相等的，所以可以通过索引号来随机访问某一个记录项

![](https://824295091-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEmUhsvIFBb8ar2-Um3%2F-MFV6TmxOLF7Y6P0xGJw%2F-MFV7mvppjqCQ7qoXChr%2Fimage.png?alt=media\&token=18ae66a7-7680-4224-a776-a35150eb046f)

### 3.3 索引顺序文件

**索引文件存在的问题：**&#x5982;果文件中的记录项比较多，且每个记录项都比较小（只有 8B），这样就会导致索引表很大，且每个索引表占 32 个字节，那么索引表都要比文件内容本身大 4 倍，这样对存储空间的利用率就太低了

**索引顺序文件思想：**&#x4E3A;每一组记录设置一个索引，每一组内的记录依然采用顺序文件

![](https://824295091-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEmUhsvIFBb8ar2-Um3%2F-MFV6TmxOLF7Y6P0xGJw%2F-MFV8qnFs6KXtY0DrlGk%2Fimage.png?alt=media\&token=b074a22b-8be2-425e-9d33-5bc300690a0e)

**性能分析**

若一个顺序文件有 10000 个记录，采用索引顺序文件，分为 100 组，每组 100 个记录

* 索引文件：采用二分查找，平均需要找 5000 次
* 索引顺序文件：先找出组别，平均 50 次，再找出具体某一项平均 50 次，一共 100 次

可以很直观的看出，索引顺序文件性能的提升

### 3.4 多级索引文件

我们把数据集增大，假设有 $$10^6$$ 个记录，分为 1000 组，每组 1000 个记录，那么需要查找 500 + 500 = 1000 次，依然需要查找很多次

当我们采用多级索引时（假设是二级索引），我们把上述数据首先分为 100 组，每一组再分 100 组，其中每组 100 个记录，那么需要查找 50 + 50 + 50 = 150 次

![](https://824295091-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEmUhsvIFBb8ar2-Um3%2F-MFV9rd9ra6vL_KVbw8r%2F-MFVAa35uY69QqyOjaNq%2Fimage.png?alt=media\&token=4e567e3b-b7d4-4b4b-a1fd-6afa523c0562)
