MySQL索引底层实现原理

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。
问题1：可以用作索引的数据结构有很多（二叉树，红黑树，B树），为什么使用B+Tree这种数据结构作为mysql的索引？

二叉排序树

二叉树顾名思义首先是一个树结构，其次“二叉”代表这个树可以分为两边，递归下来就是二叉树，这棵树上的节点都是已经排序了的。具体的排序规则：（大的在右边，小的在左边）

• 若左子树不空，则左子树上所有节点的值均小于它的根节点的值
• 若右子树不空，则右字数上所有节点的值均大于它的根节点的值

• 它的左、右子树也分别为二叉排序数（递归定义）

  
  
  二叉树

此树用于查找是比较方便的，每经过一个节点，最多可以减少一半的可能，但是极端情况下所有的节点都在同一侧，直观上看就是直线，所以查询效率相对就低了，此时需要对二叉树左右子树的高度进行平衡处理，于是就有了平衡二叉树。

平衡二叉树的各个分支的高度是均匀的，它的左子树和右子树的高度之差绝对值小于1，这样就不会出现一条支路特别长的情况。于是，在这样的平衡树中进行查找时，总共比较节点的次数不超过树的高度，这就确保了查询的效率（时间复杂度为O(logn)）。但是存在问题就是数据过大的时候树的高度会很高，这样导致查询的效率也会相对的低。

B树

B树事实上是一种平衡的多叉查找树，也就是说最多可以开m个叉（m>=2），我们称之为m阶b树。

上图是一个2阶B树和5阶B树，m阶B树满足以下条件：

• 每个节点至多可以拥有m棵子树。
• 根节点，只有至少有2个节点（要么极端情况，就是一棵树就一个根节点，单细胞生物，即是根，也是叶，也是树)。
• 非根非叶的节点至少有的Ceil(m/2)个子树(Ceil表示向上取整，图中5阶B树，每个节点至少有3个子树，也就是至少有3个叉)。
• 非叶节点中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中n表示该节点中保存的关键字个数，K为关键字且Ki<Ki+1，A为指向子树根节点的指针。
• 从根到叶子的每一条路径都有相同的长度，也就是说，叶子节在相同的层，并且这些节点不带信息，实际上这些节点就表示找不到指定的值，也就是指向这些节点的指针为空。

B树的查找和二叉树类似，从根节点一次比较每个节点，因为每个节点中的关键字和左右子树都是有序的，所以只需要比较节点的关键字即可，沿着指针很快就可以查到指定的数据，如果查找失败，则会返回叶子节点，即空指针。

例如查询图中字母表中的K：

1. 从根节点P开始，K的位置在P之前，进入左侧指针。
2. 左子树中，依次比较C、F、J、M，发现K在J和M之间。
3. 沿着J和M之间的指针，继续访问子树，并依次进行比较，发现第一个关键字K即为指定查找的值。

B树的特点：

1. 关键字集合分布在整棵树中。
2. 任何一个关键字出现且只出现在一个节点中。
3. 搜索有可能在非叶子节点结束。
4. 搜索效率等价于在数据集合中进行一次二分查找。
5. B树在插入删除数据的时候会破坏B树的性质，在更新操作时，需要对树进行分裂，合并，转移的操作来保持B树的性质。

B+Tree

是B树的加强版，两者的差异在于：

• 有n棵子树的节点含有n个关键字
• 所有的关键字全部存储在叶子节点上，且叶子节点是根据关键字自小而大顺序连接的。
• 非叶子节点可以看成是索引部分，节点中仅含有其子树（根节点）中的最大（或最小）关键字。

B+tree的查找和B树类似，只不过在查找的时候，如果非叶子节点上的关键字等于给定值，并不终止，而是继续沿着指针指到叶子结点的位置，因此B+tree不管查找成功还是失败，每次查找都是走了一条从根到叶子节点的路径。

特性：

• 所有的关键字都存储在叶子节点上，且链表中的关键字是有序的
• 不可能非叶子节点命中返回。
• 非叶子节点相当于叶子节点的索引，叶子节点相当于是存储关键字的数据层。
• 更适合文件索引系统。

带有顺序访问指针的B+Tree

一般在数据库系统或文件系统中使用的B+tree结构都进行了优化，增加了顺序访问的指针。

如图所示，在B+tree的每个叶子节点添加了指向相邻叶子结点的指针，这样可以增大区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

二叉树和红黑树的比较

红黑树是平衡二叉树的一种，存在和平衡二叉树相同的问题，那就是数据量大的时候，树的深度很深，也就是深度不饿控制，每次查找数据，都需要比较每一层的节点，这样一来当数据量大的时候查找数据还是很耗时的。

B树

从图上看B树的查询效率提高，存储容量也没影响。那我们为什么不把数据全部都存在一个节点，这样深度不就是1了吗?

当然不行了！java拿取数据一般是这样的：java程序-->CPU--->内存---->硬盘，而内存与硬盘的交互是有大小限制的，是一页数据4k左右，所以不能把所有数据都放在一个节点来获取，一般来说节点会尽量预存4K容量。

看到这里，我们知道（4K=节点；节点=小节点*小节点的容量）一个节点是4K，而节点内有几个小节点，那么也就是说，只要我们每个的小节点的data容量越小，那么可以存的节点也就可以更多。

B+tree

B+Tree通过把data不放在非叶子节点来增加度（小节点），一般会一百个以上使得深度是3~5，从而减少查询次数。并且，叶子节点之间会有指针，数据又是递增的，这使得我们范围查找可以通过指针连接查找，而不再从上面节点往下一个个找.

结论：B+Tree 既减少查询次数又提供了很好的范围查询。

Mysql为什么使用B+树

红黑树等数据结构也可以用来实现索引，但是文件系统以及数据库系统普遍采用B树或者B+树。一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储在磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

B-/+Tree索引的性能分析

根据B-Tree的定义，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次IO就可以完全载入。为达到这个目的，在实现B-Tree还需要使用一些技巧：

每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上页存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需要一次IO。

B-Tree中一次检索最多需要h-1次IO（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。

综上所说B-tree作为索引结构效率是非常高的。

而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。

上文还说过B+Tree更适合作为索引，原因和内节点出度d有关。d越大索引性能越好，而出度上限却决于key和data的大小。

𝑑𝑚𝑎𝑥=𝑓𝑙𝑜𝑜𝑟(𝑝𝑎𝑔𝑒𝑠𝑖𝑧𝑒/(𝑘𝑒𝑦𝑠𝑖𝑧𝑒+𝑑𝑎𝑡𝑎𝑠𝑖𝑧𝑒+𝑝𝑜𝑖𝑛𝑡𝑠𝑖𝑧𝑒))
floor表示向下取整。由于B+Tree内节点去掉了data域，因此可以拥有更大的出度，拥有更好的性能。

在Mysql中，索引属于存储引擎级别的概念，不同的存储引擎对索引的实现方式是不同的，在Mysql中主要的存储引擎为MyISAM和innoDB。

MyISAM 非聚簇索引

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：

这里设表一共有三列，假设我们以Col1为主键，则上图是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：

同样也是一棵B+树，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。

第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

主索引 (Primary Key)

问题2：为什么mysql官方建议使用自增主键作为主索引？

上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。

辅助索引(Secondary Key)

问题3：什么是回表？

第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，上图为定义在Col3上的一个辅助索引：

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一棵B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整(页分裂，页合并，转移是特别消耗性能的)，十分低效，而使用自增字段作为主键则是一个很好的选择。
这里放两张图理解：

插入非连续的数据：

两者的区别：

• 非聚集索引与聚集索引的区别在于非聚集索引的叶子节点不存储表中的数据，而是存储该列对应的主键（行号）。

• 对于InnoDB来说，想要查找数据我们还需要根据主键再去聚集索引中进行查找，这个再根据聚集索引查找数据的过程，我们称为回表。第一次索引一般是顺序IO，回表的操作属于随机IO。需要回表的次数越多，即随机IO次数越多，我们就越倾向于使用全表扫描 。

• 通常情况下， 主键索引（聚簇索引）查询只会查一次，而非主键索引（非聚簇索引）需要回表查询多次。当然，如果是覆盖索引的话，查一次即可。

• 注意：MyISAM无论主键索引还是二级索引都是非聚簇索引，而InnoDB的主键索引是聚簇索引，二级索引是非聚簇索引。我们自己建的索引基本都是非聚簇索引。

非聚簇索引一定会回表查询吗？

不一定，这涉及到查询语句所要求的字段是否全部命中了索引，如果全部命中了索引，那么就不必再进行回表查询。一个索引包含（覆盖）所有需要查询字段的值，被称之为"覆盖索引"。

举个简单的例子，假设我们在学生表的成绩上建立了索引，那么当进行select score from student where score > 90的查询时，在索引的叶子节点上，已经包含了score 信息，不会再次进行回表查询。

如何减少回表次数？

MySQL 5.6引入了索引下推优化。默认开启，使用SET optimizer_switch = ‘index_condition_pushdown=off’;可以将其关闭。

有了索引下推优化，可以在减少回表次数，在InnoDB中只针对二级索引有效

官方文档中给的例子和解释如下：

在 people_table中有一个二级索引(zipcode，lastname，firstname)，查询是SELECT * FROM people WHERE zipcode=’95054′ AND lastname LIKE ‘%etrunia%’ AND address LIKE ‘%Main Street%’;

如果没有使用索引下推技术，则MySQL会通过zipcode=’95054’从存储引擎中查询对应的数据，返回到MySQL服务端，然后MySQL服务端基于lastname LIKE ‘%etrunia%’ and address LIKE ‘%Main Street%’来判断数据是否符合条件。

如果使用了索引下推技术，则MYSQL首先会返回符合zipcode=’95054’的索引，然后根据lastname LIKE ‘%etrunia%’ and address LIKE ‘%Main Street%’来判断索引是否符合条件。如果符合条件，则根据该索引来定位对应的数据，如果不符合，则直接reject掉。

索引的优缺点

优点：

• 可以大大的加快数据的检索速度，这是建索引的主要原因，通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

缺点：

• 时间方面：创建索引和维护索引要耗费时间，具体地，当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，会降低增/改/删的执行效率；
• 空间方面：索引需要占物理空间。

Mysql索引的类型

1、从存储结构上来划分：BTree索引（B-Tree或B+Tree索引），Hash索引，full-index全文索引，R-Tree索引。这里所描述的是索引存储时保存的形式，

2、从应用层次来分：普通索引，唯一索引，复合索引。

• 普通索引：即一个索引只包含单个列，一个表可以有多个单列索引
• 唯一索引：索引列的值必须唯一，但允许有空值
• 复合索引：多列值组成一个索引，专门用于组合搜索，其效率大于索引合并
• 聚簇索引(聚集索引)：并不是一种单独的索引类型，而是一种数据存储方式。具体细节取决于不同的实现，InnoDB的聚簇索引其实就是在同一个结构中保存了B-Tree索引(技术上来说是B+Tree)和数据行。
• 非聚簇索引： 不是聚簇索引，就是非聚簇索引

3、根据中数据的物理顺序与键值的逻辑（索引）顺序关系： 聚集索引，非聚集索引。