算法导论第十四章 B树与B+树：海量数据的守护者

第十四章 B树与B+树：海量数据的守护者

“数据不是信息，信息不是知识，知识不是理解。” —— Clifford Stoll
在信息爆炸的时代，我们需要高效管理海量数据的能力。B树家族作为数据库和文件系统的基石，完美平衡了磁盘I/O效率和内存利用率，成为处理大规模数据的首选数据结构。

14.1 B树的诞生背景

14.1.1 磁盘与内存的速度鸿沟

现代计算机系统中，磁盘访问速度比内存慢10万倍以上。当数据量超过内存容量时，传统二叉搜索树因树高过大导致磁盘I/O次数激增：

14.1.2 B树的设计哲学

1970年，Rudolf Bayer和Edward M. McCreight发明了B树，核心思想是：

1. 增大节点容量：每个节点存储多个键值
2. 降低树高：通过多路分支减少磁盘访问
3. 平衡操作：节点分裂与合并保持平衡

14.2 B树的定义与性质

14.2.1 形式化定义

一棵B树T是具有以下性质的有根树：

1. 每个节点x包含：
   • n[x]：当前存储的键数
   • key₁[x] ≤ key₂[x] ≤ … ≤ keyₙ[x]：有序键值
   • leaf[x]：布尔值，指示是否为叶节点
2. 内部节点包含n[x]+1个指针c₁[x], c₂[x], …, cₙ₊₁[x]指向子节点
3. 键值分隔子树范围：∀k ∈ subtree(cᵢ[x]), keyᵢ₋₁[x] ≤ k ≤ keyᵢ[x]
4. 所有叶节点深度相同
5. 节点键数限制：
   • 根节点：至少1个键（除非树为空）
   • 其他节点：t-1 ≤ n ≤ 2t-1（t为最小度数）

#define B_TREE_MIN_DEGREE 3
#define MAX_KEYS (2 * B_TREE_MIN_DEGREE - 1)
#define MIN_KEYS (B_TREE_MIN_DEGREE - 1)
#define MAX_CHILDREN (2 * B_TREE_MIN_DEGREE)

typedef struct BTreeNode {
    int n;                          // 当前键数
    int keys[MAX_KEYS];             // 键数组
    struct BTreeNode *children[MAX_CHILDREN]; // 子节点指针
    bool is_leaf;                   // 是否为叶节点
} BTreeNode;

typedef struct {
    BTreeNode *root;
    int t; // 最小度数
} BTree;

14.2.2 B树可视化示例(t=2)

14.3 B树的核心操作

14.3.1 搜索操作

B树搜索是二叉搜索树的多路推广：

BTreeNode* b_tree_search(BTreeNode *node, int key) {
    int i = 0;
    while (i < node->n && key > node->keys[i]) 
        i++;
    
    if (i < node->n && key == node->keys[i])
        return node;
    
    if (node->is_leaf)
        return NULL;
    
    // 从磁盘读取子节点
    return b_tree_search(node->children[i], key);
}

搜索路径示例：在t=3的B树中查找38

根节点: [20, 40, 60] → 选择第2子树(20<38≤40)
子节点: [30, 35, 38] → 找到键38

14.3.2 插入操作

插入操作需要防止节点溢出（>2t-1键），通过分裂和提升保持平衡：

节点分裂实现

void b_tree_split_child(BTree *tree, BTreeNode *parent, int index) {
    BTreeNode *full_child = parent->children[index];
    BTreeNode *new_child = b_tree_create_node(full_child->is_leaf);
    
    // 新节点获取后半部分键
    new_child->n = tree->t - 1;
    for (int j = 0; j < tree->t - 1; j++) {
        new_child->keys[j] = full_child->keys[j + tree->t];
    }
    
    // 若非叶节点，复制子指针
    if (!full_child->is_leaf) {
        for (int j = 0; j < tree->t; j++) {
            new_child->children[j] = full_child->children[j + tree->t];
        }
    }
    full_child->n = tree->t - 1;
    
    // 调整父节点
    for (int j = parent->n; j >= index + 1; j--) {
        parent->children[j + 1] = parent->children[j];
    }
    parent->children[index + 1] = new_child;
    
    for (int j = parent->n - 1; j >= index; j--) {
        parent->keys[j + 1] = parent->keys[j];
    }
    parent->keys[index] = full_child->keys[tree->t - 1];
    parent->n++;
}

14.3.3 删除操作

删除需要防止节点下溢（<t-1键），通过借键、合并和重分布保持平衡：

合并节点实现

void b_tree_merge(BTree *tree, BTreeNode *node, int index) {
    BTreeNode *child = node->children[index];
    BTreeNode *sibling = node->children[index + 1];
    
    // 将父节点键下移
    child->keys[tree->t - 1] = node->keys[index];
    
    // 复制兄弟键
    for (int i = 0; i < sibling->n; i++) {
        child->keys[i + tree->t] = sibling->keys[i];
    }
    
    // 复制兄弟子指针
    if (!child->is_leaf) {
        for (int i = 0; i <= sibling->n; i++) {
            child->children[i + tree->t] = sibling->children[i];
        }
    }
    
    // 调整父节点
    for (int i = index + 1; i < node->n; i++) {
        node->keys[i - 1] = node->keys[i];
    }
    for (int i = index + 2; i <= node->n; i++) {
        node->children[i - 1] = node->children[i];
    }
    
    child->n += sibling->n + 1;
    node->n--;
    
    free(sibling);
}

14.4 B树的性能分析

14.4.1 空间利用率

14.4.2 树高与I/O次数

对于包含n个键、最小度数为t的B树：

• 最小高度：$h_{min}=\lceil {\log }_t(n+1)\rceil -1$
• 最大高度：$h_{max}=\lfloor {\log }_t\frac{n+1}{2}\rfloor$

磁盘I/O次数：操作复杂度 $O(h)=O({\log }_{t}n)$

14.5 B+树：数据库的引擎

14.5.1 B+树与B树的区别

14.5.2 B+树节点结构

typedef struct BPlusTreeNode {
    int n;
    int keys[MAX_KEYS];
    union {
        struct BPlusTreeNode *children[MAX_CHILDREN]; // 内部节点使用
        struct {
            void *data_ptrs[MAX_KEYS]; // 叶节点使用
            struct BPlusTreeNode *next; // 下一个叶节点
            struct BPlusTreeNode *prev; // 上一个叶节点
        };
    };
    bool is_leaf;
} BPlusTreeNode;

14.5.3 B+树范围查询

void b_plus_tree_range_query(BPlusTree *tree, int start, int end) {
    BPlusTreeNode *start_node = b_plus_tree_find_leaf(tree, start);
    BPlusTreeNode *current = start_node;
    int index = 0;
    
    while (current) {
        // 找到当前节点中≥start的键
        while (index < current->n && current->keys[index] < start)
            index++;
        
        // 遍历当前节点
        while (index < current->n && current->keys[index] <= end) {
            printf("键: %d, 数据地址: %p\n", 
                  current->keys[index], 
                  current->data_ptrs[index]);
            index++;
        }
        
        if (index >= current->n) {
            current = current->next; // 跳转到下一个叶节点
            index = 0;
        } else {
            break;
        }
    }
}

14.6 B树在数据库中的应用

14.6.1 数据库索引结构

14.6.2 InnoDB存储引擎

MySQL的InnoDB使用B+树组织数据：

• 聚簇索引：主键索引，叶节点包含完整行数据
• 二级索引：辅助索引，叶节点存储主键值

// InnoDB索引项结构
typedef struct {
    uint32_t page_no;   // 页号
    uint16_t page_offset; // 页内偏移
    uint8_t record_type; // 记录类型
    uint8_t info_bits;   // 信息位
    uint16_t n_fields;   // 字段数
    // 字段数据...
} innodb_index_entry;

14.6.3 索引优化实践

1. 覆盖索引：索引包含查询所需所有字段
2. 前缀索引：对字符串前N字符建立索引
3. 索引下推：在存储引擎层过滤数据
4. MRR优化：Multi-Range Read顺序访问磁盘

14.7 B树在文件系统中的应用

14.7.1 现代文件系统对比

14.7.2 ext4文件系统目录索引

// ext4目录项结构
struct ext4_dir_entry {
    __le32 inode;         // Inode号
    __le16 rec_len;       // 目录项长度
    __le16 name_len;      // 文件名长度
    char name[EXT4_NAME_LEN]; // 文件名
};

// 目录索引节点
struct dx_root {
    struct dx_countlimit countlimit; // 限制信息
    struct dx_entry entries[];       // 索引项
};

14.8 完整B+树实现

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

#define ORDER 4
#define MAX_KEYS (ORDER - 1)
#define MIN_KEYS (ORDER / 2 - 1)

typedef struct BPlusTreeNode {
    int keys[MAX_KEYS + 1]; // 多出一个用于临时存储
    void *pointers[ORDER + 1];
    struct BPlusTreeNode *parent;
    bool is_leaf;
    int num_keys;
    struct BPlusTreeNode *next; // 仅叶节点使用
} BPlusTreeNode;

typedef struct {
    BPlusTreeNode *root;
} BPlusTree;

BPlusTreeNode* create_node(bool is_leaf) {
    BPlusTreeNode *node = (BPlusTreeNode*)malloc(sizeof(BPlusTreeNode));
    node->is_leaf = is_leaf;
    node->num_keys = 0;
    node->parent = NULL;
    node->next = NULL;
    memset(node->keys, 0, sizeof(node->keys));
    memset(node->pointers, 0, sizeof(node->pointers));
    return node;
}

BPlusTree* create_b_plus_tree() {
    BPlusTree *tree = (BPlusTree*)malloc(sizeof(BPlusTree));
    tree->root = create_node(true); // 初始为叶节点
    return tree;
}

BPlusTreeNode* find_leaf(BPlusTreeNode *node, int key) {
    if (node == NULL) return NULL;
    
    while (!node->is_leaf) {
        int i = 0;
        while (i < node->num_keys && key >= node->keys[i]) {
            i++;
        }
        node = (BPlusTreeNode*)node->pointers[i];
    }
    return node;
}

void insert_into_leaf(BPlusTreeNode *leaf, int key, void *value) {
    int i = 0;
    while (i < leaf->num_keys && leaf->keys[i] < key) {
        i++;
    }
    
    // 移动键和指针
    for (int j = leaf->num_keys; j > i; j--) {
        leaf->keys[j] = leaf->keys[j - 1];
        leaf->pointers[j] = leaf->pointers[j - 1];
    }
    
    leaf->keys[i] = key;
    leaf->pointers[i] = value;
    leaf->num_keys++;
}

void insert_into_parent(BPlusTree *tree, BPlusTreeNode *left, 
                       int key, BPlusTreeNode *right) {
    if (left->parent == NULL) {
        // 创建新根
        BPlusTreeNode *new_root = create_node(false);
        new_root->keys[0] = key;
        new_root->pointers[0] = left;
        new_root->pointers[1] = right;
        new_root->num_keys = 1;
        left->parent = new_root;
        right->parent = new_root;
        tree->root = new_root;
        return;
    }
    
    BPlusTreeNode *parent = left->parent;
    int insert_index = 0;
    while (insert_index < parent->num_keys && 
           parent->pointers[insert_index] != left) {
        insert_index++;
    }
    
    if (parent->num_keys < MAX_KEYS) {
        // 父节点有空间
        for (int j = parent->num_keys; j > insert_index; j--) {
            parent->keys[j] = parent->keys[j - 1];
            parent->pointers[j + 1] = parent->pointers[j];
        }
        
        parent->keys[insert_index] = key;
        parent->pointers[insert_index + 1] = right;
        parent->num_keys++;
        right->parent = parent;
    } else {
        // 父节点分裂
        // 简化实现：省略分裂代码
        printf("父节点分裂未实现\n");
    }
}

void b_plus_tree_insert(BPlusTree *tree, int key, void *value) {
    // 1. 找到应插入的叶节点
    BPlusTreeNode *leaf = find_leaf(tree->root, key);
    
    // 2. 检查叶节点是否有空间
    if (leaf->num_keys < MAX_KEYS) {
        insert_into_leaf(leaf, key, value);
    } else {
        // 叶节点分裂
        BPlusTreeNode *new_leaf = create_node(true);
        int temp_keys[MAX_KEYS + 1];
        void *temp_pointers[MAX_KEYS + 1];
        
        // 复制原始键和指针
        for (int i = 0; i < MAX_KEYS; i++) {
            temp_keys[i] = leaf->keys[i];
            temp_pointers[i] = leaf->pointers[i];
        }
        
        // 插入新键
        int i = 0;
        while (i < MAX_KEYS && key > temp_keys[i]) {
            i++;
        }
        for (int j = MAX_KEYS; j > i; j--) {
            temp_keys[j] = temp_keys[j - 1];
            temp_pointers[j] = temp_pointers[j - 1];
        }
        temp_keys[i] = key;
        temp_pointers[i] = value;
        
        // 分裂叶节点
        leaf->num_keys = MIN_KEYS + 1;
        new_leaf->num_keys = MIN_KEYS + 1;
        
        for (i = 0; i < leaf->num_keys; i++) {
            leaf->keys[i] = temp_keys[i];
            leaf->pointers[i] = temp_pointers[i];
        }
        
        for (i = 0; i < new_leaf->num_keys; i++) {
            new_leaf->keys[i] = temp_keys[i + leaf->num_keys];
            new_leaf->pointers[i] = temp_pointers[i + leaf->num_keys];
        }
        
        // 更新叶节点链表
        new_leaf->next = leaf->next;
        leaf->next = new_leaf;
        new_leaf->parent = leaf->parent;
        
        // 提升新叶节点的第一个键
        int promote_key = new_leaf->keys[0];
        insert_into_parent(tree, leaf, promote_key, new_leaf);
    }
}

void print_b_plus_tree(BPlusTreeNode *node, int level) {
    if (node == NULL) return;
    
    printf("Level %d: ", level);
    for (int i = 0; i < node->num_keys; i++) {
        printf("%d ", node->keys[i]);
    }
    printf("\n");
    
    if (!node->is_leaf) {
        for (int i = 0; i <= node->num_keys; i++) {
            print_b_plus_tree(node->pointers[i], level + 1);
        }
    }
}

int main() {
    BPlusTree *tree = create_b_plus_tree();
    
    // 插入示例数据
    int data[] = {10, 20, 5, 15, 30, 25, 35, 40, 45, 50, 55};
    int n = sizeof(data)/sizeof(data[0]);
    
    for (int i = 0; i < n; i++) {
        b_plus_tree_insert(tree, data[i], NULL);
    }
    
    printf("B+树结构:\n");
    print_b_plus_tree(tree->root, 0);
    
    // 模拟范围查询
    printf("\n范围查询[25, 45]:\n");
    BPlusTreeNode *leaf = find_leaf(tree->root, 25);
    while (leaf) {
        for (int i = 0; i < leaf->num_keys; i++) {
            if (leaf->keys[i] >= 25 && leaf->keys[i] <= 45) {
                printf("%d ", leaf->keys[i]);
            }
        }
        leaf = leaf->next;
    }
    
    return 0;
}

14.9 B树变种与创新

14.9.1 现代B树变种

14.9.2 LSM树 vs B+树

14.10 总结与下一章预告

B树家族通过精心设计的节点结构和平衡算法，在磁盘与内存之间架起了高效的数据桥梁：

1. 节点优化：增大节点大小匹配磁盘块
2. 平衡策略：分裂与合并保持树平衡
3. 高效查询：对数时间复杂度保证性能
4. 范围优化：B+树叶节点链表加速范围查询

下一章预告：斐波那契堆

第十五章我们将探索斐波那契堆——这种神奇的数据结构将带来前所未有的操作效率：

• 平摊常数时间的插入和合并
• 高效减少键值操作
• 图算法中的革命性应用
• 懒惰操作与延迟合并的智慧

斐波那契堆如同数据结构领域的"瑞士军刀"，在特定场景下展现出惊人的性能优势，特别是Dijkstra最短路径算法和Prim最小生成树算法。

B树家族的创新永无止境，从传统关系型数据库到现代分布式存储系统，它们持续为海量数据管理提供可靠高效的解决方案。掌握B树不仅理解了一个数据结构，更获得了处理大规模数据的核心思维模式。