|
VSAM文件 B+树的每个叶结点中的关键字均对应一个记录适宜于作为稠密索引但若让叶结点中的关键字对应一个页块则B+树可用来作为稀疏索引IBM公司VSAM文件是用B+树作为文件的稀疏索引的一个典型例子 这种文件组织的实现使用了IBM系列的操作系统的分页功能这种存取方法与存储设备无关与柱面磁道等物理存储单位没有必然的联系例如可以在一个磁道中放n个控制区间也可以一个控制区间跨n个磁道 ()VSAM文件的结构 VSAM文件的结构由三部分组成 索引集 顺序集 和 数据集 (如下图所示) ①数据集 文件的记录均存放在数据集中数据集中的一个结点称为控制区间(Control Interval)它是一个I/操作的基本单位每个控制区间含有一个或多个数据记录 ②顺序集和索引集 顺序集和索引集一起构成一棵B+树作为文件的索引部分 顺序集中存放的每个控制区间的索引项由两部分信息组成该控制区间中的最大关键字和指向控制区间的指针若干相邻的控制区间的索引项形成顺序集中的一个结点结点之间用指针相链接而每个结点又在其上一层的结点中建有索引且逐层向上建立索 引所有的索引项都由最大关键字和指针两部分信息组成这些高层的索引项形成B+树的非终端结点 VSAM文件既可在顺序集中进行顺序存取又可从最高层的索引(B+树的根结点)出发进行按关键字的随机存取顺序集中一个结点连同其对应的所有控制区间形成一个整体称做控制区域(Control Range)它相当于ISAM文件中的一个柱面而控制区间相当于一个磁道 ()VSAM文件中控制区间的结构 在VSAM文件中记录可以是不定长的因而在控制区间中除了存放记录本身之外还有每个记录的控制信息(如记录的长度等)和整个区间的控制信息(如区间中存放的记录数等)控制区间的结构如下表所示 ()VSAM文件的插入方法 VSAM文件中没有溢出区解决插入的方法是在初建文件时留出空间一是每个控制区间内并未填满记录而是在最末一个记录和控制信息之间留有空隙;二是在每个控制区域中有一些完全空的控制区间并在顺序集的索引中指明这些空区间 当插入新记录时大多数的新记录能插入到相应的控制区间内但要注意为了保持区间内记录的关键字从小至大有序则需将区间内关键字大于插入记录关键字的记录向控制信息的方向移动若在若干记录插入之后控制区间已满则在下一个记录插入时要进行控制区间的分裂即把近乎一半的记录移到同一控制区域内全空的控制区间中并修改顺序集中相应索引倘若控制区域中已经没有全空的控制区间则要进行控制区域的分裂此时顺序集中的结点亦要分裂由此需要修改索引集中的结点信息但由于控制区域较大通常很少发生分裂的情况 ()VSAM文件的删除 在VSAM文件中删除记录时需将同一控制区间中比删除记录关键字大的记录向前移动把空间留给以后插人的新记录若整个控制区间变空则回收作空闲区间用且需删除顺序集中相应的索引项 ()VSAM文件的优点 和ISAM文件相比基于B+树的VSAM文件有如下优点能保持较高的查找效率查找一个后插入记录和查找一个原有记录具有相同的速度;动态地分配和释放存储空间可以保持平均%的存储利用率;而且永远不必对文件进行再组织因而基于B+树的VSAM文件通常被作为大型索引顺序文件的标准组织 |
