1 二叉樹、多叉樹、B樹、B+樹
- 多叉樹與二叉樹對比：
樹需要加載到記憶體中，建構樹時，需要進行多次I/O操作。
如果節點非常多，會造成樹的高度非常大，降低操作速度。
多叉樹：降層高，結點數量變少，查找結點的次數就變少。（磁盤查找）
- 多叉樹與B樹的關系
1 多叉樹沒有限制平衡
2 沒有限制每個節點子樹的數量
3 周遊的時候資料是有順序的
- B+樹與B樹
1 所有資料存儲到葉子節點
2 所有葉子節點通過前後指針連結起來
- 資料庫用B+樹不用B樹
1 B樹隻适合随機檢索，而B+樹同時支援随機檢索和順序檢索
2 B+樹内部節點不存儲資料，隻存儲索引值，因為B+樹一個節點可以存儲更多的索引值，降低層數，減少了I/O次數，磁盤讀寫代價更低，I/O讀寫次數是影響索引檢索效率的最大因素
3 B+樹的查詢效率更加穩定。B樹搜尋有可能會在非葉子節點階數，約靠近根節點的記錄查找時間越短，其性能等價于在關鍵字全集内做一次二分查找。而在B+樹中，順序檢索比較明顯，随機檢索時，任何關鍵字的查找都必須走一條從根節點到葉節點的路，所有關鍵字的查找路徑相同，導緻每一個關鍵字的查詢效率相當
4 B樹在在基于範圍查詢的操作上的性能沒有B+樹好，因為B+樹的葉子節點使用了指針順序的連結在一起，隻要周遊葉子節點就可以實作整棵樹的周遊，相比較B+樹來說，由于B樹的葉子節點是互相獨立的，是以對于範圍查詢，需要從根節點再次出發查詢，增加了磁盤I/O操作次數
5 增删檔案（節點）時，效率更高，因為B+樹的葉子節點包含了所有關鍵字，并以有序的連結清單結構存儲，這樣可很好提高增删效率
一個頁4k
2 B樹的性質
一顆M階B樹T，滿足以下條件：
1 每個節點至少擁有M顆子樹
2 根節點至少有兩棵子樹
3 除了根節點外，其餘每個分支節點至少有M/2顆子樹
4 所有的葉節點都在同一層上
5 有k顆子樹的分支節點則存在k-1個關鍵字，關鍵字按照遞增順序進行排序
6 關鍵字數量滿足ceil(M/2)-1<=n<=M-1
3 B樹的實作
3.1 資料結構
typedef int KEY_VALUE;
// 結點資料結構
typedef struct _btree_node {
KEY_VALUE *keys; // key數組
struct _btree_node **childrens; // 子節點指針數組
int num; // 擁有子節點
int leaf; // 是否葉子節點，1是，0不是
} btree_node;
// 樹資料結構
typedef struct _btree {
btree_node *root; // 根節點
int t; // 2*t表示階數
} btree;
3.2 建立/删除結點、建立樹
- 建立結點，初始化結點的資料
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)); // 給key數組申請記憶體
node->childrens = (btree_node**)calloc(1, (2*t) * sizeof(btree_node*)); // 給子節點指針數組申請記憶體
node->num = 0; // 新節點沒有子節點
return node;
}
- 删除結點，釋放記憶體
void btree_destroy_node(btree_node *node) {
assert(node); // 傳進來的是空
free(node->childrens);
free(node->keys);
free(node);
}
- 建立樹，初始化資料
void btree_create(btree *T, int t) {
T->t = t;
btree_node *x = btree_create_node(t, 1); // 建立結點作為根節點，根節點是葉子節點leaf=1
T->root = x;
}
3.3 插入結點
插入結點時幾種情況：
1 找到插入的結點，并且未滿（插入點都是葉子節點）
2 找到結點，已滿:
2.1 找内節點已滿，内節點分裂
2.2 找葉子結點已滿，葉子節點分裂
分解出兩個基本操作：分裂結點，在不滿的節點裡插入
- 分裂節點
root的分裂與其他節點的分裂有一點不同，但是這個基本操作是一樣的
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; // 共2t-1個結點，分類後兩邊各t-1，中間的移到父節點上
// 1. 把y結點右邊的拷貝給z
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];
}
}
// 2. 把y的左邊分割出來
y->num = t - 1;
// 3.把中間的結點移動到父節點x裡
for (j = x->num;j >= i+1;j --) { // 結點後移
x->childrens[j+1] = x->childrens[j];
}
x->childrens[i+1] = z; // 中間結點放上去
// 更新x的key和num
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;
}
- 在不滿的節點裡插入
1 如果是葉子節點直接插入
2 如果是内節點，找到對應子節點，如果子節點滿了先分裂在插入。
void btree_insert_nonfull(btree *T, btree_node *x, KEY_VALUE k) {
int i = x->num - 1;
// 葉子節點插入
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 {
while (i >= 0 && x->keys[i] > k) i --;
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_nonfull(T, x->childrens[i+1], k);
}
}
- 插入節點整體流程
void btree_insert(btree *T, KEY_VALUE key) {
//int t = T->t;
btree_node *r = T->root;
// 如果是root結點滿了
if (r->num == 2 * T->t - 1) {
// 建立一個新的根節點，第一個children指向原來的根節點，就跟其他節點一樣了
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++; // 如果插入的key大，則在右邊插入（下标1），否咋在左邊插入（下标0）
btree_insert_nonfull(T, node->childrens[i], key);
} else {
// 如果根節點沒滿，按照非滿插入，
btree_insert_nonfull(T, r, key);
}
}
3.4 删除資料
删除節點後可能不滿足可能會不滿足B樹的性質，至少M/2顆子樹。
判斷子樹key數量是不是M/2-1
如果相鄰子樹都是M/2-1，合并。
如果左邊子樹大于M/2-1，借一個結點。
如果右邊子樹大于M/2-1，借一個結點。
4 B+樹應用場景
B+樹主要用在磁盤檔案組織、資料索引和資料庫索引。
![樹的基本概念(定義、基本術語、性質)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)