b-tree.h

btree算法

//当查找的文件较大，且存放在磁盘等直接当查找的文件较大，
//且存放在磁盘等直接存取设备中时，为了减少查找过程中对
//磁盘的读写次数，提高查找效率，基于直接存取设备的读写
//操作以"页"为单位的特征。
//  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__