本章介绍的是存储在 外存上的数据结构 (文件)的有关概念各种文件的特点组织方法及查询和更新操作我们只要对它们有一些了解就可以了本章不是重点
一文件的基本概念( 识记 )
对数据结构来说 文件 是性质相同的 记录 的集合(这不同于我们说的操作系统中的文件概念)
与文件有关的概念还有 记录 是文件中存取的 基本单位 数据项 是文件可使用的 最小单位 数据项有时称 字段 或者 属性 主关键字项 (唯一标识一个记录的字段) 次关键字项 主关键字 次关键字 单关键字文件 多关键字文件 等
文件的 逻辑结构 是一种 线性结构
文件上的操作主要有两类 检索和维护 并有 实时 和 批量处理 两种处理方式
文件的存储结构是指文件在外存上的组织方式 基本 的 组织方式 有 顺序组织 索引组织 散列组织和链组织 文件组织的各种方式往往是这四种基本方式的结合
常用的 文件组织方式 顺序文件 索引文件 散列文件和多关键字文件
评价一个文件组织的 效率 是执行文件操作所花费的 时间 和文件组织所需的 存储空间 通常文件组织的主要目的是为了能高效方便地对文件进行操作而 检索功能的多寡和速度的快慢 是衡量文件操作 质量 的 重要标志
二顺序文件( 识记 )
顺序文件 是指按记录进入文件的先后顺序存放其逻辑顺序和物理顺序一致的文件
一切存储在顺序存储器(如磁带)上的文件都只能顺序文件 这种顺序文件只能按顺序查找法存取(注意没有折半法了)
存储在 直接存取存储器(如磁盘) 上的顺序文件可以顺序查找法存取也可以用分块查找法或二分查找法存取
顺序文件多用于磁带
三索引文件( 识记 )
索引文件的组织方式通常是在文件本身(主文件)之外另外建立一张表它指明逻辑记录和物理记录之间一一对应的关系这张表就叫做 索引表 它和主文件 一起 构成 索引文件
索引非顺序文件中的索引表为 稠密索引 索引顺序文件中的索引表为 稀疏索引
若记录很大使得索引表也很大时可对索引表再建立索引称为 查找表 通常可达四级索引
四索引顺序文件( 识记 )
索引顺序文件是最常用的文件组织 因为索引顺序文件的主文件也是有序的所以它既适合于随机存取也适合于顺序存取另一方面索引非顺序文件的索引是稠密索引而索引顺序文件的稀疏索引占用空间较少因此索引顺序文件是最常用的一种文件组织
索引顺序文件 常用的有两种 ISAM 文件和 VSAM 文件
五散列文件( 识记 )
散列文件是利用散列存储方式组织的文件亦称为直接存取文件
它类似于散列表即根据文件中关键字的特点设计一个散列函数和处理沖突的方法将记录散列到存储设备上与散列表不同的是对于文件来说记录通常是成组存放的若干个记录组成一个存储单位称为桶 对散列而言处理沖突的方法主要采用拉链法
散列文件的优点是:文件随机存放记录不需要排序;插入删除方便;存取速度快;不需要索引区节省存储空间缺点是不能进行顺序存取只能按关键字随机存取且询问方式限地简单询问需要重新组织文件
六多关键字文件( 识记 )
对被查询的次关键字也建立相应的索引则这种 包含有多个次关键字索引的文件称为 多关键字文件
两种多关键字文件的组织方法 多重表文件 和 倒排表
一般的文件组织中是先找记录然后再找到该记录所含的各次关键字;而倒排文件是先给定次关键字然后查找含有该次关键字的各个记录因此称为倒排
第十章 文件 复习要点
本章在试卷中所占比例不多一般占%左右考试内容多为基本概念
文件的概念要注意这里的文件不是指操作系统意义上的文件而是指导数据库意义上的文件这样的文件指的是带有结构的记录集合
明确记录是文件中存取的基本单位数据项(字段)是文件可使用的最小单位主关键字项和次关键字项的含义关键字的含义
文件上的操作主要有两类检索和维护
文件的基本组织方式(存储结构)有四种顺序组织索引组织散列组织和链组织相应的文件有顺序文件索引文件散列文件和多关键字文件
评价一个文件组织的效率是执行文件操作所花费的时间和文件组织所需的存储空间而检索功能的多寡和速度的快慢是衡量文件操作质量的重要标志
磁带只适用于存储顺序文件而磁盘则适用于存储各种文件
一切存储在顺序存取存储器(如磁带)上的文件只能是顺序文件只能按顺序查找法查找而存储在直接存储存储器(如磁盘)上的顺序文件则可以用顺序查找法存取也可以用分块法或二分法进行存取
什么是索引文件?
索引表的索引称为查找表最高可达四级
B+树与B树的差异是什么?
散列文件亦称为直接存取文件根据文件中关键字的特点设计一个散列函数和处理沖突的方法将记录散列到存储设备上散列文件中的存储单位叫做桶
