摘要介绍二叉树、AVL树、红黑树、B树、B树和B*树等六种树的数据结构后浅析MySQL InnoDB索引选择B树的原因并给出一些MySQL 索引高频面试题。文章目录综述二叉查找树AVL树/红黑树B树(B-tree)B树B TreeB\*树树的总结实际应用中的索引优化聚集索引和辅助索引面试实战指南结束语Reference综述数据库是后端工程师绕不开的核心技术而索引则是核心中的核心。在日常工作中我们每天都在和索引打交道索引问题也是高级工程师面试中面试官最喜欢考察的地方。很多开发者在面试中谈及索引时往往只能给出一些零散、机械的记忆性答案比如“B树查询快”、“索引能提速”。这样的回答在面试官心中留下的深刻印象就是此候选人学习知识浅尝辄止不够深入不够努力。真正体现一个工程师技术深度的是对索引背后设计原理的系统性理解以及在复杂场景下进行选型和优化的能力。在 MySQL 中通常所说的索引如果没有特别声明默认都是指 B 树数据结构的索引。在介绍各种树的数据结构和MySQL索引之前先介绍本文多次使用的几个基本概念节点包含一个数据元素及若干指向子树的指针等。根节点是树的起始节点它没有父节点就像是大树的根基其它节点都从根节点衍生出来。叶子节点也叫终端节点是没有子节点的节点它们位于树的最底层就像树枝的末梢。内部节点internal Node至少有一个子节点的节点包括根节点和所有非叶子节点。兄弟节点 具有相同父节点的节点。节点的度该节点拥有的子节点个数。例如二叉树中节点的度最大为 2即每个节点最多有两个子节点。树的度整棵树中所有节点的最大度数。层级从根节点开始树的每一层都是一个层级。高度height当前节点到最远叶子节点的最长路径上的节点数。平衡因子Balance Factor简称BF每个节点的左右子树的高度之差。数据页树上每个节点在计算机中叫做数据页是 InnoDB 存储引擎与磁盘交互的最小单位默认大小为 16KB。阶数一个节点最多可以有多少个子节点即节点的最大度数一般用小写字母m表示阶数。用⌈m/2⌉表示对m/2向上取整数。例如三阶 B 树 → 每个节点最多 3 个子节点 → 最大度 3。在数据库中我们将B树作为索引结构可以加快查询速度此时树中的key一般是表的主键。例如MySQL InnoDB 的记录就是按照主键由小到大排序后存在 B 树的叶子节点里。树中每个节点存储了关键字key、关键字对应的数据data以及指向孩子节点的指针。我们将一个key及其对应的data称为一条记录。但为了方便描述除非特别说明后续文中就用“关键字”来代指key, value键值对。下面就是MySQL中索引的数据结构图1 索引的数据结构。备注磁盘块4有笔误应该删除10不同的树结构适用于不同的应用场景选择合适的树结构可以显著提高程序的性能和效率。在分析为什么MySQL InnoDB存储引擎的索引选择使用B树之前我相信很多攻城狮对数据结构中的树还是有些许模糊的因此就让我们一同踏上这趟由浅入深探讨二叉查找树、AVL树、红黑树、B树和B*树的奇妙之旅一步步引出B树以及为什么MySQL InnoDB数据库索引选择使用B树领略B树在数据库索引中应用的神奇魅力。希望通过本文你能构建起一个体系化的树和索引知识框架让你在未来的面试和工作中游刃有余。二叉查找树二叉查找树(Binary Search Tree, BST)也称为有序二叉树Ordered Binary Tree、排序二叉树sorted binary tree或者二叉搜索树是一棵满足以下三个性质的二叉树有序性任意非空左子树所有节点的值均小于该节点的值非空右子树所有节点的值均大于该节点的值递归性任意节点的子树都是二叉查找树每个节点存储一条记录且没有键值相等的节点。从递归定义的角度来看二叉查找树可以被定义为要么是一棵空树要么是由一个根节点和两棵互不相交的分别称作根的左子树和右子树组成的非空树而左子树和右子树又同样都是二叉查找树。这种递归定义方式简洁而准确地描述了二叉查找树的结构特点。它作为基础的树形结构每个节点最多有两个子节点其递归性和有序性为我们理解更复杂的树结构奠定了基础。图2 二叉搜索树如果我们需要查找id31的记录利用我们创建的BST基于二分查找算法实现的查找流程如下将根节点作为当前节点把31与当前节点的键值33比较31小于33接下来我们把当前节点的左子节点作为当前节点。继续把31和当前节点的键值28比较发现31大于28把当前节点的右子节点作为当前节点。把31和当前节点的键值31对比发现二者相等满足条件遍历结束。所以我们利用BST只需要3次即可找到目标数据。二叉树的查找、插入和删除操作的时间复杂度在平均情况下为 O(logn) 但在最坏情况下当二叉树退化为链表时时间复杂度会变为 O(n) 。这是因为在最坏情况下所有节点都在一条链上查找、插入和删除都需要遍历整个链表。如下图所示退化的二叉查找树二叉树完全不平衡时查找的时间复杂度就和链表一致了O(n)。导致这个现象的原因其实是BST变得不平衡了也就是高度太高了从而导致查找效率的不稳定。为了解决这个问题我们需要保证二叉查找树一直保持平衡从而引出了一个新的定义——平衡二叉树AVL。AVL树/红黑树平衡二叉树Balanced Binary Tree是一种特殊的、平衡的二叉搜索树通过严格控制每个节点的平衡因子来保持树的平衡。常见的平衡二叉树有AVL树和红黑树等在满足BST特性的基础上具有如下特性平衡因子限制要求平衡因子的绝对值不能超过1。递归性质左右两个子树本身也都是平衡二叉树。不管是执行插入还是删除操作只要不满足上面的条件就要通过旋转树上的节点来保持平衡使得树的高度始终保持在 O(logn)的范围内。而旋转是非常耗时的由此我们可以知道AVL树适合用于插入或者删除次数比较少但查找多的情况。 为什么要平衡保持效率平衡的二叉搜索树可以确保不管是执行插入还是删除操作都能在O(logn)时间内完成这对于需要高效处理数据的系统来说至关重要。避免最坏情况没有平衡机制的数据结构在最坏情况下可能会退化成链表导致效率大大降低。平衡机制通过旋转操作完成而旋转操作非常耗时由此我们可以知道AVL树适合用于插入或者删除次数比较少但查找多的情况。本文不介绍具体的旋转操作。平衡二叉树通过约束节点的子树高度差确保树的高度保持对数级相比于二叉查找树来说查找效率更稳定总体的查找速度也更快。红黑树Red-Black Tree因节点是红色和黑色两种颜色之一而命名它本身是一棵二叉查找树在其基础上做了如下约束根节点是黑色节点所有叶子节点NIL节点都是黑色的节点的颜色要么是黑色要么是红色无连续红色节点红色节点的子节点为黑色节点即相邻的两个节点不可能同时为红色任意节点的左子树和右子树高度只统计黑色节点相同旋转操作当插入或删除导致树不平衡时通过旋转操作来恢复平衡。这些规则看起来是否有点复杂其实它们的核心目的只有一个控制整棵树的高度防止退化成链表。下图是一个标准的红黑树黑色完美平衡“任意节点的左子树和右子树高度只统计黑色节点相同 红色节点的子节点是黑色节点”。这就保证了红黑树的“平衡性”。由于这种平衡其查询的复杂度自然也是O(log n)的。红黑树与AVL树的区别特性AVL 树红黑树平衡性非常严格平衡因子最多为1近似平衡只要求从根到叶子的最长路径不超过最短路径的两倍插入性能多次旋转效率较低快最多两次旋转删除性能多次旋转效率更低代价更高较快最多三次旋转查找性能更快稍慢但仍为 O(log n)相较于 AVL 树它是一种弱平衡二叉树不需要像 AVL 树那样严格要求平衡这也导致它的查询效率并没有 AVL 树那么高但相对的它带来的好处是对于调整失衡红黑树的旋转次数更少所以频繁的插入或删除操作红黑树更有优势。AVL 是“强迫症患者”每次插入删除都可能引发多次旋转代价太高而红黑树是“实用主义者”它不要求完全平衡只要能保证查找效率不崩就行。红黑树是在“速度”、“稳定性”和“实现成本”之间找到的一个折中王者红黑树更常用于需要高频插入和删除的场景例如java 8 HashMap和ConcurrentHashMap中链表转红黑树epoll在内核中的实现用红黑树管理事件块文件描述符Java的TreeMap和TreeSet实现linux进程CFS调度器Completely Fair Scheduler用红黑树管理进程控制块 nginx中用红黑树管理timer。AVL树更适合读多写少的场景因为它的查找性能更接近完美的平衡树。B树(B-tree)当数据量太大无法全部装入内存时就必须存放在磁盘上。磁盘I/O读写速度远远逊色于内存访问。B树和B树就是为了减少磁盘I/O次数而设计的多路平衡搜索树它们被广泛用于数据库和文件系统的索引。下面介绍B树。B树Balance Tree也称B-树是一棵平衡多路查找树节点的子节点个数可能超过两个用来存储排序后的数据。我们描述一棵B树时需要指定它的阶数m当m2时就是我们常见的二叉搜索树。B树是一种自平衡的树状数据结构能够让数据的查找、插入及删除动作都在对数时间内完成常常用在存储系统上如数据库或文件系统。一棵m阶的B树或为空树或为满足下列特性的m叉树每个节点最多有mm2棵子树除非根节点为叶子节点否则至少有两棵子树。例如对于一个4阶B树每个节点最多有4个孩子最少有2个孩子每个节点存放至少⌈m/2⌉-1个关键字至多m-1个关键字关键字个数比孩子节点个数小1。即如果一个节点有k个关键字那么它就有k 1个孩子。如下图所示为一棵3阶B树的结构示意图根节点有2个关键字和3个指针它有3个孩子这些孩子分别对应关键字划分的3个区间若根节点不是叶子节点则至少包含两棵子树特殊情况没有孩子的根节点即根节点为叶子节点整棵树只有一个根节点除根节点和叶子节点外其它每个节点至少有⌈m/2⌉棵子树每个节点中的关键字都按照从小到大的顺序排列每个关键字的左子树中的所有关键字都小于它而右子树中的所有关键字都大于它所有叶子节点都位于同一层或者说根节点到每个叶子节点的长度都相同。这保证了B树的平衡性使得查找操作的时间复杂度为O(logn)。下图即是一棵 m3 的B树在实际应用中B树的阶数都非常大通常大于100所以即使存储大量的数据B树的高度仍然比较小。每个节点中存储了关键字key和关键字对应的数据data以及孩子节点的指针。B树和平衡二叉树的不同之处B树属于多叉树父节点的子节点个数不止两个。注意: 有文章把B树和B-tree理解成了两种不同类别的树其实二者是同一种树。B树有如下数据特征数据存储在整棵树中任何一个关键字出现且只出现在一个节点中搜索有可能在非叶子节点结束故查询性能不稳定其搜索性能等价于在关键字全集内做一次二分查找自动平衡树的高度和数据页。B-树的查询方式如下从根节点开始对节点内的关键字有序序列进行二分查找如果命中则结束否则进入查询关键字所属范围的儿子节点重复直到所对应的儿子指针为空或已经是叶子节点。B树B TreeB树是在B树的基础上又一次改进的多路平衡搜索树其主要在两个方面进行了提升一方面是查询的稳定性让查询速度更加稳定其速度完全接近于二分查找另外一方面是在数据排序方面更友好更充分的利用节点的空间。B树包含两种类型的节点内部节点也称索引节点和叶子节点。根节点本身即可以是内部节点也可以是叶子节点。B树的规则与B树基本类似但是又在B树的基础上做了以下几点改进父节点存有指向右子树第一个元素的索引。内部节点不存储数据只存储索引用于路由叶子节点存完整行数据主键索引或 (索引列 主键)二级索引。这是B树与B树的最大差异。内部节点的子树指针与关键字个数相同。内部节点的关键字都按照从小到大的顺序排列对于内部节点中的一个关键字左子树中的所有关键字都小于它右子树中的关键字都大于等于它。所有叶子节点都存储指向下一个相邻叶子节点的指针形成一个单向链表。下图是一棵m3的B树MySQL中的B树是上述B树的又一次进化MySQL基于普通BTree在叶子节点添加了一个指向上一个相邻叶子节点的指针并且首尾叶子节点也是相连的也就是构造了一个如图1所示的双链表。下文再提及B树时指带有双向链表的MySQL B树。B树相对于B树有一些自己的巨大优势可以归结为下面几点优势说明更稳定的查询效率数据仅存储在叶子节点任何查找都必须走到叶子节点路径长度相同性能稳定。更高的空间利用率内部节点不存数据存储的关键字更多树更矮读取数据时I/O次数更少。强大的范围查询叶子节点通过指向前后叶子节点的指针形成了一个有序双向链表故可以高效地进行范围查询和反向排序而B树需要进行复杂的中序遍历。更适合磁盘预读磁盘按数据页读写。B树的节点通常设计为恰好一数据页大小一次I/O能加载更多键进一步减少I/O。B树的插入操作很简单只需要记住一个技巧即可当节点元素数量大于m-1的时候就按中间元素分裂成左右两部分中间元素的关键字分裂到父节点当做索引存储但是本身中间元素还是分裂到右子树中。面试题B树为什么比B树更适合作为操作系统的文件索引和数据库索引简答如下B树的磁盘读写代价更低。它的内部节点没有存储记录因此一个内部节点相对B树可以存储更多的关键字一次性读入内存中的需要查找的关键字也就越多从而降低I/O次数。B树的查询效率更加稳定。由于内部节点并不是最终指向文件内容的节点而只是叶子节点中关键字的索引。所以任何关键字的查找必须走一条从根节点到叶子节点的路。所有关键字查询的路径长度相同导致每一个数据的查询效率相当。B树支持范围查询。B树只要遍历叶子节点就可以实现整棵树的遍历支持基于范围查询而B树不支持范围查找。面试题为什么 MySQL InnoDB 选择 B 树作为索引结构相对于二叉树B 树的层级更少搜索效率更高。相对于 Hash 索引B 树支持范围查找、降序排序以及升序排序操作。B树无论是叶子节点还是非叶子节点都会保存数据这样会导致一个数据页中存储的键值减少指针跟着减少要保存同样多的数据只能增加树的高度导致性能降低。B 树中间节点没有存储数据只存储索引。这就意味着同样大小的数据页可以容纳更多节点元素在相同的数据量下B 树更加 “矮胖”I/O 操作更少。因为数据存储位置不同导致查询过程也不同B树只需找到匹配元素即可终止遍历最好情况下查找到根节点最坏情况下查找到叶子节点故查询性能很不稳定而 B 树每次必须查找到叶子节点查询性能稳定。B*树B*树B star Tree是普通B树的变形在普通B树除根节点外的内部节点增加指向兄弟节点的指针将节点的最低利用率从普通B树的1/2提升到2/3。下图是一棵m3的B*树在B树的基础上因其初始化的容量变大使得节点空间使用率更高而又存有兄弟节点的指针可以向兄弟节点转移关键字的特性使得B*树分裂次数变得更少。B树的分裂当一个节点满时分配一个新的节点并将原节点中1/2的数据复制到新节点最后在父节点中增加新节点的指针B树的分裂只影响原节点和父节点而不会影响兄弟节点所以它不需要指向兄弟节点的指针。B*树的分裂当一个节点满时如果它的下一个兄弟节点未满那么将一部分数据移到兄弟节点中再在原节点插入关键字最后修改父节点中兄弟节点的关键字因为兄弟节点的关键字范围改变了如果兄弟也满了则在原节点与兄弟节点之间增加新节点并各贡献三分之一的数据到新节点最后在父节点增加新节点的指针。所以B*树分配新节点的概率比B树要低空间使用率更高。树的总结1、相同思想和策略从平衡二叉树、B树、B树、B*树总体来看它们贯彻的思想是相同的都是采用二分查找和数据平衡策略来提升查找数据的速度。2、不同的方式对树的不断优化为了保证树的节点均匀分布所以在二叉树基础上增加了平衡算法就有了平衡二叉树。为了减少树的高度B树一个节点下面允许添加N个子节点然后每个节点的大小默认限制在16KB只需要通过一次IO就能读取到任意一个节点上的所有数据通过增加节点存储的键值对个数减少了树的高度而并没有让IO次数变多。B树在B树的基础上对查询的稳定性和排序策略进行了优化因为B树所有的数据都保存到叶子节点并且所有叶子节点本身是有序排列的。B*树为了减少树在构建过程中节点的分裂或者合并次数所以在每个非根节点的内部节点上都保存了兄弟节点的指针在节点需要进行分裂或者合并时优先从兄弟节点挪数据从而减少节点构建过程中分裂或者合并的次数提升了树的构建性能将节点的最低利用率从1/2提高到2/3。实际应用中的索引优化了解 B树 和 B树的基本原理后在实际应用中如何合理使用索引呢首先要选择合适的索引列。对于经常用作查询条件和排序的列应该建立索引。其次要注意索引的维护。频繁更新的列会导致索引重建因此要权衡索引的利弊。最后要根据查询需求选择合适的索引类型对于需要频繁进行范围查询的列B 树索引是更好的选择。在实际应用中还可以通过复合索引、覆盖索引等高级技术进一步优化查询性能。聚集索引和辅助索引MySQL InnoDB存储引擎数据库中的BTree索引可以分为聚集索引clustered index也叫主键索引、聚簇索引和辅助索引secondary index也叫非聚集索引。聚集索引也叫主键索引叶子节点中的data存储的是该主键对应的整行数据通常BTree的高度为3也就是有三层节点MySQL会把BTree第一层也就是根节点放在内存中我们根据主键索引查数据只需要两次磁盘I\O第二层1次第三层1次即可。非聚集索引也叫辅助索引叶子节点中存储的是该索引所在记录的主键值所以非聚集索引的寻址过程分两种情况(1) 非聚集索引已经索引覆盖了那么只需要遍历这非聚集索引这一个BTree即可按照上面的分析需要两次磁盘IO即可mysql会把根节点放到内存中。(2) 非聚集索引不能索引覆盖那么需要回表。先需要在非聚集索引这个BTree上两次IO找到主键然后拿着主键去聚集索引的BTree上找对应的完整数据记录。相比第一种情况IO次数要多所以我们通常喜欢索引覆盖。这个过程会增加额外的 IO 消耗和网络传输时间降低查询性能。下图表示非聚集索引不能索引覆盖的情况右侧的辅助索引先拿到主键值5然后去左侧的主键索引中寻址最后可以得到整行记录的内容。面试实战指南掌握了以上各种树的知识你已经能应对80%的索引问题。但想在面试中真正征服面试官还需要准备一些更具深度和广度的话题有备无患。在考察索引问题的时候阅人无数的面试官很可能对以下几个问题深挖你可以准确回答了吗B树与B树、红黑树等其它树的对比MySQL索引会失效吗MySQL InnoDB表中含有NULL值的列建索引有作用吗MySQL InnoDB高度为3的BTree可以存储多少条数据MySQL innoDB索引为什么不选择B*树答案即将揭晓敬请关注小编。结束语本文首先根据树的衍化历程介绍了二叉树、AVL树、红黑树、B树、B树和B*树等六种树的数据结构然后介绍了如何一步步降低树的高度提升增删改查效率最后介绍了MySQL InnoDB索引及其相关高频、高阶面试题。请暂放工作喧嚣享受汗水换来的闲暇惬意阅读。聆听内心感受自由静享丰盈时光。愿这份宁静和这篇博文滋养你前行。本文首发于 浅析二叉树、B树、B树、B*树和MySQL索引底层原理。ReferenceMySQL索引的底层数据结构原理剖析(二叉树、 红黑树、Hash、B-Tree、BTree)数据结构算法之B树(B、B、B*)https://www.tunan.fun/blog/red-black-treehttps://www.runoob.com/data-structures/dsa-advanced-tree.htmlhttps://zhuanlan.zhihu.com/p/617658684