从B+树删除关键码值为33的记录 105.4 VSAM VSAM(Virtual Storage Access Method}虚拟存储存取方法 ■B+树的应用 种索引顺序文件的组织方式 与存储设备无关,存储单位是“逻 叶结点阶5,内部阶4 辑的 张陪写 新。■印乡究 北京太 孔稳写 权新有轴命剑究 VSAM的组成 索引集 顺序集(顺序集索引) 和索引集共同形成了B+树结构的文件 索引 数据集 存放文件记录 记录可以是变长的 张铭帖编写 叔所有,轨圆即 孔写 1055B树的性能分析 包含N个关键码的B树,有N+1个外 ■N=1,999,998,m=199时 部空指针,假设外部指针在第k层 第0层为根,第一层至少两个结点 k=4 第二层至少2*m/21个结点 ■一次检索最多4层 第k层至少 -1个结点 北京大息学 张铭 权质有,印究 张帖写 1616 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 91 从B+树删除关键码值为33的记录 18 33 23 10 12 15 18 19 20 21 22 23 30 31 45 47 48 50 52 „叶结点阶5，内部阶4 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 92 10.5.4 VSAM „ VSAM(Virtual Storage Access Method)—虚拟存储存取方法 „ B+树的应用 „ 一种索引顺序文件的组织方式 „ 与存储设备无关，存储单位是“逻 辑”的 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 93 … … … 控制域 …… 控制区间 索引 顺序集 数据集 VSAM 文件结构 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 94 VSAM的组成 „ 索引集 „ 顺序集（顺序集索引） „ 和索引集共同形成了B+树结构的文件 索引 „ 数据集 „ 存放文件记录 „ 记录可以是变长的 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 95 10.5.5 B树的性能分析 „ 包含N个关键码的B树，有N+1个外 部空指针，假设外部指针在第k层。 „ 第0层为根，第一层至少两个结点， „ 第二层至少 2* 个结点， „ 第k层至少 个结点， 239 240 279 008 040 052 110 135 142 212 045 112 236 ⎡ ⎤ m / 2 1 2 ⎡ ⎤ / 2 , −1 + ≥ ⋅ k N m ⎡ ⎤ ) 2 1 1 log ( / 2 + ≤ + N k m 2 2 ⎡ ⎤ 1 ⋅ − m k / 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 96 „ N=1,999,998，m=199时 „ k=4 „ 一次检索最多4层