q=p;p=ppm[;向下一层结点搜索 GetNode(p) ∥读入该结点 result r=g; result. i- i; result. tag=1; return resuli 搜索失败,返回插入置 ■提高搜索树的路数m,可以改善树的搜索性能。 对于给定的关键码数n,如果搜索树是平衡的, 可以使m路搜索树的性能接近最佳。下面我们 将讨论一种称之为B树的平衡的m路搜索树。 在B树中我们引入“失败”结点。一个失败结 点是当搜索值x不在树中时才能到达的结点
q = p; p = p→ptr[i]; //向下一层结点搜索 GetNode (p); //读入该结点 } result.r = q; result.i = i; result.tag = 1; return result; //搜索失败,返回插入位置 }
B树 一棵m阶B树是一棵m路搜索树,它或者是 空树,或者是满足下列性质的树: ◆根结点至少有2个子女。 ◆除根结点以外的所有结点及失败结点至少有 「m21个子女。 ◆所有的失败结点都位于同一层。 事实上,在B树的每个结点中还包含有一组指 针D[m,指向实际对象的存放地址。K与D (1≤isn<m)形成一个索引项(K团,D[),通过 K可找到某个对象的存储地址D
4 101525301450 35 1015 2535 4550 非B树 B树 B树的类定义和B树结点类定义 template <class Type> class btree public Mtree<type> t ∥/继承m路搜索树的所有属性和操作
template <class Type> class Btree : public Mtree<Type> { //继承 m 路搜索树的所有属性和操作
public int Insert( const Type& x ); int Remove( const Type& x ) template< class Type> class node{∥点定义 private: int n ∥/结点中关键码个数 Anode<ype>* parent;∥双亲指针 1 pe keyin1Nm1m+1];/树指针数组0~m /键码数组1~m1 Node<type>
public: int Insert ( const Type& x ); int Remove ( const Type& x ); }; template <class Type> class Mnode { //结点定义 private: int n; //结点中关键码个数 Mnode<Type> *parent; //双亲指针 Type key[m+1]; //关键码数组 1m-1 Mnode<Type> *ptr[m+1]; //子树指针数组 0m };
B树的搜索算法 ■B树的搜索算法继承了在m路搜索树Mree上的 搜索算法。 B树的搜索过程是一个在结点内搜索和循某 条路径向下一层搜索交替进行的过程。因此, B树的搜索时间与B树的阶数m和B树的高度 h直接有关,必须加以权衡。 在B树上进行搜索,搜索成功所需的时间取决 于关键码所在的层次,搜索不成功所需的时间 取决于树的高度。如果我们定义B树的高度h 为失败结点所在的层次,需要了解树的高度h 与树中的关键码个数N之间的关系