|
VSAM文件 VSAM是Virtual Storage Access Method(虚拟存储存取方法)的缩写它也是一种索引顺序文件的组织方式采用B+树作为动态索引结构 B+树 B+树是一种常用于文件组织的B树的变型树一棵m阶的B+树和m阶的B树的差异是 ①有k个孩子的结点必有k个关键字; ②所有的叶结点包含了全部关键字的信息及指向相应的记录的指针且叶子结点本 身依照关键字的大小自小到大顺序链接 ③上面各层结点中的关键字均是下一层相应结点中最大关键字的复写(当然也可采用最小关键字复写的原则)因此所有非叶结点可看作是索引部分 【例】下图是一棵阶的B+树 注意 ①通常在B+树上有两个头指针root和sqt前者指向根结点后者指向关键字最小的叶子结点 ②对B+树可进行两种查找运算一种是从最小关键字起进行顺序查找;另一种是从根结点开始进行随机查找 B+树的运算 在B+树上进行随机查找插入和删除的过程基本上与B树类似 ()B+树的查找运算 在查找时若非叶结点上的关键字等于给定值并不终止而是继续向下直到叶子结点因此在B+树中不管查找成功与否每次查找都是走了一条从根到叶子结点的路径 B+树查找的分析类似于B树B+树的插入也仅在叶子结点上进行当结点中的关键字个数大于m时要分裂成两个结点它们所含 关键字的个数分别为 并且它们的双亲结点中应同时包含这两个结点的最大关键字 ()B+树的删除 B+树的删除仅在叶子结点进行当叶子结点中的最大关键字被删除时其在非终端结点中的值可以作为一个分界关键字存在 若因删除而使结点中关键字的个数少于 时则可能要和该结点的兄弟结点合并合并过程和B树类似 |
