做后端开发久了总会碰到一个经典问题MySQL的InnoDB索引为什么用B树而不是二叉搜索树或者红黑树这里面的主角是B树、B树这对多叉平衡树背景则是二叉树在数据库索引场景下的寸步难行。这篇内容适合刚啃完数据结构、想弄懂数据库索引原理的开发者也适合那些已经在用MySQL但一直没搞明白为什么索引能加速查询的运维和产品同学。我会从二叉树说起一路聊到B树与B树的形态差异最后落到真实存储引擎的取舍上。关于B树和B树网上文章很多但不少看完还是懵B树是红黑树吗它们到底有什么区别为什么写二叉树程序时总是报运行时错误而数据库里的索引却很少听到这种问题这些疑问背后其实是一条清晰的进化链路——二叉搜索树解决了有序查找的基本盘但面对磁盘IO和千万级数据时不够用于是有了平衡树和多叉平衡树。这篇文章想做的就是把这条链路从头到尾捋一遍。1. 从二叉搜索树说起有序查找的“天才设计”为什么会在磁盘上翻车1.1 搜索二叉树、遍历和深度这些基本功到底解决了什么问题二叉搜索树的定义很简单左子树所有节点的值小于根节点右子树所有节点的值大于根节点左右子树各自也是二叉搜索树。这个性质让查找变成了一个不断折半的过程——要找一个值从根开始比大小小往左走大往右走直到命中或者走到空节点。插入和删除也依赖同样的规则维持“任意时刻中序遍历的结果都是递增序列”这个不变量。二叉树的遍历方式前序、中序、后序本质上是在处理树的线性化问题。中序遍历之所以特殊是因为它天然输出有序序列。二叉树的深度则直接决定了查找路径的长度一颗平衡的搜索二叉树n个节点的深度约为log2 n所以单点查找只要O(log n)次比较。这个复杂度已经很好以至于很多人在初学阶段都默认“数据库索引应该就是搜索二叉树”。另外提到遍历线索二叉树是另一个经常被问到的话题它通过把空指针改为指向前驱或后继让中序遍历不需要递归和栈但它优化的是遍历本身而不是查找路径跟数据库索引这件事基本是两条路线。但这里藏着两个重要前提第一数据必须全放在内存里而且每次比较的代价是可以忽略的第二树必须保持平衡。一旦这两个前提不成立二叉搜索树的光芒就暗淡了。数据库面临的是几十GB甚至几TB的数据磁盘才是主战场而磁盘随机访问的成本和内存相比差了几个数量级。1.2 写二叉树程序总是报运行时错误其实是提前给索引实现敲响了警钟很多初学数据结构的同学都经历过这样的崩溃写了一个看似正确的二叉查找树插入几万个节点后程序突然报栈溢出或者在删除节点时出现Segment Fault。按我排了几个通宵调试的经验最常见的三类原因很典型。第一类是递归深度过大。查找和遍历用递归实现时系统栈的深度等于树高如果连续插入有序数据树退化成单链表递归层数就是节点数。几万层递归可能直接击穿默认栈空间表现为RuntimeError或者栈溢出。第二类是空指针没有提前判断比如在递归返回空节点后继续访问它的left或right。第三类是在删除节点时只free了当前节点却没有修正父节点指向它的指针造成“悬空指针”和后续解引用崩溃。这些实现层面的问题放到数据库场景里会被放大成灾难。如果一张上亿行的表用退化的二叉搜索树建索引最坏情况下的查找要走一亿个节点哪怕每个节点只做一次内存比较也无法接受。更别说磁盘IO。所以数据库索引需要的不是一个“理论上O(log n)”的树而是一个工程上能保证层高受控、节点访问次数极少的树。1.3 平衡树家族登场AVL和红黑树把“不退化”变成了硬约束为了解决二叉树退化成链表的问题计算机科学家提出了平衡树。AVL树是最早的一类它要求任意节点的左子树和右子树高度差绝对值不超过1因此任何操作后都要检查平衡因子失衡时通过单旋或双旋恢复。这种严格平衡换来的是极佳的查询稳定性代价则是插入和删除后的旋转次数偏多。红黑树则在平衡强度上做了让步它只要求从根到叶子的最长路径不超过最短路径的两倍用红黑节点的颜色标记和几条约束来实现近似平衡。这个设计让红黑树的插入/删除旋转次数远少于AVL同时依然保证O(log n)的查找复杂度所以C map、Java TreeMap、Linux内核的CFS调度器都用了红黑树。红黑树和AVL树都是二叉的它们把二叉树的深度限制在O(log n)的量级。但是把AVL或红黑树直接搬到磁盘上会立刻遇到瓶颈再怎么说也是二叉树每个节点至多两个孩子。一亿条记录的log2大约是27也就是说一次查找最多要访问27个节点如果这些节点散落在不同磁盘块就可能产生27次随机IO。在内存里27次循环是微秒级的事在磁盘上却可能变成数百毫秒的灾难。这就是数据库索引要从“二叉平衡树”进化成“多叉平衡树”的根本原因。2. 多叉平衡树的底层逻辑扇出、层高和磁盘IO是一笔账2.1 一次磁盘IO有多贵决定了树形索引的基本形态先给一个粗略的量级概念CPU从内存读一个数据大约几十到一百纳秒而从机械硬盘上随机读一个扇区大约需要10毫秒旋转延迟加寻道时间两者相差接近10万倍。即使是SSD随机读也远没有内存快而且存在写放大问题。数据库里的索引查找天然是散列式的随机访问如果设计不佳一次查询就会触发大量随机IO性能立刻崩盘。树形结构的访问模式是从根节点开始每向下一层就要读取当前节点的子节点指针指向的磁盘块。因此一次查找的磁盘IO次数约等于树的层数也就是树高。这里的优化目标很清晰在数据量固定的情况下尽量压低树高。二叉树的高度理论上只能降到log2 N如果要继续压低唯一的出路就是增加每个节点的子节点数量也就是提高“扇出”。2.2 节点变“胖”树才能变“矮”B树节点的尺寸如何与页对齐B树就是顺着这个思路设计出来的。一颗m阶B树每个节点最多有m个子树和m-1个键所有叶子节点都在同一层节点内部按键有序排列查找时在节点内部做二分或顺序扫描然后决定进入哪个子树。m越大每个节点能带的孩子越多树就越矮一次查找的磁盘IO次数就越少。但m不能无限大。每个节点最终要落在一个磁盘块上数据库存储引擎通常以页为读写单位比如InnoDB的默认页大小是16KB。一个B树节点放不下16KB就浪费了放得下但只放了一小部分又会导致扇出不足。因此工程实现上B树节点大小通常按页对齐节点的“胖瘦”其实是页的容量除以单个索引项的大小。索引项越小节点能装下的键越多扇出越大树高越低。这里要纠正一个初学者容易误解的地方B树并不是“为了多叉而多叉”而是为了让节点的逻辑访问和磁盘物理访问对齐。节点内部那些键值对和子指针在一次IO读入节点时就已经全部进内存了所以在节点内部的查找再复杂也是内存操作成本远小于一次额外的磁盘IO。多叉的真正威力是把“多找几层”变成“一层里面多找几次”。2.3 搜索二叉树、B树、B树在同样数据量下的层高账本我们来算一笔具体的账。假设索引表里有1亿条记录需要按整数主键查找。如果是平衡二叉搜索树树高约为log2 1亿约27层。最坏情况下一次查找要经手27个节点如果每个节点在不同磁盘块那是27次随机IO。如果是B树假设一个页能装下约1000个键/指针这个值取决于键长度比如8字节主键加6字节指针16KB页容得下上千个索引项树高约为log1000 1亿约3层。B树的内部节点不存数据同样结构下每个内部节点能装的键更多树高往往还能再低一些加上叶子节点有序链表范围读取也更友好。27次随机IO和3次随机IO之间的差距是数量级的。这也是为什么数据库索引最终选择多叉平衡树而不是把AVL或红黑树改改就用。层高降下来了查询延迟才能降下来这就是“扇出”的意义。3. B树与B树的细节对比从卫星数据的位置到范围查询的胜负手3.1 B树每个节点都带着卫星数据单点命中更直接但扇出和范围扫描吃亏B树的设计里有很重要的一个特点卫星数据记录指针或者在InnoDB里就是整行数据可以存放在任意一层节点上。查找时如果在根节点或者某个内部节点就找到了目标键直接返回结果不需要继续往下走所以单点查找的路径可能比B树少一层。这是B树的优点。但代价也很直接。每个内部节点既然要存数据同样大小的页能装下的键就会变少扇出随之下降。数据量一上来树会比B树高一些。更关键的是范围查询。B树的叶子之间没有像样的连续链表想要查出“id between 100 and 200”这样的区间在找到第一个符合条件的键之后只能重新回到上层节点再沿着中序遍历继续找后继键。这个过程会产生很多“上去-下来”的节点跳跃在磁盘上就是大量随机IO。如果查询范围较长性能会非常难看。3.2 B树内部节点只做路标叶子节点用链表串起全部数据B树和B树的最大区别只有一句话内部节点只保存键和子指针不保存卫星数据所有卫星数据一律放在叶子节点叶子节点之间通过prev和next指针串成一个有序双向链表。这样一改出现了三个连锁收益。第一个收益是“路标更瘦”。内部节点不存数据同样16KB的页能存下的键数量大幅增加扇出变大树更矮。第二个收益是查询路径更稳定。所有数据都在最后一层叶子节点上每次点查都必须走到底但因为树更矮总体IO次数反而更少。第三个收益是范围查询和排序查询天然友好。定位到起点叶子后沿着链表向右顺序扫描即可不仅没有回溯跳跃而且磁盘顺序读性能远好于随机读。ORDER BY、GROUP BY这类需要有序遍历的操作也经常可以直接利用B树叶子链表的顺序性。3.3 回应一个高频问题B树是红黑树吗不是但它是红黑树的磁盘版亲戚很多人看到“B树也是平衡树”就会问那B树是不是红黑树的多叉版答案是不能这么画等号。红黑树是二叉平衡树每个节点只存一个键、最多两个孩子靠颜色约束维持近似平衡B树是多路搜索树一个内部节点可以存上百上千个键有相应数量的孩子靠阶数和分裂合并维持平衡。红黑树和B树真正相似的地方是都通过某种局部操作来维持全局有序和平衡而且都不追求绝对等高的理想形态。但它们的适用场景完全不同。红黑树主要存在于内存数据结构中比如进程调度、关联容器B树则围绕磁盘页设计它的节点大小、叶子链表、分裂策略都和块设备特性深度耦合。我们可以说B树是红黑树在磁盘世界的亲戚但它绝不是简单把红黑树的孩子数量从2改成m。简单汇总一下对比项B树B树卫星数据位置内部节点和叶子节点都可能存只在叶子节点存内部节点作用既路由又携带数据只做路由单点查找可能中途命中路径略短必须走到叶子但树更矮范围查询中序回溯随机IO多叶子链表顺序扫描IO友好扇出相对小相对大常用场景内存文件系统/部分数据库关系型数据库聚簇索引和二级索引这个表格里最值得记住的是“范围查询”那一行。下面用一条SQL把这种差异落到具体行为上。3.4 用一条SQL看清两种树的查询行为差异假设有张订单表orders主键id是从1开始自增的我们在id上建了索引现在执行SELECT * FROM orders WHERE id BETWEEN 100 AND 200;如果底层是B树先沿根节点定位到100所在的节点。假设100不在根节点继续下探到某个子节点在那里找到100后B树要沿着“中序后继”的顺序继续找101、102……每找一个后继可能都需要回到父节点甚至祖先节点再下探到下一个区域节点间的随机跳跃非常频繁。范围长度越大这种倒退访问越明显。如果底层是B树先沿内部节点定位到包含100的叶子页然后从该叶子节点开始一直向右遍历链表依次读取后续叶子页直到遇到超过200的键为止。整个过程几乎没有向后倒退叶子页也是物理上按顺序排列或者顺序预读的IO模型非常友好。这就是为什么几乎所有关系型数据库的聚簇索引都采用B树而不是B树。如果你在面试里能把这个“链表连续范围扫描”的差异讲清楚基本上就把B树和B树的核心区别讲透了。4. 数据库索引的完整进化链路哈希、二叉树、多叉平衡树到底谁适合谁4.1 哈希索引为什么只配做辅助不配做主角除了树形索引之外哈希索引也是一种很常见的索引形式比如Redis的字典结构、MySQL的Memory引擎、InnoDB的自适应哈希索引。哈希索引的等值查找确实可以做到接近O(1)数据分布也足够均匀那为什么数据库不把所有索引都做成哈希核心原因是哈希结构只支持等值比较无法支持范围查询和排序。BETWEEN、大于、小于、ORDER BY这些SQL操作在散列表上全都无从下手。同时哈希索引也做不了最左前缀、模糊匹配这类操作因为它是把整列值散列后存放的键的顺序信息完全丢失。数据库的查询优化器又特别依赖顺序信息来安排扫描和归并所以哈希索引只能作为等值查询的加速补充而不是主索引。从进化链路看索引核心要解决的其实有两个问题一是让单条记录能被快速定位二是让一批有序记录能被连续访问。哈希天然擅长第一个天然不擅长第二个树形结构则可以同时兼顾。所以在主流存储引擎里哈希索引只是B树旁边的一个辅助结构真正扛大梁的始终是有序树。4.2 页、区、段这些存储概念如何反过来塑造B树的形态我在初学B树时有个困惑为什么非要把节点设计成和一个页差不多大小直到理解了存储引擎的组织方式才明白B树不是孤立的数据结构它的每个节点最终都要映射到磁盘上的一个个页。InnoDB把连续64个页称为一个区(extent)再往上是段(segment)但读写的最小单位永远是页。当一个数据页被修改时如果写得不均衡InnoDB会先改到内存里的缓冲池中再由后台线程刷盘。B树的节点分裂和页分裂因此经常是同一件事的两个视角逻辑上我们给B树增加了一个新节点和新的父指针物理上我们申请了一个新页把一半数据拷贝过去再更新页头信息。理解这个映射关系就能明白为什么B树的节点插入流程中找到合适位置后必须预留空闲空间以及为什么页填充率会直接影响写入放大。InnoDB里聚簇索引就是整张表本身叶子节点存完整行数据内部节点只存主键。二级索引则是另一棵B树叶子节点存主键值查询时先查二级索引拿到主键再回聚簇索引取整行这个过程叫回表。回表多一次B树路径查询所以覆盖索引的价值就在于让二级索引的叶子节点直接包含查询所需列省掉这次回表。这些概念如果脱离B树的节点结构去理解很容易背了就忘。4.3 插入、分裂、合并与填充因子多叉平衡树的工程实现细节B树的插入流程看起来很繁琐核心却只有四步先定位到叶子节点在叶子中按序插入键叶子满了就分裂成两个把中间键上提到父节点父节点若因此也满了继续向上分裂最后如果根节点满了就分裂根并新建一个根树高增加一层。整个过程中所有叶子节点依然在同一层这保证了O(log m N)的查找复杂度。删除操作则相反。叶子节点删除后如果节点太“空”需要先尝试从兄弟节点借一个键也就是旋转如果借不到就要和兄弟节点合并并且从父节点删掉一个分隔键父节点可能因此又要继续合并。为了减少分裂和合并带来的写放大InnoDB默认不会让页完全塞满通常会预留约1/16的空间作为填充因子让后续插入有缓冲。这也是为什么你可能观察到InnoDB索引页的填充率基本在15/16左右。这一节想强调的工程经验是B树的优雅并不体现在“绝对平衡”而是体现在“局部调整、整体稳定”。分裂、借用、合并都是局部操作最多向上传导到根涉及路径的长度等于树高而树高又因为多叉被压得很低所以每次写操作的开销也被约束在可接受范围内。如果你手写B树一定会在实现分裂时体会到为什么说“节点大小对齐页”是实用系统里无法回避的决策。5. 踩坑手记与实操建议从二叉树运行时错误到B树动画实现5.1 写二叉树程序为什么总报运行时错误给初学者的完整排查思路每次看到有人问“写二叉树程序时为什么总是报运行时错误”我几乎都能猜到代码里发生了什么。最典型的是递归查找时没有判空。比如下面这段void insert(TreeNode* root, int val) { if (root nullptr) { root new TreeNode(val); return; } if (val root-val) insert(root-left, val); else insert(root-right, val); }很多人的问题在于删除函数里用了局部变量传参导致父节点对子节点的指针没有被更新或者释放节点后没有把指针置空。另一个常见问题是递归基准条件写得不对遍历到叶子的空孩子时仍然访问孩子属性。解决办法其实很简单所有递归函数的第一行都检查指针是否为空删除节点时用指向指针的指针或者返回新的根节点遇到栈溢出时优先检查输入数据是不是有序的因为一颗退化成链表的树会让递归深度直接爆炸。从这些报错也能看出一个关键点二叉树算法的正确性高度依赖递归边界和指针生命周期。数据库索引之所以不用赤裸裸的二叉树正是因为它要在大规模、持久化、并发访问的环境下长期运行任何一个悬空指针都可能带来全库崩溃。学习数据结构时把这些报错踩一遍其实是在提前理解“为什么工业级索引实现那么严谨”。5.2 想真正吃透B树最好自己实现一遍或至少看动画模拟如果你对B树的动态变化没有画面感强烈建议先找B树动画模拟器玩一遍。观察插入时节点如何分裂、中间键如何上提以及范围查询时为什么能沿着叶子链表一路扫过去。动画看几遍比看十篇文字描述都有效。看完动画后可以尝试自己写一个迷你版B树不需要支持并发和持久化只要能在内存里完成查找、插入、删除即可。建议按这样的顺序实现第一步先实现叶子节点的有序数组和叶子链表这在功能上其实是一个跳过分层目录的有序集合第二步增加内部节点和定位逻辑让查找从根节点一路下到叶子第三步实现插入分裂和删除合并。节点结构可以简单定义成下面这样struct BPlusNode { bool isLeaf; vectorint keys; vectorRecord* values; // only for leaf vectorBPlusNode* children; // only for internal BPlusNode *prev, *next; // only for leaf };查找逻辑的核心是循环下探Record* search(BPlusNode* root, int target) { BPlusNode* node root; while (!node-isLeaf) { int i upper_bound(node-keys.begin(), node-keys.end(), target) - node-keys.begin(); node node-children[i]; } for (int i 0; i node-keys.size(); i) if (node-keys[i] target) return node-values[i]; return nullptr; }手写过程中你会发现几个以前没注意到的细节内部节点的key数量始终比孩子数少1分裂后必须给原节点和新节点都加上正确的链表指针删除时借键和合并的判断条件不是“空了就合并”而是要结合最小填充量。这些细节是看动画和读博客很难留下来的只有亲手写过一遍才会真正长在脑子里。5.3 理解B树之后再看索引优化会突然通透很多最后聊一些实际工作中和B树直接相关的索引优化经验。很多慢查询的问题归结到底就是在和B树的三件事打交道树高、叶子链表的扫描范围、以及回表次数。区分度低的列不适合单独建索引。比如性别列只有两个值B树叶子节点的筛选能力极弱扫描范围接近全表优化器可能直接放弃索引。联合索引要尊重最左前缀原则。因为B树的键是按联合列的顺序拼接比较的跳过第一个列的查询无法利用这个有序性。覆盖索引能显著提速。查询所需字段都包含在二级索引叶子节点里时不需要回表省一次B树路径。对索引列使用函数例如WHERE DATE(create_time)...会让B树的有序性失效因为函数计算破坏了原有键的顺序比较。我印象最深的一次调优是处理一张千万行日志表的按月范围查询。最初线上查询要几百毫秒后来发现瓶颈在于二级索引回表次数太多于是把查询字段都塞进联合索引形成覆盖索引延迟直接降到几十毫秒。那次排查完我回头把B树结构又过了一遍这才悟到所谓索引优化本质上是在和树的层高、叶子链表的连续性和回表次数打交道。这个底层视角一旦建立以后看任何数据库执行计划都会顺很多。
MySQL索引为什么选B+树？从二叉树到B+树的进化之路
做后端开发久了总会碰到一个经典问题MySQL的InnoDB索引为什么用B树而不是二叉搜索树或者红黑树这里面的主角是B树、B树这对多叉平衡树背景则是二叉树在数据库索引场景下的寸步难行。这篇内容适合刚啃完数据结构、想弄懂数据库索引原理的开发者也适合那些已经在用MySQL但一直没搞明白为什么索引能加速查询的运维和产品同学。我会从二叉树说起一路聊到B树与B树的形态差异最后落到真实存储引擎的取舍上。关于B树和B树网上文章很多但不少看完还是懵B树是红黑树吗它们到底有什么区别为什么写二叉树程序时总是报运行时错误而数据库里的索引却很少听到这种问题这些疑问背后其实是一条清晰的进化链路——二叉搜索树解决了有序查找的基本盘但面对磁盘IO和千万级数据时不够用于是有了平衡树和多叉平衡树。这篇文章想做的就是把这条链路从头到尾捋一遍。1. 从二叉搜索树说起有序查找的“天才设计”为什么会在磁盘上翻车1.1 搜索二叉树、遍历和深度这些基本功到底解决了什么问题二叉搜索树的定义很简单左子树所有节点的值小于根节点右子树所有节点的值大于根节点左右子树各自也是二叉搜索树。这个性质让查找变成了一个不断折半的过程——要找一个值从根开始比大小小往左走大往右走直到命中或者走到空节点。插入和删除也依赖同样的规则维持“任意时刻中序遍历的结果都是递增序列”这个不变量。二叉树的遍历方式前序、中序、后序本质上是在处理树的线性化问题。中序遍历之所以特殊是因为它天然输出有序序列。二叉树的深度则直接决定了查找路径的长度一颗平衡的搜索二叉树n个节点的深度约为log2 n所以单点查找只要O(log n)次比较。这个复杂度已经很好以至于很多人在初学阶段都默认“数据库索引应该就是搜索二叉树”。另外提到遍历线索二叉树是另一个经常被问到的话题它通过把空指针改为指向前驱或后继让中序遍历不需要递归和栈但它优化的是遍历本身而不是查找路径跟数据库索引这件事基本是两条路线。但这里藏着两个重要前提第一数据必须全放在内存里而且每次比较的代价是可以忽略的第二树必须保持平衡。一旦这两个前提不成立二叉搜索树的光芒就暗淡了。数据库面临的是几十GB甚至几TB的数据磁盘才是主战场而磁盘随机访问的成本和内存相比差了几个数量级。1.2 写二叉树程序总是报运行时错误其实是提前给索引实现敲响了警钟很多初学数据结构的同学都经历过这样的崩溃写了一个看似正确的二叉查找树插入几万个节点后程序突然报栈溢出或者在删除节点时出现Segment Fault。按我排了几个通宵调试的经验最常见的三类原因很典型。第一类是递归深度过大。查找和遍历用递归实现时系统栈的深度等于树高如果连续插入有序数据树退化成单链表递归层数就是节点数。几万层递归可能直接击穿默认栈空间表现为RuntimeError或者栈溢出。第二类是空指针没有提前判断比如在递归返回空节点后继续访问它的left或right。第三类是在删除节点时只free了当前节点却没有修正父节点指向它的指针造成“悬空指针”和后续解引用崩溃。这些实现层面的问题放到数据库场景里会被放大成灾难。如果一张上亿行的表用退化的二叉搜索树建索引最坏情况下的查找要走一亿个节点哪怕每个节点只做一次内存比较也无法接受。更别说磁盘IO。所以数据库索引需要的不是一个“理论上O(log n)”的树而是一个工程上能保证层高受控、节点访问次数极少的树。1.3 平衡树家族登场AVL和红黑树把“不退化”变成了硬约束为了解决二叉树退化成链表的问题计算机科学家提出了平衡树。AVL树是最早的一类它要求任意节点的左子树和右子树高度差绝对值不超过1因此任何操作后都要检查平衡因子失衡时通过单旋或双旋恢复。这种严格平衡换来的是极佳的查询稳定性代价则是插入和删除后的旋转次数偏多。红黑树则在平衡强度上做了让步它只要求从根到叶子的最长路径不超过最短路径的两倍用红黑节点的颜色标记和几条约束来实现近似平衡。这个设计让红黑树的插入/删除旋转次数远少于AVL同时依然保证O(log n)的查找复杂度所以C map、Java TreeMap、Linux内核的CFS调度器都用了红黑树。红黑树和AVL树都是二叉的它们把二叉树的深度限制在O(log n)的量级。但是把AVL或红黑树直接搬到磁盘上会立刻遇到瓶颈再怎么说也是二叉树每个节点至多两个孩子。一亿条记录的log2大约是27也就是说一次查找最多要访问27个节点如果这些节点散落在不同磁盘块就可能产生27次随机IO。在内存里27次循环是微秒级的事在磁盘上却可能变成数百毫秒的灾难。这就是数据库索引要从“二叉平衡树”进化成“多叉平衡树”的根本原因。2. 多叉平衡树的底层逻辑扇出、层高和磁盘IO是一笔账2.1 一次磁盘IO有多贵决定了树形索引的基本形态先给一个粗略的量级概念CPU从内存读一个数据大约几十到一百纳秒而从机械硬盘上随机读一个扇区大约需要10毫秒旋转延迟加寻道时间两者相差接近10万倍。即使是SSD随机读也远没有内存快而且存在写放大问题。数据库里的索引查找天然是散列式的随机访问如果设计不佳一次查询就会触发大量随机IO性能立刻崩盘。树形结构的访问模式是从根节点开始每向下一层就要读取当前节点的子节点指针指向的磁盘块。因此一次查找的磁盘IO次数约等于树的层数也就是树高。这里的优化目标很清晰在数据量固定的情况下尽量压低树高。二叉树的高度理论上只能降到log2 N如果要继续压低唯一的出路就是增加每个节点的子节点数量也就是提高“扇出”。2.2 节点变“胖”树才能变“矮”B树节点的尺寸如何与页对齐B树就是顺着这个思路设计出来的。一颗m阶B树每个节点最多有m个子树和m-1个键所有叶子节点都在同一层节点内部按键有序排列查找时在节点内部做二分或顺序扫描然后决定进入哪个子树。m越大每个节点能带的孩子越多树就越矮一次查找的磁盘IO次数就越少。但m不能无限大。每个节点最终要落在一个磁盘块上数据库存储引擎通常以页为读写单位比如InnoDB的默认页大小是16KB。一个B树节点放不下16KB就浪费了放得下但只放了一小部分又会导致扇出不足。因此工程实现上B树节点大小通常按页对齐节点的“胖瘦”其实是页的容量除以单个索引项的大小。索引项越小节点能装下的键越多扇出越大树高越低。这里要纠正一个初学者容易误解的地方B树并不是“为了多叉而多叉”而是为了让节点的逻辑访问和磁盘物理访问对齐。节点内部那些键值对和子指针在一次IO读入节点时就已经全部进内存了所以在节点内部的查找再复杂也是内存操作成本远小于一次额外的磁盘IO。多叉的真正威力是把“多找几层”变成“一层里面多找几次”。2.3 搜索二叉树、B树、B树在同样数据量下的层高账本我们来算一笔具体的账。假设索引表里有1亿条记录需要按整数主键查找。如果是平衡二叉搜索树树高约为log2 1亿约27层。最坏情况下一次查找要经手27个节点如果每个节点在不同磁盘块那是27次随机IO。如果是B树假设一个页能装下约1000个键/指针这个值取决于键长度比如8字节主键加6字节指针16KB页容得下上千个索引项树高约为log1000 1亿约3层。B树的内部节点不存数据同样结构下每个内部节点能装的键更多树高往往还能再低一些加上叶子节点有序链表范围读取也更友好。27次随机IO和3次随机IO之间的差距是数量级的。这也是为什么数据库索引最终选择多叉平衡树而不是把AVL或红黑树改改就用。层高降下来了查询延迟才能降下来这就是“扇出”的意义。3. B树与B树的细节对比从卫星数据的位置到范围查询的胜负手3.1 B树每个节点都带着卫星数据单点命中更直接但扇出和范围扫描吃亏B树的设计里有很重要的一个特点卫星数据记录指针或者在InnoDB里就是整行数据可以存放在任意一层节点上。查找时如果在根节点或者某个内部节点就找到了目标键直接返回结果不需要继续往下走所以单点查找的路径可能比B树少一层。这是B树的优点。但代价也很直接。每个内部节点既然要存数据同样大小的页能装下的键就会变少扇出随之下降。数据量一上来树会比B树高一些。更关键的是范围查询。B树的叶子之间没有像样的连续链表想要查出“id between 100 and 200”这样的区间在找到第一个符合条件的键之后只能重新回到上层节点再沿着中序遍历继续找后继键。这个过程会产生很多“上去-下来”的节点跳跃在磁盘上就是大量随机IO。如果查询范围较长性能会非常难看。3.2 B树内部节点只做路标叶子节点用链表串起全部数据B树和B树的最大区别只有一句话内部节点只保存键和子指针不保存卫星数据所有卫星数据一律放在叶子节点叶子节点之间通过prev和next指针串成一个有序双向链表。这样一改出现了三个连锁收益。第一个收益是“路标更瘦”。内部节点不存数据同样16KB的页能存下的键数量大幅增加扇出变大树更矮。第二个收益是查询路径更稳定。所有数据都在最后一层叶子节点上每次点查都必须走到底但因为树更矮总体IO次数反而更少。第三个收益是范围查询和排序查询天然友好。定位到起点叶子后沿着链表向右顺序扫描即可不仅没有回溯跳跃而且磁盘顺序读性能远好于随机读。ORDER BY、GROUP BY这类需要有序遍历的操作也经常可以直接利用B树叶子链表的顺序性。3.3 回应一个高频问题B树是红黑树吗不是但它是红黑树的磁盘版亲戚很多人看到“B树也是平衡树”就会问那B树是不是红黑树的多叉版答案是不能这么画等号。红黑树是二叉平衡树每个节点只存一个键、最多两个孩子靠颜色约束维持近似平衡B树是多路搜索树一个内部节点可以存上百上千个键有相应数量的孩子靠阶数和分裂合并维持平衡。红黑树和B树真正相似的地方是都通过某种局部操作来维持全局有序和平衡而且都不追求绝对等高的理想形态。但它们的适用场景完全不同。红黑树主要存在于内存数据结构中比如进程调度、关联容器B树则围绕磁盘页设计它的节点大小、叶子链表、分裂策略都和块设备特性深度耦合。我们可以说B树是红黑树在磁盘世界的亲戚但它绝不是简单把红黑树的孩子数量从2改成m。简单汇总一下对比项B树B树卫星数据位置内部节点和叶子节点都可能存只在叶子节点存内部节点作用既路由又携带数据只做路由单点查找可能中途命中路径略短必须走到叶子但树更矮范围查询中序回溯随机IO多叶子链表顺序扫描IO友好扇出相对小相对大常用场景内存文件系统/部分数据库关系型数据库聚簇索引和二级索引这个表格里最值得记住的是“范围查询”那一行。下面用一条SQL把这种差异落到具体行为上。3.4 用一条SQL看清两种树的查询行为差异假设有张订单表orders主键id是从1开始自增的我们在id上建了索引现在执行SELECT * FROM orders WHERE id BETWEEN 100 AND 200;如果底层是B树先沿根节点定位到100所在的节点。假设100不在根节点继续下探到某个子节点在那里找到100后B树要沿着“中序后继”的顺序继续找101、102……每找一个后继可能都需要回到父节点甚至祖先节点再下探到下一个区域节点间的随机跳跃非常频繁。范围长度越大这种倒退访问越明显。如果底层是B树先沿内部节点定位到包含100的叶子页然后从该叶子节点开始一直向右遍历链表依次读取后续叶子页直到遇到超过200的键为止。整个过程几乎没有向后倒退叶子页也是物理上按顺序排列或者顺序预读的IO模型非常友好。这就是为什么几乎所有关系型数据库的聚簇索引都采用B树而不是B树。如果你在面试里能把这个“链表连续范围扫描”的差异讲清楚基本上就把B树和B树的核心区别讲透了。4. 数据库索引的完整进化链路哈希、二叉树、多叉平衡树到底谁适合谁4.1 哈希索引为什么只配做辅助不配做主角除了树形索引之外哈希索引也是一种很常见的索引形式比如Redis的字典结构、MySQL的Memory引擎、InnoDB的自适应哈希索引。哈希索引的等值查找确实可以做到接近O(1)数据分布也足够均匀那为什么数据库不把所有索引都做成哈希核心原因是哈希结构只支持等值比较无法支持范围查询和排序。BETWEEN、大于、小于、ORDER BY这些SQL操作在散列表上全都无从下手。同时哈希索引也做不了最左前缀、模糊匹配这类操作因为它是把整列值散列后存放的键的顺序信息完全丢失。数据库的查询优化器又特别依赖顺序信息来安排扫描和归并所以哈希索引只能作为等值查询的加速补充而不是主索引。从进化链路看索引核心要解决的其实有两个问题一是让单条记录能被快速定位二是让一批有序记录能被连续访问。哈希天然擅长第一个天然不擅长第二个树形结构则可以同时兼顾。所以在主流存储引擎里哈希索引只是B树旁边的一个辅助结构真正扛大梁的始终是有序树。4.2 页、区、段这些存储概念如何反过来塑造B树的形态我在初学B树时有个困惑为什么非要把节点设计成和一个页差不多大小直到理解了存储引擎的组织方式才明白B树不是孤立的数据结构它的每个节点最终都要映射到磁盘上的一个个页。InnoDB把连续64个页称为一个区(extent)再往上是段(segment)但读写的最小单位永远是页。当一个数据页被修改时如果写得不均衡InnoDB会先改到内存里的缓冲池中再由后台线程刷盘。B树的节点分裂和页分裂因此经常是同一件事的两个视角逻辑上我们给B树增加了一个新节点和新的父指针物理上我们申请了一个新页把一半数据拷贝过去再更新页头信息。理解这个映射关系就能明白为什么B树的节点插入流程中找到合适位置后必须预留空闲空间以及为什么页填充率会直接影响写入放大。InnoDB里聚簇索引就是整张表本身叶子节点存完整行数据内部节点只存主键。二级索引则是另一棵B树叶子节点存主键值查询时先查二级索引拿到主键再回聚簇索引取整行这个过程叫回表。回表多一次B树路径查询所以覆盖索引的价值就在于让二级索引的叶子节点直接包含查询所需列省掉这次回表。这些概念如果脱离B树的节点结构去理解很容易背了就忘。4.3 插入、分裂、合并与填充因子多叉平衡树的工程实现细节B树的插入流程看起来很繁琐核心却只有四步先定位到叶子节点在叶子中按序插入键叶子满了就分裂成两个把中间键上提到父节点父节点若因此也满了继续向上分裂最后如果根节点满了就分裂根并新建一个根树高增加一层。整个过程中所有叶子节点依然在同一层这保证了O(log m N)的查找复杂度。删除操作则相反。叶子节点删除后如果节点太“空”需要先尝试从兄弟节点借一个键也就是旋转如果借不到就要和兄弟节点合并并且从父节点删掉一个分隔键父节点可能因此又要继续合并。为了减少分裂和合并带来的写放大InnoDB默认不会让页完全塞满通常会预留约1/16的空间作为填充因子让后续插入有缓冲。这也是为什么你可能观察到InnoDB索引页的填充率基本在15/16左右。这一节想强调的工程经验是B树的优雅并不体现在“绝对平衡”而是体现在“局部调整、整体稳定”。分裂、借用、合并都是局部操作最多向上传导到根涉及路径的长度等于树高而树高又因为多叉被压得很低所以每次写操作的开销也被约束在可接受范围内。如果你手写B树一定会在实现分裂时体会到为什么说“节点大小对齐页”是实用系统里无法回避的决策。5. 踩坑手记与实操建议从二叉树运行时错误到B树动画实现5.1 写二叉树程序为什么总报运行时错误给初学者的完整排查思路每次看到有人问“写二叉树程序时为什么总是报运行时错误”我几乎都能猜到代码里发生了什么。最典型的是递归查找时没有判空。比如下面这段void insert(TreeNode* root, int val) { if (root nullptr) { root new TreeNode(val); return; } if (val root-val) insert(root-left, val); else insert(root-right, val); }很多人的问题在于删除函数里用了局部变量传参导致父节点对子节点的指针没有被更新或者释放节点后没有把指针置空。另一个常见问题是递归基准条件写得不对遍历到叶子的空孩子时仍然访问孩子属性。解决办法其实很简单所有递归函数的第一行都检查指针是否为空删除节点时用指向指针的指针或者返回新的根节点遇到栈溢出时优先检查输入数据是不是有序的因为一颗退化成链表的树会让递归深度直接爆炸。从这些报错也能看出一个关键点二叉树算法的正确性高度依赖递归边界和指针生命周期。数据库索引之所以不用赤裸裸的二叉树正是因为它要在大规模、持久化、并发访问的环境下长期运行任何一个悬空指针都可能带来全库崩溃。学习数据结构时把这些报错踩一遍其实是在提前理解“为什么工业级索引实现那么严谨”。5.2 想真正吃透B树最好自己实现一遍或至少看动画模拟如果你对B树的动态变化没有画面感强烈建议先找B树动画模拟器玩一遍。观察插入时节点如何分裂、中间键如何上提以及范围查询时为什么能沿着叶子链表一路扫过去。动画看几遍比看十篇文字描述都有效。看完动画后可以尝试自己写一个迷你版B树不需要支持并发和持久化只要能在内存里完成查找、插入、删除即可。建议按这样的顺序实现第一步先实现叶子节点的有序数组和叶子链表这在功能上其实是一个跳过分层目录的有序集合第二步增加内部节点和定位逻辑让查找从根节点一路下到叶子第三步实现插入分裂和删除合并。节点结构可以简单定义成下面这样struct BPlusNode { bool isLeaf; vectorint keys; vectorRecord* values; // only for leaf vectorBPlusNode* children; // only for internal BPlusNode *prev, *next; // only for leaf };查找逻辑的核心是循环下探Record* search(BPlusNode* root, int target) { BPlusNode* node root; while (!node-isLeaf) { int i upper_bound(node-keys.begin(), node-keys.end(), target) - node-keys.begin(); node node-children[i]; } for (int i 0; i node-keys.size(); i) if (node-keys[i] target) return node-values[i]; return nullptr; }手写过程中你会发现几个以前没注意到的细节内部节点的key数量始终比孩子数少1分裂后必须给原节点和新节点都加上正确的链表指针删除时借键和合并的判断条件不是“空了就合并”而是要结合最小填充量。这些细节是看动画和读博客很难留下来的只有亲手写过一遍才会真正长在脑子里。5.3 理解B树之后再看索引优化会突然通透很多最后聊一些实际工作中和B树直接相关的索引优化经验。很多慢查询的问题归结到底就是在和B树的三件事打交道树高、叶子链表的扫描范围、以及回表次数。区分度低的列不适合单独建索引。比如性别列只有两个值B树叶子节点的筛选能力极弱扫描范围接近全表优化器可能直接放弃索引。联合索引要尊重最左前缀原则。因为B树的键是按联合列的顺序拼接比较的跳过第一个列的查询无法利用这个有序性。覆盖索引能显著提速。查询所需字段都包含在二级索引叶子节点里时不需要回表省一次B树路径。对索引列使用函数例如WHERE DATE(create_time)...会让B树的有序性失效因为函数计算破坏了原有键的顺序比较。我印象最深的一次调优是处理一张千万行日志表的按月范围查询。最初线上查询要几百毫秒后来发现瓶颈在于二级索引回表次数太多于是把查询字段都塞进联合索引形成覆盖索引延迟直接降到几十毫秒。那次排查完我回头把B树结构又过了一遍这才悟到所谓索引优化本质上是在和树的层高、叶子链表的连续性和回表次数打交道。这个底层视角一旦建立以后看任何数据库执行计划都会顺很多。