中国科学技术大学：《数据结构及其算法》课程教学资源（课件讲稿）第12章 文件

数据结构 一文件 中第十二章文件 主讲：张昱 重点：介绍存储在外存上的数据结构 yuzhang@ustc.edu （文件)的有关概念、各种文件的特 点、组织方法及查询和更新操作。 0551-3603804 1V2 2/23 第十二章文件 12.1有关文件的基本概念(1) 12.1有关文件的基本概念 习惯上，称存储在主存储器（内存储器）中的记录集合为表； 12.2顺序文性 称存储在二纸存储（外存储幕）中的记承集合为文件。 。文件及其类别 12.3索引这件 ,定义：由大量性质相同的记录组成的桌合。 12.4ISAM文件和VSAM文件 。按记录的类型不同，可分为： 。操作系统的文件：机是一单的连峡的牛将序列，无始构、无解弄。 12.5直接在取文件（散列文件） 。数滑库文件，是带捕构的记录的桌台。 ·按记录的长度是否固定，可分为： 12.6多关键宇文件 ,定长记录文并：奉个记录含有的信悬长度湘同 。不定长记最文件文并中合有信嘉长度不普的不定长花录 3/23 4/23 图 12.1有关文件的基本概念(2) 12.1有关文件的基本概念(3) 。文件及其类别 ◆ 记录的逻辑结构和物理结构 ,数据库文件按记录中关能字的多少，可分为： ·物理记录和逻辑记录之间的关系： 。单关艘字文件：文件中的记承凡有一个卓一标汉记承的主关被学。 ·多关字文件文外中的记录除了舍有一个主关能外。还有着干 。一个物理记录存放一个逻舞记录 个次美能李。 。一个物理记录包含多个理舞记录 。记录的逻辑结构和物理结构 。多个物理记录表示一个理辑记录。 。记录的望帽结构：是指记录在用户戒应用程序员面前呈现的方式， 。一个物理记录是指计算机用一条I/0命令进行读写的基 是用户对数据的表示和存取方式， 本数据单位。 着眼在用户使用方便， ,用户读/写一个记录是指逻辑记录，查找对应的物理记 记录的物理结构：是教塌在物理存情悬上存储的方式，是敢细的物 录则是操作系统的职责。 理表示和组织。 应考意提高存情空间的利用率和减少存取记录的时间。 5123 图 6123 图 1

1 1/23 数据结构——文件 主讲：张昱 yuzhang@ustc.edu 0551-3603804 2/23 重点：介绍存储在外存上的数据结构 （文件）的有关概念、各种文件的特 点、组织方法及查询和更新操作 。 第十二章 文件 3/23 第十二章 文件 12.1 有关文件的基本概念 12.2 顺序文件 12.3 索引文件 12.4 ISAM文件和VSAM文件 12.5 直接存取文件(散列文件) 12.6 多关键字文件 4/23 12.1 有关文件的基本概念(1) 习惯上，称存储在主存储器(内存储器)中的记录集合为表； 称存储在二级存储器(外存储器)中的记录集合为文件。 „ 文件及其类别 „ 定义：由大量性质相同的记录组成的集合。 „ 按记录的类型不同，可分为： „ 操作系统的文件：仅是一维的连续的字符序列，无结构、无解释。 „ 数据库文件：是带结构的记录的集合。 „ 按记录的长度是否固定，可分为： „ 定长记录文件：每个记录含有的信息长度相同 „ 不定长记录文件：文件中含有信息长度不等的不定长记录 5/23 12.1 有关文件的基本概念(2) „ 文件及其类别 „ 数据库文件按记录中关键字的多少，可分为： „ 单关键字文件：文件中的记录只有一个唯一标识记录的主关键字。 „ 多关键字文件：文件中的记录除了含有一个主关键字外，还含有若干 个次关键字。 „ 记录的逻辑结构和物理结构 „ 记录的逻辑结构：是指记录在用户或应用程序员面前呈现的方式， 是用户对数据的表示和存取方式。 着眼在用户使用方便。 „ 记录的物理结构：是数据在物理存储器上存储的方式，是数据的物 理表示和组织。 应考虑提高存储空间的利用率和减少存取记录的时间。 6/23 12.1 有关文件的基本概念(3) „ 记录的逻辑结构和物理结构 „ 物理记录和逻辑记录之间的关系： „ 一个物理记录存放一个逻辑记录 „ 一个物理记录包含多个逻辑记录 „ 多个物理记录表示一个逻辑记录。 „ 一个物理记录是指计算机用一条I/O命令进行读写的基 本数据单位。 „ 用户读/写一个记录是指逻辑记录，查找对应的物理记 录则是操作系统的职责

12.1有关文件的基本概念(4) 12.2顺序文件(1) 。文件的操作：检索和修改 。顺序文件(Sequential File) 。检靠的方式： ·定义：记录按其在文件中的迎辑顺序依次进入存储介质而建立的 ·原序存取：存取下一个逻操记录 文件 ·直披存取：存取第个理操记录 =>顺序文件中物理记录的顺序和理辑记录的顺序是一袁的 。按关健字存取 ·连华文件，次序相继的两个物理记录在存铺介质上的存储位量是 ,文件的修政：插入一个记录、副除一个记录、更新一个记录 相郸的 。文件的物理结构 率联文件：物理记录之间的次序由指针相链表示 。根据记录的序号或相对位置进行存取 。文件在存情介质上的组织方式称为文件的物通结构 ·姐织方式：震序组织、随机组织、链组织 ·顺序文件的特点 考意的因素：存储介质的类型、记录的类型、大小和关键字的数目 ·存取第个记录，必须先接案在它之前的-1个记录 以及时文件作何种操作等等 ·新的记录只能摘入在文件的求尾 7123 回 ·着要更新文件中的莱个记2必须将整个文件进行复制回 12.2顺序文件(2) 123索引文件() ■顺序文件的特点 ·案引文件 ,优点：连续存取的速度快 ·定义：包括文件数据区和豪引表两大部分的文件 康引表示例1：（逻将记录号，标议，物理记录号） ,用途：用于只进行顺序存取、批量修改的情况 素引表示例2：（关能字，前理花录号） ■顺序存取设备：磁带 。索引项：素引表中的年一项 ,适合于文件的数据量大、平时记录变化少、只 素引表中的索引项总是按关键字顺序排列。 作批量修政的情况 。索引顺序文件：数据区中的记录按关睫字排列 。素引非顺序文件：数据区中的记录不按关键字排列 ,批处理算法：算法12.1P310 ,查找：顺序查找 ■索引表：由系统程序自动生成 9/23 图 。图12.6P312 10/23 图 12.3索引文件(2) 123索到文件(3) ■案引文件的检索 。素引文件的修改 “方式 ·除一个记录：仅需剩去相应的案引项 ·直获存取 播入一个记录：将记录量于数据区的末尾，同时在案引表中播入家 。被关艘字存取 引项 。步漂：类似于分块查找 ,更新一个记录：将更新后的记录量于数据区的末尾，同时修改素引 先查找家引表，若存在该记录，则根调察引项的指示读取外存上的该 表中相应的家引项 记录，否则说明外存上不存在该记最， ·多级索引—静态索引，各级索引均为顺序表结构 由于素引项的长度比记录小得多，则通常可将案引表一次读入内 ·当记录数目很大时，掌引表也很大，此时可以对蜜引表建立一个常 存，由此在素引文件中进行检烹只访问外存两次，即一次读察 引，称为查找丧。 引，一次读记录。 查找素引表时可用折半查找法。 ”四级家引：数据文件家引表查找表)第二查找表→第三查找表 1123 图 多级素引不便于修玫记录（因为年次修故都要重组案引） 图 2

2 7/23 12.1 有关文件的基本概念(4) „ 文件的操作：检索和修改 „ 检索的方式： „ 顺序存取：存取下一个逻辑记录 „ 直接存取：存取第i个逻辑记录 „ 按关键字存取 „ 文件的修改：插入一个记录、删除一个记录、更新一个记录 „ 文件的物理结构 „ 文件在存储介质上的组织方式称为文件的物理结构 „ 组织方式：顺序组织、随机组织、链组织 „ 考虑的因素：存储介质的类型、记录的类型、大小和关键字的数目 以及对文件作何种操作等等 8/23 12.2 顺序文件(1) „ 顺序文件(Sequential File) „ 定义：记录按其在文件中的逻辑顺序依次进入存储介质而建立的 文件 =>顺序文件中物理记录的顺序和逻辑记录的顺序是一致的 „ 连续文件：次序相继的两个物理记录在存储介质上的存储位置是 相邻的 „ 串联文件：物理记录之间的次序由指针相链表示 „ 根据记录的序号或相对位置进行存取 „ 顺序文件的特点 „ 存取第i个记录，必须先搜索在它之前的i-1个记录 „ 新的记录只能插入在文件的末尾 „ 若要更新文件中的某个记录，必须将整个文件进行复制 9/23 12.2 顺序文件(2) „ 顺序文件的特点 „ 优点：连续存取的速度快 „ 用途：用于只进行顺序存取、批量修改的情况 „ 顺序存取设备：磁带 „ 适合于文件的数据量大、平时记录变化少、只 作批量修改的情况 „ 批处理算法：算法12.1 P310 „ 查找：顺序查找 10/23 12.3 索引文件(1) „ 索引文件 „ 定义：包括文件数据区和索引表两大部分的文件 索引表示例1：(逻辑记录号, 标识, 物理记录号) 索引表示例2：(关键字, 物理记录号) „ 索引项：索引表中的每一项 索引表中的索引项总是按关键字顺序排列。 „ 索引顺序文件：数据区中的记录按关键字排列 „ 索引非顺序文件：数据区中的记录不按关键字排列 „ 索引表：由系统程序自动生成 „ 图12.6 P312 11/23 12.3 索引文件(2) „ 索引文件的检索 „ 方式 „ 直接存取 „ 按关键字存取 „ 步骤：类似于分块查找 先查找索引表，若存在该记录，则根据索引项的指示读取外存上的该 记录；否则说明外存上不存在该记录。 „ 由于索引项的长度比记录小得多，则通常可将索引表一次读入内 存，由此在索引文件中进行检索只访问外存两次，即一次读索 引，一次读记录。 查找索引表时可用折半查找法。 12/23 12.3 索引文件(3) „ 索引文件的修改 „ 删除一个记录：仅需删去相应的索引项 „ 插入一个记录：将记录置于数据区的末尾，同时在索引表中插入索 引项 „ 更新一个记录：将更新后的记录置于数据区的末尾，同时修改索引 表中相应的索引项 „ 多级索引——静态索引，各级索引均为顺序表结构 „ 当记录数目很大时，索引表也很大，此时可以对索引表建立一个索 引，称为查找表。 „ 四级索引:数据文件Æ索引表Æ查找表Æ第二查找表Æ第三查找表 多级索引不便于修改记录（因为每次修改都要重组索引）

12.3索引文件(4) 12.4ISAM文件和VSAM文件(1) 动志章引 。ISAM文件-豪引顺序存取方法(Indexed Sequential 。如二又神序树、B-前、能州等 Access Method) :当数押文件的记录数不很多时，可采用二又摔序树作察引 ·ISAM是一种专为减盘存取设计的文件粗织方式 当文件很大时，套引表本身也在外存，为减少访门外存的次数，款应尽量 缩减素引夜的源皮。此时直采用m叉的B~刺作常引表。 。磁盘是以查组、柱面和世道三级地址存取的设告 德圳适用于作某些特辣类型的关塘字的常引表。当宗表不大时，可采用 =>可对微盘上的表据文件建立盘短、柱面和避道三级素引 双链表作存情俯构，反之，则采用Tie树。 ，每个柱面意立一个融道缘引，每个雕道案引填项由两都分想成：著本 对外存中常引表的查找效能主要取决于边月外存的次数。 食引项和泄出家引项（图12.9P314),每一都分都包括关幢字和推 针项，前者表示演减道中最束一个记录的关字，后者潮示该柱 ▣素引文件只能是磁盘文件。 面上的意道蜜引位置， ■调密索引：为每个记录速立一个案引项 柱面家引存薰在某个柱面上，若柱面案引较大占多个测道时，则 。非调密家引：为一组记录建立一个案引项 可毫立柱面常引的常引一主素引。 13/23 回 14/23 图 12.4ISAM文件和VSAM文件(2) 12.4ISAM文件和VSAM文件(3) ■ISAM文件 ·ISAM文件 ·检案：主家引→柱面豪引→磁道案引→记录所在磁道 。存储结构 的第一个记录->顺序查找 ,每个柱面的基本区一 震序存袖结构 。盖出区一链表箱构 ,每个柱面上还开辟有一个滥出区，并且磁道寨引项中 。缅入记录和世出处通P314 有逆出索引项，这是为插入记录所设置的。 ,飘除记录P315 ,SAM文件中的记录是技关能字痕序存放的，在插入记录时看 。北件除记录，在其存袖位置上作测除标记 移动记录并将同一慰道上最末一个记录移至遵出区，同时修 ,周滑地整灌工SAM文件 改藏道来引项。 ,柱面案引的位量 ,邀出区的设置方法：集中存放、分散存放、集中与分散相结 ,检家中需先查找柱面案引，则融头在各柱面间来回移物 ,柱圆宗引应放在数塘文并的中间位置的性圆上 15/23 图 16/23 图 12.4ISAM文件和VSAM文件(4) 12.4ISAM文件和VSAM文件(5) VSAM文件_虚拟存储存取方法(Virtual Storage .VSAM文件 Access Method) 。利用了操作系统的座拟存储悬的功能 ,VSAM文件的结构：索引集、顺序集和数据集 ·对用户来脱，文件只有控制区间和控制区城等泛舞存情单位 ,顺序集存放每个控制区间的索引项（该控制区间中 。用户在存取文件中的记录时，不需要考意该记最的当前位量是否在 的最大关健字和指向控制区间的指针) 内存，也不需要考虑何时执行对外存进行读/写的指★。 ,VSAM文件的结构：寒引集、顺序集和数据集 ,顺序集中一个结点连同其对应的所有控制区间形成 ,文件的记录存敢在数滑集中，数滑集中的一个结点幕为控制区间 一个整体，称做控制区域。 ,控制区同是/0操作的落本单位，每个控制区间青有一个或多个按 ,每个控制区间可视为一个逻辑磁道，每个控制区城 关楚字递增有序神列的记录 可视为一个逻辑柱面。 ,顺序集和凛引桌一起构成一银B树 图 ,VSAM文件的记录可以是不定长的 17/23 图 3

3 13/23 12.3 索引文件(4) „ 动态索引 „ 如二叉排序树、B-树、键树等 „ 当数据文件的记录数不很多时，可采用二叉排序树作索引 „ 当文件很大时，索引表本身也在外存。为减少访问外存的次数，就应尽量 缩减索引表的深度。此时宜采用m叉的B-树作索引表。 „ 键树适用于作某些特殊类型的关键字的索引表。当索引表不大时，可采用 双链表作存储结构；反之，则采用Trie树。 对外存中索引表的查找效能主要取决于访问外存的次数。 „ 索引文件只能是磁盘文件。 „ 稠密索引：为每个记录建立一个索引项 „ 非稠密索引：为一组记录建立一个索引项 14/23 12.4 ISAM文件和VSAM文件(1) „ ISAM文件—索引顺序存取方法(Indexed Sequential Access Method) „ ISAM是一种专为磁盘存取设计的文件组织方式 „ 磁盘是以盘组、柱面和磁道三级地址存取的设备 =>可对磁盘上的数据文件建立盘组、柱面和磁道三级索引 „ 每个柱面建立一个磁道索引，每个磁道索引项由两部分组成：基本 索引项和溢出索引项(图12.9 P314)，每一部分都包括关键字和指 针两项，前者表示该磁道中最末一个记录的关键字，后者指示该柱 面上的磁道索引位置。 „ 柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，则 可建立柱面索引的索引——主索引。 15/23 12.4 ISAM文件和VSAM文件(2) „ ISAM文件 „ 检索：主索引Æ柱面索引Æ磁道索引Æ记录所在磁道 的第一个记录->顺序查找 „ 每个柱面上还开辟有一个溢出区，并且磁道索引项中 有溢出索引项，这是为插入记录所设置的。 „ ISAM文件中的记录是按关键字顺序存放的，在插入记录时需 移动记录并将同一磁道上最末一个记录移至溢出区，同时修 改磁道索引项。 „ 溢出区的设置方法：集中存放、分散存放、集中与分散相结 合 16/23 12.4 ISAM文件和VSAM文件(3) „ ISAM文件 „ 存储结构 „ 每个柱面的基本区——顺序存储结构 „ 溢出区——链表结构 „ 插入记录和溢出处理 P314 „ 删除记录 P315 „ 找到待删除记录，在其存储位置上作删除标记 „ 周期地整理ISAM文件 „ 柱面索引的位置 „ 检索中需先查找柱面索引，则磁头在各柱面间来回移动 „ 柱面索引应放在数据文件的中间位置的柱面上 17/23 12.4 ISAM文件和VSAM文件(4) „ VSAM文件—虚拟存储存取方法(Virtual Storage Access Method) „ 利用了操作系统的虚拟存储器的功能 „ 对用户来说，文件只有控制区间和控制区域等逻辑存储单位 „ 用户在存取文件中的记录时，不需要考虑该记录的当前位置是否在 内存，也不需要考虑何时执行对外存进行读/写的指令。 „ VSAM文件的结构：索引集、顺序集和数据集 „ 文件的记录存放在数据集中，数据集中的一个结点称为控制区间 „ 控制区间是I/O操作的基本单位，每个控制区间含有一个或多个按 关键字递增有序排列的记录 „ 顺序集和索引集一起构成一棵B+树 18/23 12.4 ISAM文件和VSAM文件(5) „ VSAM文件 „ VSAM文件的结构：索引集、顺序集和数据集 „ 顺序集存放每个控制区间的索引项（该控制区间中 的最大关键字和指向控制区间的指针） „ 顺序集中一个结点连同其对应的所有控制区间形成 一个整体，称做控制区域。 „ 每个控制区间可视为一个逻辑磁道，每个控制区域 可视为一个逻辑柱面。 „ VSAM文件的记录可以是不定长的

12.4ISAM文件和VSAM文件(6) 12.5直接存取文件(1) VSAM文件 ·直接存取文件：利用Hash法进行组织的文件。 。VSAM没有遵出区，解决插入的办法是在初建文件时留有空间 。与哈希表不同的是：对文件来说，磁盘上的文件记录 。每个控制区间内没有填端记录，面是在量末一个记录和控制值息之 间留有空麻：或者 通常是成组存放的。 。在善个控制区间中有一世亮全空的控制区间，并在序嘉的素引中 。若干个记录组成一个存储单位，称为桶(Bucket), 指明这世空区间， ,置著一个桶能存放m个记录，则m个同义词的记录可以存敢在 ·指入：控制区间的分裂 同一地址的桶中，而第m+1个同义词出现时才发生“溢出”， ·副除：前移 。对散列文件，主要采用能地址法处理冲夹。 。优点：动态地分配和拜放存德，不需要对文件进行置组，并能较 。当发生滥出时，需要将第m+1个同义词存放到另一个桶中， 快地对摑入的记景进行查找 称之为溢出桶，相对地，麻前m个同义司存放的栖为善桶， 19123 回 20/23 图 12.5直接存取文件(2) 12.6多关键字文件(1) 。直接存取文件：利用Hash法进行组织的文件。 ·多重表文件 。查找： ,特点：记录按主关德字的哪序构成一个申联文件，并建立主关健 ,根语给定值求得哈希地址（盖福号） 字的索引：对每个次关键字项建立次关幢字家引，所有具有同一 ,将善桶的记录滨入内存进行源序查找 次关健字的记录构成一个链表。 营快到关量字等于给变值的记录，则性案成纳： 主素引为非颗密囊引，次蜜引为测密案引。 否则，内没有填黄记录其指计城为空，则检央， 每个引项包括次关健字、头指针和链表长度 。否刷，根摄微所媒的值的指景将塑出相的记章荣入内存做续进行佩序老 。评价 找。直重检常成功或不减孙，。 ·局于物程、品于修改 ·优点：文件随机存放，记录不需进行神序：插入、副除方便，存 ,可将新记录插入在链表的头指针之后 取速度快，不橘要家引区，节省存铺空。 。则去一个记录很繁项，需在每个次关黄字的链表中剩去该记录 峡点：不能进行厘序存取，只能按关健字随机存取：在经过多次 的插入、测除之后，也可能造成文件结构不合理，即滋出桶满而 精内多敷为被除的记：/ 22/23 图 12.6多关键字文件(2) 。倒排文件 ，与多置表文件的区别是次关键字拿引的结构不同 ·称倒排文件中的次关键字素引为侧排表，具有相同关 健字的记录之间不设指针相链，而在倒排表中该次关 健字的一项中存放这些记录的物理记录号。 ,倒排表中具有同一次关健字的记录号是有序排列的 插入副除时，需要作相应移动。 。峡点：维护困难 23/23 图 4

4 19/23 12.4 ISAM文件和VSAM文件(6) „ VSAM文件 „ VSAM没有溢出区，解决插入的办法是在初建文件时留有空间 „ 每个控制区间内没有填满记录，而是在最末一个记录和控制信息之 间留有空隙； 或者 „ 在每个控制区间中有一些完全空的控制区间，并在顺序集的索引中 指明这些空区间。 „ 插入：控制区间的分裂 „ 删除：前移 „ 优点：动态地分配和释放存储，不需要对文件进行重组，并能较 快地对插入的记录进行查找 20/23 12.5 直接存取文件(1) „ 直接存取文件：利用Hash法进行组织的文件。 „ 与哈希表不同的是：对文件来说，磁盘上的文件记录 通常是成组存放的。 „ 若干个记录组成一个存储单位，称为桶(Bucket). „ 假若一个桶能存放m个记录，则m个同义词的记录可以存放在 同一地址的桶中，而第m+1个同义词出现时才发生“溢出”。 „ 对散列文件，主要采用链地址法处理冲突。 „ 当发生溢出时，需要将第m+1个同义词存放到另一个桶中， 称之为溢出桶，相对地，称前m个同义词存放的桶为基桶。 21/23 12.5 直接存取文件(2) „ 直接存取文件：利用Hash法进行组织的文件。 „ 查找： „ 根据给定值求得哈希地址(基桶号) „ 将基桶的记录读入内存进行顺序查找 „ 若找到关键字等于给定值的记录，则检索成功； „ 否则，若基桶内没有填满记录或其指针域为空，则检索失败； „ 否则，根据指针域的值的指示将溢出桶的记录读入内存继续进行顺序查 找，直至检索成功或不成功。 „ 优点：文件随机存放，记录不需进行排序；插入、删除方便，存 取速度快，不需要索引区，节省存储空间。 „ 缺点：不能进行顺序存取，只能按关键字随机存取；在经过多次 的插入、删除之后，也可能造成文件结构不合理，即溢出桶满而 基桶内多数为被删除的记录。 22/23 12.6 多关键字文件(1) „ 多重表文件 „ 特点：记录按主关键字的顺序构成一个串联文件，并建立主关键 字的索引；对每个次关键字项建立次关键字索引，所有具有同一 次关键字的记录构成一个链表。 主索引为非稠密索引，次索引为稠密索引。 每个索引项包括次关键字、头指针和链表长度 „ 评价 „ 易于编程、易于修改 „ 可将新记录插入在链表的头指针之后 „ 删去一个记录很繁琐，需在每个次关键字的链表中删去该记录 23/23 12.6 多关键字文件(2) „ 倒排文件 „ 与多重表文件的区别是次关键字索引的结构不同 „ 称倒排文件中的次关键字索引为倒排表，具有相同关 键字的记录之间不设指针相链，而在倒排表中该次关 键字的一项中存放这些记录的物理记录号。 „ 倒排表中具有同一次关键字的记录号是有序排列的 插入删除时，需要作相应移动。 „ 缺点：维护困难