摘要当数据规模从几万、几百万增长到千万甚至上亿条时数据库真正需要解决的问题并不是“数据能不能保存下来”而是“如何在如此庞大的数据中快速找到目标”。从最直接的全表扫描到看起来已经足够高效的二分查找再到真正面向数据库存储模型设计的 BTree这背后并不只是数据结构的变化而是一次从算法 → Page → I/O → 数据访问模式的完整转变。一、没有索引数据库如何找到数据在上一篇文章中我们已经建立了一个最基本的数据库存储模型Database │ ▼ Storage Engine │ ▼ Heap / Data File │ ▼ Page │ ▼ Record数据库最终还是要把 Record 存放到某种持久化存储中而数据库访问数据时通常并不是直接面对一条条 Record而是通过 Page 这样的存储单位进行读取和管理。但到这里还有一个非常现实的问题如果我知道自己想找哪一条数据数据库怎么知道它在哪里于是我们继续向上走一层Index │ ▼ Database → Storage → Page → Record这一层就是数据库索引。假设现在有一张用户表User id name ---------------- 1 张三 2 李四 3 王五 4 赵六 ... 1000000000执行SELECT*FROMUserWHEREid900000000;如果数据库没有任何能够帮助定位id的索引结构那么最直接的方法就是从数据中逐步寻找Page 0 ↓ Page 1 ↓ Page 2 ↓ ... ↓ Page N然后不断检查record.id 900000000这就是Full Table Scan全表扫描。如果有 10 亿条记录在最坏情况下就需要检查大量数据。从算法角度看它的时间复杂度是O(N)数据量越大这种方式的代价就越明显。于是第一个问题出现了能不能不从第一条数据开始找二、二分查找已经是 O(log N)为什么还不够如果我们能够保证数据按照id有序排列1 2 3 4 5 ... 1000000000那么事情就简单很多。寻找900000000时我们不需要逐条检查。可以直接取中间位置500000000 / \ / \ 小于目标 大于目标 \ ...不断缩小搜索范围。这就是Binary Search二分查找它的时间复杂度是O(log N)对于 10 亿个有序元素来说理论上只需要大约 30 次比较。从纯粹的算法角度来看这已经非常优秀。那么数据库是不是直接把所有数据排好序然后使用二分查找就可以了问题恰恰出在这里。三、数据库真正需要考虑的不只是算法复杂度数据库中的数据并不是简单地存在一块无限大的连续内存里。我们之前已经知道数据库通常会以Page作为数据管理和 I/O 的基本单位。为了方便理解假设1 Record 100 Bytes 1 Page 8 KB那么一个 Page 大约可以容纳8192 / 100 ≈ 81 Records10 亿条记录就意味着需要大量 Page。现在假设我们对这些数据进行二分查找。逻辑上我们可能会不断跳跃Page 500000 ↓ Page 250000 ↓ Page 375000 ↓ ...从算法角度看这仍然是O(log N)但数据库需要考虑另外一个问题每一次跳跃访问的数据是否已经在内存中如果目标 Page 不在 Buffer Pool 中数据库就可能需要从存储设备读取对应 Page。于是一个看似很小的“比较”背后可能对应一次代价更高的数据访问。这就是数据库与普通内存算法非常重要的区别。数据库不能只看 CPU 上做了多少次比较还必须考虑数据是如何被存储和访问的。因此数据库真正希望优化的并不是简单地把O(N)变成O(log N)而是进一步考虑如何让一次查询尽可能少地访问 Page并让每次 Page 访问获得尽可能多的有效信息这就是 BTree 出现的重要原因。四、BTree让树真正适合数据库的 Page如果直接使用普通二叉搜索树50 / \ 25 75 / \ / \ 12 37 62 87每个节点最多只有两个孩子。当数据规模不断增长时树的高度也会不断增加。如果每访问一层都需要处理一个节点那么树越高就意味着可能需要访问越多的节点。BTree 的思路则完全不同。它不会把一个节点限制成只有两个孩子而是让一个节点拥有大量的子节点[30 | 60] / | \ / | \ / | \ [10 20] [40 50] [70 80]一个节点可以拥有几十、几百甚至更多的子节点。这种结构被称为多路搜索树。它最重要的效果就是降低树的高度。为什么数据库特别希望树变矮假设一个索引节点能够保存约 1000 个子指针。那么理论上第一层 1000 第二层 1000 × 1000 1,000,000 第三层 1000 × 1000 × 1000 1,000,000,000也就是说在这个简化模型中只需要很少的层级就可以覆盖非常大的数据空间。这里的1000只是为了建立数量级上的直觉。真实数据库中的节点 fanout 取决于Page 大小Key 大小Pointer 大小Page HeaderSlot / Metadata具体的数据布局但核心思想不变一个节点保存更多索引信息一个节点拥有更多子节点树的高度降低查询需要经过的 Page 更少。这才是 BTree 的第一个关键设计。五、为什么 BTree 的节点可以和 Page 很好地结合到这里我们还可以继续追问一个问题为什么一个 BTree 节点通常可以设计成一个数据库 Page因为数据库本身就是以 Page 为重要的数据管理单位。于是可以形成这样的对应关系BTree Node ≈ Database Page例如一个索引 Page 可以大致理解成-------------------------------- | Page Header | -------------------------------- | Key | Child Pointer | -------------------------------- | Key | Child Pointer | -------------------------------- | Key | Child Pointer | -------------------------------- | Key | Child Pointer | -------------------------------- | ... | --------------------------------当数据库读取这个 Page 时一次就可以获得大量 Key 以及对应的导航信息。因此BTree 的多路结构和 Page 模型形成了非常自然的匹配BTree │ ▼ 一个节点保存 大量索引信息 │ ▼ 对应一个 Page │ ▼ 一次访问获得大量信息 │ ▼ 降低树的高度 │ ▼ 减少访问 Page这也是为什么学习数据库索引时不能只从“树”本身去理解。BTree 从来不是孤立的数据结构。它和数据库的 Page、Buffer Pool、I/O 以及数据访问模式是联系在一起的。六、为什么是 BTree而不是普通的 B TreeB Tree 和 BTree 经常被放在一起讨论。两者最大的结构差异之一是数据存放的位置。B TreeB Tree 中数据可以出现在内部节点也可以出现在叶子节点[50] / \ [20] [80]也就是说当搜索50时有可能在内部节点就直接找到对应的数据。BTreeBTree 则把内部节点和叶子节点的职责进一步分离。可以简单理解为Internal Node ↓ 只负责导航 Leaf Node ↓ 保存索引项对应的数据定位信息结构类似[50] / \ / \ [10 20 30] [50 60 80]需要注意的是具体“叶子节点保存什么”与索引类型有关。例如在某些数据库的聚簇索引中叶子节点本身可以包含完整的行数据而在二级索引中叶子节点通常保存索引 Key 以及定位对应记录所需的信息。因此更准确的理解是BTree 的内部节点主要负责导航而叶子节点保存最终的索引项。这种设计带来的一个重要好处是内部节点可以尽可能紧凑。内部节点不需要保存完整的数据记录就可以放下更多 Key 和 Child Pointer。于是更多 Key ↓ 更多 Child ↓ 更大的 Fanout ↓ 更低的树高 ↓ 更少的 Page 访问这样又回到了我们最开始讨论的 Page 和 I/O。七、为什么 BTree 的叶子节点还要连接起来BTree 的另一个非常重要的设计是叶子节点通常按照 Key 的顺序连接起来[10 20 30] ↓ [40 50 60] ↓ [70 80 90] ↓ [100 110 120]为什么需要这条链因为数据库并不只有WHEREid100这样的等值查询。还有大量范围查询SELECT*FROMUserWHEREid100ANDid200;这时候我们首先需要找到100。BTree 可以通过从 Root 到 Leaf 的路径快速定位到第一个位置Root ↓ Internal Page ↓ Leaf Page ↓ 100找到之后不需要重新从 Root 开始寻找110、120、130……而是可以沿着叶子节点继续向后访问[100 110 120] ↓ [130 140 150] ↓ [160 170 180] ↓ [190 200]所以 BTree 的优势并不只是快速找到一个值。它还提供了快速定位起点 按顺序遍历后续数据。这也是 BTree 特别适合数据库范围查询的重要原因。八、一次 BTree 查询到底发生了什么现在把前面的知识全部串起来。假设执行SELECT*FROMUserWHEREid900;假设索引结构如下Root Page [500 | 800] / | \ / | \ / | \ Page A Page B Page C | ▼ [850 | 900 | 950]查询开始。第一步访问 Root数据库首先从索引的 Root 开始。Root 中有500 | 800因为900 800所以继续进入对应的子节点。第二步访问下一层进入目标 Internal Page。继续比较 Key850 | 900 | 950找到900第三步定位最终数据索引项会提供进一步定位数据所需要的信息。于是查询路径可以抽象成SQL ↓ BTree Root ↓ Internal Page ↓ Leaf Page ↓ Record Location ↓ Data Page ↓ Record如果目标数据已经在 Buffer Pool 中访问过程会进一步表现为内存中的 Page 查找。如果所需要的 Page 不在内存中则可能需要从存储设备读取。因此一次索引查询真正涉及的并不是简单的比较 Key而是Key Comparison Page Navigation Buffer Management Data Access这也是数据库索引和普通内存数据结构之间非常重要的区别。九、BTree 为什么特别适合数据库到这里可以把 BTree 的几个关键特性放到一起BTree │ ┌───────────┼───────────┐ │ │ │ ▼ ▼ ▼ 多路分支 有序 Key 叶子链 │ │ │ ▼ ▼ ▼ 低树高 快速定位 范围扫描 │ │ │ └───────────┼───────────┘ ▼ 适合数据库访问它同时解决了几个数据库非常重要的问题多路分支降低树高内部节点主要负责导航Key 保持有序叶子节点支持顺序访问节点可以与 Page 很好地结合支持动态插入和删除支持等值查询和范围查询所以 BTree 的优势不是某一个单独的特性。真正强大的是这些特性组合在一起之后形成的效果。十、索引并不是免费的如果索引这么好那么一个自然的问题就是为什么不把所有字段都建立索引因为索引本身也是数据。假设 User 表拥有id name age address phone email如果为这些字段全部建立索引那么数据库需要额外维护多棵索引树。于是查询可能变快但写入就会产生额外工作。例如INSERTUPDATEDELETE这些操作不仅需要修改数据本身还可能需要修改对应的索引。因此数据修改 │ ├── 修改 Data Page │ └── 修改 Index Page索引带来的成本主要可以从几个方面理解。1. Storage Cost索引本身需要额外的存储空间。Data Index索引越多占用的空间通常越大。2. Write Cost插入、删除和更新数据时对应索引也可能需要维护。因此INSERT ↓ Data Update Index Update3. Maintenance CostBTree 需要保持自己的结构特性。例如Page Split Page Merge Rebalance这些操作都会带来额外的维护成本。所以索引不是越多越好而是在查询收益和维护成本之间进行权衡。十一、Page SplitBTree 写入的代价假设一个 Page 已经接近或者达到容量上限[10 20 30 40]现在插入25如果当前 Page 没有足够空间就需要进行结构调整。简化来看可以理解为原 Page [10 20 25 30 40] ↓ Page Split / \ [10 20] [25 30 40]Split 之后父节点还需要增加新的索引信息。如果父节点本身也已经没有空间那么父节点也可能发生 SplitLeaf Split ↓ Parent Update ↓ Parent Split ↓ Continue Upward在极端情况下甚至可能导致 Root Split使树的高度增加。因此BTree 的写入并不是简单地“找到位置然后写进去”。它还需要不断维护整个树的结构。这也是 BTree 在高写入场景下需要重点考虑的问题。十二、为什么 Hash Index 没有取代 BTree既然 Hash Table 的等值查询平均可以达到接近 O(1)那么一个自然的问题是为什么数据库还需要 BTree关键在于数据库需要解决的不只是等值查询。Hash 非常适合WHEREid100但对于WHEREid100ANDid200Hash 就很难发挥同样的优势。因为 Hash 的核心思想是Key ↓ Hash Function ↓ Bucket它强调的是根据一个 Key 快速定位。而 BTree 强调的是维护 Key 的有序关系。因此特性HashBTree等值查询优秀优秀范围查询较弱优秀有序遍历较弱优秀排序相关操作较弱优秀前缀 / 范围访问较弱较强动态维护相对简单更复杂因此Hash 更接近“精确定位”的思维而 BTree 更接近“有序定位”的思维。数据库查询模式非常丰富需要的不只是找到一个值还需要找到一个范围 找到第一个值 找到下一个值 按照 Key 顺序遍历这也是 BTree 能够长期成为数据库索引重要方案的原因之一。十三、为什么 BTree 成为了数据库索引的重要方案现在可以回头重新看这个问题为什么数据库喜欢 BTree并不是因为 BTree 是一种优秀的数据结构。而是因为它很好地匹配了数据库的实际工作方式BTree │ ┌───────────────┼───────────────┐ │ │ │ ▼ ▼ ▼ 多路分支 Key 有序 叶子链 │ │ │ ▼ ▼ ▼ 低树高 快速定位 范围扫描 │ │ │ └───────────────┼───────────────┘ ▼ Database │ ┌─────────┴─────────┐ ▼ ▼ Page I/O它不是只考虑 CPU 上的比较次数。而是同时考虑数据结构 Page Buffer Pool I/O 数据访问模式这其实是数据库设计中一个非常重要的思想数据结构不能脱离它所运行的硬件和存储模型单独讨论。十四、BTree 也不是终点如果 BTree 这么优秀那么为什么后来又出现了LevelDBRocksDBLSM Tree等完全不同的存储设计答案来自 BTree 的另一个方面写入。一个典型的 BTree 写入过程可能涉及找到目标 Leaf ↓ 修改 Page ↓ Page 可能已满 ↓ Page Split ↓ 更新 Parent ↓ 可能继续向上 Split如果数据库长期面对大量随机写入这种维护方式可能产生较高的写放大和随机更新成本。于是另一个非常重要的设计思想出现了**既然随机更新 BTree 有成本那么能不能把大量写入先变成更适合顺序写的形式**这正是 LSM Tree 所关注的问题。于是数据库存储系统出现了另一条非常重要的路线BTree │ │ 擅长 │ 低树高 │ 有序查询 │ 范围访问 │ └──────────────┐ │ ▼ 另一种思路 │ ▼ LSM Tree │ ▼ Sequential Write Compaction这里不需要急着讨论 LSM Tree 的具体实现。真正值得留下的问题是当数据库从“读多写少”逐渐走向“写多读多”时BTree 的设计是否仍然是最合适的这个问题也正好引出了下一阶段对 LevelDB、RocksDB 和 LSM Tree 的学习。十五、真正应该记住的是什么如果这篇文章能留下些什么我希望是下面这条完整的逻辑数据规模变大 ↓ 全表扫描成本过高 ↓ 尝试二分查找 ↓ O(log N) ↓ 但数据库需要考虑 Page 和 I/O ↓ 需要降低树高和 Page 访问次数 ↓ BTree ↓ 多路分支 ↓ 低树高 ↓ Page 友好 ↓ 快速定位 有序遍历 ↓ 等值查询 范围查询所以BTree 最值得学习的并不是它有几个节点、几个指针、怎么分裂。这些当然重要但那属于实现层面。更重要的是理解它背后的设计过程当我们知道数据库的数据是以 Page 为单位管理并且 I/O 成本远高于简单的 CPU 比较之后就会开始思考能不能让一个 Page 保存尽可能多的索引信息能不能让树尽可能矮能不能在快速定位之后继续顺序访问于是BTree 的结构就不再显得神秘。它并不是凭空出现的一棵“高级树”。而是从数据库的实际约束中一步一步推导出来的。