数据结构——文件概要.pptVIP

3、ISAM和VSAM比较 ISAM是一种专为磁盘存取设计的文件组织形式，采用静态索引结构，对磁盘上的数据文件建立盘组、柱面、磁道三级索引。ISAM文件中的记录按关键字顺序存放。经过多次插入和删除记录后，文件结构变得不合理，需定时整理ISAM文件。 和ISAM文件相比，给基于B+树的VSAM文件有如下优点：能保持较高的查找效率，查找一个后插入记录和查找一个原有记录具有相同的速度；动态地分配和释放存储空间，可以保持平均75%的存储利用率；永远不必对文件进行再组织。因而基于B+树的VSAM文件，通常作为大型索引顺序文件的标准组织。 VSAM文件采用B+树动态索引结构，文件只有控制区间和控制区域等逻辑存储单位，与外存储器中的柱面，磁道等具有存储单位没有必然联系。VSAM文件结构包括索引集、顺序集和数据集三部分，记录存放于数据集中，顺序集和索引集构成B+树，作为文件的索引部分。 10.4.1 B-树 1、B-树基本概念 一棵m阶（m≥3）B-树或者为空树，或者是满足下述条件的m叉树： ① 树中每个结点至多有m棵子树； ② 若根结点不是叶子结点，则至少有两棵子树； ③ 所有非叶结点都包含信息：（n，p0，k1，p1，k2，p2，…，kn，pn），其中： ki（1≤i≤n）为关键码，且ki＜ki+1（1≤i＜n）； pj（0≤j≤n）为指向子树根结点的指针，且pj（0≤jn）所指子树中所有结点的关键码均小于kj+1，pn所指子树中所有结点的关键码均大于kn； n（?m/2?-1≤n≤m-1）为关键码个数（n+1为子树个数）。 ④ 根结点外所有非叶结点至少有?m/2?棵子树，即每个内部结点至少有?m/2?-1个关键码； ⑤ 所有叶结点都位于树的同一层次。叶结点本身都不带有数据信息，可以看作外部结点或查找失败的结点。 §10.4 动态索引B-树 1、B-树基本概念2 一棵3阶B-树实例： 1、B-树基本概念3 B-树存储结构中结点类型定义： 00 #define MAXM 10 01 typedef int KeyType; 03 tepedef struct node 04 { 05 int keynum; 06 KeyType key[MAXM]; 07 struct node *patent; 08 struct node *ptr[MAXM]; 09 } BTNode; 10 int m; 11 int Max; 12 int Min; 2、B-树查找 在一棵B-树上进行顺序查找关键码k的步骤如下： 将k与根结点中k[i]进行比较： ● 若k= k[i]，查找成功。 ● 若k＜k[i]，沿指针ptr[0]所指子树继续进行查找。 ● 若k[i]＜k＜k[i+1]，沿指针ptr[i]所示子树继续查找。 ● 若k ＞ k[n]，沿指针ptr[n]所指子树继续查找。 10.4.1 B-树2 2、B-树查找2 算法10-1 B-树查找算法 00 Result SearchBTree(BTree *T, KeyType K) 01 { 02 BTree *p,*q; 03 int n,i; 04 p=T; 05 q=NULL; 06 i=0; 07 while (p) 08 { 09 n=p-keynum; 10 i=Search(p, K); /* 在p-key[0..keynum-1]中查找 i */ 11 p-key[i]=Kp-key[i+1] 10.4.1 B-树2 2、B-树查找2 算法10-1 B-树查找算法 12 if (i0 p-key[i]==K) 13 return (p,i,1); /* 查找成功 */ 14 else 15 { 16 q=p; /* q 指示 p 的双亲 */ 17 p=p-ptr[i]; 18 } 19 } 20 return (q,i,0); /* 查找不成功 */ 21 } 10.4.1 B-树2 3、B-树插入与生成 （1）B-树插入 step 1. 位置查找 在B-树中查找k，若找到则直接返回（假设不处理相同关键码插入）；否则查找操作失败于某叶结点,将k插入到p所指叶结点第pos个位置上。 step 2.非满插入 若该叶结点原来是非满（结点中原有关键码总数小于m-1），插入k不会破坏B-树平衡性质，插入k后即完成了插入操作。 s