免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12345下一页
最近访问板块 发新帖
查看: 21758 | 回复: 44

BTREE算法C语言实现 [复制链接]

论坛徽章:
0
发表于 2007-12-07 14:54 |显示全部楼层
由于2001年-2003年间在国家863多媒体数据库管理系统的项目中工作,所以积累了大量的关于数据库底层实现的经验,而恰巧在04年的时候接手了一个非常苛刻的项目,要求每日处理上亿的数据量,需要对数据进行大量的消除重复和排序的工作,而且要求处理结果的实时性,所以埋头苦干了3个月编写了一套BTREE算法的C语言内存实现。

        为什么用BTREE算法的内存实现,大家都知道BTREE算法特别适合用在磁盘索引上,现在普遍使用的数据库管理系统的索引实现基本都是利用BTREE和BTREE+,经过我们的测试和理论分析,实际在使用BTREE的过程中的内存开销是比较小的,这是符合我们的需要的。

[ 本帖最后由 ldap 于 2007-12-7 16:09 编辑 ]

论坛徽章:
0
发表于 2007-12-07 14:55 |显示全部楼层

回复 #1 ldap 的帖子

32位Key值的带索引项的Btree实现头文件utils_btree32_i.h

/*
 *  utils_btree32_i.h
 *
 *  Author    shixuliang 2004-07-24
 *  Copyright 2004-2006,shixuliang
 *
 *  Email:shixuliang2008@yahoo.com.cn
 *  Msn:  shixl@neusoft.com
 *
 */


#ifndef __UTILS_BTREE32_I_H
#define __UTILS_BTREE32_I_H

#include "utils.h"
#include "utils_btree.h"

/* 2 <= BNODE32_I_MAX  <= 32767 it must is even */

#define BNODE32_I_MAX 252
&nbsp;
typedef struct bnode32_i
{
&nbsp;&nbsp;&nbsp;&nbsp;int16                num;
&nbsp;&nbsp;&nbsp;&nbsp;int16                pos;
&nbsp;&nbsp;&nbsp;&nbsp;int32                key[BNODE32_I_MAX];
&nbsp;&nbsp;&nbsp;&nbsp;void                *index[BNODE32_I_MAX];
&nbsp;&nbsp;&nbsp;&nbsp;struct bnode32_i    *parent;
&nbsp;&nbsp;&nbsp;&nbsp;struct bnode32_i    *child[BNODE32_I_MAX + 1];
}bnode32_i;

#define BNODE32_I_ROOT_SIZE   \
&nbsp;&nbsp;&nbsp;&nbsp;sizeof(bnode32_i)

#define BNODE32_I_LEAF_SIZE   \
&nbsp;&nbsp;&nbsp;&nbsp;(sizeof(bnode32_i) - sizeof(bnode32_i*) * BNODE32_I_MAX)

#define BNODE32_I_ROOT        0
#define BNODE32_I_LEAF        1

extern bnode32_i&nbsp;&nbsp;&nbsp;&nbsp;*create_bnode32_i(int16 type);
extern bnode32_i&nbsp;&nbsp;&nbsp;&nbsp;*search_btree32_i(bnode32_i *node, int32 key, bool *found, int16 *pos);
extern void        insert_btree32_i(bnode32_i *node, void *index, int32 key, int16 pos);
extern void        init_btree32_i_walker(walker *cc);
extern bnode32_i  *walker_btree32_i(bnode32_i *node, int16 pos, void **index, int32 *key, walker *cc);
extern void        free_btree32_i(bnode32_i *node);
extern bnode32_i  *root_btree32_i(bnode32_i *node);

#endif

论坛徽章:
0
发表于 2007-12-07 14:57 |显示全部楼层

回复 #1 ldap 的帖子

32位Key值的带索引项的Btree实现utils_btree32_i.c

/*
&nbsp;*  utils_btree32_i.c
&nbsp;*
&nbsp;*  Author    shixuliang 2004-07-24
&nbsp;*  Copyright 2004-2006,shixuliang
&nbsp;*
&nbsp;*  Email:shixuliang2008@yahoo.com.cn
&nbsp;*  Msn:  shixl@neusoft.com
&nbsp;*
&nbsp;*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include "utils.h"
#include "utils_btree.h"
#include "utils_btree32_i.h"
#include "utils_bin.h"


bnode32_i *create_bnode32_i(int16 type)
{
&nbsp;&nbsp;&nbsp;&nbsp;bnode32_i *node = NULL;

&nbsp;&nbsp;&nbsp;&nbsp;if (type == BNODE32_I_ROOT) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;node = (bnode32_i *)btree_malloc(BNODE32_I_ROOT_SIZE);
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;else if (type == BNODE32_I_LEAF) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;node = (bnode32_i *)btree_malloc(BNODE32_I_LEAF_SIZE);
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;else {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Assert(0);
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;node->num    = 0;
&nbsp;&nbsp;&nbsp;&nbsp;node->pos    = 0;
&nbsp;&nbsp;&nbsp;&nbsp;node->parent = NULL;
&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;if (type == BNODE32_I_ROOT) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;memset((void *)&node->child, (int)NULL, sizeof(node->child));
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;else if (type == BNODE32_I_LEAF) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;node->child[0] = NULL;
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;return node;
}

论坛徽章:
0
发表于 2007-12-07 14:58 |显示全部楼层

回复 #3 ldap 的帖子

bnode32_i *search_btree32_i(bnode32_i *node, int32 key, bool *found, int16 *pos)
{
&nbsp;&nbsp;&nbsp;&nbsp;ENTRY_FUNCTION("search_btree32_i", search_btree32_i);

&nbsp;&nbsp;&nbsp;&nbsp;Assert(node != NULL);
&nbsp;&nbsp;&nbsp;&nbsp;Assert(found != NULL);
&nbsp;&nbsp;&nbsp;&nbsp;Assert(pos != NULL);

start:
&nbsp;&nbsp;&nbsp;&nbsp;if (bin_search32(node->key, key, node->num - 1, pos)) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/* find the key in the current node */
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*found = true;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return node;
&nbsp;&nbsp;&nbsp;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;if (node->child[0] == NULL) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; * current node is leaf node,
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; * search to leaf node no found
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; * the key
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; */

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*found = false;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return node;
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;/* search child node */
&nbsp;&nbsp;&nbsp;&nbsp;node = node->child[*pos];
&nbsp;&nbsp;&nbsp;&nbsp;goto start;
}

论坛徽章:
3
金牛座
日期:2013-10-12 15:42:452015年辞旧岁徽章
日期:2015-03-03 16:54:15IT运维版块每日发帖之星
日期:2016-06-01 06:20:00
发表于 2007-12-07 15:00 |显示全部楼层
呵呵,楼主在寻找知己。

论坛徽章:
0
发表于 2007-12-07 15:00 |显示全部楼层

回复 #4 ldap 的帖子

static void insert_none32_i(bnode32_i *node, bnode32_i *new,
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bnode32_i *son, void *index, int32 key, int16 pos)
{
&nbsp;&nbsp;&nbsp;&nbsp;int16 i;

&nbsp;&nbsp;&nbsp;&nbsp;Assert(node != NULL);
&nbsp;&nbsp;&nbsp;&nbsp;Assert(pos >= 0);

&nbsp;&nbsp;&nbsp;&nbsp;if (node->num > pos) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;btree_memcpy(&(node->key[pos + 1]), &(node->key[pos]),
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(node->num - pos) * sizeof(int32));

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;btree_memcpy(&(node->index[pos + 1]), &(node->index[pos]),
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(node->num - pos) * sizeof(void*));

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (node->child[0] != NULL) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/* none leaf node */
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;btree_memcpy(&(node->child[pos + 2]), &(node->child[pos + 1]),
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(node->num - pos) * sizeof(bnode32_i*));
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(i = 2; i < node->num - pos + 2; i++)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;node->child[i + pos]->pos = i + pos;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;node->key[pos] = key;
&nbsp;&nbsp;&nbsp;&nbsp;node->index[pos] = index;

&nbsp;&nbsp;&nbsp;&nbsp;if (node->child[0] != NULL) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;son->parent = node;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;node->child[pos + 1] = son;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;son->pos = pos + 1;
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;node->num++;
}

static void insert_middle32_i(bnode32_i *node, bnode32_i *new,
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bnode32_i *son, void *index, void **upindex, int32 key, int32 *upkey, int16 pos)
{
&nbsp;&nbsp;&nbsp;&nbsp;int16 i, m = BNODE32_I_MAX/2;

&nbsp;&nbsp;&nbsp;&nbsp;Assert(node != NULL);
&nbsp;&nbsp;&nbsp;&nbsp;Assert(new != NULL);
&nbsp;&nbsp;&nbsp;&nbsp;Assert(upkey != NULL);
&nbsp;&nbsp;&nbsp;&nbsp;Assert(upindex != NULL);
&nbsp;&nbsp;&nbsp;&nbsp;Assert(pos >= 0);

&nbsp;&nbsp;&nbsp;&nbsp;btree_memcpy(&(new->key[0]), &(node->key[m]), m * sizeof(int32));
&nbsp;&nbsp;&nbsp;&nbsp;btree_memcpy(&(new->index[0]), &(node->index[m]), m * sizeof(void*));

&nbsp;&nbsp;&nbsp;&nbsp;if (node->child[0] != NULL) {

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/* none leaf node */

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;son->parent = new;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new->child[0] = son;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;son->pos = 0;

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;btree_memcpy(&(new->child[1]), &(node->child[m + 1]),
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m * sizeof(bnode32_i*));

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(i = 0; i < m; i++) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new->child[i + 1]->parent = new;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new->child[i + 1]->pos = i + 1;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;node->num = m;
&nbsp;&nbsp;&nbsp;&nbsp;new->num = m;

&nbsp;&nbsp;&nbsp;&nbsp;*upkey = key;
&nbsp;&nbsp;&nbsp;&nbsp;*upindex = index;
}

论坛徽章:
0
发表于 2007-12-07 15:02 |显示全部楼层
这经历够强了  进来学习

论坛徽章:
0
发表于 2007-12-07 15:02 |显示全部楼层

回复 #6 ldap 的帖子

static void insert_left32_i(bnode32_i *node, bnode32_i *new,
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bnode32_i *son, void *index, void **upindex, int32 key, int32 *upkey, int16 pos)
{
&nbsp;&nbsp;&nbsp;&nbsp;int16 i, m = BNODE32_I_MAX/2;
&nbsp;&nbsp;&nbsp;&nbsp;int32 ckey;
&nbsp;&nbsp;&nbsp;&nbsp;void  *cindex;

&nbsp;&nbsp;&nbsp;&nbsp;Assert(node != NULL);
&nbsp;&nbsp;&nbsp;&nbsp;Assert(new != NULL);
&nbsp;&nbsp;&nbsp;&nbsp;Assert(upkey != NULL);
&nbsp;&nbsp;&nbsp;&nbsp;Assert(upindex != NULL);
&nbsp;&nbsp;&nbsp;&nbsp;Assert(pos >= 0);

&nbsp;&nbsp;&nbsp;&nbsp;btree_memcpy(&(new->key[0]), &(node->key[m]), m * sizeof(int32));
&nbsp;&nbsp;&nbsp;&nbsp;btree_memcpy(&(new->index[0]), &(node->index[m]), m * sizeof(void*));
&nbsp;&nbsp;&nbsp;&nbsp;if (node->child[0] != NULL) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;btree_memcpy(&(new->child[0]), &(node->child[m]),
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(m + 1) * sizeof(bnode32_i*));

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(i = 0; i < m + 1; i++) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new->child[i]->pos = i;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new->child[i]->parent = new;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;ckey = node->key[m - 1];
&nbsp;&nbsp;&nbsp;&nbsp;cindex = node->index[m - 1];

&nbsp;&nbsp;&nbsp;&nbsp;if (m > pos + 1) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;btree_memcpy(&(node->key[pos + 1]), &(node->key[pos]),
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(m - (pos + 1)) * sizeof(int32));
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;btree_memcpy(&(node->index[pos + 1]), &(node->index[pos]),
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(m - (pos + 1)) * sizeof(void*));

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (node->child[0] != NULL) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;btree_memcpy(&(node->child[pos + 2]), &(node->child[pos + 1]),
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(m - (pos + 1)) * sizeof(bnode32_i*));

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(i = 0; i < m - (pos + 1); i++) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;node->child[i + pos + 2]->pos = i + pos + 2;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;node->key[pos] = key;
&nbsp;&nbsp;&nbsp;&nbsp;node->index[pos] = index;

&nbsp;&nbsp;&nbsp;&nbsp;if (node->child[0] != NULL) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;node->child[pos + 1] = son;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;son->pos = pos + 1;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;son->parent = node;
&nbsp;&nbsp;&nbsp;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;node->num = m;
&nbsp;&nbsp;&nbsp;&nbsp;new->num = m;

&nbsp;&nbsp;&nbsp;&nbsp;*upkey = ckey;
&nbsp;&nbsp;&nbsp;&nbsp;*upindex = cindex;
}

论坛徽章:
0
发表于 2007-12-07 15:03 |显示全部楼层

回复 #8 ldap 的帖子

static void insert_right32_i(bnode32_i *node, bnode32_i *new,
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bnode32_i *son, void *index, void **upindex, int32 key, int32 *upkey, int16 pos)
{
&nbsp;&nbsp;&nbsp;&nbsp;int16 i, m = BNODE32_I_MAX/2;

&nbsp;&nbsp;&nbsp;&nbsp;Assert(node != NULL);
&nbsp;&nbsp;&nbsp;&nbsp;Assert(new != NULL);
&nbsp;&nbsp;&nbsp;&nbsp;Assert(upkey != NULL);
&nbsp;&nbsp;&nbsp;&nbsp;Assert(upindex != NULL);
&nbsp;&nbsp;&nbsp;&nbsp;Assert(pos >= 0);

&nbsp;&nbsp;&nbsp;&nbsp;if (pos > m + 1) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;btree_memcpy(&(new->key[0]), &(node->key[m + 1]), (pos - (m + 1)) * sizeof(int32));
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;btree_memcpy(&(new->index[0]), &(node->index[m + 1]), (pos - (m + 1)) * sizeof(void*));
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (node->child[0] != NULL) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;btree_memcpy(&(new->child[0]), &(node->child[m + 1]),
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(pos - (m + 1)) * sizeof(bnode32_i*));

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(i = 0; i < pos - (m + 1); i++) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new->child[i]->pos = i;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new->child[i]->parent = new;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;new->key[pos - (m + 1)] = key;
&nbsp;&nbsp;&nbsp;&nbsp;new->index[pos - (m + 1)] = index;

&nbsp;&nbsp;&nbsp;&nbsp;if (node->child[0] != NULL) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new->child[pos - (m + 1)] = node->child[pos];
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new->child[pos - (m + 1)]->pos = pos - (m + 1);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new->child[pos - (m + 1)]->parent = new;

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new->child[pos - m] = son;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;son->pos = pos - m;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;son->parent = new;
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;if (pos < node->num) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;btree_memcpy(&(new->key[pos - m]), &(node->key[pos]),
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(node->num - pos) * sizeof(int32));
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;btree_memcpy(&(new->index[pos - m]), &(node->index[pos]),
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(node->num - pos) * sizeof(void*));

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (node->child[0] != NULL) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;btree_memcpy(&(new->child[pos - m + 1]), &(node->child[pos + 1]),
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(node->num - pos) * sizeof(bnode32_i*));

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(i = 0; i < node->num - pos; i++) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new->child[i + pos - m + 1]->pos = i + pos - m + 1;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new->child[i + pos - m + 1]->parent = new;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;node->num = m;
&nbsp;&nbsp;&nbsp;&nbsp;new->num = m;

&nbsp;&nbsp;&nbsp;&nbsp;*upkey = node->key[m];
&nbsp;&nbsp;&nbsp;&nbsp;*upindex = node->index[m];
}

论坛徽章:
0
发表于 2007-12-07 15:04 |显示全部楼层

回复 #9 ldap 的帖子

void insert_btree32_i(bnode32_i *node, void *index, int32 key, int16 pos)
{
&nbsp;&nbsp;&nbsp;&nbsp;bnode32_i *son = NULL;
&nbsp;&nbsp;&nbsp;&nbsp;bnode32_i *new = NULL;
&nbsp;&nbsp;&nbsp;&nbsp;int16       m = BNODE32_I_MAX/2;

&nbsp;&nbsp;&nbsp;&nbsp;Assert(node != NULL);
&nbsp;&nbsp;&nbsp;&nbsp;Assert(pos >= 0);

start:
&nbsp;&nbsp;&nbsp;&nbsp;/* insert the ip without divide */
&nbsp;&nbsp;&nbsp;&nbsp;if (node->num != BNODE32_I_MAX) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;insert_none32_i(node, new, son, index, key, pos);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return;
&nbsp;&nbsp;&nbsp;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;/* insert the ip with divide */

&nbsp;&nbsp;&nbsp;&nbsp;if (node->parent == NULL) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/* create new root node */
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;node->parent = create_bnode32_i(BNODE32_I_ROOT);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;node->parent->child[0] = node;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;node->pos = 0;
&nbsp;&nbsp;&nbsp;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;/* create new divide node */
&nbsp;&nbsp;&nbsp;&nbsp;if (node->child[0] == NULL) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new = create_bnode32_i(BNODE32_I_LEAF);
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;else {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new = create_bnode32_i(BNODE32_I_ROOT);
&nbsp;&nbsp;&nbsp;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;/* insert middle and divide */
&nbsp;&nbsp;&nbsp;&nbsp;if (pos == m) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;insert_middle32_i(node, new, son, index, &index, key, &key, pos);
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;/* insert left and divide */
&nbsp;&nbsp;&nbsp;&nbsp;if (pos < m) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;insert_left32_i(node, new, son, index, &index, key, &key, pos);
&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;/* insert right and divide */
&nbsp;&nbsp;&nbsp;&nbsp;if (pos > m) {
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;insert_right32_i(node, new, son, index, &index, key, &key, pos);
&nbsp;&nbsp;&nbsp;&nbsp;}

&nbsp;&nbsp;&nbsp;&nbsp;pos  = node->pos;
&nbsp;&nbsp;&nbsp;&nbsp;node = node->parent;
&nbsp;&nbsp;&nbsp;&nbsp;son  = new;
&nbsp;&nbsp;&nbsp;&nbsp;goto start;
}
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP