B樹的實現(xiàn)

今天我們就來實現(xiàn)以下B樹，B樹有什么特點那？我們來列舉一下

• 每個非葉子節(jié)點中存放若干關(guān)鍵字?jǐn)?shù)據(jù)，并且有若干指向兒子節(jié)點的指針。指針數(shù)目=關(guān)鍵字?jǐn)?shù)目+1
• 根節(jié)點有最少1個，最多m-1個關(guān)鍵字，最少2個，最多m個子節(jié)點。
• 非根節(jié)點最少有m/2，最多m-1個關(guān)鍵字
• 每個節(jié)點中的關(guān)鍵字從左到右以非降序排列
• 每個關(guān)鍵字均不小于其左子節(jié)點的關(guān)鍵字，不大于其右子節(jié)點的所有關(guān)鍵字
• 每個葉子節(jié)點都具有相同的深度

B樹的節(jié)點的增加

我們還是通過1-25個數(shù)的增加，來探索一下，B樹的增加節(jié)點有什么規(guī)律，并寫出代碼。
首先我們定義出來我們B樹的結(jié)構(gòu)，如下:

#define DEGREE		3
typedef int KEY_VALUE;

typedef struct _BTREE_NODE
{
    KEY_VALUE* keys;
    struct _BTREE_NODE** Childrens;
    int num;
    int leaf;
}BTREE_NODE,*PBTREE_NODE;

typedef struct _BTREE
{
    BTREE_NODE* root;
    int t;
};

我們來看一下B樹1-20個數(shù)字的增加的圖片
1-5

6-10

11-15

16-20

我們首先需要創(chuàng)建一個根節(jié)點:

BTREE_NODE* btree_create_node(int t, int leaf) {

    BTREE_NODE* node = (BTREE_NODE*)calloc(1, sizeof(BTREE_NODE));
    if (node == NULL) assert(0);

    node->leaf = leaf;
    node->keys = (KEY_VALUE*)calloc(1, (2 * t - 1) * sizeof(KEY_VALUE));
    node->Childrens = (BTREE_NODE**)calloc(1, (2 * t) * sizeof(BTREE_NODE*));
    node->num = 0;

    return node;
}
//創(chuàng)建根節(jié)點
void btree_create(BTREE*T,int t)
{
    T->t = t;
    PBTREE_NODE x = btree_create_node(t, 1);
    T->root = x;
}

現(xiàn)在就寫一下我們插入的代碼

BTREE_NODE* btree_create_node(int t, int leaf) {

    BTREE_NODE* node = (BTREE_NODE*)calloc(1, sizeof(BTREE_NODE));
    if (node == NULL) assert(0);

    node->leaf = leaf;
    node->keys = (KEY_VALUE*)calloc(1, (2 * t - 1) * sizeof(KEY_VALUE));
    node->Childrens = (BTREE_NODE**)calloc(1, (2 * t) * sizeof(BTREE_NODE*));
    node->num = 0;

    return node;
}
//節(jié)點分裂
void btree_split_child(BTREE* T,BTREE_NODE* x,int i)
{
    int t = T->t;

    BTREE_NODE* y = x->Childrens[i];
    BTREE_NODE* z = btree_create_node(t, y->leaf);
    z->num = t - 1;

    int j = 0;
    for (j=0;j<t-1;j++)
    {
        z->keys[j] = y->keys[j + t];
    }
    if (y->leaf==0)
    {
	    for (j=0;j<t;j++)
	    {
            z->Childrens[j] = y->Childrens[j + t];
	    }
    }
    y->num = t - 1;
    for (j=x->num;j>=i+1;j--)
    {
        x->Childrens[j + 1] = x->Childrens[j];
    }
    x->Childrens[i + 1] = z;
    for(j=x->num-1;j>=i;j--)
    {
        x->keys[j + 1] = x->keys[j];
    }
    x->keys[i] = y->keys[t - 1];
    x->num += 1;
}
//創(chuàng)建節(jié)點
void btree_create(BTREE*T,int t)
{
    T->t = t;
    PBTREE_NODE x = btree_create_node(t, 1);
    T->root = x;
}
void btree_insert_notfull(BTREE*T,BTREE_NODE *x,KEY_VALUE k)
{
	//獲取節(jié)點數(shù)量,從0開始減1
    int i = x->num-1;
    //只有1個葉子節(jié)點
	if (x->leaf==1)
	{
		while (i>=0&&x->keys[i]>k)
		{
            x->keys[i + 1] = x->keys[i];
            i--;
		}
        //賦值
        x->keys[i + 1] = k;
        x->num += 1;
	}else
	{
       //找到應(yīng)該插入的葉子節(jié)點
        while (i >= 0 && x->keys[i] > k) i--;
        //是否已經(jīng)滿了5個節(jié)點
       if (x->Childrens[i+1]->num==((2*T->t))-1)
       {
           btree_split_child(T, x, i + 1);
           if (k>x->keys[i+1])
           {
               i++;
           }
       }

       btree_insert_notfull(T, x->Childrens[i + 1], k);
       
		
	}
}
void btree_insert(BTREE *T ,KEY_VALUE key)
{
   //獲取頭節(jié)點
    BTREE_NODE* r = T->root;
    //如果滿節(jié)點就要進行這里的操作

    if (r->num==2*T->t-1)
    {
        BTREE_NODE* node = btree_create_node(T->t, 0);
        T->root = node;

        node->Childrens[0] = r;

        btree_split_child(T, node, 0);

        int i = 0;
        if (node->keys[0] < key) i++;
        btree_insert_notfull(T, node->Childrens[i], key);
    }
    else
    {
	    //如果沒有滿就要進行這里的操作
        btree_insert_notfull(T, r, key);
    }
    
}

B樹節(jié)點的刪除

我們還是看一下是如何刪除的示意圖，然后再寫代碼。
這里主要討論一下刪除的幾種情況，

B樹刪除的代碼

//釋放節(jié)點
void btree_destory_node(BTREE_NODE* node)
{
	if (node == nullptr)
	{
		return;
	}
	free(node->Childrens);
	free(node->keys);
	free(node);
}
void btree_merge(BTREE* T, BTREE_NODE* node, int idx)
{
	BTREE_NODE* left = node->Childrens[idx];
	BTREE_NODE* right = node->Childrens[idx + 1];

	int i = 0;
	left->keys[T->t - 1] = node->keys[idx];
	//開始數(shù)據(jù)的合并
	for (i = 0; i < T->t - 1; i++)
	{
		left->keys[T->t + 1] = right->keys[i];
	}
	if (!left->leaf)
	{
		for (i = 0; i < T->t; i++)
		{
			left->Childrens[T->t + 1] = right->Childrens[i];
		}
	}
	left->num += T->t;
	//合并完成摧毀節(jié)點
	btree_destory_node(right);

	//node
	for (i = idx + 1; i < node->num; i++)
	{
		node->keys[i - 1] = node->keys[i];
		node->Childrens[i] = node->Childrens[i + 1];
	}
	node->Childrens[i + 1] = NULL;
	node->num -= 1;
	if (node->num == 0)
	{
		T->root = left;
		btree_destory_node(node);
	}

}
void btree_delete_key(BTREE* T, BTREE_NODE* node, KEY_VALUE key)
{
	//如果是空節(jié)點，直接返回
	if (node == nullptr)
	{
		return;
	}
	int idx = 0, i;
	//獲取key所在的位置
	while (idx<node->num && key>node->keys[idx])
	{
		idx++;
	}
	if (idx < node->num && key == node->keys[idx])
	{
		if (node->leaf)
		{
			//如果是葉子節(jié)點，直接刪除
			for (i = idx; i < node->num - 1; i++)
			{
				node->keys[i] = node->keys[i + 1];
			}
			node->keys[node->num - 1] = 0;
			node->num--;
			//如果是根節(jié)點的情況
			if (node->num == 0)
			{
				free(node);
				T->root = nullptr;
			}
			return;
		}//直接刪除
		else if (node->Childrens[idx]->num >= T->t)
		{
			BTREE_NODE* left = node->Childrens[idx];
			node->keys[idx] = left->keys[left->num - 1];
			btree_delete_key(T, left, left->keys[left->num - 1]);
		}//直接刪除
		else if (node->Childrens[idx + 1]->num >= T->t)
		{
			BTREE_NODE* right = node->Childrens[idx + 1];
			node->keys[idx] = right->keys[0];
			btree_delete_key(T, right, right->keys[0]);

		}
		else {
			//如果都不是,說明是左右孩子節(jié)點都是T-1個關(guān)鍵字
			btree_merge(T, node, idx);
			btree_delete_key(T, node->Childrens[idx], key);
		}
	}
	else
	{
		BTREE_NODE* child = node->Childrens[idx];
		if (child == NULL)
		{
			printf("Can\'t del key=%d\n", key);
			return;
		}//子節(jié)點的數(shù)目剛好等于2
		if (child->num == T->t - 1)
		{
			BTREE_NODE* left = nullptr;
			BTREE_NODE* right = nullptr;
			if (idx - 1 >= 0)
			{
				left = node->Childrens[idx - 1];
			}
			if (idx + 1 <= node->num)
			{
				right = node->Childrens[idx + 1];
			}
			//如果左右節(jié)點任何一個都可以借用節(jié)點
			if ((left && left->num >= T->t) || (right && right->num >= T->t))
			{
				int richR = 0;
				if (right)
				{
					richR = 1;
				}
				if (left && right)
				{
					richR = (right->num > left->num) ? 1 : 0;
				}
				//從右借用節(jié)點
				if (right && right->num >= T->t && richR)
				{
					child->keys[child->num] = node->keys[idx];
					child->Childrens[child->num + 1] = right->Childrens[0];
					child->num++;
					node->keys[idx] = right->keys[0];
					//調(diào)整右邊的節(jié)點
					for (i = 0; i < right->num - 1; i++)
					{
						right->keys[i] = right->keys[i + 1];
						right->Childrens[i] = right->Childrens[i + 1];
					}

					right->keys[right->num - 1] = 0;
					right->Childrens[right->num - 1] = right->Childrens[right->num];
					right->Childrens[right->num] = NULL;
					right->num--;
				}
				else
				{
					//從左借節(jié)點
					for (i = child->num; i > 0; i--)
					{
						child->keys[i] = child->keys[i - 1];
						child->Childrens[i + 1] = child->Childrens[i];
					}
					child->Childrens[1] = child->Childrens[0];
					child->Childrens[0] = left->Childrens[left->num];
					child->keys[0] = node->keys[idx - 1];
					child->num++;

					node->keys[idx - 1] = left->keys[left->num - 1];
					left->keys[left->num - 1] = 0;
					left->Childrens[left->num] = NULL;
					left->num--;
				}
				

			}
			else if ((!left) || (left->num == T->t - 1) && (!right) || (right->num == T->t - 1))
			{
				if (left&&left->num==T->t-1)
				{
					btree_merge(T, node, idx - 1);
					child = left;
				}else if(right&&right->num==T->t-1)
				{
					btree_merge(T, node, idx);
				}
			}
			btree_delete_key(T, child, key);
		}
	}

}
int btree_delete(BTREE* T, KEY_VALUE key)
{
	if (!T->root)
	{
		return -1;
	}
	btree_delete_key(T, T->root, key);
	return 0;
}

推薦一個零聲學(xué)院免費教程，個人覺得老師講得不錯，
分享給大家：[Linux，Nginx，ZeroMQ，MySQL，Redis，
fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，
TCP/IP，協(xié)程，DPDK等技術(shù)內(nèi)容，點擊立即學(xué)習(xí):
服務(wù)器
音視頻
dpdk
Linux內(nèi)核