第06课：B树原理

索引结构 第6课 / 共25课

📖 课程概述

B树(B-Tree)是数据库索引最常用的数据结构，几乎所有关系型数据库都使用B树或其变种作为主要索引结构。本课从二叉搜索树的局限性出发，逐步推导出B树的设计动机，实现完整的B树插入、查找和删除操作。

🌳 从BST到B树的演进

B树定义（阶数m）

• 每个节点最多有m个子节点
• 每个非叶非根节点至少有⌈m/2⌉个子节点
• 根节点至少有2个子节点(如果不是叶)
• 有k个子节点的节点包含k-1个键
• 所有叶节点在同一层

💻 C语言实现：完整B树

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ORDER 5          // B树阶数
#define MAX_KEYS (ORDER-1)
#define MIN_KEYS ((ORDER+1)/2 - 1)

typedef struct BTreeNode {
    int keys[ORDER];         // 键数组(多一个用于临时溢出)
    void* values[ORDER+1];   // 值/子节点指针
    struct BTreeNode* children[ORDER+1];
    int num_keys;
    int is_leaf;
} BTreeNode;

BTreeNode* btree_create_node(int is_leaf) {
    BTreeNode* node = calloc(1, sizeof(BTreeNode));
    node->is_leaf = is_leaf;
    node->num_keys = 0;
    return node;
}

// 在节点中查找键的位置
int find_key_index(BTreeNode* node, int key) {
    int idx = 0;
    while (idx < node->num_keys && node->keys[idx] < key)
        idx++;
    return idx;
}

// 查找操作
void* btree_search(BTreeNode* root, int key) {
    if (!root) return NULL;
    int idx = find_key_index(root, key);
    if (idx < root->num_keys && root->keys[idx] == key) {
        printf("  [BTree] 找到键 %d\n", key);
        return root->values[idx];
    }
    if (root->is_leaf) {
        printf("  [BTree] 键 %d 不存在\n", key);
        return NULL;
    }
    return btree_search(root->children[idx], key);
}

// 分裂子节点
void split_child(BTreeNode* parent, int idx) {
    BTreeNode* full = parent->children[idx];
    BTreeNode* new_node = btree_create_node(full->is_leaf);

    // 中间键提升到父节点
    int mid = MAX_KEYS / 2;
    int mid_key = full->keys[mid];

    // 新节点获取右半部分
    new_node->num_keys = full->num_keys - mid - 1;
    for (int i = 0; i < new_node->num_keys; i++) {
        new_node->keys[i] = full->keys[mid + 1 + i];
        new_node->values[i] = full->values[mid + 1 + i];
    }
    if (!full->is_leaf) {
        for (int i = 0; i <= new_node->num_keys; i++) {
            new_node->children[i] = full->children[mid + 1 + i];
        }
    }

    // 原节点只保留左半部分
    full->num_keys = mid;

    // 父节点腾出位置
    for (int i = parent->num_keys; i > idx; i--) {
        parent->keys[i] = parent->keys[i - 1];
        parent->values[i] = parent->values[i - 1];
        parent->children[i + 1] = parent->children[i];
    }
    parent->keys[idx] = mid_key;
    parent->values[idx] = full->values[mid];
    parent->children[idx + 1] = new_node;
    parent->num_keys++;

    printf("  [BTree] 分裂: 键 %d 提升\n", mid_key);
}

// 插入到非满节点
void insert_non_full(BTreeNode* node, int key, void* value) {
    int idx = node->num_keys - 1;

    if (node->is_leaf) {
        // 找到插入位置并移动
        while (idx >= 0 && node->keys[idx] > key) {
            node->keys[idx + 1] = node->keys[idx];
            node->values[idx + 1] = node->values[idx];
            idx--;
        }
        node->keys[idx + 1] = key;
        node->values[idx + 1] = value;
        node->num_keys++;
    } else {
        // 找子节点
        while (idx >= 0 && node->keys[idx] > key) idx--;
        idx++;
        // 检查子节点是否满了
        if (node->children[idx]->num_keys == MAX_KEYS) {
            split_child(node, idx);
            if (key > node->keys[idx]) idx++;
        }
        insert_non_full(node->children[idx], key, value);
    }
}

// 插入操作
BTreeNode* btree_insert(BTreeNode* root, int key, void* value) {
    if (!root) {
        root = btree_create_node(1);
        root->keys[0] = key;
        root->values[0] = value;
        root->num_keys = 1;
        return root;
    }
    // 根节点满了？需要分裂根
    if (root->num_keys == MAX_KEYS) {
        BTreeNode* new_root = btree_create_node(0);
        new_root->children[0] = root;
        split_child(new_root, 0);
        insert_non_full(new_root, key, value);
        printf("  [BTree] 根节点分裂，树高度+1\n");
        return new_root;
    }
    insert_non_full(root, key, value);
    return root;
}

// 遍历打印
void btree_traverse(BTreeNode* root, int depth) {
    if (!root) return;
    printf("%*s[", depth * 2, "");
    for (int i = 0; i < root->num_keys; i++) {
        printf("%d", root->keys[i]);
        if (i < root->num_keys - 1) printf(",");
    }
    printf("]\n");
    if (!root->is_leaf) {
        for (int i = 0; i <= root->num_keys; i++) {
            btree_traverse(root->children[i], depth + 1);
        }
    }
}

// 查找前驱(左子树最大键)
int find_predecessor(BTreeNode* node) {
    while (!node->is_leaf) node = node->children[node->num_keys];
    return node->keys[node->num_keys - 1];
}

// 查找后继(右子树最小键)
int find_successor(BTreeNode* node) {
    while (!node->is_leaf) node = node->children[0];
    return node->keys[0];
}

// 合并两个子节点
void merge_children(BTreeNode* node, int idx) {
    BTreeNode* left = node->children[idx];
    BTreeNode* right = node->children[idx + 1];

    // 将父节点的键下移
    left->keys[left->num_keys] = node->keys[idx];
    left->values[left->num_keys] = node->values[idx];
    left->num_keys++;

    // 复制右节点的键和子节点
    for (int i = 0; i < right->num_keys; i++) {
        left->keys[left->num_keys + i] = right->keys[i];
        left->values[left->num_keys + i] = right->values[i];
    }
    if (!left->is_leaf) {
        for (int i = 0; i <= right->num_keys; i++) {
            left->children[left->num_keys + i] = right->children[i];
        }
    }
    left->num_keys += right->num_keys;

    // 从父节点移除下移的键
    for (int i = idx; i < node->num_keys - 1; i++) {
        node->keys[i] = node->keys[i + 1];
        node->values[i] = node->values[i + 1];
        node->children[i + 1] = node->children[i + 2];
    }
    node->num_keys--;

    free(right);
    printf("  [BTree] 合并子节点 %d\n", idx);
}

// 从左兄弟借键
void borrow_from_left(BTreeNode* node, int idx) {
    BTreeNode* child = node->children[idx];
    BTreeNode* sibling = node->children[idx - 1];

    // 右移child的键
    for (int i = child->num_keys; i > 0; i--) {
        child->keys[i] = child->keys[i - 1];
        child->values[i] = child->values[i - 1];
    }
    if (!child->is_leaf) {
        for (int i = child->num_keys + 1; i > 0; i--)
            child->children[i] = child->children[i - 1];
    }

    // 父节点键下移
    child->keys[0] = node->keys[idx - 1];
    child->values[0] = node->values[idx - 1];
    if (!child->is_leaf)
        child->children[0] = sibling->children[sibling->num_keys];

    // 兄弟最大键上移
    node->keys[idx - 1] = sibling->keys[sibling->num_keys - 1];
    node->values[idx - 1] = sibling->values[sibling->num_keys - 1];

    child->num_keys++;
    sibling->num_keys--;
    printf("  [BTree] 从左兄弟借键\n");
}

// 从右兄弟借键
void borrow_from_right(BTreeNode* node, int idx) {
    BTreeNode* child = node->children[idx];
    BTreeNode* sibling = node->children[idx + 1];

    // 父节点键下移
    child->keys[child->num_keys] = node->keys[idx];
    child->values[child->num_keys] = node->values[idx];
    if (!child->is_leaf)
        child->children[child->num_keys + 1] = sibling->children[0];

    // 兄弟最小键上移
    node->keys[idx] = sibling->keys[0];
    node->values[idx] = sibling->values[0];

    // 左移sibling的键
    for (int i = 0; i < sibling->num_keys - 1; i++) {
        sibling->keys[i] = sibling->keys[i + 1];
        sibling->values[i] = sibling->values[i + 1];
    }
    if (!sibling->is_leaf) {
        for (int i = 0; i < sibling->num_keys; i++)
            sibling->children[i] = sibling->children[i + 1];
    }

    child->num_keys++;
    sibling->num_keys--;
    printf("  [BTree] 从右兄弟借键\n");
}

// 删除操作
BTreeNode* btree_delete(BTreeNode* root, int key) {
    if (!root) return NULL;

    int idx = find_key_index(root, key);

    // 键在当前节点
    if (idx < root->num_keys && root->keys[idx] == key) {
        if (root->is_leaf) {
            // 叶子节点直接删除
            for (int i = idx; i < root->num_keys - 1; i++) {
                root->keys[i] = root->keys[i + 1];
                root->values[i] = root->values[i + 1];
            }
            root->num_keys--;
            printf("  [BTree] 从叶节点删除键 %d\n", key);
        } else {
            // 内部节点：用前驱或后继替换
            if (root->children[idx]->num_keys > MIN_KEYS) {
                int pred = find_predecessor(root->children[idx]);
                root->keys[idx] = pred;
                root->children[idx] = btree_delete(root->children[idx], pred);
            } else if (root->children[idx + 1]->num_keys > MIN_KEYS) {
                int succ = find_successor(root->children[idx + 1]);
                root->keys[idx] = succ;
                root->children[idx + 1] = btree_delete(root->children[idx + 1], succ);
            } else {
                merge_children(root, idx);
                root->children[idx] = btree_delete(root->children[idx], key);
            }
        }
    } else {
        // 键不在当前节点，递归到子节点
        if (root->is_leaf) {
            printf("  [BTree] 键 %d 不存在\n", key);
            return root;
        }
        // 确保子节点有足够的键
        if (root->children[idx]->num_keys <= MIN_KEYS) {
            if (idx > 0 && root->children[idx - 1]->num_keys > MIN_KEYS) {
                borrow_from_left(root, idx);
            } else if (idx < root->num_keys && root->children[idx + 1]->num_keys > MIN_KEYS) {
                borrow_from_right(root, idx);
            } else {
                if (idx < root->num_keys) merge_children(root, idx);
                else merge_children(root, idx - 1);
            }
        }
        root->children[idx] = btree_delete(root->children[idx], key);
    }

    // 根节点变空
    if (root->num_keys == 0) {
        BTreeNode* new_root = root->is_leaf ? NULL : root->children[0];
        if (new_root) printf("  [BTree] 根节点合并，树高度-1\n");
        free(root);
        return new_root;
    }
    return root;
}

// ========== 主函数 ==========
int main() {
    printf("╔══════════════════════════════════════╗\n");
    printf("║   B树实现 (阶数=%d)                  ║\n", ORDER);
    printf("╚══════════════════════════════════════╝\n\n");

    BTreeNode* root = NULL;

    // 插入测试
    printf("--- 插入测试 ---\n");
    int keys[] = {10, 20, 5, 6, 12, 30, 7, 17, 3, 16, 22, 35, 40, 45};
    for (int i = 0; i < 14; i++) {
        printf("插入 %d:\n", keys[i]);
        root = btree_insert(root, keys[i], (void*)(long)keys[i]);
    }

    printf("\n--- B树结构 ---\n");
    btree_traverse(root, 0);

    // 查找测试
    printf("\n--- 查找测试 ---\n");
    btree_search(root, 12);
    btree_search(root, 17);
    btree_search(root, 99);

    // 删除测试
    printf("\n--- 删除测试 ---\n");
    root = btree_delete(root, 6);
    root = btree_delete(root, 20);
    root = btree_delete(root, 30);

    printf("\n--- 删除后B树结构 ---\n");
    btree_traverse(root, 0);

    printf("\n✅ B树实现运行完成\n");
    return 0;
}

🐍 Python实现：B树可视化

"""
B树可视化与性能测试
"""
from collections import deque

class BTreeNode:
    def __init__(self, leaf=True, order=5):
        self.keys = []
        self.children = []
        self.leaf = leaf
        self.order = order

    @property
    def max_keys(self): return self.order - 1
    @property
    def min_keys(self): return (self.order + 1) // 2 - 1

class BTree:
    def __init__(self, order=5):
        self.root = BTreeNode(leaf=True, order=order)
        self.order = order
        self.splits = 0
        self.merges = 0

    def search(self, key):
        return self._search(self.root, key)

    def _search(self, node, key):
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1
        if i < len(node.keys) and node.keys[i] == key:
            return node
        if node.leaf:
            return None
        return self._search(node.children[i], key)

    def insert(self, key):
        root = self.root
        if len(root.keys) == root.max_keys:
            new_root = BTreeNode(leaf=False, order=self.order)
            new_root.children.append(self.root)
            self._split_child(new_root, 0)
            self.root = new_root
            self.splits += 1
        self._insert_non_full(self.root, key)

    def _split_child(self, parent, idx):
        child = parent.children[idx]
        mid = len(child.keys) // 2
        new_node = BTreeNode(leaf=child.leaf, order=self.order)
        mid_key = child.keys[mid]

        new_node.keys = child.keys[mid+1:]
        child.keys = child.keys[:mid]

        if not child.leaf:
            new_node.children = child.children[mid+1:]
            child.children = child.children[:mid+1]

        parent.keys.insert(idx, mid_key)
        parent.children.insert(idx + 1, new_node)

    def _insert_non_full(self, node, key):
        i = len(node.keys) - 1
        if node.leaf:
            while i >= 0 and key < node.keys[i]:
                i -= 1
            if i >= 0 and node.keys[i] == key:
                return  # duplicate
            node.keys.insert(i + 1, key)
        else:
            while i >= 0 and key < node.keys[i]:
                i -= 1
            i += 1
            if len(node.children[i].keys) == node.children[i].max_keys:
                self._split_child(node, i)
                self.splits += 1
                if key > node.keys[i]:
                    i += 1
            self._insert_non_full(node.children[i], key)

    def delete(self, key):
        self._delete(self.root, key)
        if len(self.root.keys) == 0 and not self.root.leaf:
            self.root = self.root.children[0]

    def _delete(self, node, key):
        # 简化实现：先收集所有键，删除目标，重建B树
        all_keys = self._collect_keys(node)
        if key in all_keys:
            all_keys.remove(key)
            self.root = BTreeNode(leaf=True, order=self.order)
            for k in all_keys:
                self.insert(k)
            self.merges += 1

    def _collect_keys(self, node):
        if node.leaf:
            return list(node.keys)
        keys = []
        for i, child in enumerate(node.children):
            keys.extend(self._collect_keys(child))
            if i < len(node.keys):
                keys.append(node.keys[i])
        return keys

    def height(self):
        h = 0
        node = self.root
        while node and not node.leaf:
            node = node.children[0]
            h += 1
        return h + 1 if node else 0

    def print_tree(self):
        queue = deque([(self.root, 0)])
        level = 0
        while queue:
            node, lvl = queue.popleft()
            if lvl > level:
                print()
                level = lvl
            print(f"[{' '.join(map(str, node.keys))}]", end=" ")
            if not node.leaf:
                for child in node.children:
                    queue.append((child, lvl + 1))
        print()

# ========== 性能测试 ==========
import time, random

def benchmark_btree(order, n):
    bt = BTree(order=order)
    random.seed(42)
    keys = list(range(n))
    random.shuffle(keys)

    t0 = time.perf_counter()
    for k in keys:
        bt.insert(k)
    insert_time = time.perf_counter() - t0

    t0 = time.perf_counter()
    for k in range(n):
        bt.search(k % n)
    search_time = time.perf_counter() - t0

    return bt.height(), bt.splits, insert_time*1000, search_time*1000

print(f"{'阶数':>6} | {'高度':>4} | {'分裂次数':>8} | {'插入ms':>8} | {'查找ms':>8}")
print("-" * 50)
for order in [5, 10, 20, 50, 100]:
    h, s, it, st = benchmark_btree(order, 10000)
    print(f"{order:>6} | {h:>4} | {s:>8} | {it:>7.1f} | {st:>7.1f}")

# 可视化
print("\n=== 阶数5 B树(插入20个键) ===")
bt5 = BTree(order=5)
for i in [10,20,5,6,12,30,7,17,3,16,22,35,40,45,8,9,1,2,50,55]:
    bt5.insert(i)
bt5.print_tree()
print(f"高度: {bt5.height()}, 分裂: {bt5.splits}")
print("\n✅ Python B树实现完成")

📊 性能分析

🔑 关键概念总结