MySQL的B+树：数据库界的“瑞士军刀“

MySQL的B树数据库界的瑞士军刀前言为什么我们需要聊这个想象一下你的书架上有一万本书但没有分类没有索引你怎么找到《三体》答案很简单你找不到你会先疯掉。MySQL的B树就是那个给书架建立索引的图书管理员。今天我们就来聊聊这个图书管理员是如何工作的。一、B树是什么一个胖乎乎的树1.1 从二叉树说起一棵瘦弱的树在聊B树之前我们先看看它的前辈们二叉查找树BST就像一个严格的等级制度每个节点最多有两个孩子。左孩子比爸爸小右孩子比爸爸大查找效率O(log n)但问题是如果数据插入顺序不对这棵树会长歪5 / 4 / 3 / 2这哪是树啊这是链表查找效率从O(log n)退化到O(n)就像你本来想在图书馆快速找书结果变成了要在一条长长的走廊里一间间教室找。1.2 B树开始发福为了解决树长歪的问题聪明的计算机科学家发明了B树。B树的核心思想是既然容易长歪那就让它胖一点B树的特点每个节点可以有很多孩子不止两个所有叶子节点都在同一层完美平衡节点存储数据指针就像一个肥胖的人不管怎么吃都不会长歪。1.3 B树B树的升级版B树是B树的加强版主要改进非叶子节点只存索引就像书的目录只告诉你章节在哪页不写具体内容所有数据都在叶子节点真正的内容都在最底层叶子节点用链表连接方便范围查询就像你可以连续看几章[10, 20, 30] / | \ [5,8] [15,18] [25,28] / | / | / | \ [1][3][6][9][12][16][22][26][29] ↑________________________↑ 双向链表连接范围查询神器二、B树的超能力2.1 查找快O(log n)的保证B树的树高一般只有3-4层即使存储上亿条数据假设每个节点能存储100个索引第1层1个节点100个索引第2层100个节点10,000个索引第3层10,000个节点1,000,000个索引第4层1,000,000个节点100,000,000个索引3-4次磁盘IO就能找到任何数据这就像你在100层的楼里找东西但每层都有电梯直接到你想要的房间。2.2 范围查询的杀手锏因为叶子节点有链表连接范围查询简直不要太爽SELECT*FROMusersWHEREageBETWEEN20AND30;执行步骤找到age20的记录沿着链表一直找直到age30完事儿这就像你想看第5-10章的内容直接翻到第5章然后连续往后看就行不用每章都查目录。2.3 磁盘IO友好节省体力B树的设计充分考虑了磁盘IO的特点节点大小页大小通常16KB一次IO读一个节点低树高减少磁盘访问次数顺序读取利用磁盘预读机制这就像你搬家与其跑100趟搬100个小箱子不如跑10趟搬10个大箱子。虽然总重量一样但你少跑了90趟三、MySQL中的B树实现3.1 InnoDB的B树InnoDB存储引擎使用B树作为索引结构有两种索引聚簇索引Clustered Index主键索引数据和索引在一起叶子节点存储完整的行数据一张表只能有一个聚簇索引[主键索引] / | \ [数据页1][数据页2][数据页3] ↑ ↑ ↑ 完整行数据 完整行数据 完整行数据非聚簇索引Secondary Index辅助索引索引和数据分离叶子节点存储主键值不是完整数据需要回表查询完整数据[name索引] / | \ [主键1][主键2][主键3] ↓ ↓ ↓ 回表查完整数据这就是为什么建议用主键查询少一次回表操作3.2 MyISAM的B树MyISAM的索引实现不同所有索引都是非聚簇的索引文件和数据文件分离叶子节点存储数据文件地址就像你的书在图书馆但目录在你家里想找书得先看目录然后去图书馆找。四、B树的操作详解4.1 查找操作假设我们要查找id25的记录[10, 20, 30] ← 25 20 25 30走右边 / | \ [5,8] [15,18] [25,28] ← 25在这里 / | / | / | \ [1][3][6][9][12][16][22][26][29] ↑ 找到了步骤读取根节点25在20和30之间读取右边子节点找到25读取叶子节点获取完整数据3次IO搞定4.2 插入操作插入id23[10, 20, 30] / | \ [5,8] [15,18] [25,28] / | \ [22][26][29]插入23后[10, 20, 30] / | \ [5,8] [15,18] [23,25,28] / | | \ [22][26][29]如果节点满了会分裂中间元素上移到父节点剩余元素分裂成两个子节点就像一个房间住满了就把中间的人提拔为管理员剩下的人分成两个房间。4.3 删除操作删除操作可能会导致节点合并节点数据太少和兄弟节点合并借用从兄弟节点借一个元素就像一个房间人太少就把两个房间合并或者从隔壁房间拉一个人过来。五、B树 vs 其他数据结构5.1 B树 vs 哈希表特性B树哈希表查找O(log n)O(1)范围查询支持不支持顺序访问支持不支持磁盘IO少树高低多容易冲突哈希表就像点对点快递快但只能送到指定地址B树像快递公司虽然慢一点但可以批量配送还能按路线送5.2 B树 vs 二叉树特性B树二叉树树高3-4层可能很深磁盘IO少多范围查询支持不支持节点容量大小2个孩子二叉树像竹竿又高又瘦B树像大树又矮又胖六、实战技巧如何用好B树6.1 索引设计建议主键选择使用自增ID避免页分裂不要用UUID随机性导致频繁分裂联合索引遵循最左前缀原则把选择性高的字段放前面-- 好的索引设计CREATEINDEXidx_user_age_statusONusers(age,status);-- 查询能用到索引WHEREage25ANDstatus1;✅WHEREage25;✅WHEREstatus1;❌ 违反最左前缀索引覆盖让查询只需要访问索引不需要回表-- 假设有索引(age, name)SELECTage,nameFROMusersWHEREage20;✅ 覆盖索引SELECT*FROMusersWHEREage20;❌ 需要回表6.2 避免索引失效-- ❌ 索引失效的情况WHEREYEAR(create_time)2023;-- 函数破坏索引WHEREage126;-- 表达式破坏索引WHEREnameLIKE%张%;-- 左模糊破坏索引-- ✅ 正确的写法WHEREcreate_timeBETWEEN2023-01-01AND2023-12-31;WHEREage25;WHEREnameLIKE张%;七、总结B树是MySQL索引的核心它像一位经验丰富的图书管理员结构合理矮胖的身材工作效率高技能全面点查、范围查询都擅长懂得合作叶子节点手拉手方便批量处理节省资源最小化磁盘IO节省体力记住用好B树你的数据库查询效率会提升N个档次。用不好你的数据库就会变成一只慢吞吞的蜗牛。八、最后的话理解B树不是为了面试装逼而是为了写出高效的SQL。当你看到执行计划里的Using index时你会感谢这位胖乎乎的图书管理员。数据库优化没有银弹但B树至少是一把好刀“计算机科学中的所有问题都可以通过增加一个间接层来解决除了间接层过多的问题。” —— David WheelerB树就是那个完美的间接层参考资源MySQL官方文档《高性能MySQL》《算法导论》第18章B树作者注如果这篇文章让你对B树有了更深的理解或者至少让你笑了两下那我的目的就达到了。毕竟技术不应该是枯燥的