BTree---------詳談

一種適合外查找的樹，它是一種平衡的多叉樹，稱為B樹。

一棵M階(M>2)的B樹，是一棵平衡的M路平衡搜索樹，可以是空樹或者滿足一下性質：

1. 根節點至少有兩個孩子

2. 每個非根節點有[M/2,M]個孩子

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

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

5. 所有的葉子節點都在同一層

注：使用B-tree結構可以顯著減少定位記錄時所經歷的中間過程，從而加快存取速度。按照翻譯，B 通常認為是Balance的簡稱。這個數據結構一般用于數據庫的索引，綜合效率較高。

B-tree有以下特性：

1、關鍵字集合分布在整棵樹中；

2、任何一個關鍵字出現且只出現在一個結點中；

3、搜索有可能在非葉子節點結束；

4、其搜索性能等價于在關鍵字全集內做一次二分查找；

5、自動層次控制；

鑒于B-tree具有良好的定位特性，其常被用于對檢索時間要求苛刻的場合，例如：

1、B-tree索引是數據庫中存取和查找文件(稱為記錄或鍵值)的一種方法。

2、硬盤中的結點也是B-tree結構的。與內存相比，硬盤必須花成倍的時間來存取一個數據元素，這是因為硬盤的機械部件讀寫數據的速度遠遠趕不上純電子媒體的內存。與一個結點兩個分支的二元樹相比，B-tree利用多個分支（稱為子樹）的結點，減少獲取記錄時所經歷的結點數，從而達到節省存取時間的目的。

#pragma once
#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;
	size_t _size;
	BTreeNode()
		:_parent(NULL)
		, _size(0)
	{
		for (int i = 0; i < M; ++i)
		{
			_keys[i] = K();
			_subs[i] = NULL;
		}
		_subs[M] = NULL;
	}
};//K
template<class K,class V,int M>
struct BTreeNodeKV
{
	pair<K, V> _kvs[M];
	BTreeNodeKV<K, V, M>* _subs[M + 1];
	BTreeNodeKV<K, V, M>* _parent;
	size_t _size;
};
template<class K,int M>
class BTree
{
	typedef BTreeNode<K, M> Node;
public:
	BTree()
		:_root(NULL)
	{}
	pair<Node*, int> Find(K& key)
	{
		if (_root == NULL)
			return pair<Node*, int>(NULL, -1);
		Node* cur=_root;
		Node* parent = NULL;
		while (cur)
		{
			int size = cur->_size;
			int i;
			for (i = 0; i < size;)
			{
				if (cur->_keys[i] == key)
					return pair<Node*, int>(cur, i);
				else if (cur->_keys[i] < key)
				{
					++i;
				}
				else
					break;
			}
			parent = cur;
			cur = cur->_subs[i];
		}
		return pair<Node*, int>(parent, -1);
	}
	void _Insert(Node* cur,K& key, Node* sub)
	{
		int end = cur->_size - 1;
		while (end >= 0)
		{
			if (cur->_keys[end] > key)
			{
				cur->_keys[end + 1] = cur->_keys[end];
				cur->_subs[end + 2] = cur->_subs[end+1];
				--end;
			}
			else
				break;
		}
		cur->_keys[end + 1] = key;
		cur->_subs[end + 2] = sub;
		++cur->_size;
		if (sub)
			sub->_parent=cur;
	}
	bool Insert(K& key)
	{
		if (_root == NULL)
		{
			_root = new Node;
			_root->_keys[0] = key;
			_root->_size = 1;
			return true;
		}
		else
		{
			pair<Node*,int> ret = Find(key);
			if (ret.second != -1)
				return false;
			else
			{
				Node* cur = ret.first;
				K newkey = key;
				Node* insert_sub = NULL;//第一次插入時insert_sub為NULL
				while (1)
				{
					_Insert(cur, newkey, insert_sub);
					if (cur->_size<M)
						break;
				
					//分裂
					int div = M / 2;
					Node* sub = new Node;
					int index = 0;
					int i = div+1;
					while (i < M)
					{
						sub->_keys[index] = cur->_keys[i];
						cur->_keys[i] = K();//還原為K類型的默認值
						sub->_subs[index] = cur->_subs[i];
						cur->_subs[i] = NULL;
						++index;
						++i;
						++sub->_size;
					}
					sub->_subs[index] = cur->_subs[i];
					cur->_subs[i - 1] = NULL;
					cur->_size -= (index+1);//減去右邊和key的大小
					
					if (cur->_parent == NULL)
					{
						_root = new Node;
						_root->_keys[0] = cur->_keys[div];
						cur->_keys[div] = K();
						_root->_subs[0] = cur;
						cur->_parent = _root;
						_root->_subs[1] = sub;
						sub->_parent=_root;
						_root->_size = 1;
						return true;
					}
					else
					{
						insert_sub = sub;
						newkey = cur->_keys[div];
						cur = cur->_parent;
					}
				}
				return true;
			}
		}
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
protected:
	void _InOrder(Node* root)
	{
		if (root == NULL)
			return;
		int i = 0;
		for (i = 0; i < root->_size; ++i)
		{
			_InOrder(root->_subs[i]);
			cout << root->_keys[i] << " ";
		}
		_InOrder(root->_subs[i]);
	}
protected:
	Node* _root;
};
void Test1()
{
	//int arr[] = { 20, 30, 10 };
	/*BTree<int, 3> b;
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i)
	{
		b.Insert(arr[i]);
	}*/
	int arr[] = { 53, 75, 139, 49, 145, 36, 101 };
	BTree<int, 3> b;
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i)
	{
		b.Insert(arr[i]);
	}
	b.InOrder();
}
#include"BTree.h"
int main()
{
	Test1();
	system("pause");
	return 0;
}