ps： 是向上取整

B树是一种高度平衡树

这里以M=3为例进行解释

例如一个树中有数组int arr[]={3，4，10，15，16，20，30，35，36，40，45，46，50，76，77};那么它的结构如下图

B树的插入

例如插入20 30 10 ，画图分析如下

源代码

#pragma  once
#include <vector>
#include <iostream>
using namespace std;
template<class K,int M>
struct BTreeNode
{
	K _keys[M];//关键字数组，多一个便于分解
	BTreeNode<K,M>* _subs[M+1];//连接子树的指针数组
	BTreeNode<K,M>* _parent;
	int size;//关键字个数
 
	BTreeNode()
		:size(0),_parent(NULL)
	{
		size_t i=0;
		for (i=0;i<M;++i)
		{
			_keys[i]=K();
			_subs[i]=NULL;
		}
		_subs[M]=NULL;
	}
 
};
template<class K,int M>
class BTree
{
	typedef BTreeNode<K,M> Node;
public:
	BTree()
		:_root(NULL)
	{}
 pair<Node*,int> Find(const K& key)
 {
	 Node* cur=_root;
	 Node* parent=NULL;
	 while(cur)
	 {
		 int i=0;
		 while(i<cur->size)
		 {
			 if(cur->_keys[i]<key)
			 {
			 ++i;
			 }
			 else if (cur->_keys[i]>key)
			 {
				 break;
			 }
			 else//找到关键字
			 {
               return pair<Node*,int>(cur,i);
			 }
			 
		 }
			 parent=cur;
			 cur=cur->_subs[i];
	 
	 }
	 return pair<Node*,int>(parent,-1);//没有找到关键字返回-1；
 }
 bool Insert(const K& key)
 {
	 if(_root==NULL)//空树的插入
	 {
		 _root=new Node;
		 
		 _root->_keys[0]=key;
		 _root->size=1;
		 return true;
	 }
	 pair<Node*,int> ret=Find(key);
	 if(ret.second!=-1)//如果没有找到则插入，找到则不插入
		 return false;
 
     Node* cur=ret.first;
	 K newkey=key;
	 Node* sub=NULL;
	 
	 while(1)
	 {
		 InsertKey(cur,newkey,sub);
		 if(cur->size<M)//如果插入后没有满，则直接返回
			 return true;
 
		 size_t mid=cur->size/2;//插入后导致M满了，进行分裂
		 Node* tmp=new Node;
		 int j=0;
		 for(int i=mid+1;i<cur->size;++i)//拷贝key及孩子，连续分裂
		 {
			 tmp->_keys[j]=cur->_keys[i];
			 if (cur->_subs[i])
			 {
				 tmp->_subs[j]=cur->_subs[i];
				 tmp->_subs[j+1]=sub;
				 cur->_subs[i]=NULL;
 
				 tmp->_subs[j]->_parent=tmp;
				 tmp->_subs[j+1]->_parent=tmp;
			 }
			  tmp->size++;
			  cur->_keys[i]=K();
			  cur->size--;
			  j++;
		 }
 
		 if(cur->_parent==NULL)//分裂到根节点
		 {
		 _root=new Node;
		 _root->_keys[0]=cur->_keys[mid];
		 
		 _root->_subs[0]=cur;
		 _root->_subs[1]=tmp;
         _root->size++;
 
		 cur->_keys[mid]=K();
		 cur->size--;
 
		 cur->_parent=_root;
		 tmp->_parent=_root;
 
		 return true;
		 }
		 //没有分裂到根节点
		 newkey=cur->_keys[mid];
		 cur->_keys[mid]=K();
		 cur->size--;
         sub=tmp;
		 cur=cur->_parent;//上移
		
	 }
 
	 return true;
 }
 void Inorder()
 {
	 _Inorder(_root);
	 cout<<endl;
 }
protected:
	void InsertKey(Node* node,const K& key,Node* sub)
	{
		int i=node->size-1;
		while (i>=0)
		{
			if(node->_keys[i]>key)
			{
				node->_keys[i+1]=node->_keys[i];
				node->_subs[i+2]=node->_subs[i+1];
			    --i;
			}
			else
			{
				
				break;
			}
			
		}
		node->_keys[i+1]= key;
		node->_subs[i+2]=sub;
		if(sub)
		sub->_parent=node;
		node->size++;
	}
	void _Inorder(Node* root)//打印完一个子树再递归下一步进行打印
	{
		if(root==NULL)
			return;
	    _Inorder(root->_subs[0]);
		for (int i=0;i<root->size;i++)
		{
          // _Inorder(root->_subs[i]);
           cout<<root->_keys[i]<<" ";
		}
		
		for(int i=1;i<M;++i)
		{
			_Inorder(root->_subs[i]);
		}
	}
private:
	Node* _root;
};
void testBTree()
{
 
	BTree<int,3> bt;
	int arr[]={53,75,139,49,145,36,101};
	for(int i=0;i<sizeof(arr)/sizeof(arr[0]);++i)
	{
		bt.Insert(arr[i]);
	}
	bt.Inorder();
}
 

#include "BTree.h"
#include <cstdlib>
int main()
{
	testBTree();
 
	system("pause");
	return 0;
}