一种适合外查找的树，它是一种平衡的多叉树，称为B树。

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

根节点至少有两个孩子

每个非根节点有[M/2,M]个孩子

每个非根节点有[M/2-1,M-1]个关键字，并且以升序排列

key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间

所有的叶子节点都在同一层

注：使用B-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度。按照翻译，B 通常认为是Balance的简称。这个数据结构一般用于数据库的索引，综合效率较高。

B-tree有以下特性：

1、关键字集合分布在整棵树中；

2、任何一个关键字出现且只出现在一个结点中；

3、搜索有可能在非叶子节点结束；

4、其搜索性能等价于在关键字全集内做一次二分查找；

5、自动层次控制；

鉴于B-tree具有良好的定位特性，其常被用于对检索时间要求苛刻的场合，例如：

1、B-tree索引是数据库中存取和查找文件(称为记录或键值)的一种方法。

2、硬盘中的结点也是B-tree结构的。与内存相比，硬盘必须花成倍的时间来存取一个数据元素，这是因为硬盘的机械部件读写数据的速度远远赶不上纯电子媒体的内存。与一个结点两个分支的二元树相比，B-tree利用多个分支（称为子树）的结点，减少获取记录时所经历的结点数，从而达到节省存取时间的目的。

#pragmaonce#include<iostream>usingnamespacestd;template<classK,intM>structBTreeNode{K_keys[M];BTreeNode<K,M>*_subs[M+1];BTreeNode<K,M>*_parent;size_t_size;BTreeNode():_parent(NULL),_size(0){for(inti=0;i<M;++i){_keys[i]=K();_subs[i]=NULL;}_subs[M]=NULL;}};//Ktemplate<classK,classV,intM>structBTreeNodeKV{pair<K,V>_kvs[M];BTreeNodeKV<K,V,M>*_subs[M+1];BTreeNodeKV<K,V,M>*_parent;size_t_size;};template<classK,intM>classBTree{typedefBTreeNode<K,M>Node;public:BTree():_root(NULL){}pair<Node*,int>Find(K&key){if(_root==NULL)returnpair<Node*,int>(NULL,-1);Node*cur=_root;Node*parent=NULL;while(cur){intsize=cur->_size;inti;for(i=0;i<size;){if(cur->_keys[i]==key)returnpair<Node*,int>(cur,i);elseif(cur->_keys[i]<key){++i;}elsebreak;}parent=cur;cur=cur->_subs[i];}returnpair<Node*,int>(parent,-1);}void_Insert(Node*cur,K&key,Node*sub){intend=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;}elsebreak;}cur->_keys[end+1]=key;cur->_subs[end+2]=sub;++cur->_size;if(sub)sub->_parent=cur;}boolInsert(K&key){if(_root==NULL){_root=newNode;_root->_keys[0]=key;_root->_size=1;returntrue;}else{pair<Node*,int>ret=Find(key);if(ret.second!=-1)returnfalse;else{Node*cur=ret.first;Knewkey=key;Node*insert_sub=NULL;//第一次插入时insert_sub为NULLwhile(1){_Insert(cur,newkey,insert_sub);if(cur->_size<M)break;//分裂intdiv=M/2;Node*sub=newNode;intindex=0;inti=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=newNode;_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;returntrue;}else{insert_sub=sub;newkey=cur->_keys[div];cur=cur->_parent;}}returntrue;}}}voidInOrder(){_InOrder(_root);cout<<endl;}protected:void_InOrder(Node*root){if(root==NULL)return;inti=0;for(i=0;i<root->_size;++i){_InOrder(root->_subs[i]);cout<<root->_keys[i]<<"";}_InOrder(root->_subs[i]);}protected:Node*_root;};voidTest1(){//intarr[]={20,30,10};/*BTree<int,3>b;for(inti=0;i<sizeof(arr)/sizeof(arr[0]);++i){b.Insert(arr[i]);}*/intarr[]={53,75,139,49,145,36,101};BTree<int,3>b;for(inti=0;i<sizeof(arr)/sizeof(arr[0]);++i){b.Insert(arr[i]);}b.InOrder();}#include"BTree.h"intmain(){Test1();system("pause");return0;}