B树是为磁盘或其他直接存取辅助存储设备而设计的一种平衡查找树。B树的”分支因子“可能很大，即每个节点可以有很多子女。这一因子由所用磁盘特性所决定，并且可以降低磁盘I/O操作次数。许多数据库系统都使用B树或B树的变形来存储信息。
B树结构形式如下:
其特点：
1）每个节点x有以下域：
a) x.n:当前存储在节点x中的关键字
b) x.n 个key值，，以非降序顺序存放，即 x.key(1) ≤ x.key(2) ≤ … ≤ x.key(x.n)
c) x.leaf：bool型，若为叶子节点 x.leaf=TRUE,反之为FALUSE
2） 每个节点x包含x.n+1个指向其子女的指针x.c(1),x.c(2),…x.c(x.n+1)。（叶子节点无此域）
3）各关键字x.key(i)对存储在各子树中的关键字范围加以分隔：如果k(i)为存储在x.c(i)为根的子树中的关键字，则：
4） 每个叶子节点具有相同的深度，即树的高度 h
5） 每个节点包含的key数有一个上界和下界，这些界可以用一个称为B树的最小度数的固定整数 t ≥ 2 来表示：
a) 每个非根的节点必须至少有t-1个 key. 每个非根内节点至少有t个子女。如果树非空，则根节点至少包含一个key.
b) 每个节点可包含至多2t-1个key。所以一个内节点至多可能有2t个子女。如果一个节点恰好有2t-1个key,则称该点是满的。
6）如果n ≥ 1，则对任意的一棵包含n个关键字，高度为h,最小度t ≥ 2的B树T，有：
B树插入和搜索操作的完整代码如下：
#include<iostream>#include<cstdlib>#include<cstring>#define Disk_Write(x)#define Disk_Read(x)#define t 2#define N 2*tusing namespace std;typedef struct BTNode{int n;//the number of keys storing in the current nodechar key[N];//N keys storing in nondecreasing orderbool leaf;//TRUE:left;FALSE:internal nodeBTNode *c[N+1]; //point n+1 children}BTNode;typedef struct BTree{BTNode *root;}BTree;void BTree_Print(BTNode *x){for(int i=1;i<=x->n;i++){if(x->leaf == false)BTree_Print(x->c[i]);cout<< x->key[i]<<" "; } if(x->leaf == false)BTree_Print(x->c[x->n+1]);}void BTree_SplitChild(BTNode *x,int i){BTNode *z=new BTNode();BTNode *y=x->c[i]; //split y (2t-1 keys) into y (t-1 keys) and z(t-1 keys)z->leaf=y->leaf;z->n=t-1;for(int j=1 ; j<=t-1 ; j++)z->key[j]=y->key[t+j];if(y->leaf==false)//if y has children ,copy its children to zfor(int j=1; j<=t; j++)z->c[j]=y->c[j+t];y->n=t-1;//let z become the (i+1)th child of xfor(int j=x->n+1; j>=i+1; j–)x->c[j+1]=x->c[j];x->c[i+1]=z;//insert the (t)th key of y into (i)th index of xfor(int j=x->n; j>=i; j–)x->key[j+1]=x->key[j];x->key[i]=y->key[t];x->n++;Disk_Write(y);Disk_Write(z);Disk_Write(x);}void BTree_Insert_Nonfull(BTNode *x,char k){int i=x->n;if(x->leaf){//x node is leafwhile(i>=1 && k < x->key[i]) //search for the insert index{x->key[i+1]=x->key[i];i–;}//insert keyx->key[i+1]=k;x->n++;Disk_Write(x);} else // x node is not leaf{ while(i>=1 && k < x->key[i])i–;i++;//Read its child,and insert the key into its child nodeDisk_Read(x->c[i]);//case 1: the child is fullif(x->c[i]->n == 2*t-1){BTree_SplitChild(x,i);if(k > x->key[i])i++;}//case 2:the child is not fullBTree_Insert_Nonfull(x->c[i],k);}}void BTree_Insert(BTree *T,char k){BTNode *r=T->root;if(r->n == 2*t-1){//root node is full//a new node s becomes the rootBTNode *s=new BTNode(); T->root=s;s->leaf=false;s->n=0;s->c[1]=r;//split the original root into two chilren of sBTree_SplitChild(s,1);//insert the key into the nonfull nodeBTree_Insert_Nonfull(s,k);}else//root node is not fullBTree_Insert_Nonfull(r,k); //insert key into root node directly}BTNode *BTree_Search(BTNode *x,char k,int &i){//return pair(y,i)consisting of a node y and an index i such that y.keyi=k i=1;while(i <= x->n && k > x->key[i])i++;if(i <= x->n && k == x->key[i])return x;else if(x->leaf){i=0;return NULL;}else{Disk_Read(x->c[i]);return BTree_Search(x->c[i],k,i); } }void BTree_Create(BTree *T,string ch){//first,create an empty root nodeBTNode *x=new BTNode();x->leaf=true;x->n=0;Disk_Write(x);T->root=x;//second,add new keys into T by calling Insert methodfor(int i=0;i<ch.length();i++)BTree_Insert(T,ch[i]);}void BTree_PrintDetail(BTNode *x){cout<<"The root is:";for(int i=1;i<=x->n;i++)cout<<x->key[i]<<" ";cout<<endl;cout<<"The root's child is:"<<endl;for(int j=1;j<=x->n+1;j++) {BTNode *child=x->c[j];for(int i=1;i<=child->n;i++)cout<<child->key[i]<<" ";cout<<endl;}for(int i=1;i<=x->n+1;i++){ cout<<"The "<<i<<" child"<<endl;BTNode *child0=x->c[i];int m=child0->n+1;for(int j=1;j<=m;j++) {BTNode *c1=child0->c[j];for(int jj=1;jj<=c1->n;jj++)cout<<c1->key[jj]<<" ";cout<<endl;}}}int main(){//string test_ch={'F','S','Q','K','C','L','H','T','V','W','M','R','N','P','A','B','X','Y','D','Z','E'};string test_ch="FSQKCLHTVWMRNPABXYDZE";cout<<"/*—————————-Create B-tree—————————*/"<<endl;BTree *T=new BTree();BTree_Create(T,test_ch);cout<<"After creating ,the B-tree(its degree is "<<t<<"):"<<endl;BTree_Print(T->root);cout<<endl;cout<<"The detail B-tree is:"<<endl;BTree_PrintDetail(T->root);cout<<"/*——————————————————————–*/"<<endl;cout<<"/*—————————Insert B-tree—————————-*/"<<endl;char ich;cout<<"Please input the inserting char:";cin>>ich;BTree_Insert(T,ich);cout<<"After inserting ,the B-tree:"<<endl;BTree_Print(T->root);cout<<endl;cout<<"The detail of B-tree is:"<<endl;BTree_PrintDetail(T->root);cout<<"/*———————————————————————*/"<<endl;cout<<"/*————————–Search B-tree——————————*/"<<endl;char sch;BTNode *sNode=NULL;int index;cout<<"Please input the searching char:";cin>>sch;sNode=BTree_Search(T->root,sch,index);if(sNode==NULL)cout<<"The key doesn't exist in the B-tree."<<endl;else{ cout<<"The key in the Node:";for(int i=1;i<=sNode->n;i++)cout<<sNode->key[i]<<" ";cout<<endl;cout<<"The index of the key in the node is:"<<index<<endl;} cout<<"/*———————————————————————*/"<<endl;return 0;}运行结果：
【注：若有错误，请指正~~~】
版权声明：本文为博主原创文章，未经博主允许不得转载。
慢慢学会了长大。流转的时光，
