#include "p350.cpp"		template <class Type> int Btree<Type>::Insert ( const Type & x ) {		//將關鍵碼x插入到一個駐留在磁盤上的m階B-樹中。			if (!root)			{				root=new Mnode<Type>;				insertkey ( root, 1, x, NULL );				//K, ap插入到j位置, 且p->n加1			    PutNode (root);  return 1;				    //輸出結點到磁盤, 返回調用程序							}		   Triple<Type> loc = Search (x);				//在樹中搜索x的插入位置		   if ( !loc.tag ) return 0;						//x已經存在于樹中, 不再插入		   Mnode<Type> *p = loc.r,  *q;				//r是關鍵碼x要插入的結點地址		   Mnode<Type> *ap = NULL,  *t;				//ap是插入關鍵碼x的右鄰指針		   Type K = x;  int j = loc.i;					//(K,ap)形成插入二元組		   while (1) {			 if ( p->n < m-1) {						//結點中關鍵碼個數未超出，還可容下新關鍵碼			   insertkey ( p, j+1, K, ap );				//K, ap插入到j位置, 且p->n加1			   PutNode (p);  return 1;				//輸出結點到磁盤, 返回調用程序			 }			 int s = (m+1)/2;						//準備分裂結點, s是(m/2(位置			 insertkey ( p, j+1, K, ap );					//先插入, 結點中p->n達到m			 q = new Mnode<Type>;					//建立新結點q			 move ( p, q, s, m );						//將 p的key[s+1..m]和ptr[s..m]移到q的key[1..s-1]											//和ptr[0..s-1],  p->n改為s-1, q->n改為s-1			 K = p->key[s];  ap = q;		//(K,ap)形成向上插入二元組			 if ( p->parent != NULL ) {				//從下向上進行調整: 原來的p不為根			   t = p->parent;  GetNode (t);				//從磁盤上讀取p的雙親結點			   j = 0;  t->key[(t->n)+1] = MAXKEY;			//在雙親結點內順序搜索插入位置, 設監視哨			   while ( t->key[j+1] < K ) j++;			//搜索, 找到 >K的關鍵碼停			   ap->parent = p->parent;				//新結點的雙親指針賦值	 		   PutNode (p);  PutNode (ap);				//輸出結點到磁盤			   p = t;							//p上升到父結點, 向上調整			 }			 else {								//原來的p是根, 則要產生新的根			   root = new Mnode<Type>;			   root->n = 1;  root->parent = NULL;		//創建新根			   root->key[1] = K;  root->ptr[0] = p;  root->ptr[1] = ap;			   ap->parent = p->parent = root;			   PutNode (p);  PutNode (ap);  PutNode (root);	//輸出結點到磁盤			   return 1;			 }		   }		}