实现MySQL的索引

MySQL中索引分三类：B+树索引、Hash索引、全文索引。InnoDB存储引擎中用的是B+树索引。要介绍B+树索引，不得不提二叉查找树、平衡二叉树和B树这三种数据结构。B+树是从它们三个演化来的。

二叉查找树：

图中为user表建立了一个二叉查找树的索引。节点中存储了键（key）和数据（data）。数据对应user表中的行数据。

如果查找id=12的用户信息，流程如下：
1）将根节点作为当前节点，12大于10，将10的右子节点（13节点）作为当前节点。
2）12与13比较，将13的左子节点（12节点）作为当前节点。
3）12与12比较，满足条件，从当前节点去除data，即id=12，name=xm。
利用二叉查找树，3次可找到匹配数据。如果在表中一条一条查找，需要6次。

平衡二叉树：

如果上面的二叉树这样构造：

变成了一个链表，查询id=17的用户信息，需要查7次，相当于全表扫描。导致这个现象是因为二叉查找树不平衡了。为了解决这个问题，需要用平衡二叉树。
平衡二叉树又称 AVL 树，在满足二叉查找树特性的基础上，要求每个节点的左右子树的高度差不能超过 1。

B树：
因为内存的易失性，一般会将数据和索引存储到磁盘中。和内存比，从磁盘读数据会慢很多，所以应当减少读取次数。此外，从磁盘读数据按照磁盘块来读取，而非一条一条的读。
如果我们能把尽可能多的数据放进磁盘块中，那一次磁盘读取操作就会读取更多数据，那我们查找数据的时间也会大幅度降低。如果我们用树这种数据结构作为索引的数据结构，那我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块。我们都知道平衡二叉树可是每个节点只存储一个键值和数据的。那说明什么？说明每个磁盘块仅仅存储一个键值和数据！那如果我们要存储海量的数据呢？
可以想象到二叉树的节点将会非常多，高度也会极其高，我们查找数据时也会进行很多次磁盘 IO，我们查找数据的效率将会极低！
为了解决平衡二叉树的这个弊端，我们应该寻找一种单个节点可以存储多个键值和数据的平衡树。也就是我们接下来要说的 B 树。

图中的每个节点称为页（就是磁盘块），在MySQL中数据读取的基本单位都是页。每个节点存储了更多的键值和数据。子节点的个数一般称为阶，上述图中B树为3阶B树。
查找id=28的用户信息，

流程如下：

• 1）先找到根节点也就是页 1，判断 28 在键值 17 和 35 之间，那么我们根据页 1 中的指针 p2 找到页 3。
• 2）将 28 和页 3 中的键值相比较，28 在 26 和 30 之间，我们根据页 3 中的指针 p2 找到页 8。
• 3）将 28 和页 8 中的键值相比较，发现有匹配的键值 28，键值 28 对应的用户信息为（28，bv）。

B+树：

B+树是对B树的进化，其不同：

• 1）B+树非叶子节点不存储数据，仅存储键值，B树则存储键值和数据（为什么这么做？数据库中页的大小是固定的，InnoDB中默认是16KB，如果不存数据，就可以存更多的键值，树的阶数会更大，树就会更矮胖，查找数据进行磁盘IO的次数就会减少，查询效率快）。一般根节点是常驻内存的。
• 2）B+树索引的所有数据存储在叶子节点，而且数据是按照顺序排列的（使得范围查找、排序查找、分组查找及去重查找很简单，而B树因为数据分散在各个节点，实现这一点很不容易），B+树的叶子节点中的数据通过单向链表连接，各个页之间通过双向链表连接。

过上图可以看到，在 InnoDB 中，我们通过数据页之间通过双向链表连接以及叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。

在 MySQL 中，B+ 树索引按照存储方式的不同分为聚集索引和非聚集索引。

利用聚集索引查找数据：

现在假设我们要查找 id>=18 并且 id<40 的用户数据。

对应的 sql 语句为：

select * from user where id>=18 and id<40;

其中id为主键，具体的查找过程如下：

• 1）一般根节点常驻内存的，页1已经在内存中了，不用读磁盘，直接内存读取。
• 在内存中页1查找id>=18 and id<40或者范围值，先找到id=18的键值。从页1找到指针p2，定位到页3。
• 2）从磁盘中读取页3，然后将页3放入内存中，然后进行查找，可以找到键值18，然后拿到页3中的指针p1，定位到页8。
• 3）将页8读取到内存中，根据二分查找法定位到键值18, 因为是范围查找，而且此时所有的数据又都存在叶子节点，并且是有序排列的，那么我们就可以对页 8 中的键值依次进行遍历查找并匹配满足条件的数据。
• 我们可以一直找到键值为 22 的数据，然后页 8 中就没有数据了，此时我们需要拿着页 8 中的 p 指针去读取页 9 中的数据。
• 4）因为页 9 不在内存中，就又会加载页 9 到内存中，并通过和页 8 中一样的方式进行数据的查找，直到将页 12 加载到内存中，发现 41 大于 40，此时不满足条件。那么查找到此终止。

具体流程图：

利用非聚集索引查找数据：

查找幸运数字为33的用户信息，需要回表。