一、前言
最近有很多读者要我出一些面试题的文章，个别我会给他一个老周整顿的电子书，但有些读者反馈回来的面试题我感觉还是蛮经典的，而老周又在写系列的文章，本着对读者负责的态度，我会交叉写几篇我认为比拟经典的面试题，让大家对这种经典问题不再是背八股文，而是深刻底层原理以及数据结构。后续再碰到这类问题，不论哪个公司问的，你都会得心应手、慌慌张张的答复。
明天这一篇腾讯的一道面试题：说一说 MySQL 中索引的底层原理，先不论哪个公司，如果老周是面试官，MySQL 这块我很可能也会用这道来考查，因为这能够考查出你对 MySQL 实质是否了解，而且当初很多人动不动就索引优化，索引底层是个啥我置信还有蛮多人不是特地理解。
没关系，跟着老周走，这一篇咱们彻底拿下 MySQL 的索引。
二、索引是什么？
索引是对数据库表中一列或多列的值进行排序的一种构造，应用索引可进步数据库中特定数据的查问速度。
索引的目标在于进步查问效率，就像书的目录一样。一本 1000 页的书，如果你想疾速找到其中的某一个知识点，在不借助目录的状况下，这个事件是不是很难实现？同样，对于数据库的表而言，索引其实就是它的“目录”。
三、索引的分类
常见的索引类型有：主键索引、惟一索引、一般索引、全文索引、组合索引
3.1 主键索引
即主索引，依据主键 pk_clolum（length）建设索引，不容许反复，不容许空值。
ALTER TABLE 'table_name' ADD PRIMARY KEY pk_index('col')；3.2 惟一索引
用来建设索引的列的值必须是惟一的，容许空值。
ALTER TABLE 'table_name' ADD UNIQUE index_name('col')；3.3 一般索引
MySQL 中的根本索引类型，容许在定义索引的列中插入反复值和空值。
ALTER TABLE 'table_name' ADD INDEX index_name('col')；3.4 全文索引
全文索引类型为 FULLTEXT，用大文本对象的列构建的索引，在定义索引的列上反对值的全文查找，容许在这些索引的列中插入反复值和空值。全文索引能够在 CHAR、VARCHAR 或 TEXT 类型的列上创立。MySQL 中只有 MyISAM 存储引擎反对全文索引。
ALTER TABLE 'table_name' ADD FULLTEXT INDEX ft_index('col')；3.5 组合索引
在表的多个字段组合上创立的索引，只有在查问条件中应用了这些字段的右边字段时，索引才会被应用。应用组合索引时遵循最左前缀准则，并且组合索引这多个列中的值不容许有空值。
ALTER TABLE 'table_name' ADD INDEX index_name('col1','col2','col3')；留神了，遵循最左前缀准则很重要！！！把最罕用作为检索或排序的列放在最左，顺次递加，组合索引相当于建设了 col1、col1col2、col1col2col3 三个索引，而 col2 或者 col3 是不能应用索引的。
四、索引的常见模型
索引的呈现是为了进步查问效率，然而实现索引的形式却有很多种，所以这里也就引入了索引模型的概念。能够用于进步读写效率的数据结构很多，这里我先给你介绍几种常见的数据结构，它们别离是哈希表、有序数组和搜寻树。搜寻树又能够分为二叉搜寻树、均衡二叉树、B 树、B+ 树。
MySQL 中实现索引的形式次要有两种：BTREE 和 HASH，具体和表的存储引擎无关；MyISAM 和 InnoDB 存储引擎只反对 BTREE 索引，而 MEMROY/HEAP 存储引擎能够反对 HASH 和 BTREE 索引。
这里老周说的索引模型不仅仅针对 MySQL 的哈，常见的几种都会说一下，让大家对实现索引的形式有个更加全局的理解。
4.1 哈希表
哈希表是一种以键 - 值（key-value）存储数据的构造，咱们只有输出待查找的值即 key，就能够找到其对应的值即 value。哈希的思路很简略，把值放在数组里，用一个哈希函数把 key 换算成一个确定的地位，而后把 value 放在数组的这个地位。
多个 key 值通过哈希函数的换算，会呈现同一个值的状况。解决这种状况的一种办法是，拉出一个链表。有没有发现，其实 HashMap 就是这样的数据结构。
假如，你当初保护着一个用户 id 和姓名的表，须要依据用户 id 查找对应的名字，这时对应的哈希索引的示意图如下所示：
从上图不难发现，user_id2 和 user_id3 通过哈希函数计算出来的值都是 4，这就是哈希抵触，但没有关系，前面会拉出一个链表进去。当你要查问 user_id2 姓名的时候，先通过哈希函数失去 4，再按程序遍历，找到 name2。
这里要提一下这个点，user_idn 的值并不是递增的，这样有个益处，新增用户的时候会很快，只须要往后追加；但也有毛病，因为不是有序的，所以哈希索引做区间查问的速度是很慢的。
所以，哈希表这种构造实用于只有等值查问的场景，比方 Memcached 及其他一些 NoSQL 引擎。
4.2 有序数组
下面的哈希表不适宜范畴查问，而有序数组在等值查问和范畴查问场景中的性能就都十分优良。
咱们来别离看看有序数组针对等值查问与范畴查问的工夫复杂度，等值查问比方你要查 user_id2 对应的名字，用二分法就能够疾速失去，这个工夫复杂度是 O(log(N))。范畴查问比方你要查问 [user_id2, user_id5] 之间的用户，同样利用二分查找先找到 user_id2（如果不存在 user_id2，就找到大于 user_id2 的第一个用户），而后向右遍历，直到查到第一个大于 user_id5，退出循环。
查问场景的确很优良，但有序数组也有毛病，更新数据的时候那就有点麻烦了，比方你往两头插入一条用户，该用户前面所有的记录都要往后挪动，老本太高了。
所以，有序数组索引只实用于动态存储引擎，比方你要保留的是历史某一年某个城市的所有人口信息，这类不会再批改的历史数据。
4.3 二叉树
二叉树是一棵树，其中每个节点都不能有多余两个的儿子。二叉树也是最经典的树结构，上面讲的各种树都是基于二叉树改良而来的。
咱们先来看下二叉树的特点：
- 二叉树的均匀工夫复杂度为 O(log(N))
- 每个节点最多只能有两个子节点
个别二叉树：
最坏情景的二叉树，呈现链化的状况：
实现：
因为一个二叉树节点最多有两个子节点，所以咱们能够保留间接链接到它们的链。树节点的申明在结构上相似于双链表的申明，在申明中，节点就是由 element（元素）的信息加上两个到其它节点的援用（left 和 right）组成的构造。如下：
public class BinaryNode {
Object element; // The data in the mode
BinaryNode left; // Left child
BinaryNode right; // Right child
}网上有很多说常见的索引应用的数据结构是二叉树，其实不够谨严，二叉树在索引的利用次要是二叉搜寻树以及后续演进的均衡二叉树、B 树、B+ 树等。二叉树其实有许多与搜寻无关的重要利用，比方在编译器的设计等畛域。
4.4 二叉查找树
查找树 ADT（Abstract Data Type）也就是二叉查找树，它是索引应用的数据结构中的一个利用。
咱们先来看下二叉查找树的特点：
- 二叉查找树的均匀工夫复杂度为 O(log(N))
- 每个节点最多只能有两个子节点
- 左子节点的值小于本节点的值，右子节点的值大于本节点的值。
咱们来看下如下构造：
依据二叉查找树的特点，咱们很快就能晓得，最右边的图是二叉查找树；两头的树则不是，因为在为 6 的根节点右边呈现了一个为 7 的节点，不满足二叉树第三点的个性；左边的树则是链化的二叉查找树。
实现：
二叉查找树要求所有的项都可能排序，咱们以 Java 语言为例，能够实现 Comparable 接口来实现这个排序的性质，树中的两项总能够应用 compareTo 办法进行比拟。构造如下：
public class BinarySearchTree<T extends Comparable<? super T>> {
private static class BinaryNode<T> {
T element; // The data in the mode
BinaryNode<T> left; // Left child
BinaryNode<T> right; // Right child
BinaryNode(T t) {this(t, null, null);
}
BinaryNode(T t, BinaryNode<T> lt, BinaryNode<T> rt) {
this.element = t;
this.left = lt;
this.right = rt;
}
}
// ...
}4.5 均衡二叉查找树
均衡二叉查找树也称 AVL 树（Adelson-Velsky-Landis Tree），均衡二叉查找树的呈现就是为了解决下面的二叉查找树可能呈现链化的场景。
咱们先来看下均衡二叉查找树的特点：
- 二叉查找树的均匀工夫复杂度为 O(log(N))
- 每个节点最多只能有两个子节点
- 每个节点的左右子树高度差不超过 1
咱们来看下如下构造：
右边的是 AVL 树，它的任何节点的两个子树的高度差异都 <=1；而左边的不是 AVL 树，因为 7 的两棵子树的高度相差为 2（以 2 为根节点的树的高度是 3，而以 8 为根节点的树的高度是 1）。
实现：
public class AVLTree<T extends Comparable<? super T>> {
private AVLTreeNode<T> rootNode; // root node
private static class AVLTreeNode<T> {
T element; // The data in the mode
BinaryNode<T> left; // Left child
BinaryNode<T> right; // Right child
int height; // Height
AVLTreeNode(T t) {this(t, null, null);
}
AVLTreeNode(T t, BinaryNode<T> lt, BinaryNode<T> rt) {
this.element = t;
this.left = lt;
this.right = rt;
this.height = 0;
}
}
// ...
}均衡二叉查找树通过旋转能够使每个节点的左右子树高度差不超过 1，也就是防止链化问题。磁盘的 IO 由树高决定，数据量越多，遍历次数越多，IO 次数就越多，就越慢。
4.6 BTree
下面的均衡二叉查找树可能因为数据量比拟大的时候，树高就会很高，IO 次数也就越多，这样的话会影响性能。所以，B 树就是为了解决即便数据量很大也能让 IO 次数很少的一种树。
BTree 是均衡搜寻多叉树，设树的度为 2d（d>1），高度为 h，那么 BTree 要满足以下条件：
- 每个叶子节点的高度一样，等于 h。
- 每个非叶子节点由 n-1 个 key 和 n 个指针 point 组成，其中 d<=n<=2d，key 和 point 互相距离，节点两端肯定是 key。
- 叶子节点指针都为 null
- 非叶子节点都是 [key，data] 二元组，其中 key 示意作为索引的键，data 为键值所在行的数据。
BTree 构造如下：
BTree 能够应用二分查找的查找形式，查找复杂度为 h * O(log(N))，一般来说树的高度是很小的，个别为 3 左右，因而 BTree 是一个十分高效的查找构造。
4.7 B+Tree
B+Tree 是 BTree 的一个变种，设 d 为树的度数，h 为树的高度，B+Tree 和 BTree 的不同次要在于：
- B+Tree 中的非叶子结点不存储数据，只存储键值。
- B+Tree 的叶子节点没有指针，所有键值都会呈现在叶子节点上，且 key 存储的键值对应 data 数据的物理地址。
- B+Tree 的每个非叶子节点由 n 个键值 key 和 n 个指针 point 组成
B+Tree 的构造如下：
4.8 带有程序拜访指针的 B+Tree
个别在数据库系统或文件系统中应用的 B+Tree 构造都在经典 B+Tree 的根底上进行了优化，减少了程序拜访指针。
如上图所示，在 B+Tree 的每个叶子节点减少一个指向相邻叶子节点的指针，就造成了带有程序拜访指针的 B+Tree。做这个优化的目标是为了进步区间拜访的性能，如果要查问 key 为从 18 到 49 的所有数据记录，当找到 18 后，只需顺着节点和指针程序遍历就能够一次性拜访到所有数据节点，极大提到了区间查问效率。
五、MySQL 为什么应用 B+Tree
一般来说，索引自身也很大，不可能全副存储在内存中，因而索引往往以索引文件的模式存储在磁盘上。这样的话，索引查找过程中就要产生磁盘 I/O 耗费，绝对于内存存取，I/O 存取的耗费要高几个数量级，所以评估一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘 I/O 操作次数的渐进复杂度。换句话说，索引的构造组织要尽量减少查找过程中磁盘 I/O 的存取次数。
5.1 磁盘 IO 与预读
下面说到了拜访磁盘，那么这里先简略介绍一下磁盘 IO 和预读，磁盘读取数据靠的是机械运动，每次读取数据破费的工夫能够分为寻道工夫、旋转提早、传输工夫三个局部，寻道工夫指的是磁臂挪动到指定磁道所须要的工夫，支流磁盘个别在 5ms 以下；旋转提早就是咱们常常据说的磁盘转速，比方一个磁盘 7200 转，示意每分钟能转 7200 次，也就是说 1 秒钟能转 120 次，旋转提早就是 1 /120/2 = 4.17ms；传输工夫指的是从磁盘读出或将数据写入磁盘的工夫，个别在零点几毫秒，绝对于前两个工夫能够忽略不计。那么拜访一次磁盘的工夫，即一次磁盘 IO 的工夫约等于 5+4.17 = 9ms 左右，听起来还挺不错的，但要晓得一台 500 -MIPS 的机器每秒能够执行 5 亿条指令，因为指令依附的是电的性质，换句话说执行一次 IO 的工夫能够执行 40 万条指令，数据库动辄十万百万乃至千万级数据，每次 9 毫秒的工夫，显然是个劫难。下图是计算机硬件提早的比照图，供大家参考：
思考到磁盘 IO 是十分昂扬的操作，计算机操作系统做了一些优化，当一次 IO 时，不光把以后磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为部分预读性原理通知咱们，当计算机拜访一个地址的数据的时候，与其相邻的数据也会很快被拜访到。每一次 IO 读取的数据咱们称之为一页（page）。具体一页有多大数据跟操作系统无关，个别为 4k 或 8k，也就是咱们读取一页内的数据时候，实际上才产生了一次 IO，这个实践对于索引的数据结构设计十分有帮忙。
5.2 B-/+ Tree 索引的性能剖析
上文说过个别应用磁盘 I/O 次数评估索引构造的优劣。先从 B-Tree 剖析，依据 B-Tree 的定义，可知检索一次最多须要拜访 h 个节点。数据库系统的设计者奇妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只须要一次 I/O 就能够齐全载入。为了达到这个目标，在理论实现 B-Tree 还须要应用如下技巧：
每次新建节点时，间接申请一个页的空间，这样就保障一个节点物理上也存储在一个页里，加之计算机存储调配都是按页对齐的，就实现了一个 node 只需一次 I/O。
B-Tree 中一次检索最多须要 h-1 次 I/O（根节点常驻内存），渐进复杂度 O(h)=O(logdN)O(h)=O(logdN)。个别理论利用中，出度 d 是十分大的数字，通常超过 100，因而 h 十分小（通常不超过 3）。（h 示意树的高度 & 出度 d 示意的是树的度，即树中各个节点的度的最大值）
综上所述，用 B-Tree 作为索引构造效率是十分高的。
而红黑树这种构造，h 显著要深的多。因为逻辑上很近的节点（父子）物理上可能很远，无奈利用局部性，所以红黑树的 I/O 渐进复杂度也为 O(h)，效率显著比 B-Tree 差很多。
上文还说过，B+Tree 更适宜外存索引，起因和内节点出度 d 无关。从下面剖析能够看到，d 越大索引的性能越好，而出度的下限取决于节点内 key 和 data 的大小：
dmax=floor(pagesize/(keysize+datasize+pointsize))floor 示意向下取整。因为 B+Tree 内节点去掉了 data 域，因而能够领有更大的出度，领有更好的性能。
六、MySQL 的存储引擎
MyISAM 和 InnoDB 存储引擎尽管索引构造都是 B+Tree，但实现上还是有些差异，咱们一起来看下：
6.1 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 的汇集索引辨别。
6.2 InnoDB
尽管 InnoDB 也应用 B+Tree 作为索引构造，但具体实现形式却与 MyISAM 截然不同。
第一个重大区别是 InnoDB 的数据文件自身就是索引文件。从上文晓得，MyISAM 索引文件和数据文件是拆散的，索引文件仅保留数据记录的地址。而在 InnoDB 中，表数据文件自身就是按 B+Tree 组织的一个索引构造，这棵树的叶节点 data 域保留了残缺的数据记录。这个索引的 key 是数据表的主键，因而 InnoDB 表数据文件自身就是主索引。
上图是 InnoDB 主索引（同时也是数据文件）的示意图，能够看到叶节点蕴含了残缺的数据记录。这种索引叫做汇集索引。因为 InnoDB 的数据文件自身要按主键汇集，所以 InnoDB 要求表必须有主键（MyISAM 能够没有），如果没有显式指定，则 MySQL 零碎会主动抉择一个能够惟一标识数据记录的列作为主键，如果不存在这种列，则 MySQL 主动为 InnoDB 表生成一个隐含字段作为主键，这个字段长度为 6 个字节，类型为长整型。
第二个与 MyISAM 索引的不同是 InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址。换句话说，InnoDB 的所有辅助索引都援用主键作为 data 域。例如，下图为定义在 Col3 上的一个辅助索引：
这里以英文字符的 ASCII 码作为比拟准则。汇集索引这种实现形式使得按主键的搜寻非常高效，然而辅助索引搜寻须要检索两遍索引：首先检索辅助索引取得主键，而后用主键到主索引中检索取得记录。
6.3 问题
这里你有可能会问了，为什么 InnoDB 只在主键索引树的叶子节点存储了具体数据，然而其余索引树却不存具体数据呢，而要多此一举先找到主键，再在主键索引树找到对应的数据呢?
其实很简略，因为 InnoDB 须要节俭存储空间。一个表里可能有很多个索引，InnoDB 都会给每个加了索引的字段生成索引树，如果每个字段的索引树都存储了具体数据，那么这个表的索引数据文件就变得十分微小（数据极度冗余了）。从节约磁盘空间的角度来说，真的没有必要每个字段索引树都存具体数据，通过这种看似“多此一举”的步骤，在就义较少查问的性能下节俭了微小的磁盘空间，这是十分有值得的。
6.4 MyISAM 与 InnoDB 比照
- InnoDB 反对事务，MyISAM 不反对事务。这是 MySQL 将默认存储引擎从 MyISAM 变成 InnoDB 的重要起因之一。
- InnoDB 反对外键，而 MyISAM 不反对。对一个蕴含外键的 InnoDB 表转为 MYISAM 会失败。
- InnoDB 是汇集索引，MyISAM 是非汇集索引。聚簇索引的文件寄存在主键索引的叶子节点上，因而 InnoDB 必须要有主键，通过主键索引效率很高。然而辅助索引须要两次查问，先查问到主键，而后再通过主键查问到数据。因而，主键不应该过大，因为主键太大，其余索引也都会很大。而 MyISAM 是非汇集索引，数据文件是拆散的，索引保留的是数据文件的指针。主键索引和辅助索引是独立的。
- InnoDB 不保留表的具体行数，执行 select count(*) from table 时须要全表扫描。而 MyISAM 用一个变量保留了整个表的行数，执行上述语句时只须要读出该变量即可，速度很快。
- InnoDB 最小的锁粒度是行锁，MyISAM 最小的锁粒度是表锁。一个更新语句会锁住整张表，导致其余查问和更新都会被阻塞，因而并发拜访受限。这也是 MySQL 将默认存储引擎从 MyISAM 变成 InnoDB 的重要起因之一。