这个结构一般用于数据库的索引，综合效率非常高，像 Berkerly DB , sqlite , mysql 数据库都使用了这个算法处理索引。
如果想自己做个小型数据库，可能参考一下这个算法的实现，可能会对你有所帮助。
其中的注册很详细，不用再多说了。
/*btrees.h*/
/*
*平衡多路树的一种重要方案。
*在1970年由R.Bayer和E.McCreight发明。
*/
#defineM1
/*B树的阶，即非根节点中键的最小数目。
*有些人把阶定义为非根节点中子树的最大数目。
*/
typedefinttypekey;
typedefstructbtnode{/*B-Tree节点*/
intd;/*节点中键的数目*/
typekeyk[2*M];/*键*/
char*v[2*M];/*值*/
structbtnode*p[2*M 1];/*指向子树的指针*/
}node,*btree;
/*
*每个键的左子树中的所有的键都小于这个键，
*每个键的右子树中的所有的键都大于等于这个键。
*叶子节点中的每个键都没有子树。
*/
/*当M等于1时也称为2-3树
* ---- ----
*|k0|k1|
* - ---- ---- ---
*|p0|p1|p2|
* ---- ---- ----
*/
externintbtree_disp;/*查找时找到的键在节点中的位置*/
externchar*
/*
*平衡多路树的一种重要方案。
*在1970年由R.Bayer和E.McCreight发明。
*/
#defineM1
/*B树的阶，即非根节点中键的最小数目。
*有些人把阶定义为非根节点中子树的最大数目。
*/
typedefinttypekey;
typedefstructbtnode{/*B-Tree节点*/
intd;/*节点中键的数目*/
typekeyk[2*M];/*键*/
char*v[2*M];/*值*/
structbtnode*p[2*M 1];/*指向子树的指针*/
}node,*btree;
/*
*每个键的左子树中的所有的键都小于这个键，
*每个键的右子树中的所有的键都大于等于这个键。
*叶子节点中的每个键都没有子树。
*/
/*当M等于1时也称为2-3树
* ---- ----
*|k0|k1|
* - ---- ---- ---
*|p0|p1|p2|
* ---- ---- ----
*/
externintbtree_disp;/*查找时找到的键在节点中的位置*/
externchar*
顶一下
(4)
80%
踩一下
(1)
20%
- 发表评论
-
- 最新评论 进入详细评论页>>