华科数据结构课件

华中科技大学计算机学院(16)数据结构第12章文件内存不能永久性保存数据，以及容量有限，所以需要数据以文件形式存放到外部存储器中。12.1文件的基本概念文件：由大量性质相同的记录组成的集合。记录：文件中可存取的基本数据单位，它有若干个数据项组成。数据项：最基本的不可再分的数据单位。数据项的名称称为记录的域。关键字：能够区分文件中各记录的域。

主关键字-----可以唯一地标识一个记录的关键字；

次关键字-----不能唯一地标识一个记录的关键字。文件分类：按记录类型划分：（1）流式文件：由一维的连续的字符（字节）序列组成，无结构，无解释。如C源程序。此时的记录为单个字符（字节）。（2）记录文件：记录是由一个或多个数据项组成的集合。如.db.dbf文件。按记录长度划分：（1）定长记录文件：文件中每个记录含有的信息长度相同。（2）不定长记录文件：文件有含有长度不等的记录组成。记录的逻辑结构和物理结构：逻辑结构：呈现在用户和应用程序员面前的数据组织形式，是用户对数据的表示和存取方式。着眼于用户使用方便。物理结构：数据在物理存储器上存储的方式，是数据的物理表示和组织。应考虑提高存储空间的利用率和减少存取记录的时间。物理记录：是计算机用一条I/O命令进行读写的基本数据单位。对固定的设备和操作系统，它的大小基本上是固定不变的。逻辑记录和物理记录的三种关系：（1）一个物理记录存放一个逻辑记录；（2）一个物理记录存放多个逻辑记录；（3）多个物理记录存放一个逻辑记录；用户读写记录是对逻辑记录，而操作系统对物理记录。文件的操作：（1）检索；（2）修改。文件的检索一般有三种：（1）顺序存取：从当前位置开始，存取下一个逻辑记录；（2）直接存取：存取第i个逻辑记录；以上两种存取方式都是根据记录的序号（即记录存入文件时的序号）或记录的相对位置进行存取。（3）按关键字存取：给定一个值，查询一个或一批关键字与给定值相关的记录。对数据库文件的查询有四种：（a）简单查询：查询关键字等于给定值的记录；（b）区域查询：查询关键字属于某个区域的记录；（c）函数查询：给定关键字的某个函数；例如查询平均分以上的记录。（d）布尔查询：以上三种查询用布尔运算组合起来的查询。例如查询总分600以上并且数学在100分以上，或总分在平均分以下并且外语在98分以上的所有记录。文件的修改包括：(1)插入一个记录；(2)删除一个记录；(3)更新一个记录。文件的操作有两种方式：（1）实时：应答时间要求严格，要求在给定时间内完成。（2）批量。文件组织的三种基本形式：（1）顺序组织；（2）随机组织；（3）链组织。12.2顺序文件

顺序文件（SequentialFile)是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录和逻辑记录的顺序是一致的。如果次序相继的两个物理记录在存储介质上的存储位置是相邻的，则又成连续文件。如果两个物理记录之间的次序有指针链表示，则称串联文件。顺序文件是根据记录序号或记录的相对位置来进行存取的文件组织方式，特点：（1）存取第i个记录，必须搜索在它之前的i-1个记录；（2）插入新的记录只能在文件尾；（3）若要更新文件中的某个记录，必须将整个文件复制。顺序文件的优点是连续存取速度快，在查找和修改都是成批处理的情况下，以顺序文件为佳。顺序文件的分类：（1）按关键字排列；（2）未按关键字排列，仅按先后次序。顺序文件的操作：（1）顺序存取：从文件的第1个记录依次顺序存取，存取效率很高。（2）随机存取：对指定的记录进行存取，但这种要求对顺序文件来说，极不方便，存取效率很低。（3）按关键字存取：需从文件的第1个记录开始查找，一般情况下，存取效率不高。12.3索引文件除文件自身（称作数据区）之外，另建立一张指示逻辑记录和物理记录之间一一对应关系的表：索引表。这类包括文件数据区和索引表两大部分的文件称为索引文件。索引表的每一项称为索引项。不论主文件是否按关键字有序，索引表中的索引项总是按关键字顺序排列。若数据区中的记录也按关键字顺序排列，则称索引顺序文件，反之，称索引非顺序文件。物理记录号职工号姓名职务其它10129张三教授。10205李四讲师。10302王红助教。10438。。。10531。。。10643。。。10717。。。10850。。。10949。。。11047。。。11156。。。(a)文件数据区关键字物理记录号0210305102171072910131105381044310647110491095010856111(b)索引表12.4索引顺序文件索引顺序文件是指记录按关键字顺序存放的索引文件。其存储结构分三个区：索引区、基本记录区和溢出区。基本记录区是按记录的关键字排序的。因此不必为每一个记录保存一个索引项，而只要把记录区分块，通常是一个磁道作为一块，每块记录设一个索引项。保存该块的最大关键字值。溢出记录区是为了解决插入问题而设置的，在这种文件中，由于记录按关键字值顺序存放，因此，如果新增记录要插入到两个原有记录之间时，需要调整记录区，如果当前块已满，则最后一记录被调整出当前块，放入溢出记录区。溢出区采用链表结构。基本索引项溢出索引项关键字值指针关键字值指针基本数据区每一块设一个索引项，登记该块内的最后一个记录的关键字值和该块记录的首地址。溢出数据区的记录用指针链接，从基本数据区同一块中溢出的记录形成一个链表，基本数据区有多少个块，溢出区就可能有多少个链表。溢出区索引项登记该块的第一个溢出记录的关键字值（作为本块的关键字值的上界）和该块最近溢出的记录在溢出区的地址。基本索引项溢出索引项基本索引项溢出索引项90T2，1/145T3，1/1记录2记录3记录4记录5记录R50R60R70R80R90T2R100R130R135R140R145T3T4索引基本区溢出区索引顺序文件存储示意图基本索引项溢出索引项基本索引项溢出索引项80T2，190T4，1145T3，1/1记录2记录3记录4记录5记录R50R60R65R70R80T2R100R130R135R140R145T3R90/T4索引基本区溢出区插入R65后，基本数据区的R70到

R90后移，R90到溢出区基本索引项溢出索引项基本索引项溢出索引项80T2，190T4，1140T3，1145T4，21记录2记录3记录4记录5记录R50R60R65R70R80T2R95R100R130R135R140T3R90/R145/T4索引基本区溢出区插入R95后，基本数据区的R100到

R145后移，R145到溢出区基本索引项溢出索引项基本索引项溢出索引项80T2，190T4，3140T3，1145T4，21记录2记录3记录4记录5记录R50R60R65R70R80T2R95R100R130R135R140T3R90/R145/R83T4，1T4索引基本区溢出区插入R83时，因80<83<90,所以直接加入到溢出区12.5多关键字文件

多关键字文件的特点：对文件进行检索操作时，不仅对主关键字进行简单询问，还经常对次关键字进行其它类型的询问检索。如下页表格中，学号为主关键字，专业、已修学分、选修课目等为次关键字。允许的查询：

根据学号查询某学生的信息；查询已修学分400分以上的学生；查询已修学分400分以上计算机专业的学生人数；其他查询为此，对多关键字文件，可建立一系列的次关键字索引。姓名学号专业已修学分选修课目王文1350软件412丙丁马小燕1351软件398甲丙阮森1352计算机436乙丙丁苏明明1353应用402甲丙田水1354计算机384乙丁杨青1355应用356甲薛平平1356软件398甲乙崔子健1357软件408甲丙王洪1358应用370甲丁刘倩1359应用364甲学生信息表12.5.1多重表文件

多重表文件的特点：记录按主关键字的顺序构成一个串联文件。并建立主关键字的索引（成为主索引），主索引为非稠密索引。如下页图所示为一个多重链表文件，记录按学号链接，为查找方便，分成三个链表。对每一个次关键字建立一个稠密索引。相同次关键字的记录形成一个链表。12.5.1多重表文件

多重表文件的特点：记录按主关键字的顺序构成一个串联文件。并建立主关键字的索引（成为主索引），主索引为非稠密索引。如下页图所示为一个多重链表文件，记录按学号链接，为查找方便，分成三个链表。对每一个次关键字建立一个稠密索引。相同次关键字的记录形成一个链表。记录号姓名学号专业已修学分01王文135002软件0241203丙02丁0302马小燕135103软件0739807甲04丙0303阮森135204计算机05436^乙05丙04丁0504苏明明1353^…应用0640208甲06丙0805田水135406计算机^38402乙07丁0906杨青135507应用0935610甲0707薛平平135608软件08398^甲08乙^08崔子健1357^软件^40801甲09丙^09王洪135810应用1037005甲10丁^10刘倩1359^应用^36409甲^主关键字头指针135301135705135909记录号姓名学号专业已修学分01王文135002软件0241203丙02丁0302马小燕135103软件0739807甲04丙0303阮森135204计算机05436^乙05丙04丁0504苏明明1353^…应用0640208甲06丙0805田水135406计算机^38402乙07丁0906杨青135507应用0935610甲0707薛平平135608软件08398^甲08乙^08崔子健1357^软件^40801甲09丙^09王洪135810应用1037005甲10丁^10刘倩1359^应用^36409甲^次关键字头指针长度软件014计算机032应用044记录号姓名学号专业已修学分01王文135002软件0241203丙02丁0302马小燕135103软件0739807甲04丙0303阮森135204计算机05436^乙05丙04丁0504苏明明1353^…应用0640208甲06丙0805田水135406计算机^38402乙07丁0906杨青135507应用0935610甲0707薛平平135608软件08398^甲08乙^08崔子健1357^软件^40801甲09丙^09王洪135810应用1037005甲10丁^10刘倩1359^应用^36409甲^次关键字头指针长度350～399066400～499044记录号姓名学号专业已修学分01王文135002软件0241203丙02丁0302马小燕135103软件0739807甲04丙0303阮森135204计算机05436^乙05丙04丁0504苏明明1353^…应用0640208甲06丙0805田水135406计算机^38402乙07丁0906杨青135507应用0935610甲0707薛平平135608软件08398^甲08乙^08崔子健1357^软件^40801甲09丙^09王洪135810应用1037005甲10丁^10刘倩1359^应用^36409甲^次关键字头指针长度甲027乙033丙015丁01412.5.2倒排表文件倒排文件和多重文件的区别在次关键字索引的结构不同，通常，称倒排文件中的次关键字索引为倒排表，具有相同次关键字的记录之间不设指针相链。而在倒排表中该次关键字的一项中存放这些记录的物理记录号。记录号姓名学号专业已修学分01王文135002软件0241203丙02丁0302马小燕135103软件0739807甲04丙0303阮森135204计算机05436^乙05丙04丁0504苏明明1353^…应用0640208甲06丙0805田水135406计算机^38402乙07丁0906杨青135507应用0935610甲0707薛平平135608软件08398^甲08乙^08崔子健1357^软件^40801甲09丙^09王洪135810应用1037005甲10丁^10刘倩1359^应用^36409甲^次关键字记录物理地址软件01，02，07，08计算机03，05应用04，06，09，10记录号姓名学号专业已修学分01王文135002软件0241203丙02丁0302马小燕135103软件0739807甲04丙0303阮森135204计算机05436^乙05丙04丁0504苏明明1353^…应用0640208甲06丙0805田水135406计算机^38402乙07丁0906杨青135507应用0935610甲0707薛平平135608软件08398^甲08乙^08崔子健1357^软件^40801甲09