佳音的博客

2007/04/27

[转]B+树的结构和实现代码

Filed under: Uncategorized — 佳音 @ 7:19 下午

B+树实现代码

来源:http://supercyber.139.com/article/253784.html

这个结构一般用于数据库的索引,综合效率非常高,像 Berkerly DB , sqlite , mysql 数据库都使用了这个算法处理索引。
如果想自己做个小型数据库,可能参考一下这个算法的实现,可能会对你有所帮助。

其中的注册很详细,不用再多说了。

/* btrees.h */
/*
* 平衡多路树的一种重要方案。
* 在 1970 年由 R. Bayer 和 E. McCreight 发明。
*/
#define M 1
/* B 树的阶,即非根节点中键的最小数目。
* 有些人把阶定义为非根节点中子树的最大数目。
*/
typedef
int typekey;
typedef
struct btnode { /* B-Tree 节点 */
int d; /* 节点中键的数目 */
typekey k[
2*M]; /**/
char *v[2*M]; /**/
struct btnode *p[2*M+1]; /* 指向子树的指针 */
} node,
*btree;
/*
* 每个键的左子树中的所有的键都小于这个键,
* 每个键的右子树中的所有的键都大于等于这个键。
* 叶子节点中的每个键都没有子树。
*/

/* 当 M 等于 1 时也称为 2-3 树
* +—-+—-+
* | k0 | k1 |
* +-+—-+—-+—
* | p0 | p1 | p2 |
* +—-+—-+—-+
*/
extern int btree_disp; /* 查找时找到的键在节点中的位置 */
extern char * InsValue; /* 与要插的键相对应的值 */

extern btree search(typekey, btree);
extern btree insert(typekey,btree);
extern btree delete(typekey,btree);
extern int height(btree);
extern int count(btree);
extern double payload(btree);
extern btree deltree(btree);
/* end of btrees.h */

/*******************************************************/

]]>

Powered by 00RZ