---

點(diǎn)擊 <C 語(yǔ)言編程核心突破> 快速C語(yǔ)言入門

---

---

前言

要解決問(wèn)題:

實(shí)現(xiàn)一個(gè)最簡(jiǎn)陋的B-Tree, 研究B-Tree的性質(zhì).

對(duì)于B樹(shù), 我是心向往之, 因?yàn)樗菙?shù)據(jù)庫(kù)的基石, 描述語(yǔ)言好像很容易理解, 但不造個(gè)輪子就不能徹底弄明白, 于是, 造個(gè)輪子.

想到的思路:

根據(jù)AI給的代碼架子進(jìn)行修改, 現(xiàn)在AI是個(gè)好東西, 雖說(shuō)給的代碼不一定靠譜, 但是debug一下, 還能深入了解, 總之是很有用.

其它的補(bǔ)充:

有一份C++ 的B-Tree, 是通過(guò)算法4的java代碼移植的, 但是C++ 的內(nèi)存管理教育了我, 太難整了, 于是一氣之下, 全改為智能指針, 頭疼的事就解決了. 也是很簡(jiǎn)陋的代碼, 只有增查, 沒(méi)有刪改, 就暫時(shí)不提供了.

---

一、C語(yǔ)言B-Tree

基本架構(gòu):

為了適應(yīng)不同的B-Tree節(jié)點(diǎn), 通過(guò)宏BTREE_ORDER_SIZE 規(guī)定子節(jié)點(diǎn)的數(shù)量, 使用typedef int keyOfBTree;定義節(jié)點(diǎn)的key類型, 以適應(yīng)不同需求.

BTreeNode的結(jié)構(gòu)中, 對(duì)于值和子節(jié)點(diǎn)存儲(chǔ), 直接使用數(shù)組, 而不是指針, 好處是初始化的時(shí)候比較容易, free的時(shí)候也不容易出錯(cuò), 畢竟都是數(shù)組, delete BTreeNode直接就完事了, 不用一個(gè)個(gè)的刪除值, 省時(shí)間.

不好之處, 可能是自由度和空間利用度受限, 畢竟到最后葉子節(jié)點(diǎn), 不管用不用子節(jié)點(diǎn), 都要開(kāi)辟子節(jié)點(diǎn)數(shù)組內(nèi)存, 有一點(diǎn)點(diǎn)浪費(fèi).

打印節(jié)點(diǎn)內(nèi)容以及釋放樹(shù), 是用的遞歸, 畢竟這個(gè)用遞歸太容易了.

代碼中最復(fù)雜的是分裂節(jié)點(diǎn)和向樹(shù)中插入值, 需要慢慢體會(huì), 多琢磨也不是太難.

至于刪除節(jié)點(diǎn)和更改節(jié)點(diǎn), 這里沒(méi)有實(shí)現(xiàn).

BTree.h頭文件.

#ifndef BTREE_
#define BTREE_#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

對(duì)于B樹(shù), 如果形象的比喻, 就是拍平的二叉樹(shù), 并且是平衡二叉樹(shù), 每個(gè)節(jié)點(diǎn)可以容納N個(gè)key, 同時(shí)容納N+1個(gè)子節(jié)點(diǎn), 這是一條非常重要的性質(zhì), 同時(shí), 節(jié)點(diǎn)存放的key是按順序排列的, 子節(jié)點(diǎn)也是按照順序排列的, 是完全有序的.

一般子節(jié)點(diǎn)數(shù)量是偶數(shù).

// B樹(shù)的階數(shù)，決定每個(gè)節(jié)點(diǎn)的孩子數(shù)量
#define BTREE_ORDER_SIZE 6

為了泛型, 我們只能用比較函數(shù)指針進(jìn)行比較, 畢竟C語(yǔ)言不可能重載操作符.

// 比較函數(shù)指針類型
typedef int (*cmpFuncPtr)(void *, void *);

修改keyOfBTree可以讓BTree使用不同的key

// 定義B樹(shù)的key類型, 利于泛型
typedef int keyOfBTree;// 打印函數(shù)指針類型
typedef void (*printFun)(keyOfBTree);

B樹(shù)的節(jié)點(diǎn)構(gòu)成決定了其性質(zhì), B樹(shù)含有一個(gè)key的數(shù)組, 以及子節(jié)點(diǎn)指針數(shù)組, 同時(shí)因?yàn)椴灰欢〝?shù)組全部是滿的, 必須有一個(gè)num值指示究竟含有多少個(gè)key, 以及有多少個(gè)子節(jié)點(diǎn), 也就是num + 1.

// B樹(shù)的節(jié)點(diǎn)結(jié)構(gòu)
typedef struct BTreeNode
{keyOfBTree keys[BTREE_ORDER_SIZE - 1];      // 關(guān)鍵字?jǐn)?shù)組struct BTreeNode *childs[BTREE_ORDER_SIZE]; // 孩子節(jié)點(diǎn)指針數(shù)組uint32_t num; // 當(dāng)前節(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)量int is_leaf;  // 是否為葉子節(jié)點(diǎn)
} BTreeNode;typedef BTreeNode *BTree;

B樹(shù)有一些必須接口, 也是不能再精簡(jiǎn)的接口包括節(jié)點(diǎn)創(chuàng)建, 查找索引, 在節(jié)點(diǎn)中插入值, 分裂節(jié)點(diǎn), 在B樹(shù)中插入值, 以及B樹(shù)的釋放. 打印B樹(shù)是為了展示B樹(shù)的結(jié)構(gòu), 在現(xiàn)實(shí)中, 一般是沒(méi)有的.

// 創(chuàng)建節(jié)點(diǎn)
BTreeNode *createNode(int is_leaf);// 查找關(guān)鍵字在節(jié)點(diǎn)中的索引位置
int searchKeyIndex(BTreeNode *node, keyOfBTree key, cmpFuncPtr cmp);// 插入關(guān)鍵字到節(jié)點(diǎn)中的指定位置
void insertKey(BTreeNode *node, keyOfBTree key, cmpFuncPtr cmp);// 分裂一個(gè)滿節(jié)點(diǎn)，將中間的關(guān)鍵字提升為父節(jié)點(diǎn)，并創(chuàng)建兩個(gè)新的子節(jié)點(diǎn)
void splitNode(BTreeNode *parent, int child_index);// 在B樹(shù)中插入關(guān)鍵字
void insert(BTreeNode **root, keyOfBTree key, cmpFuncPtr cmp);// 打印B樹(shù)的關(guān)鍵字
void printBTree(BTreeNode *node, printFun printKey, int left, int *cnt);// 釋放BTree
void freeBTree(BTreeNode **node);#endif

BTree.c實(shí)現(xiàn).

#include "BTree.h"

創(chuàng)建節(jié)點(diǎn)很簡(jiǎn)單, 要給一個(gè)參數(shù), 識(shí)別是不是葉子節(jié)點(diǎn), 葉子節(jié)點(diǎn)不含任何子節(jié)點(diǎn), 只含有值,

非葉子節(jié)點(diǎn), 既有值又有子節(jié)點(diǎn).

通過(guò)malloc分配內(nèi)存, 初始化置零, 賦值是否為葉子節(jié)點(diǎn).

// 創(chuàng)建節(jié)點(diǎn)
BTreeNode *createNode(int is_leaf)
{BTreeNode *node = (BTreeNode *)malloc(sizeof(BTreeNode));memset(node, 0, sizeof(BTreeNode));node->is_leaf = is_leaf;return node;
}

查找索引位置是B樹(shù)的基本函數(shù), 通過(guò)比較key和節(jié)點(diǎn)內(nèi)部key數(shù)組中的值確定索引位置.

比如值是5, 節(jié)點(diǎn)內(nèi)值數(shù)組是{1,3,8}, 用5和它們比較, 索引從0開(kāi)始, 如果5大于1, 索引增加1, 大于3, 又增加1, 所以最終的索引值是2,

這個(gè)索引值非常重要, 通過(guò)它, 才能找到正確的子節(jié)點(diǎn), 一步一步的深入找到最終的子節(jié)點(diǎn).

// 查找關(guān)鍵字在節(jié)點(diǎn)中的索引位置
int searchKeyIndex(BTreeNode *node, keyOfBTree key, cmpFuncPtr cmp)
{int index = 0;while (index < node->num && cmp(&key, &(node->keys[index])) > 0){index++;}return index;
}

這個(gè)插入函數(shù)是在確定了究竟要在哪個(gè)子節(jié)點(diǎn)插入值后使用的, 過(guò)程需要挪動(dòng)數(shù)組中的元素.

// 插入關(guān)鍵字到節(jié)點(diǎn)中的指定位置
void insertKey(BTreeNode *node, keyOfBTree key, cmpFuncPtr cmp)
{int index = (int)node->num - 1;while (index >= 0 && cmp(&key, &(node->keys[index])) < 0){node->keys[index + 1] = node->keys[index];index--;}node->keys[index + 1] = key;node->num++;
}

分裂節(jié)點(diǎn)比較復(fù)雜, 為了理解, 需要闡述一下

1. 分裂的是父節(jié)點(diǎn)的子節(jié)點(diǎn), 所以傳入的是父節(jié)點(diǎn)指針以及子節(jié)點(diǎn)索引.
2. 過(guò)程中會(huì)創(chuàng)建一個(gè)與子節(jié)點(diǎn)同樣性質(zhì), 也就是是否是葉子節(jié)點(diǎn)的節(jié)點(diǎn).
3. 如果要分裂的子節(jié)點(diǎn)是葉子節(jié)點(diǎn), 就不會(huì)分裂子節(jié)點(diǎn)的子節(jié)點(diǎn), 因?yàn)闆](méi)有, 否則值數(shù)組和子節(jié)點(diǎn)指針數(shù)組要同時(shí)分裂.
4. 分裂會(huì)把子節(jié)點(diǎn)的中間值提升給父節(jié)點(diǎn), 比如滿值是{1,2,3,4,5}, 那么就分裂為{1,2}{4,5}兩個(gè)節(jié)點(diǎn), 3提升給父節(jié)點(diǎn)接收.
5. 被分裂的子節(jié)點(diǎn)的值數(shù)量num以及父節(jié)點(diǎn)的num都要被修改.

// 分裂一個(gè)滿節(jié)點(diǎn)，將中間的關(guān)鍵字提升為父節(jié)點(diǎn)，并創(chuàng)建兩個(gè)新的子節(jié)點(diǎn)
void splitNode(BTreeNode *parent, int child_index)
{BTreeNode *child = parent->childs[child_index];BTreeNode *new_node = createNode(child->is_leaf);new_node->num = BTREE_ORDER_SIZE / 2 - 1;for (int i = 0; i < new_node->num; i++){new_node->keys[i] = child->keys[BTREE_ORDER_SIZE / 2 + i];}if (!child->is_leaf){for (int i = 0; i < BTREE_ORDER_SIZE / 2; i++){new_node->childs[i] = child->childs[BTREE_ORDER_SIZE / 2 + i];}}child->num = BTREE_ORDER_SIZE / 2 - 1;for (int i = (int)parent->num; i > child_index; i--){parent->childs[i + 1] = parent->childs[i];}parent->childs[child_index + 1] = new_node;for (int i = (int)parent->num - 1; i >= child_index; i--){parent->keys[i + 1] = parent->keys[i];}parent->keys[child_index] = child->keys[BTREE_ORDER_SIZE / 2 - 1];parent->num++;
}

向B樹(shù)插入值, 過(guò)程也比較復(fù)雜, 需要闡述:

1. 由于可能分裂根節(jié)點(diǎn), 所以傳入的是根節(jié)點(diǎn)的二級(jí)指針, 保證不丟失節(jié)點(diǎn).
2. 分三種情況, 根節(jié)點(diǎn)為空, 這個(gè)最簡(jiǎn)單, 直接生成節(jié)點(diǎn), 在此節(jié)點(diǎn)插入值, 令根節(jié)點(diǎn)指向它.
3. 根節(jié)點(diǎn)已滿, 必須分裂根節(jié)點(diǎn), 而為了分裂根節(jié)點(diǎn), 需要給根節(jié)點(diǎn)整個(gè)父節(jié)點(diǎn), 然后再將root指針指向這個(gè)父節(jié)點(diǎn), 并進(jìn)行分裂.
4. 根節(jié)點(diǎn)非空非滿, 如果根節(jié)點(diǎn)是葉子節(jié)點(diǎn), 直接插入, 如果不是葉子節(jié)點(diǎn), 那就要取得索引, 看索引地址的子節(jié)點(diǎn)是否是滿的, 是則分裂, 然后進(jìn)入子節(jié)點(diǎn)循環(huán)插入, 不是滿的, 則直接進(jìn)入子節(jié)點(diǎn)循環(huán).
5. 大家可能看出來(lái)了, 最終都是插入到葉子節(jié)點(diǎn).

// 在B樹(shù)中插入關(guān)鍵字
void insert(BTreeNode **root, keyOfBTree key, cmpFuncPtr cmp)
{BTreeNode *node = *root;// 如果根節(jié)點(diǎn)為空，則創(chuàng)建新的根節(jié)點(diǎn)if (node == NULL){*root = createNode(1);insertKey(*root, key, cmp);return;}// 如果根節(jié)點(diǎn)已滿，則需要?jiǎng)?chuàng)建一個(gè)新的根節(jié)點(diǎn)if (node->num == BTREE_ORDER_SIZE - 1){BTreeNode *new_root = createNode(0);new_root->childs[0] = node;*root = new_root;splitNode(new_root, 0);insert(root, key, cmp); // 遞歸插入return;}// 如果根節(jié)點(diǎn)既非空也未滿，直接插入while (1){if (node->is_leaf){insertKey(node, key, cmp);break;}int index = searchKeyIndex(node, key, cmp);if (node->childs[index]->num == BTREE_ORDER_SIZE - 1){splitNode(node, index);if (cmp(&key, &(node->keys[index])) > 0){index++;}}node = node->childs[index];}
}

打印B樹(shù), 可視化, 有利于理解B樹(shù)的插入規(guī)律.

// 打印B樹(shù)的關(guān)鍵字
void printBTree(BTreeNode *node, printFun printKey, int left, int *cnt)
{if (node){printf("%c%.2d([", "ABCDEFG"[left++], ++*cnt);for (int i = 0; i < node->num; i++){printKey(node->keys[i]);}printf("]);\n");if (!node->is_leaf){int leftL = left - 1;int cntL = *cnt;for (int i = 0; i <= node->num; i++){printf("%c%.2d==>", "ABCDEFG"[leftL], cntL);printBTree(node->childs[i], printKey, left, cnt);}printf("\n");}}
}

釋放B樹(shù), 傳入節(jié)點(diǎn)的二級(jí)指針, 最終確保隨后節(jié)點(diǎn)指針指向NULL, 使用遞歸, 因?yàn)楣?jié)點(diǎn)內(nèi)部都是數(shù)組和整型值, 沒(méi)有需要特殊處理的元素, 遞歸刪除整個(gè)節(jié)點(diǎn)指針即可.

// 釋放BTree
void freeBTree(BTreeNode **node)
{if (*node){// 非葉子節(jié)點(diǎn)必有子節(jié)點(diǎn), 遞歸刪除子節(jié)點(diǎn)if (!(*node)->is_leaf){// 子節(jié)點(diǎn)的數(shù)量不會(huì)大于key數(shù)量加1, 所以不用free child數(shù)組中所有節(jié)點(diǎn);for (int i = 0; i <= (*node)->num; i++){freeBTree(&((*node)->childs[i]));}}free(*node);*node = NULL;}
}

測(cè)試用例, 向B樹(shù)插入32個(gè)區(qū)間在0-999的整數(shù)值, 打印成mermaid文本, 可在markdown軟件下圖形化.

#include "BTree.h"
#include <stdlib.h>#define SIZE 32void printKey(keyOfBTree key)
{printf("%d\t", key);
}int cmpInt(const int *lhs, const int *rhs)
{return *lhs - *rhs;
}int main()
{int arr[SIZE];for (int i = 0; i != SIZE; ++i){arr[i] = rand() % 1000;}// 創(chuàng)建一個(gè)空的B樹(shù)BTree root = NULL;// 依次插入關(guān)鍵字for (int j = 0; j != SIZE; ++j){insert(&root, arr[j], (cmpFuncPtr)cmpInt);printf("```mermaid\ngraph TD;\nsubgraph BTree\n");int cnt = 0;// 打印B樹(shù)printBTree(root, printKey, 0, &cnt);printf("end\n```\n\n");}// 釋放內(nèi)存freeBTree(&root);return 0;
}

二、可視化

通過(guò)運(yùn)行測(cè)試用例, 導(dǎo)出mermaid文本, 可以在markdown編輯器中實(shí)現(xiàn)可視化, 看隨著輸入, 樹(shù)的分裂成長(zhǎng).

---

總結(jié)

通過(guò)以上的代碼, 基本可以粗略了解B-Tree的性質(zhì),

就是樹(shù)高增長(zhǎng)緩慢,

單節(jié)點(diǎn)可以存儲(chǔ)非常多的值,

查詢速度優(yōu)秀,

更貼近硬盤優(yōu)化,

我們常見(jiàn)的數(shù)據(jù)庫(kù), mysql, sqlite, postgresql的基礎(chǔ)都是B-Tree以及其變種, B+Tree,

了解底層, 期待更好的理解數(shù)據(jù)庫(kù), 在進(jìn)行數(shù)據(jù)庫(kù)設(shè)置時(shí), 可以進(jìn)行貼近底層的思考.

---

點(diǎn)擊 <C 語(yǔ)言編程核心突破> 快速C語(yǔ)言入門

---