我们都知道MySQL的索引主要以B+树为主，但是要问到为什么用B+树呢？本文就来从头到尾介绍下数据库的索引。
索引是一种数据结构，用于帮助我们在大量数据中快速定位到我们想要查找的数据。
索引在mysql数据库中分三类：
B+树索引、Hash索引、全文索引。
今天介绍的是innodb存储引擎中的的B+树索引。
要介绍B+树索引，就不得不提
二叉查找树，平衡二叉树和B树
这三种数据结构。B+树就是从他们仨演化来的。
二叉查找树
从图中可以看到，我们为user表（用户信息表）建立了一个二叉查找树的索引。图中的圆为二叉查找树的节点，节点中存储了键(key)和数据(data)。
# 我们通常使用以下语句来创建索引
CREATE INDEX index_name ON table_name (column_name)
二叉查找树的特点
就是：
任何节点的左子节点的键值都小于当前节点的键值，
右子节点的键值都大于当前节点的键值。
顶端的节点我们称为根节点，
没有子节点的节点我们称之为叶节点。
如果我们需要查找id=12的用户信息，利用我们创建的
二叉查找树索引，查找流程如下
：
- 将根节点作为当前节点，把12与当前节点的键值10比较，12大于10，接下来我们把当前节点>的右子节点作为当前节点。
- 继续把12和当前节点的键值13比较，发现12小于13，把当前节点的左子节点作为当前节点。
-
把12和当前节点的键值12对比，12等于12，满足条件，我们从当前节点中取出data，即id=12,name=xm。
利用二叉查找树我们只需要3次即可找到匹配的数据。如果在表中一条条的查找的话，我们需要6次才能找到。
如果上面的二叉树是这样的构造：
二叉查找树变成了一个链表。
如果我们需要查找id=17的用户信息，我们需要查找7次，也就相当于全表扫描了。
导致这个现象的原因其实是
二叉查找树变得不平衡了，也就是高度太高了，从而导致查找效率的不稳定。
为了解决这个问题，我们需要保证二叉查找树一直保持平衡，就需要用到
平衡二叉树
了。
平衡二叉树
平衡二叉树又称AVL树，在满足二叉查找树特性的基础上，要求
每个节点的左右子树的高度差不能超过1
。
下面是平衡二叉树和非平衡二叉树的对比：
平衡二叉树相比于二叉查找树来说，查找效率更稳定，总体的查找速度也更快。
我们都知道
平衡二叉树可是每个节点只存储一个键值和数据的
。每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块。如果我们要存储海量的数据呢？可以想象到二叉树的
节点将会非常多，高度也会及其高
，我们查找数据时也会进行
很多次磁盘IO，我们查找数据的效率将会极低
！这时候，就需要用到B树了。
B树
即为平衡树的意思，下图即是一颗B树。
B树相对于平衡二叉树，
每个节点存储了更多的键值(key)和数据(data)
，并且
每个节点拥有更多的子节点
，子节点的个数一般称为阶，上述图中的B树为3阶B树，高度也会很低。
假如我们要查找id=28的用户信息，那么我们在上图
B树中查找的流程如下
：
- 先找到根节点也就是页1，判断28在键值17和35之间，我们那么我们根据页1中的指针p2找到页3。
- 将28和页3中的键值相比较，28在26和30之间，我们根据页3中的指针p2找到页8。
- 将28和页8中的键值相比较，发现有匹配的键值28，键值28对应的用户信息为(28,bv)。
B树节点中
不仅存储键值，也会存储数据
。之所以这么做是因为在数据库中页的大小是固定的，
innodb中页的默认大小是16KB
。
如果不存储数据
，那么就会
存储更多的键值
，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，
如此一来我们查找数据进行磁盘的IO次数就会再次减少，数据查询的效率也会更快
。
B+树
B+树是对B树的进一步优化。
B+树索引的
所有数据均存储在叶子节点
，而且数据是按照
顺序排列
的。那么B+树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。而B树因为数据分散在各个节点，要实现这一点是很不容易的。
以innodb作为存储引擎的表，
表中的数据都会有一个主键
，即使你不创建主键，系统也会帮你创建一个隐式的主键。这是因为innodb是把数据存放在B+树中的，而B+树就是以主键为键值构建的索引。
有心的读者可能还发现上图B+树中各个页之间是通过双向链表连接的，叶子节点中的数据是通过单向链表连接的。
我们一定要记住这句话：
数据即索引，索引即数据
。