B树算法与实现(C语言描述)
- 格式：doc
- 大小：44.50 KB
- 文档页数：21
这个结构一般用于数据库的索引，综合效率较高。
另外还有一种与此类似的树结构叫B+树，像Berkerly DB , sqlite , mysql数据库都使用了B+树算法处理索引。
这两种处理索引的数据结构的不同之处：
1。B树中同一键值不会出现多次，并且它有可能出现在叶结点，也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中，并且有可能在非叶结点中也有可能重复出现，以维持B+树的平衡。
/*******************************************************/
/* btrees.c */
#include <stdlib.h>
#include <stdio.h>
#include "btrees.h"
btree search(typekey, btree);
for(i = t->d; i > d; i--){
t->k[ i ] = t->k[i-1];
t->v[ i ] = t->v[i-1];
t->p[i+1] = t->p[ i ];
}
/*插入键和右子树*/
t->k[ i ] = InsKey;
t->p[i+1] = NewTree;
t->v[ i ] = InsValue;
* |<- M+1 ->|<- M-1 ->|
*/
if (d > M) { /*要插入当前节点的右半部分*/
/*把从2*M-1到M+1的M-1个键值+子树对转移到新节点中,
*并且为要插入的键值+子树空出位置*/
for(i=2*M-1,j=M-1; i>=d; i--,j--) {
temp->k[j] = t->k[ i ];
t->d++;
}
/*
*前件是要插入一个键和对应的右子树，并且本节点已经满
*导致分割这个节点，插入键和对应的右子树，
*并向上层返回一个要插入键和对应的右子树
*/
void SplitNode(btree t, int d)
{
int i,j;
btree temp;
typekey temp_k;
char *temp_v;
i++;
InternalInsert(key, t->p[ i ]);
if (flag == 0)
return;
/*有新键要插入到当前节点中*/
if (t->d < 2*M) {/*当前节点未满*/
InsInNode(t, i); /*把键值+子树对插入当前节点中*/
flag = 0; /*指示上层节点没有需要插入的键值+子树，插入过程结束*/
}
else /*当前节点已满，则分割这个页面并把键值+子树对插入当前节点中*/
SplitNode(t, i); /*继续指示上层节点把返回的键值+子树插入其中*/
}
/*
*把一个键和对应的右子树插入一个节点中
*/
void InsInNode(btree t, int d)
{
int i;
/*把所有大于要插入的键值的键和对应的右子树右移*/
temp->p[0] = t->p[M];
/*保存要插入上层节点的键和值*/
temp_k = t->k[M-1];
temp_v = t->v[M-1];
/*把所有大于要插入的键值的键和对应的右子树右移*/
for(i=M-1; i>d; i--) {
t->k[ i ] = t->k[i-1];
t->v[ i ] = t->v[i-1];
btree insert(typekey,btree);
btree delete(typekey,btree);
int height(btree);
int count(btree);
double payload(btree);
btree deltree(btree);
static void InternalInsert(typekey, btree);
static typekey InsKey; /*要插入的键*/
btree search(typekey key, btree t)
{
int i,j,m;
level=btree_level-1;
while (level >= 0){
for(i=0, j=t->d-1; i<j; m=(j+i)/2, (key > t->k[m])?(i=m+1):(j=m));
InsKey = t->k[M];
InsValue = t->v[M];
}
else { /* d <= M */
/*把从2*M-1到M的M个键值+子树对转移到新节点中*/
for(i=2*M-1,j=M-1; j>=0; i--,j--) {
temp->k[j] = t->k[ i ];
temp->v[j] = t->v[ i ];
temp->d = M;
NewTree = temp;
* +----+----+----+
*/
extern int btree_disp; /*查找时找到的键在节点中的位置*/
extern char * InsValue; /*与要插的键相对应的值*/
extern btree search(typekey, btree);
extern btree insert(typekey,btree);
如果想自己做个小型数据库，可以参考一下下面给出的B树算法的实现，可能会对你有所帮助。
其中的注册很详细，不用再多说了。
/* btrees.h */
/*
*平衡多路树的一种重要方案。
*在1970年由R. Bayer和E. McCreight发明。
*/
#define M 1
/* B树的阶，即非根节点中键的最小数目。
}
/*把节点的最右子树转移成新节点的最左子树*/
temp->p[0] = t->p[M+1];
/*在新节点中插入键和右子树*/
temp->k[d-M-1] = InsKey;
temp->p[d-M] = NewTree;
temp->v[d-M-1] = InsValue;
/*设置要插入上层节点的键和值*/
t->p[i+1] = t->p[ i ];
}
/*在节点中插入键和右子树*/
t->k[d] = InsKey;
t->p[d+1] = NewTree;
t->v[d] = InsValue;
/*设置要插入上层节点的键和值*/
InsKey = temp_k;
InsValue = temp_v;
}
}
t->d =M;
static void Error(int,typekey);
int btree_disp; /*查找时找到的键在节点中的位置*/
char * InsValue = NULL; /*与要插的键相对应的值*/
static int flag; /*节点增减标志*/
static int btree_level = 0; /*多路树的高度*/
2。因为B树键位置不定，且在整个树结构中只出现一次，虽然可以节省存储空间，但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中。
3。B树的查询效率与键在树中的位置有关，最大时间复杂度与B+树相同(在叶结点的时候)，最小时间复杂度为1(在根结点的时候)。而B+树的时候复杂度对某建成的树是固定的。
{
int i,j,m;
level--;
if (level < 0){ /*到达了树的底部:指出要做的插入*/
NewTree = NULL; /*这个键没有对应的子树*/
InsKey = key; /*导致底层的叶子节点增加键值+空子树对*/
btree_count++;
flag = 1; /*指示上层节点把返回的键插入其中*/
static int btree_count = 0; /*多路树的键总数*/
static int node_sum = 0; /*多路树的节点总数*/
static int level; /*当前访问的节点所处的高度*/
static btree NewTree; /*在节点分割的时候指向新建的节点*/
/*建立新节点*/
temp = (btree)malloc(sizeof(node));
/*
* +---+--------+-----+-----+--------+-----+
* | 0 | ...... | M | M+1 | ...... |2*M-1|
* +---+--------+-----+-----+--------+-----+
static void InsInNode(btree, int);
static void SplitNode(btree, int);
另外还有一种与此类似的树结构叫B+树，像Berkerly DB , sqlite , mysql数据库都使用了B+树算法处理索引。
这两种处理索引的数据结构的不同之处：
1。B树中同一键值不会出现多次，并且它有可能出现在叶结点，也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中，并且有可能在非叶结点中也有可能重复出现，以维持B+树的平衡。
/*******************************************************/
/* btrees.c */
#include <stdlib.h>
#include <stdio.h>
#include "btrees.h"
btree search(typekey, btree);
for(i = t->d; i > d; i--){
t->k[ i ] = t->k[i-1];
t->v[ i ] = t->v[i-1];
t->p[i+1] = t->p[ i ];
}
/*插入键和右子树*/
t->k[ i ] = InsKey;
t->p[i+1] = NewTree;
t->v[ i ] = InsValue;
* |<- M+1 ->|<- M-1 ->|
*/
if (d > M) { /*要插入当前节点的右半部分*/
/*把从2*M-1到M+1的M-1个键值+子树对转移到新节点中,
*并且为要插入的键值+子树空出位置*/
for(i=2*M-1,j=M-1; i>=d; i--,j--) {
temp->k[j] = t->k[ i ];
t->d++;
}
/*
*前件是要插入一个键和对应的右子树，并且本节点已经满
*导致分割这个节点，插入键和对应的右子树，
*并向上层返回一个要插入键和对应的右子树
*/
void SplitNode(btree t, int d)
{
int i,j;
btree temp;
typekey temp_k;
char *temp_v;
i++;
InternalInsert(key, t->p[ i ]);
if (flag == 0)
return;
/*有新键要插入到当前节点中*/
if (t->d < 2*M) {/*当前节点未满*/
InsInNode(t, i); /*把键值+子树对插入当前节点中*/
flag = 0; /*指示上层节点没有需要插入的键值+子树，插入过程结束*/
}
else /*当前节点已满，则分割这个页面并把键值+子树对插入当前节点中*/
SplitNode(t, i); /*继续指示上层节点把返回的键值+子树插入其中*/
}
/*
*把一个键和对应的右子树插入一个节点中
*/
void InsInNode(btree t, int d)
{
int i;
/*把所有大于要插入的键值的键和对应的右子树右移*/
temp->p[0] = t->p[M];
/*保存要插入上层节点的键和值*/
temp_k = t->k[M-1];
temp_v = t->v[M-1];
/*把所有大于要插入的键值的键和对应的右子树右移*/
for(i=M-1; i>d; i--) {
t->k[ i ] = t->k[i-1];
t->v[ i ] = t->v[i-1];
btree insert(typekey,btree);
btree delete(typekey,btree);
int height(btree);
int count(btree);
double payload(btree);
btree deltree(btree);
static void InternalInsert(typekey, btree);
static typekey InsKey; /*要插入的键*/
btree search(typekey key, btree t)
{
int i,j,m;
level=btree_level-1;
while (level >= 0){
for(i=0, j=t->d-1; i<j; m=(j+i)/2, (key > t->k[m])?(i=m+1):(j=m));
InsKey = t->k[M];
InsValue = t->v[M];
}
else { /* d <= M */
/*把从2*M-1到M的M个键值+子树对转移到新节点中*/
for(i=2*M-1,j=M-1; j>=0; i--,j--) {
temp->k[j] = t->k[ i ];
temp->v[j] = t->v[ i ];
temp->d = M;
NewTree = temp;
* +----+----+----+
*/
extern int btree_disp; /*查找时找到的键在节点中的位置*/
extern char * InsValue; /*与要插的键相对应的值*/
extern btree search(typekey, btree);
extern btree insert(typekey,btree);
如果想自己做个小型数据库，可以参考一下下面给出的B树算法的实现，可能会对你有所帮助。
其中的注册很详细，不用再多说了。
/* btrees.h */
/*
*平衡多路树的一种重要方案。
*在1970年由R. Bayer和E. McCreight发明。
*/
#define M 1
/* B树的阶，即非根节点中键的最小数目。
}
/*把节点的最右子树转移成新节点的最左子树*/
temp->p[0] = t->p[M+1];
/*在新节点中插入键和右子树*/
temp->k[d-M-1] = InsKey;
temp->p[d-M] = NewTree;
temp->v[d-M-1] = InsValue;
/*设置要插入上层节点的键和值*/
t->p[i+1] = t->p[ i ];
}
/*在节点中插入键和右子树*/
t->k[d] = InsKey;
t->p[d+1] = NewTree;
t->v[d] = InsValue;
/*设置要插入上层节点的键和值*/
InsKey = temp_k;
InsValue = temp_v;
}
}
t->d =M;
static void Error(int,typekey);
int btree_disp; /*查找时找到的键在节点中的位置*/
char * InsValue = NULL; /*与要插的键相对应的值*/
static int flag; /*节点增减标志*/
static int btree_level = 0; /*多路树的高度*/
2。因为B树键位置不定，且在整个树结构中只出现一次，虽然可以节省存储空间，但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中。
3。B树的查询效率与键在树中的位置有关，最大时间复杂度与B+树相同(在叶结点的时候)，最小时间复杂度为1(在根结点的时候)。而B+树的时候复杂度对某建成的树是固定的。
{
int i,j,m;
level--;
if (level < 0){ /*到达了树的底部:指出要做的插入*/
NewTree = NULL; /*这个键没有对应的子树*/
InsKey = key; /*导致底层的叶子节点增加键值+空子树对*/
btree_count++;
flag = 1; /*指示上层节点把返回的键插入其中*/
static int btree_count = 0; /*多路树的键总数*/
static int node_sum = 0; /*多路树的节点总数*/
static int level; /*当前访问的节点所处的高度*/
static btree NewTree; /*在节点分割的时候指向新建的节点*/
/*建立新节点*/
temp = (btree)malloc(sizeof(node));
/*
* +---+--------+-----+-----+--------+-----+
* | 0 | ...... | M | M+1 | ...... |2*M-1|
* +---+--------+-----+-----+--------+-----+
static void InsInNode(btree, int);
static void SplitNode(btree, int);
