前言
索引是存储引擎用于快速找到记录的一种数据结构，和书的目录一样，索引的出现就是为了提高数据的查找效率。
数据量小且服务负载低的时候，索引对查询性能的影响可能并不是那么明显，一个合理的索引在数据量大的时候更能体现出对查询性能的影响。
索引的常见模型
能实现索引的方式有很多种，MySQL的InnoDB引擎使用B+Tree索引模型。这里简单介绍一些能够提高读写效率的数据结构，如哈希表、有序数组以及搜索树。
哈希表
哈希索引便是基于哈希表算法，MySQL中只有Memory引擎显示支持哈希索引
哈希表是一种以键 - 值（key-value）存储数据的结构，我们只要输入待查找的键即 key，就可以找到其对应的值即 Value。
简单的来说，哈希表就是一个数组+链表，hash算法根据输入的key计算出hash值，根据hash值得到数组对应的下标，链表的作用就是，不同的key计算得出得hash值可能是相同的，这时候，一个数组的下标就会对应多个值，所以就需要一个链表来保存。
哈希表示例
上图为一个简单的哈希表示例，User2和User3的ID_card计算出来的哈希值都为3，所以数组对应的值跟着一个链表。
缺点
因为哈希值是无序的，所以哈希表不适用于区间查找，区间查找将会导致全表扫描。
哈希表适用于等值查找
有序数组
有序数组在等值查询和范围查询场景中的性能就都非常优秀。
有序数组示例
这里我们假设身份证号没有重复，这个数组就是按照身份证号递增的顺序保存的。这时候如果你要查 ID_card_n2 对应的名字，用二分法就可以快速得到，这个时间复杂度是 O(log(N))。
同时很显然，这个索引结构支持范围查询。你要查身份证号在[ID_card_X, ID_card_Y]区间的 User，可以先用二分法找到 ID_card_X（如果不存在 ID_card_X，就找到大于 ID_card_X 的第一个 User），然后向右遍历，直到查到第一个大于 ID_card_Y 的身份证号，退出循环。
缺点
在需要更新数据的时候就麻烦了，你往中间插入一个记录就必须得挪动后面所有的记录，成本太高。
所以，有序数组索引只适用于静态存储引擎。
二叉搜索树
二叉搜索树示例
二叉搜索树的特点是：每个节点的左儿子小于父节点，父节点又小于右儿子。这样如果你要查 ID_card_n2 的话，按照图中的搜索顺序就是按照 UserA -> UserC -> UserF -> User2 这个路径得到。这个时间复杂度是 O(log(N))。
为了维持 O(log(N)) 的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 O(log(N))。
虽然二叉搜索树的查询效率很高，但是却不适用与数据库存储上使用，假设一棵 100 万节点的平衡二叉树，树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10 ms 的时间，这是很慢的。
B树（Balance-tree 平衡多路查找树）
从算法逻辑上讲，二叉搜索树的查找速度已经够快，但是对于数据库索引来说，我们还应考虑磁盘IO的问题，数据库索引是建立在磁盘上的，当数据量太大的时候是没法将整颗索引树一次性加载到内存的。
能做的只有逐一加载磁盘页（磁盘页对应索引树的节点）。
B树的每个节点最多包含
k个孩子，k被称为B树的阶，k取决于磁盘页的大小。
这里就不对B树进行展开，总结一下，B树一个节点可以存储多个元素（节点内元素是有序的），并且可以拥有多个孩子，能够有效的减少树的高度，从而减少磁盘读写次数，提升效率。
B+树
B+树是B树的变种，中间节点不保存数据，只用来索引，所有的数据都保存在叶子节点上，且叶子节点之间还用指针连接在一起。
B+树示例
相比B树的优势：
1）B+树除了叶子节点不保存数据，所以同样大小的磁盘页可以容纳更多的节点元素，也就导致IO查询次数更少。
2）B树的范围查询更加繁琐，因为取值区间可能分布在不同分支的子树上；而B+树只要查询到叶子节点，在链表上做遍历即可。
主键索引和普通索引
主键索引又称聚簇索引，主键索引和普通索引的区别在于，主键索引的叶子节点保存的是数据，而普通索引的叶子节点保存的是该行数据的主键，拿到主键后再去主键索引查找出对应的数据，这个过程称为回表。
索引维护
在插入新值的时候，如果索引键不是递增的，而是在中间某个位置插入，这时就需要挪动后面的元素，如果当前数据页已经满了，这将导致页分裂。这除了影响性能外，还将影响磁盘的利用率。
自增主键的插入数据模式，正符合了我们前面提到的递增插入的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。
覆盖索引
| id(主键) | name | age |
|---|---|---|
| 1 | Jane | 12 |
| 2 | Nick | 14 |
假设目前有 t_user表，其中id为主键，name列上建有索引，现在执行语句
SELECT * FROM t_user WHERE name = 'Jane'
将会先查询 name索引树，得到id=1，然后再从主键索引上查询出对应的数据，这个过程称为回表。
那么有没有减少回表的可能呢？如果把上面的sql改成：
SELECT id FROM t_user WHERE name = 'Jane'
这时只需要查 id 的值，而 id 的值已经在 name 索引树上了，因此可以直接提供查询结果，不需要回表。
在这个查询里面，索引 name 已经“覆盖了”我们的查询需求，我们称为覆盖索引。
如果你要查询的字段不是id，而是其它字段，这时建立联合索引，查询时也能达到覆盖索引的效果。
如建立联合索引 (name, age)，那么在执行：SELECT age FROM t_user WHERE name = 'Jane' 时也是不需要回表的。
最左前缀原则
以上面提到的联合索引(name, age)为例，执行下面的sql语句，可以用到联合索引(name, age)
SELECT * FROM t_user WHERE name = 'Jane';
SELECT * FROM t_user WHERE name LIKE 'Jan%';
如果是下面这种情况，则没法利用最左前缀原则
SELECT * FROM t_user WHERE name LIKE '%Jan';
网友评论