数据库大揭秘：10张图告诉你MySQL为什么选B+树做索引？( 二 ) _MySQL

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+树的每个节点不是保存在内存而是放在属于外部存储的「磁盘页」中。
为什么呢？因为内存快是快，但是它贵啊！而且很多数据不是热点数据，十天半个月都用不上，完全没必要都放在内存里面，想想看如果淘宝会把那种万亿级别的交易订单数据如果都存在内存中吗，马爸爸虽然有钱也不至于这么奢侈。