[转]B+树的结构和实现代码
<![CDATA[
B+树实现代码
来源:http://supercyber.139.com/article/253784.html
这个结构一般用于数据库的索引,综合效率非常高,像 Berkerly DB , sqlite , mysql 数据库都使用了这个算法处理索引。
如果想自己做个小型数据库,可能参考一下这个算法的实现,可能会对你有所帮助。
其中的注册很详细,不用再多说了。
/*
* 平衡多路树的一种重要方案。
* 在 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;
/*
* 每个键的左子树中的所有的键都小于这个键,
* 每个键的右子树中的所有的键都大于等于这个键。
* 叶子节点中的每个键都没有子树。
*/ </p>
</span>/* 当 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 \*/
/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/
]]\>