//當查找的文件較大，且存放在磁盤等直接當查找的文件較大，
//且存放在磁盤等直接存取設備中時，為了減少查找過程中對
//磁盤的讀寫次數，提高查找效率，基于直接存取設備的讀寫
//操作以"頁"為單位的特征。
//  1972年R.Bayer和E.M.McCreight提出了一種稱之為B-樹的
//多路平衡查找樹。它適合在磁盤等直接存取設備上組織動態
//的查找表。


#ifndef __B_TREE_H__ //__B_TREE_H__
#define __B_TREE_H__ //__B_TREE_H__

#include "StdAfx.h"

#define m 4
template <typename T> struct BMNode
{
	int keynum;
	BMNode<T> *parent;
	T   key[m+1];
	BMNode<T> *ptr[m+1];

	BMNode()
	{
		keynum = 0;
		parent = NULL;
		for(int i = 0; i < m+1; i++) ptr[i] = NULL;
	}
};


template <class T> class CBMTree
{
	private:
		int Insert(BMNode<T> *q, T key, int idx, BMNode<T> *ap);
		int Split (BMNode<T> *q,BMNode<T> **ap);
	public:
		bool SearchBMTree(BMNode<T> *p_root, T key, BMNode<T> **p_keypos, int &keyidx);
		int  InsertBMTree(BMNode<T> **p_root, T key);
		int  DeleteBMTree();
		CBMTree();
		~CBMTree();
};


#endif __B_TREE_H__ //__B_TREE_H__