2. 文件的逻辑结构
逻辑结构：文件内部的数据应该如何组织起来
1. 无结构文件
文件内部的数据就是一系列二进制流或字符流组成，又称流式文件
2. 有结构文件
由一组相似的记录组成，又称记录式文件。每条记录又有若干个数据项组成。如：数据库表文件。一般来说，每条记录有一个数据项可作为关键字（作为识别不同记录的 ID）
根据每条记录是否等长，又可分为定长记录和可变长记录
有结构文件的逻辑结构可分为三种，顺序文件、索引文件、索引顺序文件
3. 逻辑结构
3.1 顺序文件
文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储
顺序存储：逻辑上相邻，物理上也相邻
链式存储：逻辑上相邻，物理上不相邻
顺序文件的结构：
串结构：记录之间的顺序与关键字无关（通常按照记录存入的时间决定记录的顺序）
顺序结构：记录之间的顺序按关键字顺序排列
顺序文件可与数据结构中的线性表类比
对于链式存储：无论是定长还是可变长记录，都无法实现随机存取，每次只能从第一个记录开始依次从前往后查找
对于顺序存储：
定长：可实现随机存取。记录长度为 L，则第 i 个记录存放的相对位置是 i * L
变长：无法实现随机存取。每次只能从头往后开始依次查找
3.2 索引文件
索引文件主要就是解决可变长记录无法随机存取的问题
思路：为每一个文件建立一个索引表【索引号、长度 m、指针 ptr】，其中指针指向文件中的每个记录项的起始位置，长度为每个记录项的长度。索引表中的每个索引项的长度都是相等的，所以可以通过索引号来随机访问某一个记录项
3.3 索引顺序文件
索引文件存在的问题：如果文件中的记录项比较多，且每个记录项都比较小（只有 8B），这样就会导致索引表很大，且每个索引表占 32 个字节，那么索引表都要比文件内容本身大 4 倍，这样对存储空间的利用率就太低了
索引顺序文件思想：为每一组记录设置一个索引，每一组内的记录依然采用顺序文件
性能分析
若一个顺序文件有 10000 个记录，采用索引顺序文件，分为 100 组，每组 100 个记录
索引文件：采用二分查找，平均需要找 5000 次
索引顺序文件：先找出组别，平均 50 次，再找出具体某一项平均 50 次，一共 100 次
可以很直观的看出，索引顺序文件性能的提升
3.4 多级索引文件
我们把数据集增大，假设有 个记录，分为 1000 组，每组 1000 个记录，那么需要查找 500 + 500 = 1000 次，依然需要查找很多次
当我们采用多级索引时（假设是二级索引），我们把上述数据首先分为 100 组，每一组再分 100 组，其中每组 100 个记录，那么需要查找 50 + 50 + 50 = 150 次
Last updated
