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
樹類似
From:http://tw.wingwit.com/Article/program/sjjg/201311/23610.html
