第22课：B+树存储引擎

实战项目 第22课 / 共25课

📖 课程概述

本课在KV存储的基础上，实现一个完整的B+树存储引擎。B+树引擎支持范围查询、有序扫描和事务，是关系型数据库存储引擎的核心。我们将实现B+树的磁盘持久化、页面管理和事务支持。

💻 C语言实现：B+树存储引擎

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <assert.h>

#define ORDER       6
#define MAX_KEYS    (ORDER - 1)
#define PAGE_SIZE   4096
#define MAX_PAGES   256
#define MAX_VAL     128
#define BUFFER_SIZE 32

// ===== 页面定义 =====
typedef uint32_t PageID;

typedef struct {
    int      key;
    char     value[MAX_VAL];
    uint32_t txn_id;
    uint8_t  deleted;
} Record;

typedef struct BPTPage {
    PageID   page_id;
    int      is_leaf;
    int      keys[ORDER + 1];
    Record   records[ORDER + 1];  // 叶子节点数据
    PageID   children[ORDER + 2]; // 内部节点子页ID
    PageID   next_leaf;           // 叶子链表
    int      num_keys;
    int      dirty;
    int      pin_count;
    int      ref_bit;
} BPTPage;

// ===== 缓冲池 =====
typedef struct {
    BPTPage* pages[MAX_PAGES];
    int      num_pages;
    int      clock_hand;
    int      hits;
    int      misses;
} BufferPool;

BufferPool* bp_create() {
    BufferPool* pool = calloc(1, sizeof(BufferPool));
    return pool;
}

BPTPage* bp_fetch(BufferPool* pool, PageID pid) {
    for (int i = 0; i < pool->num_pages; i++) {
        if (pool->pages[i]->page_id == pid) {
            pool->hits++;
            pool->pages[i]->ref_bit = 1;
            pool->pages[i]->pin_count++;
            return pool->pages[i];
        }
    }
    pool->misses++;
    BPTPage* page = calloc(1, sizeof(BPTPage));
    page->page_id = pid;
    page->pin_count = 1;
    page->ref_bit = 1;
    if (pool->num_pages < MAX_PAGES) {
        pool->pages[pool->num_pages++] = page;
    } else {
        // Clock替换(简化)
        int found = 0;
        for (int scan = 0; scan < MAX_PAGES * 2; scan++) {
            BPTPage* p = pool->pages[pool->clock_hand];
            if (p->pin_count == 0) {
                if (p->ref_bit) {
                    p->ref_bit = 0;
                } else {
                    if (p->dirty) printf("  [BP] Flush dirty page %u\n", p->page_id);
                    free(p);
                    pool->pages[pool->clock_hand] = page;
                    found = 1;
                    break;
                }
            }
            pool->clock_hand = (pool->clock_hand + 1) % pool->num_pages;
        }
        if (!found) { free(page); return NULL; }
    }
    return page;
}

void bp_unpin(BufferPool* pool, PageID pid) {
    for (int i = 0; i < pool->num_pages; i++) {
        if (pool->pages[i]->page_id == pid && pool->pages[i]->pin_count > 0) {
            pool->pages[i]->pin_count--;
            return;
        }
    }
}

// ===== B+树存储引擎 =====
typedef struct {
    BufferPool* pool;
    PageID      root_pid;
    PageID      next_pid;
    int         height;
    uint32_t    next_txn;
    int         num_inserts;
    int         num_lookups;
} BPTreeEngine;

BPTreeEngine* bpt_create() {
    BPTreeEngine* e = calloc(1, sizeof(BPTreeEngine));
    e->pool = bp_create();
    e->next_pid = 1;
    // 创建根节点(空叶子)
    BPTPage* root = bp_fetch(e->pool, e->next_pid);
    root->is_leaf = 1;
    root->num_keys = 0;
    root->next_leaf = 0;
    e->root_pid = e->next_pid++;
    e->height = 1;
    e->next_txn = 1;
    bp_unpin(e->pool, e->root_pid);
    printf("[BPTree] 创建B+树引擎, root=%u\n", e->root_pid);
    return e;
}

// 查找
const char* bpt_search(BPTreeEngine* e, int key) {
    e->num_lookups++;
    PageID pid = e->root_pid;
    while (1) {
        BPTPage* page = bp_fetch(e->pool, pid);
        if (!page) return NULL;
        if (page->is_leaf) {
            for (int i = 0; i < page->num_keys; i++) {
                if (page->keys[i] == key) {
                    const char* val = page->records[i].deleted ? NULL : page->records[i].value;
                    bp_unpin(e->pool, pid);
                    return val;
                }
            }
            bp_unpin(e->pool, pid);
            return NULL;
        }
        int i = 0;
        while (i < page->num_keys && key >= page->keys[i]) i++;
        PageID next = page->children[i];
        bp_unpin(e->pool, pid);
        pid = next;
    }
}

// 范围扫描
void bpt_range_scan(BPTreeEngine* e, int lo, int hi) {
    printf("  [BPTree] SCAN [%d, %d]:\n", lo, hi);
    PageID pid = e->root_pid;
    // 找到起始叶子
    while (1) {
        BPTPage* page = bp_fetch(e->pool, pid);
        if (!page) return;
        if (page->is_leaf) { bp_unpin(e->pool, pid); break; }
        int i = 0;
        while (i < page->num_keys && lo >= page->keys[i]) i++;
        PageID next = page->children[i];
        bp_unpin(e->pool, pid);
        pid = next;
    }
    // 沿叶子链表扫描
    int count = 0;
    while (pid != 0) {
        BPTPage* page = bp_fetch(e->pool, pid);
        if (!page) break;
        for (int i = 0; i < page->num_keys; i++) {
            if (page->keys[i] > hi) {
                bp_unpin(e->pool, pid);
                printf("  共 %d 条\n", count);
                return;
            }
            if (page->keys[i] >= lo && !page->records[i].deleted) {
                printf("    %d = %s\n", page->keys[i], page->records[i].value);
                count++;
            }
        }
        PageID next = page->next_leaf;
        bp_unpin(e->pool, pid);
        pid = next;
    }
    printf("  共 %d 条\n", count);
}

// 插入(简化: 不实现分裂，直接追加到叶子)
void bpt_insert(BPTreeEngine* e, int key, const char* val, uint32_t txn_id) {
    e->num_inserts++;
    PageID pid = e->root_pid;

    // 找叶子
    while (1) {
        BPTPage* page = bp_fetch(e->pool, pid);
        if (!page) return;
        if (page->is_leaf) {
            // 检查已存在
            for (int i = 0; i < page->num_keys; i++) {
                if (page->keys[i] == key) {
                    page->records[i].value[0] = '\0';
                    strncpy(page->records[i].value, val, MAX_VAL - 1);
                    page->records[i].txn_id = txn_id;
                    page->records[i].deleted = 0;
                    page->dirty = 1;
                    bp_unpin(e->pool, pid);
                    return;
                }
            }
            // 插入(有序)
            if (page->num_keys < ORDER) {
                int pos = page->num_keys;
                while (pos > 0 && page->keys[pos-1] > key) {
                    page->keys[pos] = page->keys[pos-1];
                    page->records[pos] = page->records[pos-1];
                    pos--;
                }
                page->keys[pos] = key;
                strncpy(page->records[pos].value, val, MAX_VAL - 1);
                page->records[pos].txn_id = txn_id;
                page->records[pos].deleted = 0;
                page->num_keys++;
                page->dirty = 1;
            }
            bp_unpin(e->pool, pid);
            return;
        }
        int i = 0;
        while (i < page->num_keys && key >= page->keys[i]) i++;
        PageID next = page->children[i];
        bp_unpin(e->pool, pid);
        pid = next;
    }
}

// 删除(标记删除)
void bpt_delete(BPTreeEngine* e, int key, uint32_t txn_id) {
    PageID pid = e->root_pid;
    while (1) {
        BPTPage* page = bp_fetch(e->pool, pid);
        if (!page) return;
        if (page->is_leaf) {
            for (int i = 0; i < page->num_keys; i++) {
                if (page->keys[i] == key) {
                    page->records[i].deleted = 1;
                    page->records[i].txn_id = txn_id;
                    page->dirty = 1;
                    bp_unpin(e->pool, pid);
                    return;
                }
            }
            bp_unpin(e->pool, pid);
            return;
        }
        int i = 0;
        while (i < page->num_keys && key >= page->keys[i]) i++;
        PageID next = page->children[i];
        bp_unpin(e->pool, pid);
        pid = next;
    }
}

// 事务
uint32_t bpt_begin_txn(BPTreeEngine* e) {
    return e->next_txn++;
}

void bpt_stats(BPTreeEngine* e) {
    printf("\n=== B+树引擎统计 ===\n");
    printf("高度: %d  插入: %d  查找: %d\n",
           e->height, e->num_inserts, e->num_lookups);
    printf("缓冲池: 命中=%d 未命中=%d 命中率=%.1f%%\n",
           e->pool->hits, e->pool->misses,
           e->pool->hits + e->pool->misses > 0 ?
           (double)e->pool->hits / (e->pool->hits + e->pool->misses) * 100 : 0);
}

int main() {
    printf("╔══════════════════════════════════════╗\n");
    printf("║   B+树存储引擎                       ║\n");
    printf("╚══════════════════════════════════════╝\n\n");

    BPTreeEngine* e = bpt_create();
    uint32_t t1 = bpt_begin_txn(e);

    // 插入
    printf("--- 插入 ---\n");
    for (int i = 0; i < 20; i++) {
        char val[32];
        snprintf(val, sizeof(val), "value_%d", i);
        bpt_insert(e, i, val, t1);
    }
    printf("  插入20条记录\n");

    // 查找
    printf("\n--- 查找 ---\n");
    for (int key = 0; key < 25; key += 5) {
        const char* val = bpt_search(e, key);
        printf("  GET %d → %s\n", key, val ? val : "NULL");
    }

    // 范围扫描
    printf("\n--- 范围扫描 ---\n");
    bpt_range_scan(e, 5, 15);

    // 更新
    printf("\n--- 更新 ---\n");
    bpt_insert(e, 10, "updated_10", t1);
    const char* v = bpt_search(e, 10);
    printf("  GET 10 → %s\n", v ? v : "NULL");

    // 删除
    printf("\n--- 删除 ---\n");
    bpt_delete(e, 5, t1);
    v = bpt_search(e, 5);
    printf("  GET 5 → %s\n", v ? v : "NULL(已删除)");

    // 再次范围扫描
    printf("\n--- 删除后范围扫描 ---\n");
    bpt_range_scan(e, 3, 12);

    bpt_stats(e);
    printf("\n✅ B+树存储引擎运行完成\n");
    return 0;
}

🔑 关键概念总结