B树算法与实现(C语言描述).doc

《B树算法与实现(C语言描述).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、这个结构一般用于数据库的索引，综合效率较高。另外还有一种与此类似的树结构叫B+树，像BerkerlyDB,sqlite,mysql数据库都使用了B+树算法处理索引。这两种处理索引的数据结构的不同之处：1。B树中同一键值不会出现多次，并且它有可能出现在叶结点，也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中，并且有可能在非叶结点中也有可能重复出现，以维持B+树的平衡。2。因为B树键位置不定，且在整个树结构中只出现一次，虽然可以节省存储空间，但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中。3。B树的查询效率与键在树中的位置有关，最大时间复杂度与B+

2、树相同(在叶结点的时候)，最小时间复杂度为1(在根结点的时候)。而B+树的时候复杂度对某建成的树是固定的。如果想自己做个小型数据库，可以参考一下下面给出的B树算法的实现，可能会对你有所帮助。  其中的注册很详细，不用再多说了。/*btrees.h*//**平衡多路树的一种重要方案。*在1970年由R.Bayer和E.McCreight发明。*/#defineM1/*B树的阶，即非根节点中键的最小数目。*有些人把阶定义为非根节点中子树的最大数目。*/typedefinttypekey;typedefstructbtnode{    /*B-Tree节点*/    intd;  

3、  /*节点中键的数目*/    typekeyk[2*M];    /*键*/    char*v[2*M];    /*值*/    structbtnode*p[2*M+1];    /*指向子树的指针*/}node,*btree;/**每个键的左子树中的所有的键都小于这个键，*每个键的右子树中的所有的键都大于等于这个键。*叶子节点中的每个键都没有子树。*//*当M等于1时也称为2-3树*    +----+----+*    

4、k0

5、k1

6、                    *  +-+----+----+---*  

7、p0

8、p1

9、p2

10、*  +----+----

11、+----+*/externintbtree_disp;/*查找时找到的键在节点中的位置*/externchar*InsValue;/*与要插的键相对应的值*/externbtreesearch(typekey,btree);externbtreeinsert(typekey,btree);externbtreedelete(typekey,btree);externintheight(btree);externintcount(btree);externdoublepayload(btree);externbtreedeltree(btree);/*endofbtrees.

12、h*//*******************************************************//*btrees.c*/#include#include#include"btrees.h"btreesearch(typekey,btree);btreeinsert(typekey,btree);btreedelete(typekey,btree);intheight(btree);intcount(btree);doublepayload(btree);btreedeltree(btree);staticvoidI

13、nternalInsert(typekey,btree);staticvoidInsInNode(btree,int);staticvoidSplitNode(btree,int);staticbtreeNewRoot(btree);staticvoidInternalDelete(typekey,btree);staticvoidJoinNode(btree,int);staticvoidMoveLeftNode(btreet,int);staticvoidMoveRightNode(btreet,int);staticvoidDelFromNode(btreet,int)

14、;staticbtreeFreeRoot(btree);staticbtreedelall(btree);staticvoidError(int,typekey);intbtree_disp;/*查找时找到的键在节点中的位置*/char*InsValue=NULL;/*与要插的键相对应的值*/staticintflag;/*节点增减标志*/staticintbtree_level=0;/*多路树的高度*/staticintbtree_count=0;/*多路树的键总数*/staticintnode_su