jwp@sdchema.UUCP (John Pierce) (10/22/84)
In response to the 30 or so requests, here is the code for B and B+ trees
I mentioned on the net. I claim no credit for it; I did not write it and I
no longer remember who did (I'm not even certain I ever did know). I also
have never gotten around to running it to see if it works. I would like to
know if it works, or of any fixes needed to make it work, but I'm in no
position at the moment to spend any time working on it.
John Pierce, Chemistry, UC San Diego
{sdcsvax,decvax}!sdchema!jwp
------------------------------- cut here -----------------------------------
# This is a shell archive. Remove anything before this line, then
# unpack it by saving it in a file and typing "sh file". (Files
# unpacked will be owned by you and have default permissions.)
#
# This archive contains:
# README B+_tree.c B+_tree_dsk.c B_tree.c B_tree_dsk.c
echo x - README
cat > "README" << '//E*O*F README//'
15Oct84
The enclosed code claims to do search, insert, and delete operations on B and
B+ trees. It was given to me (third hand) by a friend several years ago to
use in a database application I was working on. Unfortunately, that project
got shoved well down on the stack shortly thereafter [another brilliant idea
fallen victim to the exigencies of keeping machines running, doing what users
think they want rather than what they really need, etc, etc], and I've never
taken the time to see whether or not this stuff really works. As nearly as I
remember, I believe I was told that it was written by a CS grad student (long
since departed) for the Prof he was working for, primarily as an exercise in
turning a known Pascal implementation into C. The coding style certainly does
nothing to belie that memory.
If it does work, or if it doesn't and you fix it, I would certainly appreciate
hearing about it. Good luck.
John Pierce, Chemistry, UC San Diego
{decvax,sdcsvax}!sdchema!jwp
//E*O*F README//
echo x - B+_tree.c
cat > "B+_tree.c" << '//E*O*F B+_tree.c//'
/* B+ tree search, insertion and delation */
#define N 2
#define NN 4 /* index page size */
#define L 2
#define LL 4 /* data page size */
#define NULL 0
#define LEAF 0
#define INDEX 1
typedef struct page {
int page_type;
union {
struct {
int m;
struct page *p0;
struct {
int key;
struct page *p;
} e[1+NN];
} indexp;
struct {
int k;
struct {
int key;
int count;
} d[1+LL];
} leafp;
} type;
} PAGE, *REF;
typedef struct item {
int key;
struct page *p;
} ITEM;
typedef struct info {
int key;
int count;
} INFO;
REF root;
main()
{
REF q, leaf;
int x, h;
ITEM u;
char *new();
scanf("%d", &x);
root = (REF)new(sizeof(*root));
root->page_type = INDEX;
root->type.indexp.m = 1;
root->type.indexp.p0 = leaf = (REF)new(sizeof(*leaf));
leaf->page_type = LEAF;
leaf->type.leafp.k = 0;
root->type.indexp.e[1].key = x;
root->type.indexp.e[1].p = leaf = (REF)new(sizeof(*leaf));
leaf->page_type = LEAF;
leaf->type.leafp.d[1].key = x;
leaf->type.leafp.k = 1;
leaf->type.leafp.d[1].count = 0;
while(x != 0){
printf("search key %d\n", x);
search(x, root, &h, &u);
if (h){ /* insert new base page */
q = root;
root = (REF)new(sizeof(*root));
root->page_type = INDEX;
root->type.indexp.m = 1;
root->type.indexp.p0 = q;
root->type.indexp.e[1].key = u.key;
root->type.indexp.e[1].p = u.p;
}
printtree(root, 1);
scanf("%d", &x);
}
scanf("%d", &x);
while(x != 0){
printf("delete key %d\n", x);
delete(x, root, &h);
if(h){ /* base page size was reduced */
if(root->type.indexp.m == 0){
q = root;
root = q->type.indexp.p0;
}
}
printtree(root, 1);
scanf("%d", &x);
}
}
char *new(n)
unsigned int n;
{
char *p, *malloc();
if((p=malloc(n))==NULL){ /* no space available */
printf("no space at all\n");
exit(1);
}
else
return(p);
}
search(x, a, h, v) /* Search key x on B_tree with root a; if found,
increment counter, otherwise insert an item with
key x and count 1 in tree. If an item emerges to
be passed to a lower level, then assign it to v,
h = "tree a has become higher" */
int x;
REF a;
int *h;
ITEM *v;
{
int k, l, r;
REF q;
ITEM u;
INFO z;
char *new();
/* search for key x on page *a; h = false */
if(a->page_type == LEAF){
l = 1;
r = a->type.leafp.k;
while(r >= l){ /* binary array search */
k = (l+r)/2;
if(x <= a->type.leafp.d[k].key)
r = k-1;
if(x >= a->type.leafp.d[k].key)
l = k+1;
};
if(l-r > 1){ /* found */
a->type.leafp.d[k].count += 1;
*h = 0;
}
else {
z.key = x;
z.count = 1;
insertl(a, r, h, v, &z);
}
}
else{
l = 1;
r = a->type.indexp.m;
while(r >= l) { /* binary array search */
k = (l+r)/2;
if(x <= a->type.indexp.e[k].key)
r = k-1;
if(x >= a->type.indexp.e[k].key)
l = k+1;
};
if(l-r > 1 ){ /* found */
q = a->type.indexp.e[k].p;
search(x, q, h, &u);
}
else{ /* item is not in this page */
if(r == 0)
q = a->type.indexp.p0;
else
q = a->type.indexp.e[r].p;
search(x, q, h, &u);
if(*h){ /* an item u is being passed up */
inserti(a, r, h, v, &u);
}
}
}
}
insertl(a, r, h, v, z)
REF a;
int r, *h;
ITEM *v;
INFO *z;
{
/* insert u to the right of a->e[r] */
int i, count;
REF b;
char *new();
if(a->type.leafp.k < LL){ /* insert z on page *a. h = false */
a->type.leafp.k += 1;
*h = 0;
for(i=a->type.leafp.k; i >= r+2; i--){
a->type.leafp.d[i].key = a->type.leafp.d[i-1].key;
a->type.leafp.d[i].count = a->type.leafp.d[i-1].count;
}
a->type.leafp.d[r+1].key = z->key;
a->type.leafp.d[r+1].count = z->count;
}
else{ /* page *a is full; split it and assign the emerging item to v */
*h = 1;
b = (REF)new(sizeof(*b));
b->page_type = LEAF;
if(r <= L){
if(r == L){
v->key = z->key;
count = 1;
}
else{
v->key = a->type.leafp.d[L].key;
count = a->type.leafp.d[L].count;
for(i=L; i >= r+2; i--){
a->type.leafp.d[i].key = a->type.leafp.d[i-1].key;
a->type.leafp.d[i].count = a->type.leafp.d[i-1].count;
}
a->type.leafp.d[r+1].key = z->key;
a->type.leafp.d[r+1].count = z->count;
}
b->type.leafp.d[1].key = v->key;
b->type.leafp.d[1].count = 1;
for(i=1; i <= L; i++){
b->type.leafp.d[i+1].key = a->type.leafp.d[i+L].key;
b->type.leafp.d[i+1].count = a->type.leafp.d[i+L].count;
}
}
else{ /* insert u in right page */
r = r-L+1;
v->key = a->type.leafp.d[L+1].key;
for(i=1; i <= r-1; i++){
b->type.leafp.d[i].key = a->type.leafp.d[L+i].key;
b->type.leafp.d[i].count = a->type.leafp.d[L+i].count;
}
b->type.leafp.d[r].key = z->key;
b->type.leafp.d[r].count = z->count;
for(i= r+1; i <= L+1; i++){
b->type.leafp.d[i].key = a->type.leafp.d[i+L-1].key;
b->type.leafp.d[i].count = a->type.leafp.d[i+L-1].count;
}
}
a->type.leafp.k = L;
b->type.leafp.k = L+1;
v->p = b;
}
}
inserti(a, r, h, v, u)
REF a;
int r, *h;
ITEM *v, *u;
{
/* insert u to the right of a->e[r] */
int i;
REF b;
char *new();
if(a->type.indexp.m < NN){ /* insert u on page *a. h = false */
a->type.indexp.m += 1;
*h = 0;
for(i=a->type.indexp.m; i >= r+2; i--){
a->type.indexp.e[i].key = a->type.indexp.e[i-1].key;
a->type.indexp.e[i].p = a->type.indexp.e[i-1].p;
}
a->type.indexp.e[r+1].key = u->key;
a->type.indexp.e[r+1].p = u->p;
}
else{ /* page *a is full; split it and assign the emerging item to v */
b = (REF)new(sizeof(*b));
b->page_type = INDEX;
if(r <= N){
if(r == N){
v->key = u->key;
v->p = u->p;
}
else{
v->key = a->type.indexp.e[N].key;
v->p = a->type.indexp.e[N].p;
for(i=N; i >= r+2; i--){
a->type.indexp.e[i].key = a->type.indexp.e[i-1].key;
a->type.indexp.e[i].p = a->type.indexp.e[i-1].p;
}
a->type.indexp.e[r+1].key = u->key;
a->type.indexp.e[r+1].p = u->p;
}
for(i=1; i <= N; i++){
b->type.indexp.e[i].key = a->type.indexp.e[i+N].key;
b->type.indexp.e[i].p = a->type.indexp.e[i+N].p;
}
}
else{ /* insert u in right page */
r = r-N;
v->key = a->type.indexp.e[N+1].key;
v->p = a->type.indexp.e[N+1].p;
for(i=1; i <= r-1; i++){
b->type.indexp.e[i].key = a->type.indexp.e[N+i+1].key;
b->type.indexp.e[i].p = a->type.indexp.e[N+i+1].p;
}
b->type.indexp.e[r].key = u->key;
b->type.indexp.e[r].p = u->p;
for(i= r+1; i <= N; i++){
b->type.indexp.e[i].key = a->type.indexp.e[i+N].key;
b->type.indexp.e[i].p = a->type.indexp.e[i+N].p;
}
}
a->type.indexp.m = N;
b->type.indexp.m = N;
b->type.indexp.p0 = v->p;
v->p = b;
}
}
delete(x, a, h) /* search and delete key x in b_tree a; if a page
underflow is necessary, balance with adjacant
page if possible, otherwise merge; h = "page a
is undersiize" */
int x;
REF a;
int *h;
{
int i, k, l, r;
REF q;
if(a->page_type == LEAF) {
l = 1;
r = a->type.leafp.k;
while(r >= l) { /* binary array search */
k = (l+r)/2;
if(x <= a->type.leafp.d[k].key)
r = k-1;
if(x >= a->type.leafp.d[k].key)
l = k+1;
};
if(l-r > 1) { /* found */
a->type.leafp.k -= 1; /* delete key from leaf page */
*h = a->type.leafp.k < L; /* set h if underflow */
for(i=k; i <= a->type.leafp.k; i++){
a->type.leafp.d[i].key = a->type.leafp.d[i+1].key;
a->type.leafp.d[i].count = a->type.leafp.d[i+1].count;
}
}
else {
printf("key is not in tree\n");
*h = 0;
}
}
else{
l = 1;
r = a->type.indexp.m;
do { /* binary array search */
k = (l+r)/2;
if(x <= a->type.indexp.e[k].key)
r = k-1;
if(x >= a->type.indexp.e[k].key)
l = k+1;
} while(r >= l);
if(l-r > 1){ /* found, now delete e[k] */
q = a->type.indexp.e[k].p;
delete(x, q, h);
if(*h)
underflow(a, q, k, h);
}
else {
if(r == 0)
q = a->type.indexp.p0;
else
q = a->type.indexp.e[r].p;
delete(x, q, h);
if(*h)
underflow(a, q, r, h);
}
}
}
underflow(c, a, s, h) /* a = underflow page, c = ancestor page */
REF c, a;
int s, *h;
{
REF b;
int i, k, mb, mc;
if(c == root && c->type.indexp.m == 1 && a->page_type == LEAF)
return; /* only root left in index */
if(a->page_type == LEAF) {
mc = c->type.indexp.m; /* h = true, a->m = N-1 */
if(s < mc) { /* b = page to the right of a */
s += 1;
b = c->type.indexp.e[s].p;
mb = b->type.leafp.k;
k = (mb-L+1)/2; /* k = no. of items available on adjacant page b */
if(k > 0) { /* move k items from b to a */
for(i=1; i<= k; i++) {
a->type.leafp.d[i+L-1].key = b->type.leafp.d[i].key;
a->type.leafp.d[i+L-1].count = b->type.leafp.d[i].count;
}
c->type.indexp.e[s].key = b->type.leafp.d[k+1].key;
mb -= k;
for(i=1; i<=mb; i++) {
b->type.leafp.d[i].key = b->type.leafp.d[i+k].key;
b->type.leafp.d[i].count = b->type.leafp.d[i+k].count;
}
b->type.leafp.k = mb;
a->type.leafp.k = L-1+k;
*h = 0;
}
else { /* merge pages a and b */
for(i=1; i<=L; i++) {
a->type.leafp.d[i+L-1].key = b->type.leafp.d[i].key;
a->type.leafp.d[i+L-1].count = b->type.leafp.d[i].count;
}
for(i=s; i<= mc-1; i++){
c->type.indexp.e[i].key = c->type.indexp.e[i+1].key;
c->type.indexp.e[i].p = c->type.indexp.e[i+1].p;
}
a->type.leafp.k = LL-1;
c->type.indexp.m = mc-1;
*h = c->type.indexp.m < N;
/* if(c == root) b->type.leafp.k = 0 else dispose(b) */
}
}
else { /* b = page to the left of a */
if(s == 1)
b = c->type.indexp.p0;
else
b = c->type.indexp.e[s-1].p;
mb = b->type.leafp.k;
k = (mb-L+1)/2;
if(k>0) { /* move k items from page b to a */
for(i=L-1; i>=1; i--) {
a->type.leafp.d[i+k].key = a->type.leafp.d[i].key;
a->type.leafp.d[i+k].count = a->type.leafp.d[i].count;
}
mb = mb - k;
for(i=k; i>=1; i--) {
a->type.leafp.d[i].key = b->type.leafp.d[i+mb].key;
a->type.leafp.d[i].count = b->type.leafp.d[i+mb].count;
}
c->type.indexp.e[s].key = a->type.leafp.d[1].key;
b->type.leafp.k = mb;
a->type.leafp.k = L-1+k;
*h = 0;
}
else { /* merge pages a and b */
for(i=1; i<=L-1; i++) {
b->type.leafp.d[i+mb].key = a->type.leafp.d[i].key;
b->type.leafp.d[i+mb].count = a->type.leafp.d[i].count;
}
b->type.leafp.k = LL-1;
c->type.indexp.m = mc-1;
*h = c->type.indexp.m < N;
/* if(c == root) a-type.leafp.k = 0 else dispose a */
}
}
}
else { /* index pages */
mc = c->type.indexp.m; /* h = true, a->m = N-1 */
if(s < mc) { /* b = page to the right of a */
s += 1;
b = c->type.indexp.e[s].p;
mb = b->type.indexp.m;
k = (mb-N+1)/2; /* k = no. of items available on adjacant page b */
a->type.indexp.e[N].key = c->type.indexp.e[s].key;
a->type.indexp.e[N].p = b->type.indexp.p0;
if(k > 0) { /* move k items from b to a */
for(i=1; i<= k-1; i++) {
a->type.indexp.e[i+N].key = b->type.indexp.e[i].key;
a->type.indexp.e[i+N].p = b->type.indexp.e[i].p;
}
c->type.indexp.e[s].key = b->type.indexp.e[k].key;
b->type.indexp.p0 = b->type.indexp.e[k].p;
mb -= k;
for(i=1; i<=mb; i++) {
b->type.indexp.e[i].key = b->type.indexp.e[i+k].key;
b->type.indexp.e[i].p = b->type.indexp.e[i+k].p;
}
b->type.indexp.m = mb;
a->type.indexp.m = N-1+k;
*h = 0;
}
else { /* merge pages a and b */
for(i=1; i<=N; i++) {
a->type.indexp.e[i+N].key = b->type.indexp.e[i].key;
a->type.indexp.e[i+N].p = b->type.indexp.e[i].p;
}
for(i=s; i<= mc-1; i++){
c->type.indexp.e[i].key = c->type.indexp.e[i+1].key;
c->type.indexp.e[i].p = c->type.indexp.e[i+1].p;
}
a->type.indexp.m = NN;
c->type.indexp.m = mc-1; /* dispose(b) */
*h = c->type.indexp.m < N;
}
}
else { /* b = page to the left of a */
if(s == 1)
b = c->type.indexp.p0;
else
b = c->type.indexp.e[s-1].p;
mb = b->type.indexp.m + 1;
k = (mb-N)/2;
if(k>0) { /* move k items from page b to a */
for(i=N-1; i>=1; i--) {
a->type.indexp.e[i+k].key = a->type.indexp.e[i].key;
a->type.indexp.e[i+k].p = a->type.indexp.e[i].p;
}
a->type.indexp.e[k].key = c->type.indexp.e[s].key;
a->type.indexp.e[k].p = a->type.indexp.p0;
mb = mb - k;
for(i=k-1; i>=1; i--) {
a->type.indexp.e[i].key = b->type.indexp.e[i+mb].key;
a->type.indexp.e[i].p = b->type.indexp.e[i+mb].p;
}
a->type.indexp.p0 = b->type.indexp.e[mb].p;
c->type.indexp.e[s].key = b->type.indexp.e[mb].key;
b->type.indexp.m = mb-1;
a->type.indexp.m = N-1+k;
*h = 0;
}
else { /* merge pages a and b */
b->type.indexp.e[mb].key = c->type.indexp.e[s].key;
b->type.indexp.e[mb].p = a->type.indexp.p0;
for(i=1; i<=N-1; i++) {
b->type.indexp.e[i+mb].key = a->type.indexp.e[i].key;
b->type.indexp.e[i+mb].p = a->type.indexp.e[i].p;
}
b->type.indexp.m = NN;
c->type.indexp.m = mc-1; /* dispose a */
*h = c->type.indexp.m < N;
}
}
}
}
printtree(p, l)
REF p;
int l;
{
int i;
if(p->page_type != LEAF){
for(i=1; i<=l; i++)
printf(" ");
for(i=1; i<=p->type.indexp.m; i++)
printf("%4d", p->type.indexp.e[i].key);
printf("\n");
printtree(p->type.indexp.p0, l+1);
for(i=1; i<=p->type.indexp.m; i++)
printtree(p->type.indexp.e[i].p, l+1);
}
else{
for(i=1; i<=l; i++)
printf(" ");
for(i=1; i<=p->type.leafp.k; i++)
printf("%4d", p->type.leafp.d[i].key);
printf("\n");
}
}
//E*O*F B+_tree.c//
echo x - B+_tree_dsk.c
cat > "B+_tree_dsk.c" << '//E*O*F B+_tree_dsk.c//'
/* B+ tree search, insertion and delation */
#define N 63
#define NN 126 /* index page size */
#define L 2
#define LL 4 /* data page size */
#define NIL -1
#define LEAF 0
#define INDEX 1
#include <stdio.h>
typedef char ALIGN;
typedef union page {
struct {
int page_type;
long int my_offset;
union {
struct {
int m;
long int p0;
struct {
int key;
long int p;
} e[NN];
} indexp;
struct {
int k;
struct {
int key;
int count;
} d[LL];
} leafp;
} type;
};
ALIGN x[1024];
} PAGE;
typedef struct item {
int key;
long int p;
} INDX;
typedef struct info {
int key;
int count;
} ITEM;
PAGE *root;
long int rootoffset;
PAGE *fetchp();
long int insertp(), pnew();
main()
{
PAGE *leaf;
int x, h, fd1, hight, count;
PAGE bufi, bufp;
INDX u;
FILE *fp;
fd1 = creat("b+tree.pag", 0644);
close(fd1);
dbminitf();
fp = fopen("B+_tree.dat", "w");
hight = 1; /* hight of tree */
count = 1; /* no. of keys */
scanf("%d", &x);
root = &bufi;
root->page_type = INDEX;
root->type.indexp.m = 1;
root->type.indexp.e[0].key = x;
leaf = &bufp;
leaf->page_type = LEAF;
leaf->type.leafp.k = 0;
root->type.indexp.p0 = insertp(leaf, pnew());
leaf->type.leafp.d[0].key = x;
leaf->type.leafp.d[0].count = 0;
leaf->type.leafp.k = 1;
root->type.indexp.e[0].p = insertp(leaf, pnew());
root->my_offset = rootoffset = pnew();
insertp(root, rootoffset);
scanf("%d", &x);
while(x != 0){
/* printf("search key %d\n", x); */
search(x, root, &h, &u);
if (h){ /* insert new base page */
root->page_type = INDEX;
root->type.indexp.m = 1;
root->type.indexp.p0 = rootoffset;
root->type.indexp.e[0].key = u.key;
root->type.indexp.e[0].p = u.p;
root->my_offset = rootoffset = pnew();
insertp(root, rootoffset);
hight += 1;
}
/* printtree(root, 1); */
count += 1;
scanf("%d", &x);
}
fprintf(fp, "dskB+_tree: no. of keys is: %d\n", count);
fprintf(fp, "dskB+_tree: tree hight is: %d\n", hight);
scanf("%d", &x);
while(x != 0){
/* printf("delete key %d\n", x); */
delete(x, root, &h);
if(h){ /* base page size was reduced */
if(root->type.indexp.m == 0){
deletep(root->my_offset);
rootoffset = root->type.indexp.p0;
root = fetchp(&bufi, root->type.indexp.p0);
}
}
/* printtree(root, 1); */
scanf("%d", &x);
}
}
search(x, a, h, v) /* Search key x on B_tree with root a; if found,
increment counter, otherwise insert an item with
key x and count 1 in tree. If an item emerges to
be passed to a lower level, then assign it to v,
h = "tree a has become higher" */
int x;
PAGE *a;
int *h;
INDX *v;
{
int k, l, r;
PAGE buf, *q;
INDX u;
ITEM z;
/* search for key x on page *a; h = false */
if(a->page_type == LEAF){
l = 0;
r = a->type.leafp.k-1;
while(r >= l){ /* binary array search */
k = (l+r)/2;
if(x <= a->type.leafp.d[k].key)
r = k-1;
if(x >= a->type.leafp.d[k].key)
l = k+1;
};
if(l-r > 1){ /* found */
a->type.leafp.d[k].count += 1;
*h = 0;
insertp(a, a->my_offset);
printf("b+_tree: key %d is allready in file\n", x);
}
else {
z.key = x;
z.count = 1;
insertl(a, r, h, v, &z);
insertp(a, a->my_offset);
}
}
else{
l = 0;
r = a->type.indexp.m-1;
while(r >= l) { /* binary array search */
k = (l+r)/2;
if(x <= a->type.indexp.e[k].key)
r = k-1;
if(x >= a->type.indexp.e[k].key)
l = k+1;
};
if(l-r > 1 ){ /* found */
q = fetchp(&buf, a->type.indexp.e[k].p);
search(x, q, h, &u);
}
else{ /* item is not in this page */
if(r == -1)
q = fetchp(&buf, a->type.indexp.p0);
else
q = fetchp(&buf, a->type.indexp.e[r].p);
search(x, q, h, &u);
if(*h){ /* an item u is being passed up */
inserti(a, r, h, v, &u);
insertp(a, a->my_offset);
}
}
}
}
insertl(a, r, h, v, z)
PAGE *a;
int r, *h;
INDX *v;
ITEM *z;
{
/* insert u to the right of a->e[r] */
int i, count;
PAGE buf, *b;
if(a->type.leafp.k < LL){ /* insert z on page *a. h = false */
a->type.leafp.k += 1;
*h = 0;
for(i=a->type.leafp.k-1; i >= r+2; i--){
a->type.leafp.d[i].key = a->type.leafp.d[i-1].key;
a->type.leafp.d[i].count = a->type.leafp.d[i-1].count;
}
a->type.leafp.d[r+1].key = z->key;
a->type.leafp.d[r+1].count = z->count;
}
else{ /* page *a is full; split it and assign the emerging item to v */
*h = 1;
b = &buf;
b->page_type = LEAF;
if(r <= L-1){
if(r == L-1){
v->key = z->key;
count = 1;
}
else{
v->key = a->type.leafp.d[L-1].key;
count = a->type.leafp.d[L-1].count;
for(i=L-1; i >= r+2; i--){
a->type.leafp.d[i].key = a->type.leafp.d[i-1].key;
a->type.leafp.d[i].count = a->type.leafp.d[i-1].count;
}
a->type.leafp.d[r+1].key = z->key;
a->type.leafp.d[r+1].count = z->count;
}
b->type.leafp.d[0].key = v->key;
b->type.leafp.d[0].count = 1;
for(i=0; i <= L-1; i++){
b->type.leafp.d[i+1].key = a->type.leafp.d[i+L].key;
b->type.leafp.d[i+1].count = a->type.leafp.d[i+L].count;
}
}
else{ /* insert u in right page */
r = r-L+1;
v->key = a->type.leafp.d[L].key;
for(i=0; i <= r-1; i++){
b->type.leafp.d[i].key = a->type.leafp.d[L+i].key;
b->type.leafp.d[i].count = a->type.leafp.d[L+i].count;
}
b->type.leafp.d[r].key = z->key;
b->type.leafp.d[r].count = z->count;
for(i= r+1; i <= L; i++){
b->type.leafp.d[i].key = a->type.leafp.d[L+i-1].key;
b->type.leafp.d[i].count = a->type.leafp.d[L+i-1].count;
}
}
a->type.leafp.k = L;
b->type.leafp.k = L+1;
v->p = insertp(b, pnew());
}
}
inserti(a, r, h, v, u)
PAGE *a;
int r, *h;
INDX *v, *u;
{
/* insert u to the right of a->e[r] */
int i;
PAGE buf, *b;
if(a->type.indexp.m < NN){ /* insert u on page *a. h = false */
a->type.indexp.m += 1;
*h = 0;
for(i=a->type.indexp.m-1; i >= r+2; i--){
a->type.indexp.e[i].key = a->type.indexp.e[i-1].key;
a->type.indexp.e[i].p = a->type.indexp.e[i-1].p;
}
a->type.indexp.e[r+1].key = u->key;
a->type.indexp.e[r+1].p = u->p;
}
else{ /* page *a is full; split it and assign the emerging item to v */
b = &buf;
b->page_type = INDEX;
if(r <= N-1){
if(r == N-1){
v->key = u->key;
v->p = u->p;
}
else{
v->key = a->type.indexp.e[N].key;
v->p = a->type.indexp.e[N].p;
for(i=N-1; i >= r+2; i--){
a->type.indexp.e[i].key = a->type.indexp.e[i-1].key;
a->type.indexp.e[i].p = a->type.indexp.e[i-1].p;
}
a->type.indexp.e[r+1].key = u->key;
a->type.indexp.e[r+1].p = u->p;
}
for(i=0; i <= N-1; i++){
b->type.indexp.e[i].key = a->type.indexp.e[i+N].key;
b->type.indexp.e[i].p = a->type.indexp.e[i+N].p;
}
}
else{ /* insert u in right page */
r = r-N;
v->key = a->type.indexp.e[N].key;
v->p = a->type.indexp.e[N].p;
for(i=0; i <= r-1; i++){
b->type.indexp.e[i].key = a->type.indexp.e[N+i+1].key;
b->type.indexp.e[i].p = a->type.indexp.e[N+i+1].p;
}
b->type.indexp.e[r].key = u->key;
b->type.indexp.e[r].p = u->p;
for(i= r+1; i <= N-1; i++){
b->type.indexp.e[i].key = a->type.indexp.e[N+i].key;
b->type.indexp.e[i].p = a->type.indexp.e[N+i].p;
}
}
a->type.indexp.m = N;
b->type.indexp.m = N;
b->type.indexp.p0 = v->p;
v->p = insertp(b, pnew());
}
}
delete(x, a, h) /* search and delete key x in b_tree a; if a page
underflow is necessary, balance with adjacant
page if possible, otherwise merge; h = "page a
is undersiize" */
int x;
PAGE *a;
int *h;
{
int i, k, l, r;
PAGE buf, *q;
if(a->page_type == LEAF) {
l = 0;
r = a->type.leafp.k-1;
while(r >= l) { /* binary array search */
k = (l+r)/2;
if(x <= a->type.leafp.d[k].key)
r = k-1;
if(x >= a->type.leafp.d[k].key)
l = k+1;
};
if(l-r > 1) { /* found */
a->type.leafp.k -= 1; /* delete key from leaf page */
*h = a->type.leafp.k < L; /* set h if underflow */
for(i=k; i <= a->type.leafp.k-1; i++){
a->type.leafp.d[i].key = a->type.leafp.d[i+1].key;
a->type.leafp.d[i].count = a->type.leafp.d[i+1].count;
}
insertp(a, a->my_offset);
}
else {
printf("key is not in tree\n");
*h = 0;
}
}
else{
l = 0;
r = a->type.indexp.m-1;
do { /* binary array search */
k = (l+r)/2;
if(x <= a->type.indexp.e[k].key)
r = k-1;
if(x >= a->type.indexp.e[k].key)
l = k+1;
} while(r >= l);
if(l-r > 1){ /* found, now delete e[k] */
q = fetchp(&buf, a->type.indexp.e[k].p);
delete(x, q, h);
if(*h)
underflow(a, q, k, h);
}
else {
if(r == -1)
q = fetchp(&buf, a->type.indexp.p0);
else
q = fetchp(&buf, a->type.indexp.e[r].p);
delete(x, q, h);
if(*h)
underflow(a, q, r, h);
}
}
}
underflow(c, a, s, h) /* a = underflow page, c = ancestor page */
PAGE *c, *a;
int s, *h;
{
PAGE buf, *b;
int i, k, mb, mc;
if(c == root && c->type.indexp.m == 1 && a->page_type == LEAF)
return; /* only root left in index */
if(a->page_type == LEAF) {
mc = c->type.indexp.m; /* h = true, a->m = L-1 */
if(s < mc-1) { /* b = page to the right of a */
s += 1;
b = fetchp(&buf, c->type.indexp.e[s].p);
mb = b->type.leafp.k;
k = (mb-L+1)/2; /* k = no. of items available on adjacant page b */
if(k > 0) { /* move k items from b to a */
for(i=0; i<= k-1; i++) {
a->type.leafp.d[i+L-1].key = b->type.leafp.d[i].key;
a->type.leafp.d[i+L-1].count = b->type.leafp.d[i].count;
}
c->type.indexp.e[s].key = b->type.leafp.d[k].key;
mb -= k;
for(i=0; i<=mb-1; i++) {
b->type.leafp.d[i].key = b->type.leafp.d[i+k].key;
b->type.leafp.d[i].count = b->type.leafp.d[i+k].count;
}
b->type.leafp.k = mb;
a->type.leafp.k = L-1+k;
insertp(b, b->my_offset);
*h = 0;
}
else { /* merge pages a and b */
for(i=0; i<=L-1; i++) {
a->type.leafp.d[i+L-1].key = b->type.leafp.d[i].key;
a->type.leafp.d[i+L-1].count = b->type.leafp.d[i].count;
}
for(i=s; i<= mc-2; i++){
c->type.indexp.e[i].key = c->type.indexp.e[i+1].key;
c->type.indexp.e[i].p = c->type.indexp.e[i+1].p;
}
a->type.leafp.k = LL-1;
c->type.indexp.m = mc-1;
*h = c->type.indexp.m < N;
/* if(c == root) then b->type.leafp.k = 0 else dispose(b) */
if(c == root)
b->type.leafp.k = 0;
else
deletep(b->my_offset);
}
insertp(a, a->my_offset);
insertp(c, c->my_offset);
}
else { /* b = page to the left of a */
if(s == 0)
b = fetchp(&buf, c->type.indexp.p0);
else
b = fetchp(&buf, c->type.indexp.e[s-1].p);
mb = b->type.leafp.k;
k = (mb-L+1)/2;
if(k>0) { /* move k items from page b to a */
for(i=L-2; i>=0; i--) {
a->type.leafp.d[i+k].key = a->type.leafp.d[i].key;
a->type.leafp.d[i+k].count = a->type.leafp.d[i].count;
}
mb -= k;
for(i=k-1; i>=0; i--) {
a->type.leafp.d[i].key = b->type.leafp.d[i+mb].key;
a->type.leafp.d[i].count = b->type.leafp.d[i+mb].count;
}
c->type.indexp.e[s].key = a->type.leafp.d[0].key;
b->type.leafp.k = mb;
a->type.leafp.k = L-1+k;
insertp(a, a->my_offset);
*h = 0;
}
else { /* merge pages a and b */
for(i=0; i<=L-2; i++) {
b->type.leafp.d[i+mb].key = a->type.leafp.d[i].key;
b->type.leafp.d[i+mb].count = a->type.leafp.d[i].count;
}
b->type.leafp.k = LL-1;
c->type.indexp.m = mc-1;
*h = c->type.indexp.m < N;
/* if(c == root) a-type.leafp.k = 0 else dispose a */
if(c == root)
a->type.leafp.k = 0;
else
deletep(a->my_offset);
}
insertp(b, b->my_offset);
insertp(c, c->my_offset);
}
}
else { /* index pages */
mc = c->type.indexp.m; /* h = true, a->m = N-1 */
if(s < mc-1) { /* b = page to the right of a */
s += 1;
b = fetchp(&buf, c->type.indexp.e[s].p);
mb = b->type.indexp.m;
k = (mb-N+1)/2; /* k = no. of items available on adjacant page b */
a->type.indexp.e[N-1].key = c->type.indexp.e[s].key;
a->type.indexp.e[N-1].p = b->type.indexp.p0;
if(k > 0) { /* move k items from b to a */
for(i=0; i<= k-2; i++) {
a->type.indexp.e[i+N].key = b->type.indexp.e[i].key;
a->type.indexp.e[i+N].p = b->type.indexp.e[i].p;
}
c->type.indexp.e[s].key = b->type.indexp.e[k-1].key;
b->type.indexp.p0 = b->type.indexp.e[k-1].p;
mb -= k;
for(i=0; i<=mb-1; i++) {
b->type.indexp.e[i].key = b->type.indexp.e[i+k].key;
b->type.indexp.e[i].p = b->type.indexp.e[i+k].p;
}
b->type.indexp.m = mb;
a->type.indexp.m = N-1+k;
insertp(b, b->my_offset);
*h = 0;
}
else { /* merge pages a and b */
for(i=0; i<=N-1; i++) {
a->type.indexp.e[i+N].key = b->type.indexp.e[i].key;
a->type.indexp.e[i+N].p = b->type.indexp.e[i].p;
}
for(i=s; i<= mc-1; i++){
c->type.indexp.e[i].key = c->type.indexp.e[i+1].key;
c->type.indexp.e[i].p = c->type.indexp.e[i+1].p;
}
a->type.indexp.m = NN;
c->type.indexp.m = mc-1;
*h = c->type.indexp.m < N;
deletep(b->my_offset); /* dispose(b) */
}
insertp(a, a->my_offset);
insertp(c, c->my_offset);
}
else { /* b = page to the left of a */
if(s == 0)
b = fetchp(&buf, c->type.indexp.p0);
else
b = fetchp(&buf, c->type.indexp.e[s-1].p);
mb = b->type.indexp.m + 1;
k = (mb-N)/2;
if(k>0) { /* move k items from page b to a */
for(i=N-2; i>=0; i--) {
a->type.indexp.e[i+k].key = a->type.indexp.e[i].key;
a->type.indexp.e[i+k].p = a->type.indexp.e[i].p;
}
a->type.indexp.e[k-1].key = c->type.indexp.e[s].key;
a->type.indexp.e[k-1].p = a->type.indexp.p0;
mb = mb - k;
for(i=k-2; i>=0; i--) {
a->type.indexp.e[i].key = b->type.indexp.e[i+mb].key;
a->type.indexp.e[i].p = b->type.indexp.e[i+mb].p;
}
a->type.indexp.p0 = b->type.indexp.e[mb-1].p;
c->type.indexp.e[s].key = b->type.indexp.e[mb-1].key;
b->type.indexp.m = mb-1;
a->type.indexp.m = N-1+k;
insertp(a, a->my_offset);
*h = 0;
}
else { /* merge pages a and b */
b->type.indexp.e[mb-1].key = c->type.indexp.e[s].key;
b->type.indexp.e[mb-1].p = a->type.indexp.p0;
for(i=0; i<=N-2; i++) {
b->type.indexp.e[i+mb].key = a->type.indexp.e[i].key;
b->type.indexp.e[i+mb].p = a->type.indexp.e[i].p;
}
b->type.indexp.m = NN;
c->type.indexp.m = mc-1; /* dispose a */
*h = c->type.indexp.m < N;
deletep(a->my_offset);
}
insertp(b, b->my_offset);
insertp(c, c->my_offset);
}
}
}
/* printtree(p, l)
PAGE *p;
int l;
{
int i;
PAGE buf, *u;
if(p->page_type != LEAF){
for(i=1; i<=l; i++)
printf(" ");
for(i=0; i<=p->type.indexp.m-1; i++)
printf("%6d", p->type.indexp.e[i].key);
printf("\n");
u = fetchp(&buf, p->type.indexp.p0);
printtree(u, l+1);
for(i=0; i<=p->type.indexp.m-1; i++) {
u = fetchp(&buf, p->type.indexp.e[i].p);
printtree(u, l+1);
}
}
else{
for(i=1; i<=l; i++)
printf(" ");
for(i=0; i<=p->type.leafp.k-1; i++) {
printf("%6d", p->type.leafp.d[i].key);
}
printf("\n");
}
} */
static long int headp, filesize;
static int fd1, fd2;
static PAGE *u, p;
dbminitf()
{
int i;
long int offset;
if((fd1=open("b+tree.pag", 2)) == -1)
error("dbminit: can't open btree.pag");
headp = -1;
filesize = 0;
}
long int pnew()
{
long int temp;
if(headp == -1) {
temp = filesize;
filesize += sizeof(PAGE);
}
else{
temp = headp;
lseek(fd1, headp, 0);
u = &p;
read(fd1, (char *)u, sizeof(PAGE));
headp = p.type.indexp.p0;
}
return(temp);
}
deletep(offset)
long int offset;
{
u = &p;
p.type.indexp.p0 = headp;
p.my_offset = offset;
headp = offset;
lseek(fd1, offset, 0);
if(write(fd1, (char *)u, sizeof(PAGE)) != sizeof(PAGE))
error("delete: write error");
}
PAGE *fetchp(p, offset)
PAGE *p;
long int offset;
{
if(offset == NIL)
return((PAGE *)NIL);
lseek(fd1, offset, 0);
if(read(fd1, (char *)p, sizeof(PAGE)) != sizeof(PAGE))
error("fetch: read error");
return(p);
}
long int insertp(p, offset)
PAGE *p;
long int offset;
{
p->my_offset = offset;
lseek(fd1, offset, 0);
if(write(fd1, (char *)p, sizeof(PAGE)) != sizeof(PAGE))
error("insert: write error");
return(offset);
}
error(s)
char *s;
{
printf("%s\n", s);
exit(1);
}
//E*O*F B+_tree_dsk.c//
echo x - B_tree.c
cat > "B_tree.c" << '//E*O*F B_tree.c//'
/* B tree search, insertion and delation */
#define N 2
#define NN 4 /* page size */
#define NULL 0
struct page {
int m;
struct page *p0;
struct {
int key;
struct page *p;
int count;
} e[1+NN];
};
struct item {
int key;
struct page *p;
int count;
};
typedef struct page *REF;
typedef struct item ITEM;
main()
{
REF root, q;
int x, h;
ITEM u;
char *cp, *malloc();
root = NULL;
scanf("%d", &x);
while(x != 0){
printf("search key %d\n", x);
search(x, root, &h, &u);
if (h){ /* insert new base page */
q = root;
cp = malloc(sizeof(*root));
if (cp == NULL){ /* no space available */
printf("no space at all\n");
exit();
}
root = (REF)cp;
root->m = 1;
root->p0 = q;
root->e[1].key = u.key;
root->e[1].p = u.p;
root->e[1].count = u.count;
}
printtree(root, 1);
scanf("%d", &x);
}
scanf("%d", &x);
while(x != 0){
printf("delete key %d\n", x);
delete(x, root, &h);
if(h){ /* base page size was reduced */
if(root->m == 0){
q = root;
root = q->p0;
/* despose (q) */
}
}
printtree(root, 1);
scanf("%d", &x);
}
}
search(x, a, h, v) /* Search key x on B_tree with root a; if found,
increment counter, otherwise insert an item with
key x and count 1 in tree. If an item emerges to
be passed to a lower level, then assign it to v,
h = "tree a has become higher" */
int x;
REF a;
int *h;
ITEM *v;
{
int k, l, r;
REF q;
ITEM u;
/* search for key x on page *a; h = false */
if(a == NULL ){ /* item with key x is not in tree */
*h = 1;
v->key = x;
v->count = 1;
v->p = NULL;
}
else{
l = 1;
r = a->m;
do{ /* binary array search */
k = (l+r)/2;
if(x <= a->e[k].key)
r = k-1;
if(x >= a->e[k].key)
l = k+1;
}while(r >= l);
if(l-r > 1 ){ /* found */
a->e[k].count += 1;
*h = 0;
}
else{ /* item is not in this page */
if(r == 0)
q = a->p0;
else
q = a->e[r].p;
search(x, q, h, &u);
if(*h)
insert(a, r, h, v, &u);
}
}
}
insert(a, r, h, v, u)
REF a;
int r, *h;
ITEM *v, *u;
{
/* insert u to the right of a->e[r] */
int i;
REF b;
char *cp, *malloc();
if(a->m < NN){
a->m += 1;
*h = 0;
for(i=a->m; i >= r+2; i--){
a->e[i].key = a->e[i-1].key;
a->e[i].p = a->e[i-1].p;
a->e[i].count = a->e[i-1].count;
}
a->e[r+1].key = u->key;
a->e[r+1].p = u->p;
a->e[r+1].count = u->count;
}
else{ /* page *a is full; split it and assign the emerging item to v */
cp = malloc(sizeof(*b));
if (cp == NULL){ /* no space available */
printf("no space at all\n");
exit();
}
b = (REF)cp;
if(r <= N){
if(r == N){
v->key = u->key;
v->p = u->p;
v->count = u->count;
}
else{
v->key = a->e[N].key;
v->p = a->e[N].p;
v->count = a->e[N].count;
for(i=N; i >= r+2; i--){
a->e[i].key = a->e[i-1].key;
a->e[i].p = a->e[i-1].p;
a->e[i].count = a->e[i-1].count;
}
a->e[r+1].key = u->key;
a->e[r+1].p = u->p;
a->e[r+1].count = u->count;
}
for(i=1; i <= N; i++){
b->e[i].key = a->e[i+N].key;
b->e[i].p = a->e[i+N].p;
b->e[i].count = a->e[i+N].count;
}
}
else{ /* insert u in right page */
r = r-N;
v->key = a->e[N+1].key;
v->p = a->e[N+1].p;
v->count = a->e[N+1].count;
for(i=1; i <= r-1; i++){
b->e[i].key = a->e[N+i+1].key;
b->e[i].p = a->e[N+i+1].p;
b->e[i].count = a->e[N+i+1].count;
}
b->e[r].key = u->key;
b->e[r].p = u->p;
b->e[r].count = u->count;
for(i= r+1; i <= N; i++){
b->e[i].key = a->e[i+N].key;
b->e[i].p = a->e[i+N].p;
b->e[i].count = a->e[i+N].count;
}
}
a->m = N;
b->m = N;
b->p0 = v->p;
v->p = b;
}
}
delete(x, a, h) /* search and delete key x in b_tree a; if a page
underflow is necessary, balance with adjacant
page if possible, otherwise merge; h = "page a
is undersiize" */
int x;
REF a;
int *h;
{
int i, k, l, r;
REF q;
if(a == NULL){
printf("key is not in tree\n");
*h = 0;
}
else{
l = 1;
r = a->m;
do { /* binary array search */
k = (l+r)/2;
if(x <= a->e[k].key)
r = k-1;
if(x >= a->e[k].key)
l = k+1;
} while(r >= l);
if(r == 0)
q = a->p0;
else
q = a->e[r].p;
if(l-r > 1){ /* found, now delete e[k] */
if(q == NULL){ /* a is leaf page */
a->m -= 1;
*h = a->m < N;
for(i = k; i <= a->m; i++){
a->e[i].key = a->e[i+1].key;
a->e[i].p = a->e[i+1].p;
a->e[i].count = a->e[i+1].count;
}
}
else {
del(q, h, a, k);
if(*h)
underflow(a, q, r, h);
}
}
else {
delete(x, q, h);
if(*h)
underflow(a, q, r, h);
}
}
}
del(p, h, a, k)
REF p;
int *h;
REF a;
int k;
{
REF q;
q = p->e[p->m].p;
if(q != NULL){
del(q, h, a, k);
if(*h)
underflow(p, q, p->m, h);
}
else {
a->e[k].key = p->e[p->m].key;
a->e[k].count = p->e[p->m].count;
p->m -= 1;
*h = p->m < N;
}
}
underflow(c, a, s, h) /* a = underflow page, c = ancestor page */
REF c, a;
int s, *h;
{
REF b;
int i, k, mb, mc;
mc = c->m; /* h = true, a->m = N-1 */
if(s < mc) { /* b = page to the right of a */
s += 1;
b = c->e[s].p;
mb = b->m;
k = (mb-N+1)/2; /* k = no. of items available on adjacant page b */
a->e[N].key = c->e[s].key;
a->e[N].count = c->e[s].count;
a->e[N].p = b->p0;
if(k > 0) { /* move k items from b to a */
for(i=1; i<= k-1; i++) {
a->e[i+N].key = b->e[i].key;
a->e[i+N].count = b->e[i].count;
a->e[i+N].p = b->e[i].p;
}
c->e[s].key = b->e[k].key;
c->e[s].count = b->e[k].count;
c->e[s].p = b;
b->p0 = b->e[k].p;
mb -= k;
for(i=1; i<=mb; i++) {
b->e[i].key = b->e[i+k].key;
b->e[i].count = b->e[i+k].count;
b->e[i].p = b->e[i+k].p;
}
b->m = mb;
a->m = N-1+k;
*h = 0;
}
else { /* merge pages a and b */
for(i=1; i<=N; i++) {
a->e[i+N].key = b->e[i].key;
a->e[i+N].count = b->e[i].count;
a->e[i+N].p = b->e[i].p;
}
for(i=s; i<= mc-1; i++){
c->e[i].key = c->e[i+1].key;
c->e[i].count = c->e[i+1].count;
c->e[i].p = c->e[i+1].p;
}
a->m = NN;
c->m = mc-1; /* dispose(b) */
*h = c->m < N;
}
}
else { /* b = page to the left of a */
if(s == 1)
b = c->p0;
else
b = c->e[s-1].p;
mb = b->m + 1;
k = (mb-N)/2;
if(k>0) { /* move k items from page b to a */
for(i=N-1; i>=1; i--) {
a->e[i+k].key = a->e[i].key;
a->e[i+k].count = a->e[i].count;
a->e[i+k].p = a->e[i].p;
}
a->e[k].key = c->e[s].key;
a->e[k].count = c->e[s].count;
a->e[k].p = a->p0;
mb = mb - k;
for(i=k-1; i>=1; i--) {
a->e[i].key = b->e[i+mb].key;
a->e[i].count = b->e[i+mb].count;
a->e[i].p = b->e[i+mb].p;
}
a->p0 = b->e[mb].p;
c->e[s].key = b->e[mb].key;
c->e[s].count = b->e[mb].count;
c->e[s].p = a;
b->m = mb-1;
a->m = N-1+k;
*h = 0;
}
else { /* merge pages a and b */
b->e[mb].key = c->e[s].key;
b->e[mb].count = c->e[s].count;
b->e[mb].p = a->p0;
for(i=1; i<=N-1; i++) {
b->e[i+mb].key = a->e[i].key;
b->e[i+mb].count = a->e[i].count;
b->e[i+mb].p = a->e[i].p;
}
b->m = NN;
c->m = mc-1; /* dispose a */
*h = c->m < N;
}
}
}
printtree(p, l)
REF p;
int l;
{
int i;
if(p != NULL){
for(i=1; i<=l; i++)
printf(" ");
for(i=1; i<=p->m; i++)
printf("%4d", p->e[i].key);
printf("\n");
printtree(p->p0, l+1);
for(i=1; i<=p->m; i++)
printtree(p->e[i].p, l+1);
}
}
//E*O*F B_tree.c//
echo x - B_tree_dsk.c
cat > "B_tree_dsk.c" << '//E*O*F B_tree_dsk.c//'
/* B tree search, insertion and delation */
#define NULL -1
#define N 41
#define NN 82 /* page size */
typedef char ALIGN;
typedef union page {
struct {
int m;
long int p0;
struct {
int key;
long int p;
int count;
} e[1+NN];
};
ALIGN x[1024];
} PAGE, *REF;
struct item {
int key;
long int p;
int count;
};
typedef struct item ITEM;
PAGE *fetchp();
long int insertp(), pnew();
main()
{
REF root;
int x, h, fd1, fd2;
ITEM u;
PAGE p;
long int root_offset;
fd1 = creat("btree.pag", 0644);
close(fd1);
dbminitf();
root = (REF)NULL;
root_offset = -1;
scanf("%d", &x);
while(x != 0){
/* printf("search key %d\n", x); */
search(x, root, &h, &u);
if (h){ /* insert new base page */
root = &p;
p.m = 1;
p.p0 = root_offset;
p.e[1].key = u.key;
p.e[1].p = u.p;
p.e[1].count = u.count;
root_offset = root->e[0].p = pnew();
insertp(&p, root_offset);
}
/* printtree(root, 1); */
scanf("%d", &x);
}
root = fetchp(&p, root_offset);
scanf("%d", &x);
while(x != 0){
/* printf("delete key %d\n", x); */
deletekey(x, root, &h);
if(h){ /* base page size was reduced */
if(root->m == 0){
deletep(root->e[0].p);
root_offset = root->p0;
root = fetchp(&p, root->p0);
}
}
/* printtree(root, 1); */
scanf("%d", &x);
}
}
search(x, a, h, v) /* Search key x on B_tree with root a; if found,
increment counter, otherwise insert an item with
key x and count 1 in tree. If an item emerges to
be passed to a lower level, then assign it to v,
h = "tree a has become higher" */
int x;
REF a;
int *h;
ITEM *v;
{
int k, l, r;
ITEM u;
PAGE buf, *q;
/* search for key x on page *a; h = false */
if(a == (REF)NULL ){ /* item with key x is not in tree */
*h = 1;
v->key = x;
v->count = 1;
v->p = NULL;
}
else{
l = 1;
r = a->m;
do{ /* binary array search */
k = (l+r)/2;
if(x <= a->e[k].key)
r = k-1;
if(x >= a->e[k].key)
l = k+1;
}while(r >= l);
if(l-r > 1 ){ /* found */
a->e[k].count += 1;
*h = 0;
insertp(a, a->e[0].p);
}
else{ /* item is not in this page */
if(r == 0)
q = fetchp(&buf, a->p0);
else
q = fetchp(&buf, a->e[r].p);
search(x, q, h, &u);
if(*h) {
insertkey(a, r, h, v, &u);
insertp(a, a->e[0].p);
}
}
}
}
insertkey(a, r, h, v, u)
REF a;
int r, *h;
ITEM *v, *u;
{
/* insert u to the right of a->e[r] */
int i;
PAGE b;
if(a->m < NN){
a->m += 1;
*h = 0;
for(i=a->m; i >= r+2; i--){
a->e[i].key = a->e[i-1].key;
a->e[i].p = a->e[i-1].p;
a->e[i].count = a->e[i-1].count;
}
a->e[r+1].key = u->key;
a->e[r+1].p = u->p;
a->e[r+1].count = u->count;
}
else{ /* page *a is full; split it and assign the emerging item to v */
if(r <= N){
if(r == N){
v->key = u->key;
v->p = u->p;
v->count = u->count;
}
else{
v->key = a->e[N].key;
v->p = a->e[N].p;
v->count = a->e[N].count;
for(i=N; i >= r+2; i--){
a->e[i].key = a->e[i-1].key;
a->e[i].p = a->e[i-1].p;
a->e[i].count = a->e[i-1].count;
}
a->e[r+1].key = u->key;
a->e[r+1].p = u->p;
a->e[r+1].count = u->count;
}
for(i=1; i <= N; i++){
b.e[i].key = a->e[i+N].key;
b.e[i].p = a->e[i+N].p;
b.e[i].count = a->e[i+N].count;
}
}
else{ /* insert u in right page */
r = r-N;
v->key = a->e[N+1].key;
v->p = a->e[N+1].p;
v->count = a->e[N+1].count;
for(i=1; i <= r-1; i++){
b.e[i].key = a->e[N+i+1].key;
b.e[i].p = a->e[N+i+1].p;
b.e[i].count = a->e[N+i+1].count;
}
b.e[r].key = u->key;
b.e[r].p = u->p;
b.e[r].count = u->count;
for(i= r+1; i <= N; i++){
b.e[i].key = a->e[i+N].key;
b.e[i].p = a->e[i+N].p;
b.e[i].count = a->e[i+N].count;
}
}
a->m = N;
b.m = N;
b.p0 = v->p;
v->p = insertp(&b, pnew());
}
}
deletekey(x, a, h) /* search and delete key x in b_tree a; if a page
underflow is necessary, balance with adjacant
page if possible, otherwise merge; h = "page a
is undersiize" */
int x;
REF a;
int *h;
{
int i, k, l, r;
PAGE buf, *q;
if(a == (REF)NULL){
/* printf("key is not in tree\n"); */
*h = 0;
}
else{
for(k=0; k <= a->m; k++)
l = 1;
r = a->m;
do { /* binary array search */
k = (l+r)/2;
if(x <= a->e[k].key)
r = k-1;
if(x >= a->e[k].key)
l = k+1;
} while(r >= l);
if(r == 0)
q = fetchp(&buf, a->p0);
else
q = fetchp(&buf, a->e[r].p);
if(l-r > 1){ /* found, now delete e[k] */
if(q == (REF)NULL){ /* a is leaf page */
a->m -= 1;
*h = a->m < N;
for(i = k; i <= a->m; i++){
a->e[i].key = a->e[i+1].key;
a->e[i].p = a->e[i+1].p;
a->e[i].count = a->e[i+1].count;
}
insertp(a, a->e[0].p);
}
else {
del(q, h, a, k);
if(*h)
underflow(a, q, r, h);
}
}
else {
deletekey(x, q, h);
if(*h)
underflow(a, q, r, h);
}
}
}
del(p, h, a, k)
REF p;
int *h;
REF a;
int k;
{
PAGE buf, *q;
q = fetchp(&buf, p->e[p->m].p);
if(q != (REF)NULL){
del(q, h, a, k);
if(*h)
underflow(p, q, p->m, h);
}
else {
a->e[k].key = p->e[p->m].key;
a->e[k].count = p->e[p->m].count;
p->m -= 1;
*h = p->m < N;
insertp(a, a->e[0].p);
insertp(p, p->e[0].p);
}
}
underflow(c, a, s, h) /* a = underflow page, c = ancestor page */
REF c, a;
int s, *h;
{
PAGE buf, *b;
int i, k, mb, mc;
mc = c->m; /* h = true, a->m = N-1 */
if(s < mc) { /* b = page to the right of a */
s += 1;
b = fetchp(&buf, c->e[s].p);
mb = b->m;
k = (mb-N+1)/2; /* k = no. of items available on adjacant page b */
a->e[N].key = c->e[s].key;
a->e[N].count = c->e[s].count;
a->e[N].p = b->p0;
if(k > 0) { /* move k items from b to a */
for(i=1; i<= k-1; i++) {
a->e[i+N].key = b->e[i].key;
a->e[i+N].count = b->e[i].count;
a->e[i+N].p = b->e[i].p;
}
c->e[s].key = b->e[k].key;
c->e[s].count = b->e[k].count;
b->p0 = b->e[k].p;
mb -= k;
for(i=1; i<=mb; i++) {
b->e[i].key = b->e[i+k].key;
b->e[i].count = b->e[i+k].count;
b->e[i].p = b->e[i+k].p;
}
b->m = mb;
a->m = N-1+k;
insertp(b, b->e[0].p);
*h = 0;
}
else { /* merge pages a and b */
for(i=1; i<=N; i++) {
a->e[i+N].key = b->e[i].key;
a->e[i+N].count = b->e[i].count;
a->e[i+N].p = b->e[i].p;
}
for(i=s; i<= mc-1; i++){
c->e[i].key = c->e[i+1].key;
c->e[i].count = c->e[i+1].count;
c->e[i].p = c->e[i+1].p;
}
a->m = NN;
c->m = mc-1;
*h = c->m < N;
deletep(b->e[0].p); /* despose(b) */
}
insertp(a, a->e[0].p);
insertp(c, c->e[0].p);
}
else { /* b = page to the left of a */
if(s == 1)
b = fetchp(&buf, c->p0);
else
b = fetchp(&buf, c->e[s-1].p);
mb = b->m + 1;
k = (mb-N)/2;
if(k>0) { /* move k items from page b to a */
for(i=N-1; i>=1; i--) {
a->e[i+k].key = a->e[i].key;
a->e[i+k].count = a->e[i].count;
a->e[i+k].p = a->e[i].p;
}
a->e[k].key = c->e[s].key;
a->e[k].count = c->e[s].count;
a->e[k].p = a->p0;
mb = mb - k;
for(i=k-1; i>=1; i--) {
a->e[i].key = b->e[i+mb].key;
a->e[i].count = b->e[i+mb].count;
a->e[i].p = b->e[i+mb].p;
}
a->p0 = b->e[mb].p;
c->e[s].key = b->e[mb].key;
c->e[s].count = b->e[mb].count;
b->m = mb-1;
a->m = N-1+k;
insertp(a, a->e[0].p);
*h = 0;
}
else { /* merge pages a and b */
b->e[mb].key = c->e[s].key;
b->e[mb].count = c->e[s].count;
b->e[mb].p = a->p0;
for(i=1; i<=N-1; i++) {
b->e[i+mb].key = a->e[i].key;
b->e[i+mb].count = a->e[i].count;
b->e[i+mb].p = a->e[i].p;
}
b->m = NN;
c->m = mc-1;
*h = c->m < N;
deletep(a->e[0].p); /* dispose(a) */
}
insertp(b, b->e[0].p);
insertp(c, c->e[0].p);
}
}
/* printtree(p, l)
REF p;
int l;
{
int i;
PAGE q, *u;
if(p != (REF)NULL){
for(i=1; i<=l; i++)
printf(" ");
for(i=1; i<=p->m; i++)
printf("%4d", p->e[i].key);
printf("\n");
u = fetchp(&q, p->p0);
printtree(u, l+1);
for(i=1; i<=p->m; i++) {
u = fetchp(&q, p->e[i].p);
printtree(u, l+1);
}
}
} */
static long int headp, root, filesize;
static int fd1, fd2;
static PAGE *u, p;
dbminitf()
{
int i;
long int offset;
if((fd1=open("btree.pag", 2)) == -1)
error("dbminit: can't open btree.pag");
headp = -1;
root = 0;
filesize = 0;
}
long int pnew()
{
long int temp;
if(headp == -1) {
temp = filesize;
filesize += sizeof(PAGE);
}
else{
temp = headp;
lseek(fd1, headp, 0);
u = &p;
read(fd1, (char *)u, sizeof(PAGE));
headp = p.p0;
}
return(temp);
}
deletep(offset)
long int offset;
{
u = &p;
p.p0 = headp;
p.e[0].key = -1;
p.e[0].p = offset;
headp = offset;
lseek(fd1, offset, 0);
if(write(fd1, (char *)u, sizeof(PAGE)) != sizeof(PAGE))
error("delete: write error");
}
PAGE *fetchp(p, offset)
PAGE *p;
long int offset;
{
if(offset == NULL)
return((REF)NULL);
lseek(fd1, offset, 0);
if(read(fd1, (char *)p, sizeof(PAGE)) != sizeof(PAGE))
error("fetch: read error");
return(p);
}
long int insertp(p, offset)
PAGE *p;
long int offset;
{
p->e[0].key = 0;
p->e[0].p = offset;
lseek(fd1, offset, 0);
if(write(fd1, (char *)p, sizeof(PAGE)) != sizeof(PAGE))
error("insert: write error");
return(offset);
}
error(s)
char *s;
{
printf("%s\n", s);
exit(1);
}
//E*O*F B_tree_dsk.c//
exit 0