各位老少爷们、婶子大娘、父老乡亲们大家上午好锣鼓敲得震天响欢声笑语挤满场欢迎来到MySQL索引的“斗兽场”。很多人每天都在用索引却从未思考过为什么是B树当面试官问“为什么不用Hash索引Hash不是O(1)吗”或者“为什么不用二叉树”如果你只能回答“因为B树快”那还停留在“知其然”的层面。今天我们要深入到磁盘I/O、树的高度和范围查询的底层逻辑彻底拆解B树的“统治地位”看看它是如何在数据结构的“适者生存”中胜出的。数据结构对比为什么Hash和二叉树都输了辛辛苦苦设计出来的不比b少半点心血啊为什么我愤慨首先我们要打破一个迷思索引并不是越快越好而是要“综合性能”最好。Hash索引的“偏科”Hash索引就像是查字典。你查“Apple”直接算个哈希值一步到位速度是O(1)快得飞起。但想查“所有以A开头的单词”范围查询Hash索引就傻眼了。因为哈希后的值是乱序的你没法按顺序找只能全表扫描。MySQL是通用数据库范围查询WHERE id 100是高频操作Hash索引这种“偏科生”自然被淘汰。没得办法、命格冲突了二叉树的“高瘦”二叉树或红黑树虽然支持范围查询但它太“高”了。假设你有100万条数据二叉树的高度大约是20层。因为数据库数据是存在磁盘上的每访问一层节点就可能发生一次磁盘I/O。20层意味着20次磁盘I/O。磁盘I/O的速度是毫秒级的20次就是几百毫秒这对于高并发系统来说是致命的。我们需要的是“矮胖”的树。不要以当前某些人类的喜好来对待我们mysql、”肤浅“B树的“矮胖”哲学B树之所以胜出核心在于它把树变“矮”了而且把数据存得“巧”了。浓缩的精华非叶子节点只存索引B树的非叶子节点只存键值Key和指针不存数据。这就好比图书馆的目录卡片卡片上只写书名和书架号不写书的内容。这样一个16KB的磁盘页Page能存下成千上万个索引项。结果就是一棵B树的高度通常只有2-4层。查询1000万条数据只需要3-4次磁盘I/O。叶子节点存数据且相连B树的所有数据都存在叶子节点而且叶子节点之间用双向链表连起来了。这就好比图书馆的书不仅按顺序排在书架上而且书架之间还有通道。当你查“100到200之间的订单”时B树先定位到100然后顺着链表往后走就行了不需要再回溯到树根。这就是B树在范围查询上碾压B树和Hash索引的杀手锏。页分裂B树的动态维护B树不是一成不变的当你插入数据时它会动态调整结构。当一个数据页16KB被填满时InnoDB会触发页分裂。它会把当前页的数据一分为二一半留在原页一半移到新页并更新父节点的索引。如果父节点也满了会递归向上分裂甚至可能导致树的高度增加。这就是为什么使用UUID作为主键会导致性能问题UUID是随机的插入位置不固定会频繁触发页分裂产生大量磁盘碎片和I/O开销。而使用自增主键数据总是追加到末尾页分裂的概率大大降低性能更稳定。聚簇索引与二级索引数据到底存在哪在InnoDB中索引和数据是长在一起的。聚簇索引主键索引聚簇索引的叶子节点存的就是整行数据。表数据本身就是按照主键组织的B树。所以用主键查询直接定位到叶子节点拿到数据一步到位。二级索引非聚簇索引二级索引的叶子节点存的是索引列的值和主键ID。当你用WHERE name Alice查询时先在name的二级索引树中找到Alice拿到她的id比如1001。然后拿着1001去主键索引树中再查一遍拿到完整数据。这个过程叫回表。覆盖索引如果你只查SELECT id FROM user WHERE name Alice因为二级索引里已经有id了就不需要回表了。这就好比查目录时目录上直接写了摘要不用去书架翻书了。这就是覆盖索引性能极高。总结B树的胜利是“磁盘I/O优化”的胜利。它用“矮胖”的结构减少了I/O次数。它用“链表”结构优化了范围查询。它用“聚簇”结构保证了数据的物理有序。最后送上金句“索引设计的本质是‘空间换时间’。B树通过降低树的高度矮胖将随机I/O转化为顺序I/O这是关系型数据库屹立不倒的基石。”
B+树的胜利：为什么MySQL索引非它莫属？
发布时间：2026/5/22 3:25:36
各位老少爷们、婶子大娘、父老乡亲们大家上午好锣鼓敲得震天响欢声笑语挤满场欢迎来到MySQL索引的“斗兽场”。很多人每天都在用索引却从未思考过为什么是B树当面试官问“为什么不用Hash索引Hash不是O(1)吗”或者“为什么不用二叉树”如果你只能回答“因为B树快”那还停留在“知其然”的层面。今天我们要深入到磁盘I/O、树的高度和范围查询的底层逻辑彻底拆解B树的“统治地位”看看它是如何在数据结构的“适者生存”中胜出的。数据结构对比为什么Hash和二叉树都输了辛辛苦苦设计出来的不比b少半点心血啊为什么我愤慨首先我们要打破一个迷思索引并不是越快越好而是要“综合性能”最好。Hash索引的“偏科”Hash索引就像是查字典。你查“Apple”直接算个哈希值一步到位速度是O(1)快得飞起。但想查“所有以A开头的单词”范围查询Hash索引就傻眼了。因为哈希后的值是乱序的你没法按顺序找只能全表扫描。MySQL是通用数据库范围查询WHERE id 100是高频操作Hash索引这种“偏科生”自然被淘汰。没得办法、命格冲突了二叉树的“高瘦”二叉树或红黑树虽然支持范围查询但它太“高”了。假设你有100万条数据二叉树的高度大约是20层。因为数据库数据是存在磁盘上的每访问一层节点就可能发生一次磁盘I/O。20层意味着20次磁盘I/O。磁盘I/O的速度是毫秒级的20次就是几百毫秒这对于高并发系统来说是致命的。我们需要的是“矮胖”的树。不要以当前某些人类的喜好来对待我们mysql、”肤浅“B树的“矮胖”哲学B树之所以胜出核心在于它把树变“矮”了而且把数据存得“巧”了。浓缩的精华非叶子节点只存索引B树的非叶子节点只存键值Key和指针不存数据。这就好比图书馆的目录卡片卡片上只写书名和书架号不写书的内容。这样一个16KB的磁盘页Page能存下成千上万个索引项。结果就是一棵B树的高度通常只有2-4层。查询1000万条数据只需要3-4次磁盘I/O。叶子节点存数据且相连B树的所有数据都存在叶子节点而且叶子节点之间用双向链表连起来了。这就好比图书馆的书不仅按顺序排在书架上而且书架之间还有通道。当你查“100到200之间的订单”时B树先定位到100然后顺着链表往后走就行了不需要再回溯到树根。这就是B树在范围查询上碾压B树和Hash索引的杀手锏。页分裂B树的动态维护B树不是一成不变的当你插入数据时它会动态调整结构。当一个数据页16KB被填满时InnoDB会触发页分裂。它会把当前页的数据一分为二一半留在原页一半移到新页并更新父节点的索引。如果父节点也满了会递归向上分裂甚至可能导致树的高度增加。这就是为什么使用UUID作为主键会导致性能问题UUID是随机的插入位置不固定会频繁触发页分裂产生大量磁盘碎片和I/O开销。而使用自增主键数据总是追加到末尾页分裂的概率大大降低性能更稳定。聚簇索引与二级索引数据到底存在哪在InnoDB中索引和数据是长在一起的。聚簇索引主键索引聚簇索引的叶子节点存的就是整行数据。表数据本身就是按照主键组织的B树。所以用主键查询直接定位到叶子节点拿到数据一步到位。二级索引非聚簇索引二级索引的叶子节点存的是索引列的值和主键ID。当你用WHERE name Alice查询时先在name的二级索引树中找到Alice拿到她的id比如1001。然后拿着1001去主键索引树中再查一遍拿到完整数据。这个过程叫回表。覆盖索引如果你只查SELECT id FROM user WHERE name Alice因为二级索引里已经有id了就不需要回表了。这就好比查目录时目录上直接写了摘要不用去书架翻书了。这就是覆盖索引性能极高。总结B树的胜利是“磁盘I/O优化”的胜利。它用“矮胖”的结构减少了I/O次数。它用“链表”结构优化了范围查询。它用“聚簇”结构保证了数据的物理有序。最后送上金句“索引设计的本质是‘空间换时间’。B树通过降低树的高度矮胖将随机I/O转化为顺序I/O这是关系型数据库屹立不倒的基石。”
