MySQL 为什么采用 B+树作为索引？不只告诉你答案还告诉你答案背后的脉络，五年经验程序员整理回答

坐对真成被花恼，出门一笑大江横 前言 为什么 MySQL 采用B+树作为索引？ 如果纯粹的猜测MySQL数据库索引为什么使用B+树？那么围绕这个问题的回答通常一定是围绕B+树本身是什么，有什么优势这两点去解释这个问题。 （这不是我开始这么去想的，看了很多文章都是从这一维度问答，这些回答让我失望啊。直到那天问了坐在我旁边那个整天摸鱼的5年程序员；他慵懒的回答：你想为什么是使用的是树结构呢？ 咦，听到这回答，一下打开了我的思绪，有点意思！） 先抛开B+树是什么，有什么优势，这些先入为主的答案。 （我并不想要这个往我脑袋硬塞的硬邦邦的答案。） 我想要的是为什么？ 为什么MySQL的索引有那么多的数据结构可选，偏偏选树结构？为什么那么多的树结构？为什么又偏偏采用 B+ 树作为索引? 这才是我要想明白的！我想要的是不只是答案还要答案背后的脉络！ 我想要的不仅是要知其然，更想要知其所以然。 那么多数据结构，为什么选树结构？ 众多的数据结构在逻辑层面可分为：线性结构 和 非线性结构。 线性结构有：数组、链表，基于它们衍生出的有哈希表（哈希表也称散列表）、栈、队列等。 非线性结构有：树、图。 还有其他数据结构如：跳表、位图 也都由基础数据结构演化而来，不同的数据结构存在即都是为了解决某些场景问题。 如果要知道索引适合什么数据结构，那我们得先来回答索引需要来解决什么样的问题（痛点）？和发挥着什么样的作用？其次再才是选择什么样的数据结构；后者只是果，前者才是因。 我们都知道MySQL存储的数据是在磁盘里，因为即使设备断电，放在磁盘的数据是不会有影响的，保障了数据不丢失，这意味着MySQL在磁盘上的数据是持久化的。 但数据存储在磁盘得到保障的同时也是有代价的，这代价就是磁盘的处理速度是毫秒级别的，相比内存纳秒级别的速度，简直是小巫见大巫。 你可能对时间单位没什么概念，可以看 1毫秒能慢上纳秒几万倍。

​

编辑

添加图片注释，不超过 140 字（可选）

索引虽然存储在磁盘上，但使用索引查找数据时，可以从磁盘先读取索引放到内存中，再通过索引从磁盘找到数据；再然后将磁盘读取到的数据也放到内存里。 索引就让磁盘和内存强强联手，趁机搭上了内存的车，感受了一把纳秒级别速度的推背感。

​

编辑

添加图片注释，不超过 140 字（可选）

但是不管查询的过程中怎么优化，只要根还在磁盘，就避免不了会发生多次磁盘 I/O ，而磁盘 I/O 次数越多，消耗的时间也越多。 （聪明的同学这会可以看出这其实就是个需要考虑解决的痛点了）

• 要尽少在磁盘做 I/O 操作。

但还有那么多的数据结构可选呢。 其实索引的需要发挥的目的已经决定了有哪些数据结构可选，那么就可以缩小选择其他数据结构的范围。 从为什么要建索引本身的首要目的出发。

• 要能尽快的按照区间高效地范围查找。

当然索引首要目的能支持高效范围查询，还要有插入更新等操作的动态数据结构。 所以有满足以这两条主要条件的除了树结构你还会想到其他什么数据结构？ 哈希表、跳表 哈希表 先看哈希表，哈希表对于我们来说太熟悉不过，哈希表的物理存储是一个数组，而数组在内存中是连续地址的空间。数据以Key、Value的方式存储。哈希表拥有精确的查询，所以时间复杂度是 O(1)。 而哈希表之所以能这么快是通过Key计算数组下标来快速找到Value。最简单的计算的方式是 余数法，通过先计算key的 HashCode，再通过哈希表的数组长度对 HashCode 求余，求余得出的余数就是数组下标，最后由下标访问到哈希表中存的Key、Value。

​

编辑切换为居中

添加图片注释，不超过 140 字（可选）

但是 Key 计算出的下标