100、实战：完整项目——数据库迷你引擎（SQL解析+B+树存储+事务）

说实话，这个题目是我整个课程里最想讲的一章。为什么？因为一个迷你数据库引擎，几乎把C++的核心能力全串起来了——内存管理、数据结构、并发控制、协议解析。我在公司带新人时，经常让他们手写一个简化版，比看十本《数据库系统概论》都管用。

今天我们就来拆解这个项目。我会带着你从零搭一个能跑SQL、能持久化、能回滚事务的迷你引擎。别被「数据库引擎」四个字吓到，说白了，核心就三块：SQL解析器、B+树存储引擎、事务管理器。

项目整体架构

客户端输入SQL → SQL解析器生成抽象语法树 → 查询执行器调用B+树接口 → B+树操作磁盘页 → 事务管理器记录undo日志

客户端 (SQL) SQL解析器 (Lexer + Parser) 查询执行器 B+树存储引擎 事务管理器 (Undo Log) 磁盘页文件 日志文件

一、SQL解析器——把字符串变成可执行指令

SQL解析器说白了就是一个词法分析器 + 语法分析器。我早期写过一版手写的递归下降解析器，后来发现用flex/bison生成更省事。但为了让你理解原理，这里我用手写的方式展示核心逻辑。

举个例子，输入 SELECT id, name FROM users WHERE age > 18，解析器要干三件事：

  1. 词法分析：把字符串拆成Token流——SELECT、id、,、name、FROM、users、WHERE、age、>、18
  2. 语法分析：根据SQL语法规则，构建抽象语法树（AST）
  3. 语义分析：检查表名、列名是否存在，类型是否匹配
// 简化的Token定义
enum class TokenType {
    SELECT, FROM, WHERE, INSERT, UPDATE, DELETE,
    IDENTIFIER, NUMBER, STRING,
    EQ, NE, GT, LT, GE, LE,
    COMMA, SEMICOLON, LPAREN, RPAREN
};

struct Token {
    TokenType type;
    std::string value;
    size_t line, column;
};

// 词法分析器核心
class Lexer {
public:
    explicit Lexer(const std::string& sql) : sql_(sql), pos_(0) {}
    
    std::vector<Token> tokenize() {
        std::vector<Token> tokens;
        while (pos_ < sql_.size()) {
            char c = sql_[pos_];
            if (std::isspace(c)) { ++pos_; continue; }
            if (std::isalpha(c)) { tokens.push_back(parseIdentifier()); }
            else if (std::isdigit(c)) { tokens.push_back(parseNumber()); }
            else if (c == '\'') { tokens.push_back(parseString()); }
            else { tokens.push_back(parseSymbol()); }
        }
        return tokens;
    }
    
private:
    Token parseIdentifier() {
        size_t start = pos_;
        while (pos_ < sql_.size() && (std::isalnum(sql_[pos_]) || sql_[pos_] == '_')) {
            ++pos_;
        }
        std::string word = sql_.substr(start, pos_ - start);
        // 判断是否为关键字
        if (word == "SELECT") return {TokenType::SELECT, word};
        if (word == "FROM")   return {TokenType::FROM, word};
        // ... 其他关键字
        return {TokenType::IDENTIFIER, word};
    }
    
    // parseNumber, parseString, parseSymbol 类似
    const std::string& sql_;
    size_t pos_;
};

我的经验：解析器最容易踩的坑是错误恢复。用户输入SQL时经常少个分号、多写个逗号。我建议在语法分析阶段做「恐慌模式」——遇到错误就跳过当前语句，等下一个分号再恢复。这样至少不会让整个解析器崩溃。

二、B+树存储引擎——磁盘上的有序结构

B+树是数据库存储的标配。为什么不用红黑树？因为B+树磁盘IO友好。一个节点就是一个磁盘页（通常4KB），一次IO能读取几百个键值对。红黑树每个节点只存一个键，磁盘IO次数多到无法接受。

B+树的核心特性：

  • 所有数据都在叶子节点，内部节点只存索引键
  • 叶子节点用链表串联，支持范围查询
  • 节点分裂与合并，保持树平衡
// B+树节点定义（简化版）
constexpr int ORDER = 4;  // 阶数，实际项目通常100+
constexpr int PAGE_SIZE = 4096;

struct BPlusNode {
    bool is_leaf;
    int key_count;
    int keys[ORDER - 1];
    union {
        struct {  // 内部节点
            BPlusNode* children[ORDER];
        } internal;
        struct {  // 叶子节点
            std::string values[ORDER - 1];
            BPlusNode* next;  // 指向下一个叶子节点
        } leaf;
    };
    
    // 序列化到磁盘页
    void serialize(char* buffer) const;
    // 从磁盘页反序列化
    static BPlusNode* deserialize(const char* buffer);
};

// B+树插入核心逻辑
class BPlusTree {
public:
    void insert(int key, const std::string& value) {
        if (root_ == nullptr) {
            root_ = createLeafNode();
            root_->leaf.keys[0] = key;
            root_->leaf.values[0] = value;
            root_->key_count = 1;
            return;
        }
        
        // 查找插入位置，如果节点满则分裂
        auto [new_node, new_key] = insertInternal(root_, key, value);
        if (new_node != nullptr) {
            // 根节点分裂，树高度+1
            auto* new_root = createInternalNode();
            new_root->internal.keys[0] = new_key;
            new_root->internal.children[0] = root_;
            new_root->internal.children[1] = new_node;
            new_root->key_count = 1;
            root_ = new_root;
        }
    }
    
    // 范围查询：返回 [min, max] 之间的所有记录
    std::vector<std::pair<int, std::string>> rangeQuery(int min, int max) {
        std::vector<std::pair<int, std::string>> result;
        BPlusNode* leaf = findLeaf(min);
        while (leaf != nullptr) {
            for (int i = 0; i < leaf->key_count; ++i) {
                if (leaf->leaf.keys[i] > max) return result;
                if (leaf->leaf.keys[i] >= min) {
                    result.emplace_back(leaf->leaf.keys[i], leaf->leaf.values[i]);
                }
            }
            leaf = leaf->leaf.next;
        }
        return result;
    }
    
private:
    BPlusNode* root_;
    // insertInternal, findLeaf, splitNode 等实现
};

注意：B+树的并发控制是个大坑。我曾经在生产环境遇到过「写倾斜」——两个事务同时分裂同一个节点，导致索引损坏。解决方案是使用「锁耦合」技术：从上往下遍历时，先锁父节点，再锁子节点，然后释放父节点。这样既能保证安全，又不会锁住整棵树。

三、事务管理器——要么全做，要么全不做

事务的ACID特性，在迷你引擎里我们重点实现原子性和持久性。实现方式就是Undo日志——在修改数据之前，先把旧值写到日志里。如果事务回滚，就用日志恢复旧值。

事务的生命周期：

  1. BEGIN：分配事务ID，创建日志缓冲区
  2. 执行SQL：每次修改前，先写Undo日志（记录修改前的值）
  3. COMMIT：强制刷日志到磁盘，然后写Commit记录
  4. ROLLBACK：从后往前回放Undo日志，恢复旧值
// Undo日志条目
struct UndoLogEntry {
    uint64_t transaction_id;
    std::string table_name;
    int key;           // 被修改行的主键
    std::string old_value;  // 修改前的值
    std::string new_value;  // 修改后的值（用于Redo）
};

// 事务管理器
class TransactionManager {
public:
    uint64_t beginTransaction() {
        uint64_t tid = next_tid_++;
        Transaction tx;
        tx.id = tid;
        tx.state = TransactionState::ACTIVE;
        active_transactions_[tid] = tx;
        return tid;
    }
    
    void commit(uint64_t tid) {
        // 1. 强制刷当前事务的所有日志到磁盘
        flushLogs(tid);
        // 2. 写Commit记录
        writeCommitRecord(tid);
        // 3. 标记事务结束
        active_transactions_.erase(tid);
    }
    
    void rollback(uint64_t tid) {
        // 从后往前遍历Undo日志
        auto& logs = transaction_logs_[tid];
        for (auto it = logs.rbegin(); it != logs.rend(); ++it) {
            // 恢复旧值
            btree_->update(it->key, it->old_value);
        }
        // 写Abort记录
        writeAbortRecord(tid);
        active_transactions_.erase(tid);
    }
    
    // 在修改前调用，记录旧值
    void logBeforeUpdate(uint64_t tid, const std::string& table, 
                         int key, const std::string& old_val, 
                         const std::string& new_val) {
        UndoLogEntry entry{tid, table, key, old_val, new_val};
        transaction_logs_[tid].push_back(entry);
        // 同时写入内存缓冲区，定期刷盘
        log_buffer_.push_back(entry);
    }
    
private:
    uint64_t next_tid_{1};
    std::unordered_map<uint64_t, Transaction> active_transactions_;
    std::unordered_map<uint64_t, std::vector<UndoLogEntry>> transaction_logs_;
    std::vector<UndoLogEntry> log_buffer_;  // 批量刷盘
    BPlusTree* btree_;
    
    void flushLogs(uint64_t tid) {
        // 将日志缓冲区写入磁盘文件
        // 使用O_SYNC保证写入完成
    }
};

避坑指南：我曾经在实现事务时犯过一个低级错误——先写数据再写日志。结果系统在写数据后、写日志前崩溃了，恢复时根本不知道哪些数据需要回滚。正确的顺序是：先写日志（Write-Ahead Logging），再写数据。这样即使崩溃，也能通过日志完整恢复。

四、整合运行——让一切转起来

把上面三块拼起来，就是一个能工作的迷你引擎了。我写了一个简单的REPL（Read-Eval-Print Loop）来测试：

int main() {
    BPlusTree btree;
    TransactionManager tm(&btree);
    SQLLexer lexer;
    SQLParser parser;
    
    std::string sql;
    while (true) {
        std::cout << "minidb> ";
        std::getline(std::cin, sql);
        if (sql == "exit") break;
        
        try {
            auto tokens = lexer.tokenize(sql);
            auto ast = parser.parse(tokens);
            
            if (ast->type == ASTType::BEGIN) {
                uint64_t tid = tm.beginTransaction();
                std::cout << "Transaction " << tid << " started.\n";
            }
            else if (ast->type == ASTType::COMMIT) {
                tm.commit(current_tid);
                std::cout << "Committed.\n";
            }
            else if (ast->type == ASTType::INSERT) {
                // 先写日志，再写数据
                tm.logBeforeUpdate(current_tid, ast->table, 
                                   ast->key, "", ast->value);
                btree.insert(ast->key, ast->value);
                std::cout << "Inserted.\n";
            }
            else if (ast->type == ASTType::SELECT) {
                auto results = btree.rangeQuery(ast->min_key, ast->max_key);
                for (auto& [k, v] : results) {
                    std::cout << k << ": " << v << "\n";
                }
            }
        } catch (const std::exception& e) {
            std::cerr << "Error: " << e.what() << "\n";
        }
    }
    return 0;
}

性能数据参考（我本地测试的结果）：

操作耗时（微秒）说明
解析简单SQL5-10SELECT * FROM t WHERE id=1
B+树单点插入50-200取决于树高度，3层以内
B+树范围查询（100条）200-500顺序读取叶子节点
事务提交（含刷盘）500-2000取决于日志大小和磁盘速度

嗯，到这里，一个迷你数据库引擎的核心骨架就搭完了。你可能会问：这能用在生产环境吗？当然不能。它缺少了太多东西——多版本并发控制（MVCC）、查询优化器、崩溃恢复、缓存管理……但作为学习项目，它把数据库最核心的三个概念用C++完整实现了一遍。我个人觉得，能把这个项目跑通，你对C++的理解会上一个台阶。

最后说一句：代码里我刻意省略了一些边界检查和内存管理细节，你在自己实现时一定要补上。尤其是智能指针和RAII，别裸new/delete，否则内存泄漏会让你怀疑人生。

公众号:蓝海资料掘金营，微信deep3321
← 上一章 📖 返回目录 下一章 →