存储工程索引
汇总本站存储工程系列文章，覆盖 HDD、SSD、NVMe、持久内存、索引结构、压缩、分布式存储与对象存储。
btree 标签归档
共 19 篇文章 · 返回首页
数据库内核实验索引
汇总本站数据库内核文章：PostgreSQL / MySQL InnoDB / 列存、湖仓、流处理、查询引擎、RocksDB、向量、Redis、全文检索、TiKV/HTAP、FoundationDB、SQLite 与 WiredTiger 内核，以及 LSM-Tree 实验与其它单篇。
【PG 内核】PostgreSQL 内核机制深度拆解
从进程模型到磁盘页面、从 MVCC 到流复制——对 PostgreSQL 内核做完整的源码级拆解。不止步于源码分析：26 篇中 6 篇是运维实战——经典故障的根因与排查路径、性能调查的五层工具链、配置陷阱与恢复边界。面向想读懂 PG 内核源码、在生产环境排查过问题、准备给 PG 贡献代码的工程师。
【SQLite 内核】B-Tree 遍历与分裂：表 B-Tree、索引 B-Tree 与 cell 布局
钉住 SQLite table b-tree 与 index b-tree 的字节布局差异、cell pointer array 如何做到逻辑有序物理可乱序、overflow 阈值与 balance() 分裂/合并触发条件；源码以 btree.c 函数签名为准，学术锚点是 Bayer & McCreight 1972。
【MySQL InnoDB 内核】InnoDB 存储引擎机制深度拆解
从线程模型到页格式、从 undo log MVCC 到 binlog 两阶段提交——对 MySQL InnoDB 做源码级拆解，并与 PostgreSQL 内核系列逐章对照。20 篇覆盖内核机制与生产运维实战，面向 MySQL DBA、从 PG 转 MySQL 的后端与数据库内核开发者。
【WiredTiger 内核】文档库存储引擎全景：MongoDB 默认引擎的生态位
定位文档库默认引擎 WiredTiger 相对 PG/InnoDB/SQLite/RocksDB 的生态位；钉住 Session→Cache→Reconcile→HS→Checkpoint 主线、站内分工与 17 篇阅读路线，并以 Berenson 隔离词汇与 Durable History 为学术/工程锚点。
【WiredTiger 内核】B-Tree 与 update chain：未提交更新只挂链
拆解 WiredTiger row-store B-Tree 的 WT_BTREE/WT_REF 结构，以及叶页上 WT_INSERT skiplist 与 WT_UPDATE 链如何承载插入与多版本；说明未提交更新不进磁盘镜像，为 Reconciliation 与 History Store 铺垫。
【SQLite 内核】嵌入式行存全景：单文件、单写者、零 IPC
定位单文件嵌入式行存在服务器行存与 LSM 嵌入 KV 之间的生态位；钉住 SQLite 架构约束、站内分工与 17 篇阅读路线，并以 Bayer/McCreight、官方 file format、PVLDB 2022 为学术锚点。
【SQLite 内核】单文件格式与页面头
拆解 SQLite 单文件格式：100 字节 database header 与 B-Tree 页面头的逐字段布局，用本机 3.53.2 CLI 实测 hexdump 核对 magic、page size、页类型标志，并钉住 file format 官方规范与 Bayer/McCreight 谱系。
【SQLite 内核】索引与 covering scan：什么时候真的省掉了第二次查找
钉住 covering index 消除的具体开销：第 4 篇 index b-tree 只存 key+rowid，命中后仍要回表这一次二次查找；用本机 3.53.2 实测 SELECT 列是否全部落在索引内如何改变 EQP 输出，并区分语句级自动索引与 sqlite_autoindex_* 约束索引这两个常被混淆的概念。
【SQLite 内核】单文件 · Pager · B-Tree · VDBE · WAL · 锁
补齐嵌入式行存内核层：从单文件格式、Pager/B-Tree、VDBE 到 Rollback Journal/WAL、锁状态机与计划器，并以 PG/InnoDB、DuckDB、RocksDB 对照收束；承接 sqlite-billion-rows 性能叙事。
【FoundationDB 内核】SSD Engine 与 Redwood：从 SQLite 派生到版本化 B-Tree
梳理 FoundationDB 存储引擎谱系：SIGMOD 2021 时代的 SQLite 派生 SSD Engine 如何把 SQL 剥掉只留 B-Tree，再到 7.x 的 Redwood 多版本前缀压缩 B-Tree；划清无本地事务 WAL 的系统边界，并与 RocksDB LSM 对照机制而非性能排名。
【MySQL InnoDB 内核】B+Tree 与索引：聚簇、回表与页分裂
从 btr0btr.cc 拆解 InnoDB B+Tree：聚簇索引即数据、二级索引回表、Page Directory、btr_cur_search_to_nth_level、页分裂 btr_page_split 与合并、索引 latch。对照 PG nbtree。
【PG 内核】B-Tree 索引：页面分裂、rightlink 与去重
拆解 PostgreSQL B-Tree 索引的内核实现：BTPageOpaque 页面布局（high key / rightlink 的工程意义）、_bt_doinsert() 插入路径与 _bt_split() 页面分裂的完整流程（分裂点选择不是简单的 50/50）、PG 12+ 去重（deduplicate_items）的触发条件与 posting list 压缩策略、B-Tree WAL 记录类型与恢复，以及用 bt_page_items() 和 bt_metap() 观察索引内部结构的实验方法。
【PG 内核】BRIN 与其他索引：什么时候不建 B-Tree 反而更好
过一遍 BRIN 索引的范围摘要哲学——用每个 page range 一条摘要替代逐行索引，在 1TB 的表上创建时间从小时降到秒级。同时讨论两条"不建 B-Tree"的高性价比路径：Hash 索引在 PG 10+ 的 WAL 安全边界和 Bloom 索引的多列任意组合过滤。附带代价对比表和建索引决策树。
【存储工程】存储引擎概览：堆文件到 LSM-Tree 的演化路径
数据库系统的架构可以划分为两大层：上层的查询处理层负责解析 SQL、生成执行计划、优化查询；下层的存储引擎（Storage Engine）负责把数据持久化到磁盘，并在需要时高效地把数据取回来。查询处理层决定"做什么"，存储引擎决定"怎么存、怎么取"。同一个查询处理层可以对接不同的存储引擎——MySQL 的 InnoDB…
【存储工程】B-Tree 与 B+Tree：页式存储引擎的工程实现
数据库要把数据存到磁盘上，又要以尽可能少的磁盘 I/O 把数据找回来。这个矛盾催生了一系列面向磁盘的索引结构（Disk-oriented Index），其中最成功的就是 B-Tree 家族。从 1970 年 Rudolf Bayer 和 Edward McCreight 在波音科学研究实验室提出 B-Tree 起，这个…
【存储工程】索引结构：从 B+Tree 到倒排索引
数据库里存了一亿行数据，要找出 userid 42 的那一行。没有索引的做法是全表扫描（Full Table Scan）——从第一个数据页读到最后一个数据页，逐行比对。假设每个数据页 16 KB，一亿行占 20 GB，即使顺序读能跑到 500 MB/s，也需要 40 秒。加一个 B+Tree 索引，三次磁盘 I/O 就…
【存储工程】XFS 架构：大文件与高并发
XFS 诞生于 1993 年的硅谷图形公司（Silicon Graphics, Inc.），最初运行在 IRIX 操作系统上。 SGI 的核心业务是高性能计算和影视后期制作，客户需要处理的文件动辄几十 GB 甚至数 TB。 当时主流的 EFS（Extent File System）在面对这类工作负载时已经力不从心：元数…