B-树 C++模板类封装（有图有真相）

template<class K,int M=3>
struct BTreeNode
{
	K _key[M];	//关键字 (有效关键字个数为M-1)
	BTreeNode<K, M>* _sub[M + 1];	//链接子树的指针数组
	size_t _size;		//节点中关键字的个数
	BTreeNode<K, M>* _parent;	//指向父节点的指针

	BTreeNode()
		:_size(0)
		, _parent(NULL)
	{
		for (size_t i = 0; i < M + 1; i++)
		{
			_sub[i] = NULL;
		}
	}
};

template<class K,class V>
struct Pair
{
	K _first;
	V _second;
	
	Pair(const K &k = K(), const V& v = V())
		:_first(k)
		, _second(v)
	{}
};

        //递归查找key
	Pair<BTreeNode<K, M>*, int> Find(const K& key)
	{
		BTreeNode<K, M>* parent=NULL;
		BTreeNode<K, M>* cur=_root;
		
		while (cur!=NULL)
		{
			size_t i = 0;
			while (i < cur->_size&&cur->_key[i] < key)
				++i;
			if (cur->_key[i] == key)
				return Pair<BTreeNode<K, M>*, int>(cur, i);	
			// key<_key[i] 则走向与key[i]下标相同的子树
			parent = cur;
			cur = cur->_sub[i];
		}
		return Pair<BTreeNode<K, M>*, int>(parent, -1);
	}

//插入数据
	bool Insert(K& key)
	{
		// 1.B-树为空
		if (NULL == _root)
		{
			_root = new BTreeNode<K, M>;
			_root->_key[0] = key;
			++_root->_size;
			return true;
		}

		Pair<BTreeNode<K, M>*, int> ret = Find(key);
		// 2.该数据已经存在
		if (ret._second != -1)	
			return false;

		// 3.插入数据到关键字数组
		BTreeNode<K, M>* cur = ret._first;
		BTreeNode<K, M>* sub = NULL;
		while (1)
		{
			int i = 0;
			for ( i = cur->_size - 1; i >= 0; )
			{ // 把大数往后挪，对应子树也要进行挪动
				if (cur->_key[i] > key)
				{
					cur->_key[i + 1] = cur->_key[i];
					cur->_sub[i + 2] = cur->_sub[i + 1]; 
					i--;
				}
				else
				{
					break;
				}
			}
			cur->_key[i + 1] = key;
			cur->_sub[i + 2] = sub;
			if (sub!=NULL)
				cur->_sub[i+2]->_parent = cur;
			cur->_size++;

			//关键字数组未满，插入成功
			if (cur->_size < M)
				return true;

			//关键字数组已满，需要进行分裂
			int mid = M / 2;
			BTreeNode<K, M>* tmp = new BTreeNode<K, M>;
			int index = 0;
			size_t k;

			for ( k = mid + 1; k < cur->_size; k++)
			{
				tmp->_key[index] = cur->_key[k];
				if (cur->_sub[k] != NULL)
				{
					tmp->_sub[index] = cur->_sub[k];
					cur->_sub[k] = NULL;
					tmp->_sub[index]->_parent = tmp;
				}
				tmp->_size++;
				cur->_size--;
				index++;
			}
			if (cur->_sub[k] != NULL)
			{
				tmp->_sub[index] = cur->_sub[k];
				cur->_sub[k] = NULL;
				tmp->_sub[index]->_parent = tmp;
			}
			//父节点为空时的链接
			if (cur->_parent == NULL)
			{
				_root = new BTreeNode<K, M>;
				_root->_key[0] = cur->_key[mid];
				cur->_size--;
				_root->_sub[0] = cur;
				_root->_sub[1] = tmp;
				_root->_size++;
				
				//链接
				tmp->_parent = _root;
				cur->_parent = _root;
				return true;
			}
			//父节点不为空时的链接
			key = cur->_key[mid];
			cur->_size--;
			cur = cur->_parent;
			sub = tmp;
		}
	}