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 图 33 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文件的记录可以是不定长的