浅析B树的分裂过程

B-树>

     最近一直在研究树的这种数据结构，今天实现了一颗适合外查找的平衡多叉树就是B树，有的地方也叫B-树(不要误读为"B减树"奥).当然了还存在B+树，B*树,在这片文章中主要讲述的是B-树的插入和中序遍历.

 一.B-树的性质>

     一颗M阶(M>2)的B树，是一颗平衡的M路平衡搜索树，可以是空树或者满足下面几条性质>

     1).根结点至少有两个孩子.

     2).每个非根结点存在[M/2,M)个孩子.

     3).每个非根结点有[M/2-1,M-1)个关键字，且以升序排列.

      非根结点的孩子始终比非根结点的关键字多一个.

     4).对于一个关键字来说它的左孩子的下标一定和它一样，它的右孩子的下标一定比它多一个.

     5).所有的叶子结点都在同一层

 B-树的结点结构>

template<class K,int M>
struct BTreeNode
{
	//多给一个便于分裂
	K _keys[M];                //关键字数组
	BTreeNode<K,M> *_sub[M+1]; //链接子树的指针数组
	BTreeNode<K,M> *_parent;
	int _size;                 //关键字的个数
	BTreeNode()
		:_parent(NULL)
		,_size(0)
	{
		for (size_t i=0;i<M;++i)
		{
			_keys[i]=K();
			_sub[i]=NULL;
		}
		_sub[M]=NULL;
	}
};