#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;
			 }
		   }
		}