B+树代码实现

//by svking

//2012.5

/****************************************************************

B+树的实现。这个 B+树是建立在操作系统的文件系统之上的，并没有自己的文件系

统。

B+树的节点全部存储在一个文件中。由于每个节点的大小是相同的，所以我对每个节点

进 行 编 号 ， 即 每 个 节 点 的 id 。 这 样 每 个 节 点 在 文 件 的 字 节 位 置 就 可 以 通 过 计 算

sizeof(BPNode)*(c->id - 1)得到。

记录打开这个文件时的文件指针

因为这个文件只记录 B+树的节点，所以每次插入的时候只需要直接插入最后（只有

num 个节点，同时新插入的节点的 id 是 num+1）

暂时不考虑删除节点的文件空间回收。

*****************************************************************/

/

*******************************************************************************

************************

打开文件是要注意打开模式，r+模式可以才可以随意用 fseek()定位之后，读或写。

fseek()和 fread()和 fwrite()是用于二进制打开的文件，如果文本模式打开，可能出现问题，

#include <string.h>

#define T 3 //b+树的度数

#define KeyType int

#define Pointer int

//节点结构体

typedef struct BPNode

{

unsigned int id;//记录这个节点在文件的中的编号

unsigned int n;//记录这个节点有多少个关键字

int leaf; //判断是否为页节点

Pointer next;//指针，，记录下一个兄弟

//树的结构体

}BPTree,*P_BPTree;

BPTree indexBPTree; //全局变量，b+树

int writeNode(P_BPNode w)

{

fseek(indexBPTree.fp, sizeof(BPNode)*(w->id - 1) + 2*sizeof(int), SEEK_SET);

fwrite(w, sizeof(BPNode),1,indexBPTree.fp);

return 0;

}

int readNode(P_BPNode r, Pointer id)

{

int createIndexBPTree (char *tableName, char *attr)

{//创建 B+树,并进行相应的初始化，B+树的结构体是一个全局变量。

P_BPNode root;

indexBPTree.root = (P_BPNode)malloc(sizeof(BPNode));

indexBPTree.num = 1;

indexBPTree.start = 1;

memcpy(indexBPTree.name, ".\\table\\", sizeof(".\\table\\"));

strcat(indexBPTree.name, ".");

strcat(indexBPTree.name, attr);

puts(indexBPTree.name);

fwrite(&indexBPTree.locate, sizeof(int),1,indexBPTree.fp);

writeNode(root);

fclose(indexBPTree.fp);

/*

printf("原始：%d\n", indexBPTree.root->next);

memset(indexBPTree.root,0,sizeof(BPNode));

printf("memset 后：%d\n", indexBPTree.root->next);

indexBPTree.fp = fopen(indexBPTree.name,"r");

fread(indexBPTree.root, sizeof(BPNode),1,indexBPTree.fp);

fclose(indexBPTree.fp);

printf("读取文件后：%d\n", indexBPTree.root->next);

*/

free(root);

indexBPTree.root = NULL;

return 0;

{//节点的分裂，要求 p 节点至少还能插入一个节点，c 节点是满的，即 n 为 2*T;

int j;

P_BPNode b;

b = (P_BPNode)malloc(sizeof(BPNode));

b->leaf = c->leaf;

b->n = T;

b->id = indexBPTree.num+1; //为 b 赋值 id 号，用于表示该节点，，同时 id 号就是这个

b->next = c->next; //为 b 的 next 赋值，即原来的 c 节点的 next

//将 c 节点的后半部分关键字复制给 b

for (j = 0; j < T; j++)

{

b->key[j] = c->key[j+T];

//至此 b 节点的对应元素已经建立好了，但还需要写入文件

for (j = p->n - 1; j > i; j--)

{

p->key[j+1] = p->key[j];

}

p->key[i+1] = b->key[0];

p->child[i+1] = b->id;

writeNode(p);

writeNode(c);

writeNode(b);

int insertBPNodeNotFull(P_BPNode s, KeyType k, unsigned int id)

{//插入，要求 s 节点不是满的

int i = s->n-1;

if (s->leaf)

while (i >= 0 && s->key[i] > k)