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 图 44 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) „ 倒排文件 „ 与多重表文件的区别是次关键字索引的结构不同 „ 称倒排文件中的次关键字索引为倒排表，具有相同关 键字的记录之间不设指针相链，而在倒排表中该次关 键字的一项中存放这些记录的物理记录号。 „ 倒排表中具有同一次关键字的记录号是有序排列的 插入删除时，需要作相应移动。 „ 缺点：维护困难