无结构文件
由一系列二进制流或者字符流组成,又叫做流式文件:比如txt文件
有结构文件
有一组相似记录组成,又叫做记录式文件。比如数据库表文件
一般来说,每条记录有一个数据项可作为关键字,根据各类记录的长度是否相等,可以分为定长记录和可变长记录两种
由结构文件的逻辑结构
顺序文件
文件中的记录一个接一个顺序排列,记录是定长的或可变长的,各个记录在物理上可以顺序存储和链式存储
链式存储
无论定长/可变长
都无法实现随机存储
顺序存储
可变长记录
无法实现随机存取
定长记录
串结构
记录之间的顺序和关键字无关
无法快速找到某个关键字对应的记录
顺序结构
记录之间的顺序按照关键字顺序排列
可以快速找到某个关键字对应的记录,折半查找
定长记录
可实现随机存取,记录长度为L,则第i个记录存放的相对位置是i*L
如果考试题目中说顺序文件,指的是物理上顺序存储的顺序文件
索引文件
对于可变长记录,要找到第i个记录,必须先顺序查找前i-1个记录,但是很多场景用的是可变长记录
因此我们建立一张索引表以加快文件检索速度,每条记录对应一个索引项
文件中这些记录在物理上可以离散存放
sql就是根据某个数据建立索引的功能
索引顺序文件
索引文件的缺点:每个记录对应一个索引表项,索引表可能会较大,文件每个记录平均只占8B,而每个索引表占32字节,那么索引表会比本身大4倍,效率低下
索引顺序文件就是索引文件和顺序文件的思想结合,索引顺序文件中,同样会为文件建立一张索引表,但不同的是,并非每一个记录对应一个索引表项,而是一组记录对应一个表项

类似这样,A开头放一起,B开头放一起
若一个顺序文件有10000个记录,则根据关键字检测文件只能从头开始顺序查找,平均5000个记录
若采用索引顺序文件可以吧10000个记录分为100组【开根号】每组100个记录,则需要先顺序查找索引表找到分组,找到分组之后,再在分组中顺序查找记录,可见采用索引顺序文件结构后,平均查找次数减少为50+50=100
多级索引顺序文件
依然套娃,给索引表建立索引表