B-tree平衡算法

/* btrees.h */

/*

* 平衡多路樹的一種重要方案。

* 在 1970 年由 R. Bayer 和 E. McCreight 發(fā)明。

*/

#define M 1

/* B 樹的階，即非根節(jié)點(diǎn)中鍵的最小數(shù)目。

* 有些人把階定義為非根節(jié)點(diǎn)中子樹的最大數(shù)目。

*/

typedef int typekey;

typedef struct btnode { /* B-Tree 節(jié)點(diǎn) */

int d; /* 節(jié)點(diǎn)中鍵的數(shù)目 */

typekey k[2*M]; /* 鍵 */

char *v[2*M]; /* 值 */

struct btnode *p[2*M+1]; /* 指向子樹的指針 */

} node, *btree;

/*

* 每個(gè)鍵的左子樹中的所有的鍵都小于這個(gè)鍵，

* 每個(gè)鍵的右子樹中的所有的鍵都大于等于這個(gè)鍵。

* 葉子節(jié)點(diǎn)中的每個(gè)鍵都沒有子樹。

*/

/* 當(dāng) M 等于 1 時(shí)也稱為 2-3 樹

* +----+----+

* | k0 | k1 |

* +-+----+----+---

* | p0 | p1 | p2 |

* +----+----+----+

*/

extern int btree_disp; /* 查找時(shí)找到的鍵在節(jié)點(diǎn)中的位置 */

extern char * InsValue; /* 與要插的鍵相對應(yīng)的值 */

extern btree search(typekey, btree);

extern btree insert(typekey,btree);

extern btree delete(typekey,btree);

extern int height(btree);

extern int count(btree);

extern double payload(btree);

extern btree deltree(btree);

/* end of btrees.h */

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

/* btrees.c */

#include <stdlib.h>

#include <stdio.h>

#include "btrees.h"

btree search(typekey, btree);

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 void InsInNode(btree, int);

static void SplitNode(btree, int);

static btree NewRoot(btree);

static void InternalDelete(typekey, btree);

static void JoinNode(btree, int);

static void MoveLeftNode(btree t, int);

static void MoveRightNode(btree t, int);

static void DelFromNode(btree t, int);

static btree FreeRoot(btree);

static btree delall(btree);

static void Error(int,typekey);

int btree_disp; /* 查找時(shí)找到的鍵在節(jié)點(diǎn)中的位置 */

char * InsValue = NULL; /* 與要插的鍵相對應(yīng)的值 */

static int flag; /* 節(jié)點(diǎn)增減標(biāo)志 */

static int btree_level = 0; /* 多路樹的高度 */

static int btree_count = 0; /* 多路樹的鍵總數(shù) */

static int node_sum = 0; /* 多路樹的節(jié)點(diǎn)總數(shù) */

static int level; /* 當(dāng)前訪問的節(jié)點(diǎn)所處的高度 */

static btree NewTree; /* 在節(jié)點(diǎn)分割的時(shí)候指向新建的節(jié)點(diǎn) */

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));

if (key == t->k [ i ])

{

btree_disp = i;

return t;

}

if (key > t->k [ i ]) /* i == t->d-1 時(shí)有可能出現(xiàn) */

i++;

t = t->p[ i ];

level--;

}

return NULL;

}

btree insert(typekey key, btree t)

{

level=btree_level;

InternalInsert(key, t);

if (flag == 1) /* 根節(jié)點(diǎn)滿之后，它被分割成兩個(gè)半滿節(jié)點(diǎn) */

t=NewRoot(t); /* 樹的高度增加 */

return t;

}

void InternalInsert(typekey key, btree t)

{

int i,j,m;

level--;

if (level < 0) /* 到達(dá)了樹的底部: 指出要做的插入 */

{

NewTree = NULL; /* 這個(gè)鍵沒有對應(yīng)的子樹 */

InsKey = key; /* 導(dǎo)致底層的葉子節(jié)點(diǎn)增加鍵值+空子樹對 */

btree_count++;

flag = 1; /* 指示上層節(jié)點(diǎn)把返回的鍵插入其中 */

return;

}

for(i=0, j=t->d-1; i<j; m=(j+i)/2, (key > t->k[m])?(i=m+1):(j=m));

if (key == t->k[ i ])

{

Error(1,key); /* 鍵已經(jīng)在樹中 */

flag = 0;

return;

}

if (key > t->k[ i ]) /* i == t->d-1 時(shí)有可能出現(xiàn) */

i++;

InternalInsert(key, t->p[ i ]);

if (flag == 0)

return;

/* 有新鍵要插入到當(dāng)前節(jié)點(diǎn)中 */

if (t->d < 2*M) /* 當(dāng)前節(jié)點(diǎn)未滿 */

{

InsInNode(t, i); /* 把鍵值+子樹對插入當(dāng)前節(jié)點(diǎn)中 */

flag = 0; /* 指示上層節(jié)點(diǎn)沒有需要插入的鍵值+子樹，插入過程結(jié)束 */

}

else /* 當(dāng)前節(jié)點(diǎn)已滿，則分割這個(gè)頁面并把鍵值+子樹對插入當(dāng)前節(jié)點(diǎn)中 */

SplitNode(t, i); /* 繼續(xù)指示上層節(jié)點(diǎn)把返回的鍵值+子樹插入其中 */

}

/*

* 把一個(gè)鍵和對應(yīng)的右子樹插入一個(gè)節(jié)點(diǎn)中

*/

void InsInNode(btree t, int d)

{

int i;

/* 把所有大于要插入的鍵值的鍵和對應(yīng)的右子樹右移 */

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;

t->d++;

}

/*

* 前件是要插入一個(gè)鍵和對應(yīng)的右子樹，并且本節(jié)點(diǎn)已經(jīng)滿

* 導(dǎo)致分割這個(gè)節(jié)點(diǎn)，插入鍵和對應(yīng)的右子樹，

* 并向上層返回一個(gè)要插入鍵和對應(yīng)的右子樹

*/

void SplitNode(btree t, int d)

{

int i,j;

btree temp;

typekey temp_k;

char *temp_v;

/* 建立新節(jié)點(diǎn) */

temp = (btree)malloc(sizeof(node));

/*

* +---+--------+-----+-----+--------+-----+

* | 0 | ...... | M | M+1 | ...... |2*M-1|

* +---+--------+-----+-----+--------+-----+

* |<- M+1 ->|<- M-1 ->|

*/

if (d > M) /* 要插入當(dāng)前節(jié)點(diǎn)的右半部分 */

{

/* 把從 2*M-1 到 M+1 的 M-1 個(gè)鍵值+子樹對轉(zhuǎn)移到新節(jié)點(diǎn)中,

* 并且為要插入的鍵值+子樹空出位置 */

for(i=2*M-1,j=M-1; i>=d; i--,j--)

{

temp->k[j] = t->k[ i ];

temp->v[j] = t->v[ i ];

temp->p[j+1] = t->p[i+1];

}

for(i=d-1,j=d-M-2; j>=0; i--,j--)

{

temp->k[j] = t->k[ i ];

temp->v[j] = t->v[ i ];

temp->p[j+1] = t->p[i+1];

}

/* 把節(jié)點(diǎn)的最右子樹轉(zhuǎn)移成新節(jié)點(diǎn)的最左子樹 */

temp->p[0] = t->p[M+1];

/* 在新節(jié)點(diǎn)中插入鍵和右子樹 */

temp->k[d-M-1] = InsKey;

temp->p[d-M] = NewTree;

temp->v[d-M-1] = InsValue;

/* 設(shè)置要插入上層節(jié)點(diǎn)的鍵和值 */

InsKey = t->k[M];

InsValue = t->v[M];

}

else /* d <= M */

{

/* 把從 2*M-1 到 M 的 M 個(gè)鍵值+子樹對轉(zhuǎn)移到新節(jié)點(diǎn)中 */

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->p[j+1] = t->p[i+1];

}

if (d == M) /* 要插入當(dāng)前節(jié)點(diǎn)的正中間 */

/* 把要插入的子樹作為新節(jié)點(diǎn)的最左子樹 */

temp->p[0] = NewTree;

/* 直接把要插入的鍵和值返回給上層節(jié)點(diǎn) */

else /* (d<M) 要插入當(dāng)前節(jié)點(diǎn)的左半部分 */

{

/* 把節(jié)點(diǎn)當(dāng)前的最右子樹轉(zhuǎn)移成新節(jié)點(diǎn)的最左子樹 */

temp->p[0] = t->p[M];

/* 保存要插入上層節(jié)點(diǎn)的鍵和值 */

temp_k = t->k[M-1];

temp_v = t->v[M-1];

/* 把所有大于要插入的鍵值的鍵和對應(yīng)的右子樹右移 */

for(i=M-1; i>d; i--)

{

t->k[ i ] = t->k[i-1];

t->v[ i ] = t->v[i-1];

t->p[i+1] = t->p[ i ];

}

/* 在節(jié)點(diǎn)中插入鍵和右子樹 */

t->k[d] = InsKey;

t->p[d+1] = NewTree;

t->v[d] = InsValue;

/* 設(shè)置要插入上層節(jié)點(diǎn)的鍵和值 */

InsKey = temp_k;

InsValue = temp_v;

}

}

t->d =M;

temp->d = M;

NewTree = temp;

node_sum++;

}

btree delete(typekey key, btree t)

{

level=btree_level;

InternalDelete(key, t);

if (t->d == 0)

/* 根節(jié)點(diǎn)的子節(jié)點(diǎn)合并導(dǎo)致根節(jié)點(diǎn)鍵的數(shù)目隨之減少，

* 當(dāng)根節(jié)點(diǎn)中沒有鍵的時(shí)候，只有它的最左子樹可能非空 */

t=FreeRoot(t);

return t;

}

void InternalDelete(typekey key, btree t)

{

int i,j,m;

btree l,r;

int lvl;

level--;

if (level < 0)

{

Error(0,key); /* 在整個(gè)樹中未找到要?jiǎng)h除的鍵 */

flag = 0;

return;

}

for(i=0, j=t->d-1; i<j; m=(j+i)/2, (key > t->k[m])?(i=m+1):(j=m));

if (key == t->k[ i ]) /* 找到要?jiǎng)h除的鍵 */

{

if (t->v[ i ] != NULL)

free(t->v[ i ]); /* 釋放這個(gè)節(jié)點(diǎn)包含的值 */

if (level == 0) /* 有子樹為空則這個(gè)鍵位于葉子節(jié)點(diǎn) */

{

DelFromNode(t,i);

btree_count--;

flag = 1;

/* 指示上層節(jié)點(diǎn)本子樹的鍵數(shù)量減少 */

return;

}

else /* 這個(gè)鍵位于非葉節(jié)點(diǎn) */

{

lvl = level-1;

/* 找到前驅(qū)節(jié)點(diǎn) */

r = t->p[ i ];

while (lvl > 0)

{

r = r->p[r->d];

lvl--;

}

t->k[ i ]=r->k[r->d-1];

t->v[ i ]=r->v[r->d-1];

r->v[r->d-1]=NULL;

key = r->k[r->d-1];

}

}

else if (key > t->k[ i ]) /* i == t->d-1 時(shí)有可能出現(xiàn) */

i++;

InternalDelete(key,t->p[ i ]);

/* 調(diào)整平衡 */

if (flag == 0)

return;

if (t->p[ i ]->d < M)

{

if (i == t->d) /* 在最右子樹中發(fā)生了刪除 */

i--; /* 調(diào)整最右鍵的左右子樹平衡 */

l = t->p [ i ];

r = t->p[i+1];

if (r->d > M)

MoveLeftNode(t,i);

else if(l->d > M)

MoveRightNode(t,i);

else

{

JoinNode(t,i);

/* 繼續(xù)指示上層節(jié)點(diǎn)本子樹的鍵數(shù)量減少 */

return;

}

flag = 0;

/* 指示上層節(jié)點(diǎn)本子樹的鍵數(shù)量沒有減少，刪除過程結(jié)束 */

}

}

/*

* 合并一個(gè)節(jié)點(diǎn)的某個(gè)鍵對應(yīng)的兩個(gè)子樹

*/

void JoinNode(btree t, int d)

{

btree l,r;

int i,j;

l = t->p[d];

r = t->p[d+1];

/* 把這個(gè)鍵下移到它的左子樹 */

l->k[l->d] = t->k[d];

l->v[l->d] = t->v[d];

/* 把右子樹中的所有鍵值和子樹轉(zhuǎn)移到左子樹 */

for (j=r->d-1,i=l->d+r->d; j >= 0 ; j--,i--)

{

l->k[ i ] = r->k[j];

l->v[ i ] = r->v[j];

l->p[ i ] = r->p[j];

}

l->p[l->d+r->d+1] = r->p[r->d];

l->d += r->d+1;

/* 釋放右子樹的節(jié)點(diǎn) */

free(r);

/* 把這個(gè)鍵右邊的鍵和對應(yīng)的右子樹左移 */

for (i=d; i < t->d-1; i++)

{

t->k[ i ] = t->k[i+1];

t->v[ i ] = t->v[i+1];

t->p[i+1] = t->p[i+2];

}

t->d--;

node_sum--;

}

/*

* 從一個(gè)鍵的右子樹向左子樹轉(zhuǎn)移一些鍵，使兩個(gè)子樹平衡

*/

void MoveLeftNode(btree t, int d)

{

btree l,r;

int m; /* 應(yīng)轉(zhuǎn)移的鍵的數(shù)目 */

int i,j;

l = t->p[d];

r = t->p[d+1];

m = (r->d - l->d)/2;

/* 把這個(gè)鍵下移到它的左子樹 */

l->k[l->d] = t->k[d];

l->v[l->d] = t->v[d];

/* 把右子樹的最左子樹轉(zhuǎn)移成左子樹的最右子樹

* 從右子樹向左子樹移動(dòng) m-1 個(gè)鍵+子樹對 */

for (j=m-2,i=l->d+m-1; j >= 0; j--,i--)

{

l->k[ i ] = r->k[j];

l->v[ i ] = r->v[j];

l->p[ i ] = r->p[j];

}

l->p[l->d+m] = r->p[m-1];

/* 把右子樹的最左鍵提升到這個(gè)鍵的位置上 */

t->k[d] = r->k[m-1];

t->v[d] = r->v[m-1];

/* 把右子樹中的所有鍵值和子樹左移 m 個(gè)位置 */

r->p[0] = r->p[m];

for (i=0; i<r->d-m; i++)

{

r->k[ i ] = r->k[i+m];

r->v[ i ] = r->v[i+m];

r->p[ i ] = r->p[i+m];

}

r->p[r->d-m] = r->p[r->d];

l->d+=m;

r->d-=m;

}

/*

* 從一個(gè)鍵的左子樹向右子樹轉(zhuǎn)移一些鍵，使兩個(gè)子樹平衡

*/

void MoveRightNode(btree t, int d)

{

btree l,r;

int m; /* 應(yīng)轉(zhuǎn)移的鍵的數(shù)目 */

int i,j;

l = t->p[d];

r = t->p[d+1];

m = (l->d - r->d)/2;

/* 把右子樹中的所有鍵值和子樹右移 m 個(gè)位置 */

r->p[r->d+m]=r->p[r->d];

for (i=r->d-1; i>=0; i--)

{

r->k[i+m] = r->k[ i ];

r->v[i+m] = r->v[ i ];

r->p[i+m] = r->p[ i ];

}

/* 把這個(gè)鍵下移到它的右子樹 */

r->k[m-1] = t->k[d];

r->v[m-1] = t->v[d];

/* 把左子樹的最右子樹轉(zhuǎn)移成右子樹的最左子樹 */

r->p[m-1] = l->p[l->d];

/* 從左子樹向右子樹移動(dòng) m-1 個(gè)鍵+子樹對 */

for (i=l->d-1,j=m-2; j>=0; j--,i--)

{

r->k[j] = l->k[ i ];

r->v[j] = l->v[ i ];

r->p[j] = l->p[ i ];

}

/* 把左子樹的最右鍵提升到這個(gè)鍵的位置上 */

t->k[d] = l->k[ i ];

t->v[d] = l->v[ i ];

l->d-=m;

r->d+=m;

}

/*

* 把一個(gè)鍵和對應(yīng)的右子樹從一個(gè)節(jié)點(diǎn)中刪除

*/

void DelFromNode(btree t, int d)

{

int i;

/* 把所有大于要?jiǎng)h除的鍵值的鍵左移 */

for(i=d; i < t->d-1; i++)

{

t->k[ i ] = t->k[i+1];

t->v[ i ] = t->v[i+1];

}

t->d--;

}

/*

* 建立有兩個(gè)子樹和一個(gè)鍵的根節(jié)點(diǎn)

*/

btree NewRoot(btree t)

{

btree temp;

temp = (btree)malloc(sizeof(node));

temp->d = 1;

temp->p[0] = t;

temp->p[1] = NewTree;

temp->k[0] = InsKey;

temp->v[0] = InsValue;

btree_level++;

node_sum++;

return(temp);

}

/*

* 釋放根節(jié)點(diǎn)，并返回它的最左子樹

*/

btree FreeRoot(btree t)

{

btree temp;

temp = t->p[0];

free(t);

btree_level--;

node_sum--;

return temp;

}

void Error(int f,typekey key)

{

if (f)

printf("Btrees error: Insert %d!\n",key);

else

printf("Btrees error: delete %d!\n",key);

}

int height(btree t)

{

return btree_level;

}

int count(btree t)

{

return btree_count;

}

double payload(btree t)

{

if (node_sum==0)

return 1;

return (double)btree_count/(node_sum*(2*M));

}

btree deltree (btree t)

{

level=btree_level;

btree_level = 0;

return delall(t);

}

btree delall(btree t)

{

int i;

level--;

if (level >= 0)

{

for (i=0; i < t->d; i++)

if (t->v[ i ] != NULL)

free(t->v[ i ]);

if (level > 0)

for (i=0; i<= t->d ; i++)

t->p[ i ]=delall(t->p[ i ]);

free(t);

}

return NULL;

}

/* end of btrees.c */

鑒于B-tree具有良好的定位特性，其常被用于對檢索時(shí)間要求苛刻的場合，例如:

1、B-tree索引是數(shù)據(jù)庫中存取和查找文件(稱為記錄或鍵值)的一種方法。

2、硬盤中的結(jié)點(diǎn)也是B-tree結(jié)構(gòu)的。與內(nèi)存相比，硬盤必須花成倍的時(shí)間來存取一個(gè)數(shù)據(jù)元素，這是因?yàn)橛脖P的機(jī)械部件讀寫數(shù)據(jù)的速度遠(yuǎn)遠(yuǎn)趕不上純電子媒體的內(nèi)存。與一個(gè)結(jié)點(diǎn)兩個(gè)分支的二元樹相比，B-tree利用多個(gè)分支(稱為子樹)的結(jié)點(diǎn)，減少獲取記錄時(shí)所經(jīng)歷的結(jié)點(diǎn)數(shù)，從而達(dá)到節(jié)省存取時(shí)間的目的。

B-tree有以下特性:

1、關(guān)鍵字集合分布在整棵樹中;

2、任何一個(gè)關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)結(jié)點(diǎn)中;

3、搜索有可能在非葉子結(jié)點(diǎn)結(jié)束;

4、其搜索性能等價(jià)于在關(guān)鍵字全集內(nèi)做一次二分查找;

5、自動(dòng)層次控制;

由于限制了除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)，至少含有M/2個(gè)兒子，確保了結(jié)點(diǎn)的至少利用率，其最低搜索性能為:

其中，M為設(shè)定的非葉子結(jié)點(diǎn)最多子樹個(gè)數(shù)，N為關(guān)鍵字總數(shù);

所以B-樹的性能總是等價(jià)于二分查找(與M值無關(guān))，也就沒有B樹平衡的問題;

由于M/2的限制，在插入結(jié)點(diǎn)時(shí)，如果結(jié)點(diǎn)已滿，需要將結(jié)點(diǎn)分裂為兩個(gè)各占M/2的結(jié)點(diǎn);刪除結(jié)點(diǎn)時(shí)，需將兩個(gè)不足M/2的兄弟結(jié)點(diǎn)合并。

B-tree中，每個(gè)結(jié)點(diǎn)包含:

1、本結(jié)點(diǎn)所含關(guān)鍵字的個(gè)數(shù);

2、指向父結(jié)點(diǎn)的指針;

3、關(guān)鍵字;

4、指向子結(jié)點(diǎn)的指針;

對于一棵m階B-tree，每個(gè)結(jié)點(diǎn)至多可以擁有m個(gè)子結(jié)點(diǎn)。各結(jié)點(diǎn)的關(guān)鍵字和可以擁有的子結(jié)點(diǎn)數(shù)都有限制，規(guī)定m階B-tree中，根結(jié)點(diǎn)至少有2個(gè)子結(jié)點(diǎn)，除非根結(jié)點(diǎn)為葉子節(jié)點(diǎn)，相應(yīng)的，根結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)為1~m-1;非根結(jié)點(diǎn)至少有[m/2]([]，向上取整)個(gè)子結(jié)點(diǎn)，相應(yīng)的，關(guān)鍵字個(gè)數(shù)為[m/2]-1~m-1。

另外還有一種與此類似的樹結(jié)構(gòu)叫B+樹，像 Berkerly DB , sqlite , mysql 數(shù)據(jù)庫都使用了B+樹算法處理索引。

B+和B-(即B)是因?yàn)槊總€(gè)結(jié)點(diǎn)上的關(guān)鍵字不同。一個(gè)多一個(gè)，一個(gè)少一個(gè)。

對于B+樹，其結(jié)點(diǎn)結(jié)構(gòu)與B-tree相同，不同的是各結(jié)點(diǎn)的關(guān)鍵字和可以擁有的子結(jié)點(diǎn)數(shù)。如m階B+樹中，每個(gè)結(jié)點(diǎn)至多可以擁有m個(gè)子結(jié)點(diǎn)。非根結(jié)點(diǎn)至少有[m/2]個(gè)子結(jié)點(diǎn)，而關(guān)鍵字個(gè)數(shù)比B-tree多一個(gè)，為[m/2]~m。

這兩種處理索引的數(shù)據(jù)結(jié)構(gòu)的不同之處:

1。B樹中同一鍵值不會(huì)出現(xiàn)多次，并且它有可能出現(xiàn)在葉結(jié)點(diǎn)，也有可能出現(xiàn)在非葉結(jié)點(diǎn)中。而B+樹的鍵一定會(huì)出現(xiàn)在葉結(jié)點(diǎn)中，并且有可能在非葉結(jié)點(diǎn)中也有可能重復(fù)出現(xiàn)，以維持B+樹的平衡。

2。因?yàn)锽樹鍵位置不定，且在整個(gè)樹結(jié)構(gòu)中只出現(xiàn)一次，雖然可以節(jié)省存儲(chǔ)空間，但使得在插入、刪除操作復(fù)雜度明顯增加。B+樹相比來說是一種較好的折中。

3。B樹的查詢效率與鍵在樹中的位置有關(guān)，最大時(shí)間復(fù)雜度與B+樹相同(在葉結(jié)點(diǎn)的時(shí)候)，最小時(shí)間復(fù)雜度為1(在根結(jié)點(diǎn)的時(shí)候)。而B+樹的時(shí)間復(fù)雜度對某建成的樹是固定的。