数据库真正有意思的地方并不是“知道它用了 BTree”而是同一种数据结构为什么不同数据库会做出完全不同的实现上次我们认识了 BTree。今天开始从“数据结构”进入“数据库实现”。我们重点比较三个非常经典的数据库SQLitePostgreSQLMySQL InnoDB它们都大量使用 B-Tree 家族索引但存储模型并不一样。一、先看一个最重要的问题假设有一张表User id name age 1 张三 20 2 李四 25 3 王五 30现在SELECT*FROMUserWHEREid2;数据库最终必须完成一件事情找到id 2对应的数据但这里存在两种完全不同的设计。设计 A索引只保存“数据在哪里”例如BTree 2 | ↓ Page 10 Slot 3找到Page 10 Slot 3然后再去读取真正的数据。也就是Index ↓ Record Location ↓ Data设计 B索引本身就是数据例如BTree 2 | ↓ ------------- | id2 | | name李四 | | age25 | -------------找到索引节点数据本身也就找到了。这两个设计看起来只是一个小区别。实际上它会影响整个数据库的存储结构查询路径主键性能二级索引更新方式Page 组织磁盘空间Buffer Pool 使用而 SQLite、PostgreSQL、InnoDB 恰好体现了不同的设计思想。二、SQLiteB-Tree 就是数据组织的核心先看最简单、最紧凑的 SQLite。SQLite 与 MySQL、PostgreSQL 最大的不同之一它不是一个独立的数据库服务器。它通常直接嵌入应用程序Application | ↓ SQLite | ↓ database.db数据库本身就是一个文件。三、SQLite 的核心B-Tree PageSQLite 内部大量数据都组织在 B-Tree 中。可以简单理解成Database File --------- | Page 1 | --------- | Page 2 | --------- | Page 3 | --------- | Page 4 | ---------这些 Page 并不是简单的数据块。它们可以作为B-Tree Internal Page或者B-Tree Leaf PageSQLite 的一个重要特点SQLite 的表本身可以组织成一种 B-Tree。例如Table B-Tree Root | ---------- | | Page A Page B | | Records Records因此 SQLite 的存储模型相对紧凑。它没有简单地采用Heap Separate Primary Index这种模型。四、SQLite 为什么适合这样设计因为 SQLite 的目标非常明确小型、可靠、嵌入式、零配置。它需要一个文件一个进程很少的后台组件尽可能简单的部署方式所以 SQLite 的存储设计非常集中。你可以把它理解为SQLite | -- B-Tree | -- Pager | -- WAL预写日志 | -- File它的很多数据库能力最终都会落到这个文件和 Page 管理体系上。五、PostgreSQL数据和索引分开接下来来看 PostgreSQL。它采用了一个非常重要的设计表数据和索引通常是分开的。例如Table | ↓ Heap | -- Page 0 -- Page 1 -- Page 2另外Index | ↓ B-Tree | -- Index Page -- Index Page -- Index Page两者是独立的。六、PostgreSQL 的索引保存什么假设User id100 name张三Heap 中Page 5 ---------------- | Tuple | | id100 | | name张三 | ----------------B-Tree 索引中100 | ↓ Tuple Location这个位置通常通过**TIDTuple Identifier**来定位。可以把它理解为TID | -- Block Number | -- Tuple Offset也就是Index | ↓ 某个 Heap Page | ↓ 某条 Tuple七、为什么 PostgreSQL 要这样设计因为 PostgreSQL 的设计非常强调表数据本身的独立性。一张表可以拥有多个索引Table | Heap / | \ / | \ ↓ ↓ ↓ Index1 Index2 Index3例如PRIMARY KEY(id) INDEX(name) INDEX(age) INDEX(email)这些索引都指向Heap Tuple因此 PostgreSQL 可以非常灵活地增加不同类型的索引。八、这带来一个重要问题Index Scan 不是终点假设SELECT*FROMUserWHEREid100;PostgreSQLSQL ↓ B-Tree Index ↓ TID ↓ Heap Page ↓ Tuple因此一次查询可能至少涉及Index Page Heap Page这被称为Index Scan Heap Fetch这也是 PostgreSQL 查询性能分析中非常重要的一件事情。九、InnoDB完全不同的思路现在进入 MySQL 的 InnoDB。这里是今天最重要的部分。InnoDB 使用Clustered Index聚簇索引作为表数据的核心组织方式。十、什么叫 Clustered Index假设User id name 1 张三 2 李四 3 王五InnoDB 可以把主键 BTree 组织成Root | [1 | 2 | 3] | ↓ ------------------------- | id1 | 张三 | | id2 | 李四 | | id3 | 王五 | -------------------------叶子节点不只是索引。而是直接保存整行数据。所以Primary Key | ↓ Clustered BTree | ↓ Row Data这就是聚簇索引。十一、为什么 InnoDB 要这么做核心目标之一让主键访问非常高效。例如SELECT*FROMUserWHEREid100;InnoDBRoot ↓ Internal Page ↓ Leaf Page ↓ Row到了 Leaf Page数据已经在那里不需要再Index ↓ Heap ↓ Tuple多走一步。十二、三种数据库放在一起现在我们可以画出一张非常重要的图。SQLiteB-Tree | ↓ Table DataPostgreSQLB-Tree Index | ↓ TID | ↓ Heap | ↓ TupleInnoDBPrimary Key BTree | ↓ Row Data十三、那么二级索引呢这里 InnoDB 又出现一个非常有意思的设计。假设PRIMARY KEY(id) INDEX(name)主键索引id ↓ 完整Row但是name索引不能直接保存整行否则每个二级索引都会非常巨大。因此二级索引通常保存name Primary Key例如name Index 张三 → id100 李四 → id200 王五 → id300查询SELECT*FROMUserWHEREname李四;路径Secondary Index | ↓ Primary Key | ↓ Clustered Index | ↓ Row于是发生了第二次 BTree 查询。这个过程通常被称为回表Table Lookup十四、三种数据库的核心差异现在可以正式比较特性SQLitePostgreSQLInnoDB数据组织B-TreeHeapClustered BTree主键索引B-Tree结构独立索引聚簇索引索引与数据高度融合分离主键融合二级索引依实现而定指向Heap Tuple指向主键查询路径B-TreeIndex → HeapClustered Index设计倾向简洁、嵌入式灵活、扩展性OLTP、高效主键访问这里最重要的不是记住表格。而是理解BTree 只是工具真正决定数据库行为的是“BTree 数据组织方式”。十五、为什么 PostgreSQL 的 Heap 不像 InnoDB 那样直接放到 BTree这是一个非常值得思考的问题。如果把数据直接放进 BTreeBTree | -- Row -- Row -- Row看起来非常高效。但是数据的位置与主键绑定得更加紧密。而 PostgreSQLHeap | -- Tuple -- Tuple -- Tuple Index | -- Index -- Index数据和索引相对独立这样做可以带来更大的灵活性。例如一张表可以拥有B-Tree Hash GiST GIN BRIN等不同索引类型。它们都可以针对同一份 Heap 数据。十六、为什么数据库没有一种“完美”的索引设计因为数据库面临的需求不同。如果目标是主键查询极快。Clustered Index 非常优秀。如果目标是一个表需要多个不同类型的索引。Heap Index 非常灵活。如果目标是极简、单文件、嵌入式。SQLite 的设计非常合适。所以数据库设计 ≠ 寻找最优秀的数据结构 数据库设计 针对目标场景做权衡这是整个数据库内核学习过程中非常重要的思想。十七、再看一个更新问题假设id100 name张三现在UPDATEUserSETnameAlexanderWHEREid100;如果新的数据长度发生变化张三变成Alexander数据可能无法继续放在原来的空间。这时候数据库需要考虑原位置是否足够是否需要移动 Tuple是否产生空闲空间索引是否需要更新其他事务看到什么版本于是**存储结构开始与事务系统产生联系。**这就是下一阶段非常重要的内容。十八、应该建立的知识体系我们已经从Database走到了Database | ↓ Storage Engine | ↓ Page | ↓ Data Organization | ├── Heap | └── BTree | ↓ Index而现在又进一步发现BTree | ── SQLite | ── PostgreSQL | └── InnoDB虽然名字相似B-Tree / BTree但是背后的数据组织方式完全可以不同。十九、重要的三个结论① Index 不等于 DataPostgreSQL 中Index → Heap → Tuple索引只是定位工具。② Clustered Index 可以同时承担 Data IndexInnoDBBTree ↓ Row索引本身就是数据组织结构。③ 数据库设计的核心不是“选择哪个算法”而是根据访问模式、数据规模、写入方式、事务需求和硬件特性决定数据应该如何组织。