B-樹是一種適合外查找的平衡搜索多叉樹，一棵M階(M>2)的B樹，是一棵平衡的M路平衡搜索樹，可以是空樹或者滿足一下性質：

創(chuàng)新互聯(lián)建站服務項目包括富蘊網(wǎng)站建設、富蘊網(wǎng)站制作、富蘊網(wǎng)頁制作以及富蘊網(wǎng)絡營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關系等，向廣大中小型企業(yè)、政府機構等提供互聯(lián)網(wǎng)行業(yè)的解決方案，富蘊網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務的客戶以成都為中心已經(jīng)輻射到富蘊省份的部分城市，未來相信會繼續(xù)擴大服務區(qū)域并繼續(xù)獲得客戶的支持與信任！

1. 根節(jié)點至少有兩個孩子；

2. 每個非根節(jié)點有[2/M,M]個孩子；

3. 每個非根節(jié)點有[2/M-1,M-1]個關鍵字，并且以升序排列；

4. key[i]和key[i+1]之間的孩子節(jié)點的值介于key[i]、key[i+1]之間；

5. 所有的葉子節(jié)點都在同一層；

這里要提的是，2/M要上取整，也就是當為偶數(shù)個進行除二的時候取上半部分的中間數(shù)；

下面是對于B-樹的簡單實現(xiàn)，最主要的是插入的過程：

#pragma once

#include 
using namespace std;

template 
struct BTreeNode
{
	K _key[M];//存放關鍵值數(shù)組
	BTreeNode* _subs[M+1];//存放孩子結點的數(shù)組
	BTreeNode* _parent;//指向父節(jié)點的指針
	int _size;//表示當前結點的關鍵值個數(shù)

	BTreeNode()
		:_parent(NULL)
		,_size(0)
	{
		for(int i = 0; i < M; ++i)
			_key[i] = K();

		for(int i = 0; i < M+1; ++i)
			_subs[i] = NULL;
	}
};

template 
struct mypair
{
	BTreeNode* first;
	int second;

	mypair(BTreeNode* f, int s)
		:first(f)
		,second(s)
	{}

	mypair* operator->()
	{
		return this;
	}
};

template 
class BTree
{
public:
	BTree()
		:_root(NULL)
	{}
	~BTree()
	{
		_ClearBTree(_root);
	}


	//插入關鍵值
	bool Insert(const K& key)
	{
		if(_root == NULL)//如果一個結點也沒有，創(chuàng)建結點并將關鍵字放入，返回真
		{
			_root = new BTreeNode;
			_root->_key[0] = key;
			_root->_size = 1;
			return true;
		}

		mypair p = Find(key);
		if(p->second >= 0)//如果已有結點，則返回假
			return false;
		
		BTreeNode* node = p->first;
		K newkey = key;
		BTreeNode* sub = NULL;

		while(1)
		{
			int end = node->_size-1;
			while(end >= 0)//相當于用插入排序的方法將關鍵值插入合適的位置
			{
				if(newkey < node->_key[end])
				{
					node->_key[end+1] = node->_key[end];
					node->_subs[end+2] = node->_subs[end+1];
				}
				else
					break;
				--end;
			}
			++end;
			node->_key[end] = newkey;
			node->_subs[end+1] = sub;
			++(node->_size);

			if(node->_size >= M)//當一個結點中關鍵值個數(shù)等于空間大小時就要進行向上分裂
			{
				int mid = (M-1)/2;//首先上取整拿出中間數(shù)
				if(node == _root)//如果分裂到了根結點
				{
					BTreeNode* tmp = new BTreeNode;//重新new出一塊空間存放右半邊數(shù)據(jù)
					int index = 0;
					int i = mid+1;
					for(; i < node->_size; ++i)
					{
						tmp->_key[index] = node->_key[i];
						tmp->_subs[index] = node->_subs[i];//分裂移動數(shù)據(jù)的時候要將其子樹一起移動
						++index;
						++(tmp->_size);
						node->_key[i] = K();//將分裂出去的數(shù)據(jù)的位置重新置位
						node->_subs[i] = NULL;
					}

					tmp->_subs[index] = node->_subs[i];
					node->_subs[i] = NULL;

					BTreeNode* newroot = new BTreeNode;//將中間數(shù)據(jù)向上提升作為新的根結點
					newroot->_key[0] = node->_key[mid];
					newroot->_subs[0] = node;
					newroot->_subs[1] = tmp;
					newroot->_size = 1;
					tmp->_parent = newroot;//更新父結點

					node->_key[mid] = K();
					node->_size = (node->_size) - (tmp->_size) - 1;
					node->_parent = newroot;
					_root = newroot;
					return true;
				}
				else
				{
					newkey = node->_key[mid];//因為不是根結點要向上插入中間結點，先保存
					BTreeNode* tmp = new BTreeNode;//重新new出一塊空間存放右半邊數(shù)據(jù)
					int index = 0;
					int i = mid+1;
					for(; i < node->_size; ++i)
					{
						tmp->_key[index] = node->_key[i];
						tmp->_subs[index] = node->_subs[i];
						++index;
						++(tmp->_size);
						node->_key[i] = K();//將分裂出去的數(shù)據(jù)的位置重新置位
						node->_subs[i] = NULL;
					}
					tmp->_subs[index] = node->_subs[i];//因為孩子比關鍵值要多一個，因此當循環(huán)出來時要記得
					node->_subs[i] = NULL;
					node->_key[mid] = K();
					tmp->_parent = node->_parent;
					node->_size = (node->_size) - (tmp->_size) - 1;

					sub = tmp;//將分裂復制完成的結點賦給下一步插入時要一塊移動的變量保存
					node = node->_parent;//更新結點，向上其父結點進行插入
				}
			}
			else//如果插入結點后并沒有滿，則正確返回
				return true;
		}
	}

	//查找指定關鍵值
	mypair Find(const K& key)
	{
		return _Find(_root, key);
	}

	//中序遍歷打印B樹
	void InOrder()
	{
		_InOrder(_root);
		cout< _Find(BTreeNode* root, const K& key)
	{
		int i = 0;
		for(; i < root->_size; ++i)
		{
			if(root->_key[i] == key)//如果找到，返回
				return mypair(root, i);
			else if(root->_key[i] > key)//如果要找的關鍵值小于當前關鍵值，則直接跳出去遞歸
				break;
			else//如果要找的關鍵值大，則繼續(xù)向后查找
				continue;
		}
		
		if(root->_subs[i] == NULL)
			return mypair(root, -1);//如果其孩子結點為NULL的時候一定找不到，就不用往下遍歷了
		else
			return _Find(root->_subs[i], key);//如果不為空則繼續(xù)遍歷
	}

	//清除結點
	void _ClearBTree(BTreeNode* root)
	{
		if(root == NULL)
			return;
		
		for(int i = 0; i <= root->_size; ++i)
		{
			_ClearBTree(root->_subs[i]);
		}//當遍歷完一層所有的孩子之后，改層才能delete
		delete root;
	}

	//中序遍歷
	void _InOrder(BTreeNode* root)
	{
		if(root == NULL)
			return;
		
		int i = 0;
		for(; i < root->_size; ++i)
		{
			_InOrder(root->_subs[i]);//按照每一層的孩子去遍歷
			cout<_key[i]<<" ";//當遍歷返回的時候往往就找到了當前子樹的最左結點值
		}
		_InOrder(root->_subs[i]);//不要忘記比關鍵值多出來的一個子樹
	}
private:
	BTreeNode* _root;
};



//1.每一次插入結點的時候一定是在葉子結點進行插入
//2.每一次進行分裂將中間數(shù)向上提升插入的時候，其結點附帶的孩子也一定是滿的
void Test()
{
	BTree 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();
}

運行結果：