# 2. 文件的逻辑结构

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

## 1. 无结构文件

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

## 2. 有结构文件

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

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

有结构文件的[逻辑结构](/operating-system/di-si-zhang-wen-jian-guan-li/2.-wen-jian-de-luo-ji-jie-gou.md)可分为三种，顺序文件、索引文件、索引顺序文件

## 3. 逻辑结构

### 3.1 顺序文件

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

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

顺序文件的结构：

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

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

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

### 3.2 索引文件

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

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

![](/files/-MFV7mvppjqCQ7qoXChr)

### 3.3 索引顺序文件

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

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

![](/files/-MFV8qnFs6KXtY0DrlGk)

**性能分析**

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

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

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

### 3.4 多级索引文件

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

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

![](/files/-MFVAa35uY69QqyOjaNq)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lfool.gitbook.io/operating-system/di-si-zhang-wen-jian-guan-li/2.-wen-jian-de-luo-ji-jie-gou.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.