这个结构一般用于数据库的索引，综合效率非常高，像 Berkerly DB,sqlite,MysqL 数据库都使用了这个算法处理索引。 @H_301_0@

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

/* @H_301_0@ * 每个键的左子树中的所有的键都小于这个键， @H_301_0@ * 每个键的右子树中的所有的键都大于等于这个键。 @H_301_0@ * 叶子节点中的每个键都没有子树。 @H_301_0@ */ @H_301_0@

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

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

/*******************************************************/ @H_301_0@

/*******************************************************/ @H_301_0@

/* btrees.c */ @H_301_0@ #include @H_301_0@ #include @H_301_0@ #include "btrees.h" @H_301_0@

btree search(typekey,btree); @H_301_0@ btree insert(typekey,btree); @H_301_0@ btree delete(typekey,btree); @H_301_0@ int height(btree); @H_301_0@ int count(btree); @H_301_0@ double payload(btree); @H_301_0@ btree deltree(btree); @H_301_0@

static void InternalInsert(typekey,btree); @H_301_0@ static void InsInNode(btree,int); @H_301_0@ static void SplitNode(btree,int); @H_301_0@ static btree NewRoot(btree); @H_301_0@

static void InternalDelete(typekey,btree); @H_301_0@ static void JoinNode(btree,int); @H_301_0@ static void MoveLeftNode(btree t,int); @H_301_0@ static void MoveRightNode(btree t,int); @H_301_0@ static void DelFromNode(btree t,int); @H_301_0@ static btree FreeRoot(btree); @H_301_0@

static btree delall(btree); @H_301_0@ static void Error(int,typekey); @H_301_0@

int btree_disp; /* 查找时找到的键在节点中的位置 */ @H_301_0@ char * InsValue = NULL; /* 与要插的键相对应的值 */ @H_301_0@ static int flag; /* 节点增减标志 */ @H_301_0@ static int btree_level = 0; /* 多路树的高度 */ @H_301_0@ static int btree_count = 0; /* 多路树的键总数 */ @H_301_0@ static int node_sum = 0; /* 多路树的节点总数 */ @H_301_0@ static int level; /* 当前访问的节点所处的高度 */ @H_301_0@ static btree NewTree; /* 在节点分割的时候指向新建的节点 */ @H_301_0@ static typekey InsKey; /* 要插入的键 */ @H_301_0@

btree search(typekey key,btree t) @H_301_0@ { @H_301_0@ int i,j,m; @H_301_0@ level=btree_level-1; @H_301_0@ while (level >= 0){ @H_301_0@ for(i=0,j=t->d-1; i t->k[m])?(i=m+1):(j=m)); @H_301_0@ if (key == t->k){ @H_301_0@ btree_disp = i; @H_301_0@ return t; @H_301_0@

if (key > t->k) /* i == t->d-1 时有可能出现 */ @H_301_0@ i++; @H_301_0@ t = t->p; @H_301_0@ level--; @H_301_0@ btree insert(typekey key,btree t) @H_301_0@ { @H_301_0@ level=btree_level; @H_301_0@ InternalInsert(key,t); @H_301_0@ if (flag == 1) /* 根节点满之后，它被分割成两个半满节点 */ @H_301_0@ t=NewRoot(t); /* 树的高度增加 */ @H_301_0@ return t; @H_301_0@ void InternalInsert(typekey key,btree t) @H_301_0@ { @H_301_0@ int i,m; @H_301_0@

level--; @H_301_0@ if (level < 0){ /* 到达了树的底部: 指出要做的插入 */ @H_301_0@ NewTree = NULL; /* 这个键没有对应的子树 */ @H_301_0@ InsKey = key; /* 导致底层的叶子节点增加键值+空子树对 */ @H_301_0@ btree_count++; @H_301_0@ flag = 1; /* 指示上层节点把返回的键插入其中 */ @H_301_0@ return; @H_301_0@

for(i=0,j=t->d-1; i t->k[m])?(i=m+1):(j=m)); @H_301_0@ if (key == t->k) { @H_301_0@ Error(1,key); /* 键已经在树中 */ @H_301_0@ flag = 0; @H_301_0@ return; @H_301_0@ if (key > t->k) /* i == t->d-1 时有可能出现 */ @H_301_0@ i++; @H_301_0@ InternalInsert(key,t->p); @H_301_0@

if (flag == 0) @H_301_0@ return; @H_301_0@ /* 有新键要插入到当前节点中 */ @H_301_0@ if (t->d < 2*M) {/* 当前节点未满 */ @H_301_0@ InsInNode(t,i); /* 把键值+子树对插入当前节点中 */ @H_301_0@ flag = 0; /* 指示上层节点没有需要插入的键值+子树，插入过程结束 */ @H_301_0@

else /* 当前节点已满，则分割这个页面并把键值+子树对插入当前节点中 */ @H_301_0@ SplitNode(t,i); /* 继续指示上层节点把返回的键值+子树插入其中 */ @H_301_0@ /* @H_301_0@ * 把一个键和对应的右子树插入一个节点中 @H_301_0@ */ @H_301_0@ void InsInNode(btree t,int d) @H_301_0@ { @H_301_0@ int i; @H_301_0@ /* 把所有大于要插入的键值的键和对应的右子树右移 */ @H_301_0@ for(i = t->d; i > d; i--){ @H_301_0@ t->k = t->k[i-1]; @H_301_0@ t->v = t->v[i-1]; @H_301_0@ t->p[i+1] = t->p; @H_301_0@ /* 插入键和右子树 */ @H_301_0@ t->k = InsKey; @H_301_0@ t->p[i+1] = NewTree; @H_301_0@ t->v = InsValue; @H_301_0@ t->d++; @H_301_0@ /* @H_301_0@ * 前件是要插入一个键和对应的右子树，并且本节点已经满 @H_301_0@ * 导致分割这个节点，插入键和对应的右子树， @H_301_0@ * 并向上层返回一个要插入键和对应的右子树 @H_301_0@ */ @H_301_0@ void SplitNode(btree t,int d) @H_301_0@ { @H_301_0@ int i,j; @H_301_0@ btree temp; @H_301_0@ typekey temp_k; @H_301_0@ char *temp_v; @H_301_0@ /* 建立新节点 */ @H_301_0@ temp = (btree)malloc(sizeof(node)); @H_301_0@ /* @H_301_0@ * +---+--------+-----+-----+--------+-----+ @H_301_0@ * | 0 | ...... | M | M+1 | ...... |2*M-1| @H_301_0@ * +---+--------+-----+-----+--------+-----+ @H_301_0@ * |<- M+1 ->|<- M-1 ->| @H_301_0@ */ @H_301_0@ if (d > M) { /* 要插入当前节点的右半部分 */ @H_301_0@ /* 把从 2*M-1 到 M+1 的 M-1 个键值+子树对转移到新节点中,@H_301_0@ * 并且为要插入的键值+子树空出位置 */ @H_301_0@ for(i=2*M-1,j=M-1; i>=d; i--,j--) { @H_301_0@ temp->k[j] = t->k; @H_301_0@ temp->v[j] = t->v; @H_301_0@ temp->p[j+1] = t->p[i+1]; @H_301_0@ for(i=d-1,j=d-M-2; j>=0; i--,j--) { @H_301_0@ temp->k[j] = t->k; @H_301_0@ temp->v[j] = t->v; @H_301_0@ temp->p[j+1] = t->p[i+1]; @H_301_0@ /* 把节点的最右子树转移成新节点的最左子树 */ @H_301_0@ temp->p[0] = t->p[M+1]; @H_301_0@ /* 在新节点中插入键和右子树 */ @H_301_0@ temp->k[d-M-1] = InsKey; @H_301_0@ temp->p[d-M] = NewTree; @H_301_0@ temp->v[d-M-1] = InsValue; @H_301_0@ /* 设置要插入上层节点的键和值 */ @H_301_0@ InsKey = t->k[M]; @H_301_0@ InsValue = t->v[M]; @H_301_0@ else { /* d <= M */ @H_301_0@ /* 把从 2*M-1 到 M 的 M 个键值+子树对转移到新节点中 */ @H_301_0@ for(i=2*M-1,j=M-1; j>=0; i--,j--) { @H_301_0@ temp->k[j] = t->k; @H_301_0@ temp->v[j] = t->v; @H_301_0@ temp->p[j+1] = t->p[i+1]; @H_301_0@ if (d == M) /* 要插入当前节点的正中间 */ @H_301_0@ /* 把要插入的子树作为新节点的最左子树 */ @H_301_0@ temp->p[0] = NewTree; @H_301_0@ /* 直接把要插入的键和值返回给上层节点 */ @H_301_0@ else { /* (d /* 把节点当前的最右子树转移成新节点的最左子树 */ @H_301_0@ temp->p[0] = t->p[M]; @H_301_0@ /* 保存要插入上层节点的键和值 */ @H_301_0@ temp_k = t->k[M-1]; @H_301_0@ temp_v = t->v[M-1]; @H_301_0@ /* 把所有大于要插入的键值的键和对应的右子树右移 */ @H_301_0@ for(i=M-1; i>d; i--) { @H_301_0@ t->k = t->k[i-1]; @H_301_0@ t->v = t->v[i-1]; @H_301_0@ t->p[i+1] = t->p; @H_301_0@ /* 在节点中插入键和右子树 */ @H_301_0@ t->k[d] = InsKey; @H_301_0@ t->p[d+1] = NewTree; @H_301_0@ t->v[d] = InsValue; @H_301_0@ /* 设置要插入上层节点的键和值 */ @H_301_0@ InsKey = temp_k; @H_301_0@ InsValue = temp_v; @H_301_0@ t->d =M; @H_301_0@ temp->d = M; @H_301_0@ NewTree = temp; @H_301_0@ node_sum++; @H_301_0@ btree delete(typekey key,btree t) @H_301_0@ { @H_301_0@ level=btree_level; @H_301_0@ InternalDelete(key,t); @H_301_0@ if (t->d == 0) @H_301_0@ /* 根节点的子节点合并导致根节点键的数目随之减少， @H_301_0@ * 当根节点中没有键的时候，只有它的最左子树可能非空 */ @H_301_0@ t=FreeRoot(t); @H_301_0@ return t; @H_301_0@ void InternalDelete(typekey key,m; @H_301_0@ btree l,r; @H_301_0@ int lvl; @H_301_0@

level--; @H_301_0@ if (level < 0) { @H_301_0@ Error(0,key); /* 在整个树中未找到要删除的键 */ @H_301_0@ flag = 0; @H_301_0@ return; @H_301_0@

for(i=0,j=t->d-1; i t->k[m])?(i=m+1):(j=m)); @H_301_0@ if (key == t->k) { /* 找到要删除的键 */ @H_301_0@ if (t->v != NULL) @H_301_0@ free(t->v); /* 释放这个节点包含的值 */ @H_301_0@ if (level == 0) { /* 有子树为空则这个键位于叶子节点 */ @H_301_0@ DelFromNode(t,i); @H_301_0@ btree_count--; @H_301_0@ flag = 1; @H_301_0@ /* 指示上层节点本子树的键数量减少 */ @H_301_0@ return; @H_301_0@ lvl = level-1; @H_301_0@ /* 找到前驱节点 */ @H_301_0@ r = t->p; @H_301_0@ while (lvl > 0) { @H_301_0@ r = r->p[r->d]; @H_301_0@ lvl--; @H_301_0@ t->k=r->k[r->d-1]; @H_301_0@ t->v=r->v[r->d-1]; @H_301_0@ r->v[r->d-1]=NULL; @H_301_0@ key = r->k[r->d-1]; @H_301_0@ else if (key > t->k) /* i == t->d-1 时有可能出现 */ @H_301_0@ i++; @H_301_0@ InternalDelete(key,t->p); @H_301_0@ /* 调整平衡 */ @H_301_0@ if (flag == 0) @H_301_0@ return; @H_301_0@ if (t->p->d < M) { @H_301_0@ if (i == t->d) /* 在最右子树中发生了删除 */ @H_301_0@ i--; /* 调整最右键的左右子树平衡 */ @H_301_0@ l = t->p; @H_301_0@ r = t->p[i+1]; @H_301_0@ if (r->d > M) @H_301_0@ MoveLeftNode(t,i); @H_301_0@ else if(l->d > M) @H_301_0@ MoveRightNode(t,i); @H_301_0@ else { @H_301_0@ JoinNode(t,i); @H_301_0@ /* 继续指示上层节点本子树的键数量减少 */ @H_301_0@ return; @H_301_0@ flag = 0; @H_301_0@ /* 指示上层节点本子树的键数量没有减少，删除过程结束 */ @H_301_0@ /* @H_301_0@ * 合并一个节点的某个键对应的两个子树 @H_301_0@ */ @H_301_0@ void JoinNode(btree t,int d) @H_301_0@ { @H_301_0@ btree l,r; @H_301_0@ int i,j; @H_301_0@ l = t->p[d]; @H_301_0@ r = t->p[d+1]; @H_301_0@

/* 把这个键下移到它的左子树 */ @H_301_0@ l->k[l->d] = t->k[d]; @H_301_0@ l->v[l->d] = t->v[d]; @H_301_0@ /* 把右子树中的所有键值和子树转移到左子树 */ @H_301_0@ for (j=r->d-1,i=l->d+r->d; j >= 0 ; j--,i--) { @H_301_0@ l->k = r->k[j]; @H_301_0@ l->v = r->v[j]; @H_301_0@ l->p = r->p[j]; @H_301_0@

l->p[l->d+r->d+1] = r->p[r->d]; @H_301_0@ l->d += r->d+1; @H_301_0@ /* 释放右子树的节点 */ @H_301_0@ free(r); @H_301_0@ /* 把这个键右边的键和对应的右子树左移 */ @H_301_0@ for (i=d; i < t->d-1; i++) { @H_301_0@ t->k = t->k[i+1]; @H_301_0@ t->v = t->v[i+1]; @H_301_0@ t->p[i+1] = t->p[i+2]; @H_301_0@ t->d--; @H_301_0@ node_sum--; @H_301_0@ /* @H_301_0@ * 从一个键的右子树向左子树转移一些键，使两个子树平衡 @H_301_0@ */ @H_301_0@ void MoveLeftNode(btree t,r; @H_301_0@ int m; /* 应转移的键的数目 */ @H_301_0@ int i,j; @H_301_0@ l = t->p[d]; @H_301_0@ r = t->p[d+1]; @H_301_0@ m = (r->d - l->d)/2; @H_301_0@

/* 把这个键下移到它的左子树 */ @H_301_0@ l->k[l->d] = t->k[d]; @H_301_0@ l->v[l->d] = t->v[d]; @H_301_0@ /* 把右子树的最左子树转移成左子树的最右子树 @H_301_0@ * 从右子树向左子树移动 m-1 个键+子树对 */ @H_301_0@ for (j=m-2,i=l->d+m-1; j >= 0; j--,i--) { @H_301_0@ l->k = r->k[j]; @H_301_0@ l->v = r->v[j]; @H_301_0@ l->p = r->p[j]; @H_301_0@

l->p[l->d+m] = r->p[m-1]; @H_301_0@ /* 把右子树的最左键提升到这个键的位置上 */ @H_301_0@ t->k[d] = r->k[m-1]; @H_301_0@ t->v[d] = r->v[m-1]; @H_301_0@ /* 把右子树中的所有键值和子树左移 m 个位置 */ @H_301_0@ r->p[0] = r->p[m]; @H_301_0@ for (i=0; id-m; i++) { @H_301_0@ r->k = r->k[i+m]; @H_301_0@ r->v = r->v[i+m]; @H_301_0@ r->p = r->p[i+m]; @H_301_0@ r->p[r->d-m] = r->p[r->d]; @H_301_0@ l->d+=m; @H_301_0@ r->d-=m; @H_301_0@ /* @H_301_0@ * 从一个键的左子树向右子树转移一些键，使两个子树平衡 @H_301_0@ */ @H_301_0@ void MoveRightNode(btree t,j; @H_301_0@ l = t->p[d]; @H_301_0@ r = t->p[d+1]; @H_301_0@

m = (l->d - r->d)/2; @H_301_0@ /* 把右子树中的所有键值和子树右移 m 个位置 */ @H_301_0@ r->p[r->d+m]=r->p[r->d]; @H_301_0@ for (i=r->d-1; i>=0; i--) { @H_301_0@ r->k[i+m] = r->k; @H_301_0@ r->v[i+m] = r->v; @H_301_0@ r->p[i+m] = r->p; @H_301_0@

/* 把这个键下移到它的右子树 */ @H_301_0@ r->k[m-1] = t->k[d]; @H_301_0@ r->v[m-1] = t->v[d]; @H_301_0@ /* 把左子树的最右子树转移成右子树的最左子树 */ @H_301_0@ r->p[m-1] = l->p[l->d]; @H_301_0@ /* 从左子树向右子树移动 m-1 个键+子树对 */ @H_301_0@ for (i=l->d-1,j=m-2; j>=0; j--,i--) { @H_301_0@ r->k[j] = l->k; @H_301_0@ r->v[j] = l->v; @H_301_0@ r->p[j] = l->p; @H_301_0@ /* 把左子树的最右键提升到这个键的位置上 */ @H_301_0@ t->k[d] = l->k; @H_301_0@ t->v[d] = l->v; @H_301_0@ l->d-=m; @H_301_0@ r->d+=m; @H_301_0@ /* @H_301_0@ * 把一个键和对应的右子树从一个节点中删除 @H_301_0@ */ @H_301_0@ void DelFromNode(btree t,int d) @H_301_0@ { @H_301_0@ int i; @H_301_0@ /* 把所有大于要删除的键值的键左移 */ @H_301_0@ for(i=d; i < t->d-1; i++) { @H_301_0@ t->k = t->k[i+1]; @H_301_0@ t->v = t->v[i+1]; @H_301_0@ /* @H_301_0@ * 建立有两个子树和一个键的根节点 @H_301_0@ */ @H_301_0@ btree NewRoot(btree t) @H_301_0@ { @H_301_0@ btree temp; @H_301_0@ temp = (btree)malloc(sizeof(node)); @H_301_0@ temp->d = 1; @H_301_0@ temp->p[0] = t; @H_301_0@ temp->p[1] = NewTree; @H_301_0@ temp->k[0] = InsKey; @H_301_0@ temp->v[0] = InsValue; @H_301_0@ btree_level++; @H_301_0@ node_sum++; @H_301_0@ return(temp); @H_301_0@ /* @H_301_0@ * 释放根节点，并返回它的最左子树 @H_301_0@ */ @H_301_0@ btree FreeRoot(btree t) @H_301_0@ { @H_301_0@ btree temp; @H_301_0@ temp = t->p[0]; @H_301_0@ free(t); @H_301_0@ btree_level--; @H_301_0@ node_sum--; @H_301_0@ return temp; @H_301_0@ void Error(int f,typekey key) @H_301_0@ { @H_301_0@ if (f) @H_301_0@ printf("Btrees error: Insert %d! ",key); @H_301_0@ else @H_301_0@ printf("Btrees error: delete %d! ",key); @H_301_0@ int height(btree t) @H_301_0@ { @H_301_0@ return btree_level; @H_301_0@ int count(btree t) @H_301_0@ { @H_301_0@ return btree_count; @H_301_0@ double payload(btree t) @H_301_0@ { @H_301_0@ if (node_sum==0) @H_301_0@ return 1; @H_301_0@ return (double)btree_count/(node_sum*(2*M)); @H_301_0@ btree deltree (btree t) @H_301_0@ { @H_301_0@ level=btree_level; @H_301_0@ btree_level = 0; @H_301_0@ return delall(t); @H_301_0@ btree delall(btree t) @H_301_0@ { @H_301_0@ int i; @H_301_0@ level--; @H_301_0@ if (level >= 0) { @H_301_0@ for (i=0; i < t->d; i++) @H_301_0@ if (t->v != NULL) @H_301_0@ free(t->v); @H_301_0@ if (level > 0) @H_301_0@ for (i=0; i<= t->d ; i++) @H_301_0@ t->p=delall(t->p); @H_301_0@ free(t); @H_301_0@ /* end of btrees.c */