数据库大揭秘：10张图告诉你MySQL为什么选B+树做索引？
上一次吊打各种树这篇文章 堂主柠檬带大家学习一遍数据结构中的各种树，对数据结构还不够熟悉的同学，那篇文章可以作为基础入门，我画了很多图理解起来不困难，建议回头先学习下那篇文章，更容易理解本文要讲的内容。
文章里有提到B+树被广泛应用于MySQL数据库的索引实现，不过并未展开细说，但是呢B+树是一种重要的数据结构，常年出现在各种面试题中，这次就来一起学习下和B+树相关的MySQL索引底层实现的内容。
面试官：简单讲讲MySQL数据库的索引实现，以及为什么这么实现？
这个面试题出现的频率非常之高，从我自己和朋友们参加的大小厂面试都有被问过这个问题，大部分人可能看过一些网上的博客能说出个一二三，如果面试官没有细问还真能混过去，但是对于细节没能真正理解的非常透彻。
所以今天堂主柠檬就来写写这个话题，让你知其然也知其所以然。写作目标是无论你是否学过数据结构，看完都能彻底搞懂这个问题，花5分钟来跟着学一遍看看我有没有做到吧。
首先需要明白，数据库索引是在存储引擎层实现，常见的存储引擎有 2 种。
InnoDB 存储引擎：
innoDB存储引擎支持事务，其设计目标是面向在线事务处理的应用，行锁设计、支持外键，默认度操作不会产生锁，从MySLQ 5.5.7版本开始，InnoDB存储引擎作为默认的存储引擎存在于MySLQ中。
MyISAM 存储引擎：
MyISAM存储引擎不支持事务，表锁设计，支持全文索引，主要面向离线事务处理的数据库应用，在InnoDB引擎成为默认引擎之前，MyISAM存储引擎一直霸占着默认存储引擎的位置，直到他被InnoDB取代，这是个悲伤的故事。
存储引擎不同，索引实现方式也不尽相同，因此，我们先约定本文讲的索引都是InnoDB存储引擎实现的B+树索引。
MySQL架构
索引由存储引擎实现，那存储引擎到底是个什么东西呢？
从我们平常使用的的角度来看，对MySQL的直观感受是命令行的各种指令，或是一个数据库管理工具比如SQLyog的界面点击操作，堂主柠檬在刚接触MySQL时就是用的SQLyon图形界面操作，就是下面这个小海豚。
MySQL可能是世界上最流行的开源数据库引擎，但使用基于文本的工具和配置文件管理起来可能很困难。SQLyog提供了一个完整的图形界面，即使对于初学者来说，使用MySQL的强大功能也很简单，SQLyog直观的图形用户界面使您可以轻松管理MySQL数据库的各个方面。
不管是使用图形界面还是命令行，我们接触到的都只是客户端，MySQL作为一个软件系统的架构，存储引擎在MySQL服务端系统架构的什么位置呢？
总的来说，MySLQ系统架构分为 3 层，直接上图，看下MySQL的架构划分。
- 第一层：连接管理层。MySLQ是典型的CS模型软件，所谓CS就是客户端/服务端的意思，作为一个靠网络连接的服务，必不可少的要有连接管理层，用于管理和维护MySQL服务端和客户端之间的连接、鉴权等等。
- 第二层：这一层是MySQL的核心服务功能层，包括了查询缓存、解析器、优化器等所有跨存储引擎的功能都在这一层实现，屏蔽掉存储引擎间的差别，对上层也就是连接管理层提供统一的接口。
- 第三层：存储引擎层就在这一层实现，负责MySQL中数据的存储和提取，这其中有我们今天的主角InnoDB存储引擎和它实现的B+树索引。
如何指定存储引擎类型
既然要研究innoDB的索引，那我们首先来创建一个使用innoDB存储引擎的表。
MySQL目前支持的存储引擎种类非常丰富，可以在连接MySQL客户端，进入到命令行模式下，输入如下命令查看当前版本MySQL提供的所有存储引擎。
show engines;
可以看到上图中有包含MyISAM 和 InnoDB 这两种常见引擎，关于这些存储引擎的详细介绍，可以参考MySQL的官方文档，我放上链接：
https://dev.mysql.com/doc/refman/8.0/en/storage-engines.html
好了，现在来创建数据表并指定innoDB存储引擎。
举个栗子：创建表一张大佬数据表 BigOld，表中第一个字段是大佬 id 标识，第二个字段是大佬名字 name，并指定数据库使用的存储引擎类型ENGINE=InnoDB ，下面这条建表语句创建并指定了一个使用 InnoDB 存储引擎的数据库表。
CREATE TABLE BigOld (
id INT,
name CHAR (32),
PRIMARY KEY (id)) ENGINE=InnoDB;
当然，如果你一开始创建的表使用的不是InnoDB引擎，那也没关系，还可以再创建表之后修改表的存储引擎，像下面的这样操作。
alert table BigOld engine = InnoDB
索引
好了，经过前面的操作，终于我们有了一个innoDB的数据表，现在我们可以来讲讲innoDB存储引擎的索引，索引的作用当然是为了快速的存取MySQL数据库的数据。
举个栗子，如果把MySQL比作一个大型图书馆，其中的数据比作图书馆里的书。
图书馆 unsplash.com
你去图书馆找书，图书馆那么大我们不可能一头扎进去，一层层、一个个书架去找想要的书，这时候我们会在图书管理系统中通过图书编号（索引）查询到图书所在的楼层，到了指定的楼层在通过书架上的提示找到对应区域，最终在某个书架找到想要的书，这个图书编号就起到索引的作用，帮助我们快速找到图书（数据）。
存储形式
InnoDB存储引擎用B+树实现索引，说到B+树不得不提到他的兄弟B树，这两者的区别比较微妙，但查询磁盘存储数据的性能上却相差很大，要知道为何MySQL InnoDB 选择B+树而不选择B树做索引，我们先来假设分别用这两种数据结构实现索引对比一下。
B树索引
拿来一本数据结构的教材，我们翻开B树的定义。一棵M阶的b树是这么定义的：
定义任意非叶子结点最多只有M个儿子，且M>2；
根结点的儿子数为[2, M]；
除根结点以外的非叶子结点的儿子数为[M/2, M]，向上取整；
非叶子结点的关键字个数=儿子数-1；
所有叶子结点位于同一层；
k个关键字把节点拆成k+1段，分别指向k+1个儿子，同时满足查找树的大小关系。
看完你大概有点懵，不过没关系，我们现是要对比它和B+树在数据库索引上的使用，不是要去手写一个数据库索引，只要抓住它主要的特点便于理解帮助我们理解索引原理即可，这里抓住B树最主要的两个特点：
- 非叶子节点只存放「索引」和指向子节点的「指针」。
- 叶子节点存放「索引」和「数据」，且叶子节点之间没有关联。
便于理解，假如在数据库中使用B树来做索引结构，我试着画出这个B树的索引结构图，如下：
B+树索引
看完了B树索引实现，现在我们来用B+树实现索引看看，一样的随便打开一本数据结构教材找到B+树的定义，一颗M阶的B+树：
有n棵子树的非叶子结点中含有n个关键字（b树是n-1个），这些关键字不保存数据，只用来索引，所有数据都保存在叶子节点（b树是每个关键字都保存数据）。
所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
所有的非叶子结点可以看成是索引部分，结点中仅含其子树中的最大（或最小）关键字。
通常在b+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。
同一个数字会在不同节点中重复出现，根节点的最大元素就是b+树的最大元素。
如果以前没接触过数据结构相关概念，看完估计还是不大明白，没关系，那不是本文的重点，我们不去深究细枝末节。
我来帮你总结下，B+树和B树有很多相同的特点，但也有一些不同让B+树在查询磁盘存储的数据时有更好的性能（为什么？我们稍后讲），最大的不同是下面两个：
- 「数据」只存放叶子节点上面的，非叶子节点存放「索引」和「指针」。
- 叶子节点按大小顺序通过双向链表连接起来，可以像遍历链表一样遍历整棵B+树。
innoDB的选择
innoDB的索引选择用B+树来实现，B树和B+树非常相似，为什么用B+树不用B树做索引呢？这就要从数据库的存储方式说起。
性能瓶颈
innoDB索引以B+树形式组织存储，我们首先要明白B+树的每个节点不是保存在内存而是放在属于外部存储的「磁盘页」中。
为什么呢？因为内存快是快，但是它贵啊！而且很多数据不是热点数据，十天半个月都用不上，完全没必要都放在内存里面，想想看如果淘宝会把那种万亿级别的交易订单数据如果都存在内存中吗，马爸爸虽然有钱也不至于这么奢侈。
重点关注下这里所说的磁盘页，的大小每个系统可能不一样，就堂主所用的这个centos linux系统来说，通过下面的命令查看磁盘页大小为 4096B 也就是 4KB
[lemon/test]$ getconf PAGE_SIZE
4096
这些磁盘数据页如果是B+树的叶子节点，那就保存着关键字和数据（就是我们用 INSERT 语句塞进数据库的那些数据）。
如果是非叶子节点那就保存着关键字和指针（指向子节点的指针），从上图B+树实现的索引示意图也可以看到这两种存储形式的差别。
内存VS外存
当我们在MySQL InnoDB中执行 select 查询语句，这个查找数据的过程是这样的：
- 沿着B+树索引来查找一个给定关键字（或者范围关键字）的所在的数据行。
- 找到数据行所在的磁盘页，把这个磁盘页加载到内存中。
- 在内存中进行查找（比如二分查找），最终得到目标数据行内容。
我们知道磁盘是外部存储设备，那MySQL数据库查找的时候将磁盘中数据读入内存这个过程是非常缓慢的，对于机械硬盘具体来说，从磁盘加载数据需要经过寻道、旋转以及传输的这些过程，时间花费至少是几十毫秒，作为对比，DDR4内存寻址时间仅为6ns左右。
机械硬盘
内存读取速度是磁盘读取速度的100万倍！虽然现在固态硬盘的速度提升了很多，但和内存比起来还是有很大的差距，所以要尽量减少数据库对磁盘数据页的随机IO操作。
由于磁盘读写耗时的原因，在高并发系统中关系型数据库MySQL会成为系统性能瓶颈。
在高并发服务中几十毫秒的的耗时太久了，假设10ms处理一个请求，那1秒处理100个 QPS=100 对比秒杀这一类的场景这个吞吐量完全是不够用的，这也是现在像redis这样的高速缓存数据库会站在前面，为MySQL挡一刀的原因，因为Redis都是内存操作，速度非常快！
Why B+树？
为了更方便的说明B树和B+树两种存储结构的差异，我们来对比下两种树实现的索引上读取数据的过程，i再来回答innoDB 引擎为什么选B+树。
为方便对比，假设我们在B和B+树中我们都要「查询 1 < id < 6 之间」的所有数据行。
B树索引
先来看下如果索引用B树来实现，查找数据的流程图：
在不考虑任何优化的前提下，图中绿色虚线是在B树索引上查找数据的遍历轨迹，来拆解一下：
- 从索引树根节点开始，加载磁盘页 page1 找到第一个节点 key=1 数据行（1，小林）不符合。
- 继续通过指针找到磁盘页面page2，加载磁盘页page2到内存，key=2 符合，读取数据行（2, 石头）
- 重新加载磁盘页 page1 找到第二个节点 key=3符合，读取数据行（3，轩辕）。
- 继续通过指针加载磁盘页 page4 到内存，key=4 符合，读取数据行（4，小北）。
- 重新加载磁盘页 page1 找到第三个节点 key=5 符合，读取数据行（5，why神）。
数一数上面的5个步骤有几个「加载磁盘页」字眼，5个，还记得上面我们说的：**加载磁盘数据非常费时！**这种随机大量的磁盘IO造成了B树索引的的性能瓶颈，使其与innoDB索引无缘。
B+树索引
再来看下现在innoDB的用B+树的实现方案吧，同样的查询条件，还是画出数据查找的遍历轨迹：
在不考虑任何优化的前提下，图中绿色虚线是在innoDB B+树索引上查找数据的遍历轨迹，同样来拆解一下：
- 从索引树根节点开始，加载磁盘页 page1 找到第一个节点 key=1不符合，继续往下搜索。
- 通过指针找到磁盘页page2, 加载磁盘页page2 到内存，其中存放了key=1、2的数据行，读取符合条件数据行。
- 由于叶子节点间组成双向链表，直接顺着page2 加载磁盘页page3 、 加载磁盘页page4，读取其中符合条件的数据行。
这其中涉及了4次加载磁盘页的操作，看起来只是比上面的B树少了一次，但这是在我的简单例子，为了便于理解数据量比较少。
实际应用中B+确实能够减少大量的磁盘IO，从而大大提高查询性能，而且由于B+树根节点的数据已经是排序好的双向链表，我们可以像链表一样遍历所有数据，非常适合范围查找和排序操作！
再谈B树
B树索引并非一无是处。虽然我们前面详细对比了在innoDB中使用B+树索引的优势，但不要以为B树就一无是处了，一种数据结构被设计出来肯定是有使用场景的需求，不然谁也不会闲着没事折腾出一个东西，你说对吧。
事实上B树也被用于实现数据库索引，只不过不是在MySQL上。在MongoDB的索引设计上就使用了B树做索引，什么是MongoDB呢？我不做过多介绍，感兴趣的可以下来了解一下，下面这段话来自MongoDB 英文Wiki
MongoDB is a cross-platform document-oriented database program. Classified as a NoSQL database program, MongoDB uses JSON-like documents with optional schemas. MongoDB is developed by MongoDB Inc. and licensed under the Server Side Public License (SSPL).
只需要知道它和MySQl不同，MongoDB是一种文档型的非关系型数据库，被划分为NoSql数据库，使用类似JSON的语法存储文档，熟悉Redis的同学应该很容易理解NoSQL的含义。
因为关系型数据库比如 MySQL 经常需要执行遍历和范围查找的操作，B+树的特点正是迎合了这样的需求。但是在MongoDB这样的NoSLQ数据库中，在数据表的设计层面就决定了不会有太多的遍历和范围查找，基本就是一个键对应一个值的单一查询。
在MongoDB上的查找如果用B+树来实现索引的话，由于非叶子节点不存放数据，每次查询必须搜索到B+树的叶子节点才能获取到数据，时间复杂度是固定的树的高度 log n；
而如果用B树实现索引，由于每个节点都可以存放数据，幸运的话有可能不必找到叶子节点就能取得数据，复杂度更低，再来看下B树实现的索引，如果换作是 MongoDB 你仔细品。
虽然没有MySQL的使用普及程度那么高，用B树实现索引的MongoDB很多大公司也都有使用。
使用客户
脱离业务场景谈具体实现都是耍流氓。正是由于关系型数据库和非关系型数据库应用场景的不同，工程实现上最终会在损失和收益中找到平衡点，使得B树和B+树在不同数据库上有各自的用武之地。
所以下次面试和面试官夸MySQL B+树索引好处的时候，注意别把 B 树喷的太惨，以防面试官来个回马枪，让你说说为啥MongoDB还要用B树来实现索引？这时候虽然你心里笑开了花，还是要假装再思考下，愣着干嘛，接着继续吹B树啊。
感谢各位的阅读，文章的目的是分享对知识的理解，技术类文章我都会反复求证以求最大程度保证准确性，若文中出现明显纰漏也欢迎指出，我们一起在探讨中学习。
Hi，我是堂主柠檬，一线互联网大厂后端程序员一枚，个人技术gzh主要分享后端开发相关的技术学习，每篇文章都是我精心创作，如果文章对你有帮助，这次一定不要白piao，点赞 或 分享 给需要的朋友，这对柠檬很重要，在此先谢过各位大佬了！我是柠檬，我们下期再见。
可以微信搜索公众号「 后端技术学堂 」回复「1024」获取50本计算机电子书，回复「进群」拉你进百人读者技术百人群，文章每周持续更新，我们下期见！
