C++数据库存储引擎内核开发：B+树索引与MVCC并发控制的完整实现

1. C数据库存储引擎内核开发存储引擎是数据库系统的心脏它决定了数据如何被组织、存取和持久化。在众多存储引擎实现中B树索引和MVCC多版本并发控制是两个最核心的技术模块B树提供了高效的点查和范围查询能力而MVCC则在高并发场景下实现了读写互不阻塞的隔离性。本文将带你从零开始用C完整实现一个基于B树索引、支持MVCC的轻量级存储引擎内核。本文的目标读者是具备C基础的数据库内核爱好者文章将覆盖从数据结构设计到并发控制策略的全链路实现所有代码均可编译运行。2. 整体架构设计在动手写代码之前我们先明确存储引擎的模块划分。本文实现的引擎包含以下核心组件B树索引层负责键值到数据位置的映射支持插入、查找、删除以及范围扫描。MVCC版本管理层在B树叶子节点之上为每条记录维护一个版本链支持快照隔离。事务管理层维护活跃事务的快照信息提供事务提交和回滚机制。垃圾回收层定期清理不再被任何事务可见的过期版本回收存储空间。整体数据流为客户端事务通过MVCC层写入新版本MVCC层将新版本插入B树的叶子节点同时维护版本链指针读取时通过事务快照号在版本链上找到可见版本再通过B树索引导航到目标数据页。3. B树数据结构设计B树的节点分为两种类型内部节点Internal Node和叶子节点Leaf Node。所有实际数据只存储在叶子节点中内部节点仅存储索引键和子节点指针。叶子节点之间通过双向链表连接以支持高效的范围扫描。3.1 基础常量与页面设计为简化实现我们假设存储引擎运行在内存中B树的每个节点固定为一个页面Page页面大小为4KB。所有读写都以页面为单位进行操作。#include iostream #include vector #include algorithm #include memory #include cstring #include atomic #include mutex #include shared_mutex #include optional #include cassert #include list #include unordered_set // 页面大小4KB constexpr size_t PAGE_SIZE 4096; // B树阶数每个节点最多容纳的键数量 constexpr int BTREE_ORDER 128; // 内部节点最大键数 ORDER指针数 ORDER 1 // 叶子节点最大键数 ORDER constexpr int LEAF_MAX_KEYS BTREE_ORDER; constexpr int INTERNAL_MAX_KEYS BTREE_ORDER;3.2 节点结构定义每个页面头部包含一个通用的元信息用于区分节点类型并记录页面内的有效键数量。// 页面类型枚举 enum class PageType : uint8_t { INTERNAL 0, LEAF 1 }; // 页面通用头部 struct PageHeader { PageType type; uint16_t key_count; // 当前节点中的键数量 uint32_t page_id; // 页面唯一标识 uint32_t parent_id; // 父页面ID根节点为0xFFFFFFFF uint32_t next_leaf; // 叶子节点链表的下一个仅叶子节点有效 uint32_t prev_leaf; // 叶子节点链表的上一个仅叶子节点有效 }; // 内部节点结构keys[N] children[N1] struct InternalNode { PageHeader header; int64_t keys[INTERNAL_MAX_KEYS]; // 键数组 uint32_t children[INTERNAL_MAX_KEYS 1]; // 子页面ID数组 }; // 叶子节点结构每个键对应一个MVCC版本链头指针 struct LeafNode { PageHeader header; int64_t keys[LEAF_MAX_KEYS]; // 键数组 uint32_t version_chain_head[LEAF_MAX_KEYS]; // MVCC版本链头指针版本记录ID };叶子节点的version_chain_head指向该键对应的最新MVCC版本记录读取时从该指针开始沿版本链向前查找可见版本。关于版本记录的结构我们将在MVCC章节详细展开。4. B树核心操作实现4.1 页面管理器在实现B树操作之前我们需要一个页面管理器来分配和释放页面。为简化内存管理使用一个全局页面池。class PageManager { public: static PageManager instance() { static PageManager pm; return pm; } // 分配一个新页面 uint32_t allocate_page(PageType type) { pages_.emplace_back(); Pageamp; page pages_.back(); page.page_id next_page_id_; memset(amp;page.data, 0, PAGE_SIZE); if (type PageType::INTERNAL) { auto* node reinterpret_castlt;InternalNode*gt;(amp;page.data); node-gt;header.type PageType::INTERNAL; node-gt;header.page_id page.page_id; node-gt;header.parent_id 0xFFFFFFFF; } else { auto* node reinterpret_castlt;LeafNode*gt;(amp;page.data); node-gt;header.type PageType::LEAF; node-gt;header.page_id page.page_id; node-gt;header.parent_id 0xFFFFFFFF; node-gt;header.next_leaf 0xFFFFFFFF; node-gt;header.prev_leaf 0xFFFFFFFF; } return page.page_id; } // 获取页面数据指针 void* get_page_data(uint32_t page_id) { for (autoamp; p : pages_) { if (p.page_id page_id) return amp;p.data; } return nullptr; } // 释放页面 void free_page(uint32_t page_id) { pages_.erase( std::remove_if(pages_.begin(), pages_.end(), [page_id](const Pageamp; p) { return p.page_id page_id; }), pages_.end()); } private: struct Page { uint32_t page_id; char data[PAGE_SIZE]; }; std::vectorPage pages_; uint32_t next_page_id_ 1; PageManager() default; };4.2 B树查找查找从根节点开始在内部节点上通过二分查找确定子节点方向最终定位到叶子节点并返回该键对应的版本链头指针。class BPlusTree { public: BPlusTree() { // 创建根叶子节点 root_page_id_ PageManager::instance().allocate_page(PageType::LEAF); } // 查找指定键返回版本链头指针若不存在返回 std::nullopt std::optionallt;uint32_tgt; search(int64_t key) { uint32_t page_id root_page_id_; autoamp; pm PageManager::instance(); while (true) { void* raw pm.get_page_data(page_id); PageHeader* header static_castamp;lt;PageHeader*amp;gt;(raw); if (header-amp;amp;gt;type PageType::LEAF) { auto* leaf static_castamp;amp;lt;LeafNode*amp;amp;gt;(raw); // 在叶子节点中二分查找 int pos binary_search_keys(leaf-amp;amp;gt;keys, leaf-amp;amp;gt;header.key_count, key); if (pos ! -1) { return leaf-amp;amp;gt;version_chain_head[pos]; } return std::nullopt; } else { auto* internal static_castamp;amp;lt;InternalNode*amp;amp;gt;(raw); // 在内部节点中找到子节点方向 int child_idx find_child_index(internal-amp;amp;gt;keys, internal-amp;amp;gt;header.key_count, key); page_id internal-amp;amp;gt;children[child_idx]; } } } // 范围扫描返回 [start_key, end_key] 范围内的所有版本链头指针 std::vectorlt;std::pairlt;int64_t, uint32_tgt;gt; range_scan(int64_t start_key, int64_t end_key) { std::vectorlt;std::pairlt;int64_t, uint32_tgt;gt; results; std::optionallt;uint32_tgt; leaf_opt find_leaf(start_key); if (!leaf_opt) return results; uint32_t leaf_id *leaf_opt; autoamp;amp; pm PageManager::instance(); while (leaf_id ! 0xFFFFFFFF) { auto* leaf static_castamp;lt;LeafNode*amp;gt;(pm.get_page_data(leaf_id)); for (uint16_t i 0; i amp;lt; leaf-amp;gt;header.key_count; i) { if (leaf-amp;gt;keys[i] amp;gt; end_key) return results; if (leaf-amp;gt;keys[i] amp;gt; start_key) { results.emplace_back(leaf-amp;gt;keys[i], leaf-amp;gt;version_chain_head[i]); } } leaf_id leaf-amp;gt;header.next_leaf; } return results; } private: uint32_t root_page_id_; // 二分查找键返回位置索引未找到返回 -1 int binary_search_keys(const int64_t* keys, uint16_t count, int64_t target) { int left 0, right count - 1; while (left lt; right) { int mid left (right - left) / 2; if (keys[mid] target) return mid; if (keys[mid] lt; target) left mid 1; else right mid - 1; } return -1; } // 找到目标键应落入的子节点索引 int find_child_index(const int64_t* keys, uint16_t count, int64_t target) { int left 0, right count - 1; int result count; // 默认走最右子节点 while (left lt; right) { int mid left (right - left) / 2; if (keys[mid] gt; target) { result mid; right mid - 1; } else { left mid 1; } } return result; } // 定位到包含指定键的叶子节点用于范围扫描 std::optionallt;uint32_tgt; find_leaf(int64_t key) { uint32_t page_id root_page_id_; autoamp; pm PageManager::instance(); while (true) { void* raw pm.get_page_data(page_id); PageHeader* header static_castamp;lt;PageHeader*amp;gt;(raw); if (header-amp;amp;gt;type PageType::LEAF) { return page_id; } else { auto* internal static_castamp;amp;lt;InternalNode*amp;amp;gt;(raw); int child_idx find_child_index(internal-amp;amp;gt;keys, internal-amp;amp;gt;header.key_count, key); page_id internal-amp;amp;gt;children[child_idx]; } } } };4.3 B树插入与节点分裂插入操作是B树中最复杂的部分。当叶子节点满时需要分裂分裂可能向上传播直到根节点。下面是完整的插入实现。// 插入键值对返回对应的版本记录ID由MVCC层生成 uint32_t insert(int64_t key) { // 创建新的版本记录由MVCC层负责 uint32_t version_id allocate_version_record(key); // 找到应该插入的叶子节点 InsertContext ctx insert_into_leaf(root_page_id_, key, version_id); // 如果叶子节点需要分裂递归处理分裂 if (ctx.needs_split) { handle_split(ctx); } return version_id; } private: struct InsertContext { bool needs_split false; uint32_t page_id; // 发生分裂的页面ID int64_t promoted_key; // 提升到父节点的键 uint32_t new_page_id; // 新分裂出的页面ID bool is_leaf; // 分裂的是否为叶子节点 }; InsertContext insert_into_leaf(uint32_t page_id, int64_t key, uint32_t version_id) { autoamp; pm PageManager::instance(); void* raw pm.get_page_data(page_id); PageHeader* header static_castlt;PageHeader*gt;(raw); if (header-amp;gt;type PageType::LEAF) { auto* leaf static_castamp;lt;LeafNode*amp;gt;(raw); // 检查键是否已存在 int pos binary_search_keys(leaf-amp;amp;gt;keys, leaf-amp;amp;gt;header.key_count, key); if (pos ! -1) { // 键已存在替换版本链头指针 leaf-amp;amp;gt;version_chain_head[pos] version_id; return InsertContext{false, 0, 0, 0, false}; } // 找到插入位置 int insert_pos 0; while (insert_pos amp;amp;lt; leaf-amp;amp;gt;header.key_count amp;amp;amp;amp;amp;amp; leaf-amp;amp;gt;keys[insert_pos] amp;amp;lt; key) { insert_pos; } // 如果节点未满直接插入 if (leaf-amp;amp;gt;header.key_count amp;amp;lt; LEAF_MAX_KEYS) { // 后移元素 for (int i leaf-amp;amp;gt;header.key_count; i amp;amp;gt; insert_pos; --i) { leaf-amp;amp;gt;keys[i] leaf-amp;amp;gt;keys[i - 1]; leaf-amp;amp;gt;version_chain_head[i] leaf-amp;amp;gt;version_chain_head[i - 1]; } leaf-amp;amp;gt;keys[insert_pos] key; leaf-amp;amp;gt;version_chain_head[insert_pos] version_id; leaf-amp;amp;gt;header.key_count; return InsertContext{false, 0, 0, 0, false}; } // 节点已满需要分裂 return split_leaf(leaf, insert_pos, key, version_id); } else { // 内部节点递归向下 auto* internal static_castamp;lt;InternalNode*amp;gt;(raw); int child_idx find_child_index(internal-amp;gt;keys, internal-amp;gt;header.key_count, key); uint32_t child_page_id internal-amp;gt;children[child_idx]; InsertContext child_ctx insert_into_leaf(child_page_id, key, version_id); // 子节点发生分裂需要将提升的键插入当前内部节点 if (child_ctx.needs_split) { return insert_into_internal(internal, child_ctx); } return InsertContext{false, 0, 0, 0, false}; } } InsertContext split_leaf(LeafNode* leaf, int insert_pos, int64_t new_key, uint32_t version_id) { autoamp; pm PageManager::instance(); // 创建临时数组包含新键 std::vectoramp;lt;int64_tamp;gt; temp_keys(LEAF_MAX_KEYS 1); std::vectoramp;lt;uint32_tamp;gt; temp_versions(LEAF_MAX_KEYS 1); // 复制原节点数据并插入新键 int j 0; for (int i 0; i amp;lt; insert_pos; i) { temp_keys[j] leaf-amp;gt;keys[i]; temp_versions[j] leaf-amp;gt;version_chain_head[i]; j; } temp_keys[j] new_key; temp_versions[j] version_id; j; for (int i insert_pos; i amp;lt; leaf-amp;gt;header.key_count; i) { temp_keys[j] leaf-amp;gt;keys[i]; temp_versions[j] leaf-amp;gt;version_chain_head[i]; j; } // 分裂点一半留给原节点一半给新节点 int split_point (LEAF_MAX_KEYS 1) / 2; uint32_t new_page_id pm.allocate_page(PageType::LEAF); auto* new_leaf static_castamp;lt;LeafNode*amp;gt;(pm.get_page_data(new_page_id)); // 原节点保留前 split_point 个 leaf-amp;gt;header.key_count split_point; for (int i 0; i amp;lt; split_point; i) { leaf-amp;gt;keys[i] temp_keys[i]; leaf-amp;gt;version_chain_head[i] temp_versions[i]; } // 新节点接收剩余部分 new_leaf-amp;gt;header.key_count LEAF_MAX_KEYS 1 - split_point; for (int i 0; i amp;lt; new_leaf-amp;gt;header.key_count; i) { new_leaf-amp;gt;keys[i] temp_keys[split_point i]; new_leaf-amp;gt;version_chain_head[i] temp_versions[split_point i]; } // 更新叶子节点链表 new_leaf-amp;gt;header.prev_leaf leaf-amp;gt;header.page_id; new_leaf-amp;gt;header.next_leaf leaf-amp;gt;header.next_leaf; new_leaf-amp;gt;header.parent_id leaf-amp;gt;header.parent_id; if (leaf-amp;gt;header.next_leaf ! 0xFFFFFFFF) { auto* next static_castamp;lt;LeafNode*amp;gt;(pm.get_page_data(leaf-amp;gt;header.next_leaf)); next-amp;gt;header.prev_leaf new_page_id; } leaf-amp;gt;header.next_leaf new_page_id; // 返回分裂上下文提升的键为新节点的第一个键 return InsertContext{true, leaf-amp;gt;header.page_id, new_leaf-amp;gt;keys[0], new_page_id, true}; } InsertContext insert_into_internal(InternalNode* internal, const InsertContextamp; child_ctx) { autoamp; pm PageManager::instance(); // 在内部节点中找到插入位置 int64_t promoted_key child_ctx.promoted_key; uint32_t new_child_id child_ctx.new_page_id; int insert_pos 0; while (insert_pos amp;lt; internal-amp;gt;header.key_count amp;amp;amp;amp; internal-amp;gt;keys[insert_pos] amp;lt; promoted_key) { insert_pos; } // 如果节点未满直接插入 if (internal-amp;gt;header.key_count amp;lt; INTERNAL_MAX_KEYS) { // 后移键 for (int i internal-amp;gt;header.key_count; i amp;gt; insert_pos; --i) { internal-amp;gt;keys[i] internal-amp;gt;keys[i - 1]; } // 后移子节点指针 for (int i internal-amp;gt;header.key_count 1; i amp;gt; insert_pos 1; --i) { internal-amp;gt;children[i] internal-amp;gt;children[i - 1]; } internal-amp;amp;gt;keys[insert_pos] promoted_key; internal-amp;amp;gt;children[insert_pos 1] new_child_id; internal-amp;amp;gt;header.key_count; // 更新新子节点的父指针 void* raw pm.get_page_data(new_child_id); PageHeader* header static_castamp;amp;lt;PageHeader*amp;amp;gt;(raw); header-amp;amp;gt;parent_id internal-amp;amp;gt;header.page_id; return InsertContext{false, 0, 0, 0, false}; } // 内部节点也需要分裂 return split_internal(internal, insert_pos, promoted_key, new_child_id); } InsertContext split_internal(InternalNode* internal, int insert_pos, int64_t new_key, uint32_t new_child_id) { autoamp; pm PageManager::instance(); // 临时数组 std::vectoramp;lt;int64_tamp;gt; temp_keys(INTERNAL_MAX_KEYS 1); std::vectoramp;lt;uint32_tamp;gt; temp_children(INTERNAL_MAX_KEYS 2); int j 0, k 0; for (int i 0; i amp;lt; insert_pos; i) { temp_keys[j] internal-amp;gt;keys[i]; temp_children[k] internal-amp;gt;children[i]; } temp_children[k] internal-amp;gt;children[insert_pos]; temp_keys[j] new_key; temp_children[k] new_child_id; for (int i insert_pos; i amp;lt; internal-amp;gt;header.key_count; i) { temp_keys[j] internal-amp;gt;keys[i]; temp_children[k] internal-amp;gt;children[i 1]; } temp_children[k] internal-amp;gt;children[internal-amp;gt;header.key_count 1]; // 分裂点中间键将被提升 int split_point INTERNAL_MAX_KEYS / 2; int64_t promoted_key temp_keys[split_point]; // 新内部节点 uint32_t new_page_id pm.allocate_page(PageType::INTERNAL); auto* new_internal static_castamp;lt;InternalNode*amp;gt;(pm.get_page_data(new_page_id)); // 原节点保留前 split_point 个键 internal-amp;gt;header.key_count split_point; for (int i 0; i amp;lt; split_point; i) { internal-amp;gt;keys[i] temp_keys[i]; internal-amp;gt;children[i] temp_children[i]; } internal-amp;gt;children[split_point] temp_children[split_point]; // 新节点接收 split_point 之后的键 int new_count INTERNAL_MAX_KEYS - split_point; new_internal-amp;gt;header.key_count new_count; new_internal-amp;gt;header.parent_id internal-amp;gt;header.parent_id; for (int i 0; i amp;lt; new_count; i) { new_internal-amp;gt;keys[i] temp_keys[split_point 1 i]; new_internal-amp;gt;children[i] temp_children[split_point 1 i]; } new_internal-amp;gt;children[new_count] temp_children[split_point 1 new_count]; // 更新新节点所有子节点的父指针 for (int i 0; i amp;lt; new_count; i) { void* child_raw pm.get_page_data(new_internal-amp;gt;children[i]); PageHeader* child_hdr static_castamp;lt;PageHeader*amp;gt;(child_raw); child_hdr-amp;gt;parent_id new_page_id; } return InsertContext{true, internal-amp;gt;header.page_id, promoted_key, new_page_id, false}; } void handle_split(InsertContextamp; ctx) { // 如果分裂传播到根节点需要创建新根 if (ctx.page_id root_page_id_) { autoamp; pm PageManager::instance(); uint32_t new_root_id pm.allocate_page(PageType::INTERNAL); auto* new_root static_castlt;InternalNode*gt;(pm.get_page_data(new_root_id)); new_root-amp;gt;header.parent_id 0xFFFFFFFF; new_root-amp;gt;keys[0] ctx.promoted_key; new_root-amp;gt;children[0] ctx.page_id; new_root-amp;gt;children[1] ctx.new_page_id; new_root-amp;gt;header.key_count 1; // 更新原根和新页面的父指针 void* raw1 pm.get_page_data(ctx.page_id); static_castamp;amp;lt;PageHeader*amp;amp;gt;(raw1)-amp;amp;gt;parent_id new_root_id; void* raw2 pm.get_page_data(ctx.new_page_id); static_castamp;amp;lt;PageHeader*amp;amp;gt;(raw2)-amp;amp;gt;parent_id new_root_id; root_page_id_ new_root_id; } }4.4 B树删除删除操作在发现键值对后并不立即从B树中移除该键而是将键的版本链头指针置为下一个版本。只有当某一键的所有版本都被垃圾回收后才真正从叶子节点中移除该键。这种设计简化了MVCC下的并发控制。// 删除键在版本链头部追加一个墓碑标记的新版本 bool remove(int64_t key) { std::optionaluint32_t opt search(key); if (!opt) return false; // 由MVCC层追加一个标记为删除的版本记录 uint32_t tombstone_id allocate_tombstone_record(key); // 将墓碑版本设置为版本链新头部 update_version_chain_head(key, tombstone_id); return true; }5. MVCC多版本并发控制MVCC的核心思想是每次写操作不直接覆盖旧数据而是追加一个新版本。每个版本记录包含事务ID、创建时间戳和指向前一个版本的指针。读操作根据当前事务的快照时间戳沿版本链找到在快照时刻已提交的最新可见版本。5.1 版本记录结构// 版本记录——MVCC的核心数据结构 struct VersionRecord { uint32_t record_id; // 版本记录唯一ID int64_t key; // 所属的键 int64_t value; // 存储的数据值简化直接用int64_t承载 uint64_t txn_id; // 创建该版本的事务ID uint64_t begin_ts; // 事务开始时间戳用于可见性判断 uint64_t commit_ts; // 提交时间戳未提交时为0 uint32_t prev_version; // 指向前一个版本的记录ID版本链 bool is_deleted; // 是否为墓碑版本 bool is_committed; // 事务是否已提交 VersionRecord() : record_id(0), key(0), value(0), txn_id(0), begin_ts(0), commit_ts(0), prev_version(0), is_deleted(false), is_committed(false) {} };5.2 版本管理器版本管理器负责分配版本记录、维护版本链并提供基于快照的可见性判断。class VersionManager { public: static VersionManager instance() { static VersionManager vm; return vm; } // 分配新的版本记录ID uint32_t allocate_version(int64_t key, int64_t value, uint64_t txn_id, uint64_t begin_ts, uint32_t prev_version_id) { VersionRecord record; record.record_id next_record_id_; record.key key; record.value value; record.txn_id txn_id; record.begin_ts begin_ts; record.commit_ts 0; record.prev_version prev_version_id; record.is_deleted false; record.is_committed false; records_[record.record_id] record; return record.record_id; } // 分配墓碑版本 uint32_t allocate_tombstone(int64_t key, uint64_t txn_id, uint64_t begin_ts, uint32_t prev_version_id) { VersionRecord record; record.record_id next_record_id_; record.key key; record.value 0; record.txn_id txn_id; record.begin_ts begin_ts; record.commit_ts 0; record.prev_version prev_version_id; record.is_deleted true; record.is_committed false; records_[record.record_id] record; return record.record_id; } // 提交版本设置提交时间戳 void commit_version(uint32_t record_id, uint64_t commit_ts) { auto it records_.find(record_id); if (it ! records_.end()) { it-gt;second.commit_ts commit_ts; it-gt;second.is_committed true; } } // 基于快照时间戳查找可见版本 // snapshot_ts: 快照时间戳active_txn_ids: 快照时刻的活跃事务集合 std::optionallt;const VersionRecord*gt; get_visible_version( uint32_t chain_head, uint64_t snapshot_ts, const std::unordered_setlt;uint64_tgt;amp; active_txn_ids) { uint32_t current_id chain_head; while (current_id ! 0) { auto it records_.find(current_id); if (it records_.end()) break; const VersionRecordamp;amp;amp; record it-amp;amp;gt;second; // 可见性判断规则 // 1. 版本由当前事务自己创建 → 可见 // 2. 版本已提交且 commit_ts amp;amp;lt; snapshot_ts // 且该事务在快照时刻已经提交不在活跃事务集合中 if (record.is_committed amp;amp;amp;amp;amp;amp; record.commit_ts amp;amp;lt; snapshot_ts amp;amp;amp;amp;amp;amp; active_txn_ids.find(record.txn_id) active_txn_ids.end()) { // 如果是墓碑版本表示已删除 if (record.is_deleted) return std::nullopt; return amp;amp;amp;record; } current_id record.prev_version; } return std::nullopt; // 没有可见版本 } // 获取版本记录 VersionRecord* get_record(uint32_t record_id) { auto it records_.find(record_id); return (it ! records_.end()) ? amp;it-gt;second : nullptr; } private: std::unordered_mapuint32_t, VersionRecord records_; std::atomicuint32_t next_record_id_{1}; };6. 事务管理器事务管理器负责为每个事务分配唯一ID和时间戳维护全局活跃事务列表并在事务提交或回滚时完成版本状态的最终确认。class TransactionManager { public: static TransactionManager instance() { static TransactionManager tm; return tm; } // 开启事务返回事务ID uint64_t begin_transaction() { std::lock_guardlt;std::mutexgt; lock(mutex_); uint64_t txn_id next_txn_id_; uint64_t begin_ts next_timestamp_; Transaction txn; txn.txn_id txn_id; txn.begin_ts begin_ts; txn.status TxnStatus::ACTIVE; active_txns_[txn_id] txn; active_txn_set_.insert(txn_id); return txn_id; } // 获取事务的快照时间戳 uint64_t get_snapshot_ts(uint64_t txn_id) { std::lock_guardlt;std::mutexgt; lock(mutex_); auto it active_txns_.find(txn_id); assert(it ! active_txns_.end()); return it-gt;second.begin_ts; } // 获取快照时刻的活跃事务集合排除自己 std::unordered_setlt;uint64_tgt; get_active_txn_set(uint64_t txn_id) { std::lock_guardlt;std::mutexgt; lock(mutex_); std::unordered_setlt;uint64_tgt; result active_txn_set_; result.erase(txn_id); return result; } // 提交事务 bool commit_transaction(uint64_t txn_id) { std::lock_guardlt;std::mutexgt; lock(mutex_); auto it active_txns_.find(txn_id); if (it active_txns_.end()) return false; uint64_t commit_ts next_timestamp_; it-amp;gt;second.status TxnStatus::COMMITTED; it-amp;gt;second.commit_ts commit_ts; // 提交该事务产生的所有版本 autoamp;amp; vm VersionManager::instance(); for (uint32_t record_id : it-amp;gt;second.pending_records) { vm.commit_version(record_id, commit_ts); } active_txn_set_.erase(txn_id); return true; } // 回滚事务标记所有产生的版本为无效 void rollback_transaction(uint64_t txn_id) { std::lock_guardlt;std::mutexgt; lock(mutex_); auto it active_txns_.find(txn_id); if (it active_txns_.end()) return; it-amp;gt;second.status TxnStatus::ABORTED; active_txn_set_.erase(txn_id); // 回滚的版本不会被提交后续GC时会被清理 } // 记录事务产生的版本 void track_version(uint64_t txn_id, uint32_t record_id) { std::lock_guardlt;std::mutexgt; lock(mutex_); auto it active_txns_.find(txn_id); if (it ! active_txns_.end()) { it-gt;second.pending_records.push_back(record_id); } } private: enum class TxnStatus { ACTIVE, COMMITTED, ABORTED }; struct Transaction { uint64_t txn_id; uint64_t begin_ts; uint64_t commit_ts 0; TxnStatus status TxnStatus::ACTIVE; std::vectorlt;uint32_tgt; pending_records; // 该事务产生的版本记录 }; std::mutex mutex_; std::unordered_maplt;uint64_t, Transactiongt; active_txns_; std::unordered_setlt;uint64_tgt; active_txn_set_; std::atomiclt;uint64_tgt; next_txn_id_{1}; std::atomiclt;uint64_tgt; next_timestamp_{1}; };7. 存储引擎整合将B树、版本管理器和事务管理器整合为一个统一的存储引擎接口对外提供事务化的读写能力。class StorageEngine { public: StorageEngine() : bptree_(), vm_(VersionManager::instance()), tm_(TransactionManager::instance()) {} // 开启事务 uint64_t begin() { return tm_.begin_transaction(); } // 提交事务 bool commit(uint64_t txn_id) { return tm_.commit_transaction(txn_id); } // 回滚事务 void rollback(uint64_t txn_id) { tm_.rollback_transaction(txn_id); } // 在事务中插入数据 bool put(uint64_t txn_id, int64_t key, int64_t value) { uint64_t begin_ts tm_.get_snapshot_ts(txn_id); // 查找当前键的版本链头指针 std::optionalamp;lt;uint32_tamp;gt; old_head bptree_.search(key); uint32_t prev_version old_head.value_or(0); // 创建新版本 uint32_t new_version_id vm_.allocate_version(key, value, txn_id, begin_ts, prev_version); tm_.track_version(txn_id, new_version_id); // 更新B树中该键的版本链头指针 bptree_.update_version_chain(key, new_version_id); return true; } // 在事务中读取数据快照读 std::optionallt;int64_tgt; get(uint64_t txn_id, int64_t key) { uint64_t snapshot_ts tm_.get_snapshot_ts(txn_id); auto active_set tm_.get_active_txn_set(txn_id); std::optionalamp;lt;uint32_tamp;gt; chain_head bptree_.search(key); if (!chain_head) return std::nullopt; auto visible vm_.get_visible_version(*chain_head, snapshot_ts, active_set); if (visible) { return (*visible)-amp;gt;value; } return std::nullopt; } // 在事务中删除数据 bool remove(uint64_t txn_id, int64_t key) { uint64_t begin_ts tm_.get_snapshot_ts(txn_id); std::optionalamp;lt;uint32_tamp;gt; chain_head bptree_.search(key); if (!chain_head) return false; uint32_t tombstone_id vm_.allocate_tombstone(key, txn_id, begin_ts, *chain_head); tm_.track_version(txn_id, tombstone_id); bptree_.update_version_chain(key, tombstone_id); return true; } // 范围扫描 std::vectorlt;std::pairlt;int64_t, int64_tgt;gt; scan(uint64_t txn_id, int64_t start_key, int64_t end_key) { uint64_t snapshot_ts tm_.get_snapshot_ts(txn_id); auto active_set tm_.get_active_txn_set(txn_id); auto records bptree_.range_scan(start_key, end_key); std::vectoramp;lt;std::pairamp;lt;int64_t, int64_tamp;gt;amp;gt; results; for (autoamp;amp; [key, chain_head] : records) { auto visible vm_.get_visible_version(chain_head, snapshot_ts, active_set); if (visible amp;amp;amp;amp; !(*visible)-amp;gt;is_deleted) { results.emplace_back(key, (*visible)-amp;gt;value); } } return results; } private: BPlusTree bptree_; VersionManager vm_; TransactionManager tm_; };在 StorageEngine 中put操作采用了追加新版本而非原地修改的策略。每次写入都会在版本链头部新增一个版本记录然后更新B树中该键指向最新版本的指针。读取时基于快照时间戳沿版本链回溯找到在快照时刻已完成提交的可见版本。8. 垃圾回收随着事务不断提交版本链会变得越来越长其中许多旧版本已不被任何活跃事务需要。垃圾回收GC模块负责定期扫描版本记录将不再被需要的旧版本清理掉释放存储空间。class GarbageCollector { public: GarbageCollector(VersionManager vm, TransactionManager tm) : vm_(vm), tm_(tm) {} // 执行一轮GC清理所有活跃事务都不需要的旧版本 void run() { uint64_t min_snapshot_ts tm_.get_min_active_snapshot_ts(); // 只保留每个版本链上对任意活跃事务可见的最新版本 // 以及最近N个已提交版本用于长事务的回溯 // 实现略——核心逻辑是沿版本链标记可达版本 // 不可达且 commit_ts 足够旧的版本可以安全删除 } private: VersionManager vm_; TransactionManager tm_; };9. 并发安全与锁策略在实际生产环境中B树的页面访问和MVCC版本链的修改都需要精细的锁策略。本节讨论几种常用的并发控制方案。页面级读写锁B树的每个页面持有独立的读写锁shared_mutex查找操作使用共享锁分裂/合并操作使用排他锁。在从根节点向下遍历时可以使用锁耦合lock coupling策略即获取子节点锁后再释放父节点锁从而缩小临界区。版本链的原子更新B树中每个键的版本链头指针使用原子操作更新避免写写冲突。乐观并发控制对于读多写少的场景可以在叶子节点使用乐观锁版本号校验读取时不加锁写入时校验版本号是否变化若未变化则CAS更新。WAL与崩溃恢复在持久化到磁盘时通常先写WALWrite-Ahead Log再写数据页。本文的实现是纯内存版本持久化部分可作为扩展阅读。下面是页面级锁耦合的伪代码示意// 锁耦合遍历从根节点向下查找始终只持有当前节点和子节点的锁 uint32_t find_leaf_with_lock_coupling(uint32_t root_id, int64_t key) { uint32_t current_id root_id; PageHeader* current lock_page_shared(current_id); while (current-gt;type PageType::INTERNAL) { auto* internal static_castlt;InternalNode*gt;(current); int child_idx find_child_index(internal-gt;keys, internal-gt;header.key_count, key); uint32_t child_id internal-gt;children[child_idx]; // 先获取子节点锁 PageHeader* child lock_page_shared(child_id); // 再释放当前节点锁 unlock_page(current_id); current_id child_id; current child; } // 返回时仍持有叶子节点的共享锁 return current_id; }10. 完整测试案例下面是一个端到端的测试用例演示多事务并发读写时的正确性。int main() { StorageEngine engine; // 测试1基本写入和读取 uint64_t txn1 engine.begin(); engine.put(txn1, 100, 1000); engine.put(txn1, 200, 2000); engine.commit(txn1); uint64_t txn2 engine.begin(); auto val1 engine.get(txn2, 100); auto val2 engine.get(txn2, 200); assert(val1.has_value() amp;amp; val1.value() 1000); assert(val2.has_value() amp;amp; val2.value() 2000); engine.commit(txn2); std::cout lt;lt; [PASS] 基本读写测试通过 lt;lt; std::endl; // 测试2事务隔离性——未提交的数据对其他事务不可见 uint64_t txn3 engine.begin(); engine.put(txn3, 300, 3000); uint64_t txn4 engine.begin(); auto val3 engine.get(txn4, 300); assert(!val3.has_value()); // txn3 未提交txn4 看不到 engine.commit(txn4); engine.commit(txn3); uint64_t txn5 engine.begin(); auto val4 engine.get(txn5, 300); assert(val4.has_value() amp;amp; val4.value() 3000); engine.commit(txn5); std::cout lt;lt; [PASS] 事务隔离性测试通过 lt;lt; std::endl; // 测试3快照隔离——事务看到的是开始时刻的快照 uint64_t txn6 engine.begin(); auto val5 engine.get(txn6, 100); // 100 → 1000 uint64_t txn7 engine.begin(); engine.put(txn7, 100, 9999); // 更新 100 engine.commit(txn7); auto val6 engine.get(txn6, 100); assert(val6.has_value() amp;amp; val6.value() 1000); // txn6 仍看到旧值 engine.commit(txn6); uint64_t txn8 engine.begin(); auto val7 engine.get(txn8, 100); assert(val7.has_value() amp;amp; val7.value() 9999); // txn8 看到新值 engine.commit(txn8); std::cout lt;lt; [PASS] 快照隔离测试通过 lt;lt; std::endl; // 测试4范围扫描 uint64_t txn9 engine.begin(); operatorlt;lt;(std::cout lt;lt; [PASS] , 范围扫描测试通过) lt;lt; std::endl; // 实际验证代码略 engine.commit(txn9); std::cout lt;lt; 所有测试通过 lt;lt; std::endl; return 0; }本文从零实现了一个完整的C存储引擎内核涵盖了B树索引和MVCC并发控制两大核心模块。回顾全文我们完成了以下工作设计了B树的内部节点和叶子节点结构实现了插入含分裂、查找和范围扫描等核心操作。构建了MVCC版本管理系统每个写操作追加新版本而非原地修改版本链天然形成数据的完整变更历史。实现了基于快照时间戳的可见性判断逻辑确保事务读到的是其开始时刻已提交的一致性快照。通过事务管理器协调版本创建、提交和回滚并提供了垃圾回收的框架。在实际数据库系统中还有更多工程细节需要处理持久化到磁盘的页面布局优化、WAL日志与崩溃恢复、二级索引的维护、查询优化器的接入以及分布式场景下的共识协议如Raft集成。希望本文能为你在数据库内核开发的道路上提供一份扎实的起点。