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文件通常被作為大型索引順序文件的標准組織
From:http://tw.wingwit.com/Article/program/sjjg/201311/23538.html
