一、常见索引类型
1.哈希索引
哈希表是一种以键 - 值（key-value）存储数据的结构，我们只要输入待查找的值即 key，就可以找到其对应的值即 Value。当多个 key 值经过哈希换算出现同一个值的情况下，就拉出一个链表。
优点：哈希表这种结构适用于只有等值查询的场景，新增方便。
缺点：非有序，做区间查询的速度是很慢，需要全部遍历。哈希索引也不支持多列联合索引的最左匹配规则；
2.有序数组
按照顺序排列的索引数组，有序数组索引只适用于静态存储引擎。
优点：等值查询和范围查询场景中的性能非常好
缺点：更新数据麻烦，尤其需要在数组中间插入一个记录的时候，就必须得挪动后面所有的记录。
3.红黑树
红黑树：是平衡的BST，性能稳定在O(logN)， 但因为是二叉树，树的高度随着数据量增加而增加，并且需要再平衡。适合数据都在内存的情况，比如Java里的HashMap。但是在硬盘寻址的场景下IO成本会比较高。
4.二叉树
二叉树的概念本身很简单，除了根节点之外，每个节点最多有两个孩子；并且二叉树上的元素拥有顺序，所有比它小的元素在它的左子树，比它大的元素在它的右子树。n个元素的二叉搜索树，对应的树高为log(n)：
- 优点：查找元素、插入元素的时间为log(n)。
- 缺点：递增或者递减插入，树形结构会退化成链表。
为了解决二叉搜索树不平衡的问题，在此基础上提出了各种平衡树。AVL就是一颗经典的平衡树，平衡树的思路很朴素，就是在插入元素的时候进行判断，如果当前的元素的插入或删除会影响树的平衡性，那么则进行旋转操作，从而维持树的平衡。
旋转平衡
3.B树及B+树
B树（Balance Tree，也叫B-树）是一棵多叉搜索树，B树对节点存在着一些限制，具体的定义如下：
- B树中每个节点的元素数量和子树的数量都是有限的，除了根节点外，所有节点最多拥有M-1个元素，所有非叶子非根节点最多拥有M个子树（称为M阶B树）
- 根节点至少拥有两个子树，除了根节点之外的非叶子节点拥有K个子树以及K-1个元素((M+1/2) < K < M)，元素按照递增或递减顺序排列
- 所有叶子节点属于同一层。
B/B+树是为了磁盘或其它存储设备而设计的一种平衡多路查找树(相对于二叉，B树每个内节点有多个分支/叉)，与红黑树相比，在相同的的节点的情况下，一颗B/B+树的高度远远小于红黑树的高度，B/B+树上操作的时间通常由存取磁盘的时间和CPU计算时间这两部分构成，而CPU的速度非常快，所以B树的操作效率取决于访问磁盘的次数，关键字总数相同的情况下B树的高度越小，磁盘I/O所花的时间越少。
下面列举B树和B+树的两个示例图:
（图片来源网络）B 树：将数据保存在非叶子节点。而这个特点会导致非页子节点不能存储大量的索引
针对B数的特点， B+ Tree做了优化。如下图所示：
（图片来源网络）B+ Tree 将所有的 data 数据都保存到了叶子节点中，非叶子节点只保存索引和指针
二、Mysql索引
1. Mysql引擎类型
数据库中的引擎类型主要分为：MyISAM和InnoDB。
MyISAM是MySQL的默认数据库引擎（5.5版之前）。虽然性能极佳，而且提供了大量的特性，包括全文索引、压缩、空间函数等，但MyISAM不支持事务和行级锁，而且最大的缺陷就是崩溃后无法安全恢复。不过，5.5版本之后，MySQL引入了InnoDB（事务性数据库引擎），MySQL 5.5版本后默认的存储引擎为InnoDB。
大多数时候我们使用的都是 InnoDB 存储引擎，但是在某些情况下使用 MyISAM 也是合适的比如读密集的情况下。（如果你不介意 MyISAM 崩溃恢复问题的话）。
2. MyISAM和InnoDB两者的对比
- 是否支持行级锁 : MyISAM 只有表级锁(table-level locking)，而InnoDB 支持行级锁(row-level locking)和表级锁，默认为行级锁。
- 是否支持事务和崩溃后的安全恢复： MyISAM 强调的是性能，每次查询具有原子性,其执行速度比InnoDB类型更快，但是不提供事务支持。但是InnoDB 提供事务支持事务，外部键等高级数据库功能。 具有事务(commit)、回滚(rollback)和崩溃修复能力(crash recovery capabilities)的事务安全(transaction-safe (ACID compliant))型表。
- 是否支持外键： MyISAM不支持，而InnoDB支持。
-
是否支持MVCC ：仅 InnoDB 支持。应对高并发事务, MVCC比单纯的加锁更高效;MVCC只在
READ COMMITTED和REPEATABLE READ两个隔离级别下工作;MVCC可以使用 乐观(optimistic)锁 和 悲观(pessimistic)锁来实现;各数据库中MVCC实现并不统一。推荐阅读：MySQL-InnoDB-MVCC多版本并发控制
-
是否支持MVCC ：仅 InnoDB 支持。应对高并发事务, MVCC比单纯的加锁更高效;MVCC只在
目前基本都会选择InnoDB，但是某些情况下你并不在乎可扩展能力和并发能力，也不需要事务支持，也不在乎崩溃后的安全恢复问题的话，选择MyISAM也可以。但是一般情况下，我们都是需要考虑到这些问题的。
3. Innodb中的B+树设计原理
a.为什么索引要放到磁盘？
在上一篇《Mysql篇之架构设计》中介绍到Innodb引擎会在内存引入buffer pool，但是由于内存容易丢失，一般而言会配合各种日志和刷盘策略，将数据持久化在磁盘文件中，但是和内存相比，从磁盘中读取数据的速度会慢上百倍千倍甚至万倍，所以，我们应当尽量减少从磁盘中读取数据的次数。另外，从磁盘中读取数据时，都是按照磁盘块来读取的，并不是一条一条的读。如果我们能把尽量多的数据放进磁盘块中，那一次磁盘读取操作就会读取更多数据，那我们查找数据的时间也会大幅度降低。如果采用树这种数据结构作为索引的数据结构，那每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块。
b.为什么不用平衡二叉树作为索引呢？
平衡二叉树每个节点只存储一个键值和数据的，这就意味着每个磁盘块仅仅存储一个键值和数据！存的越多，二叉树的节点也会越多，并且高度也会极其高，查找数据时也会进行很多次磁盘 IO，效率也非常低下！为了解决这个问题，就可以采用 B 树结构来解决层级过高的问题。
B树的每个节点称为页，页就是前面提到的磁盘块，B 树相对于平衡二叉树，每个节点存储了更多的键值（key）和数据（data），并且每个节点拥有更多的子节点，子节点的个数一般称为阶。 基于这个特性，B 树查找数据读取磁盘的次数将会很少，数据的查找效率也会比平衡二叉树高很多。
c.划重点：为什么要用B+树？
- B 树节点中不仅存储键值，也会存储数据，而B+ 树非叶子节点上是不存储数据的，仅存储键值，如果不存储数据，那么就会存储更多的键值，层高基本不会因为数据扩大而增高（三层树结构大概可以存放两千万数据量）。
- B+树有利于磁盘的IO，数据越多，只需要提升树的阶数（节点的子节点树）即可，树就会更矮更胖，IO次数就更少。
- B+树的所有数据都在叶子节点上，所以B+树的查询效率稳定，一般都是查询3次（根节点存放在内存中）。B+ 树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的。范围查找，排序查找，分组查找以及去重查找变得异常简单，而B 树因为数据分散在各个节点，要实现这一点是很不容易的。
- B+ 树中各个页之间是通过双向链表连接的，叶子节点中的数据是通过单向链表连接的。在 InnoDB 中，我们通过数据页之间通过双向链表连接以及叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。
4.InnoDB的页目录
MySQL的数据是以页为基本单位组合而成的，页的大小是16KB，里面包含我们的多条数据，它还有指向下一页的指针和指向上一页的指针。数据库在查询到一条数据的时候会把页中相邻的数据也取出来，为什么这样做呢？这是遵循了这样一个原则：“一个程序在访问了一条数据之后，在之后会有极大的可能再次访问这条数据和访问这条数据的相邻数据”，所以索性直接加载4KB（OS页打小为4k，通常为其整数倍）的数据到内存中，下次要访问这一页的数据时，直接从内存中找，可以减少磁盘IO次数。
page页结构
数据库在插入数据时要对其进行排序，这样做的好处就是优化插入和查询的效率，在数据不断变多的情况下，MySQL会再去开辟新的页来存放新的数据，而每个页都有指向下一页的指针和指向上一页的指针，将所有页组织起来。在开辟新页的时候，我们插入的数据不一定是放在新开辟的页上，而是要进行所有页的数据比较，来决定这条插入的数据放在哪一页上，而完成数据插入之后，最终的多页结构就会像上图中画的那样。这里可以看到插入索引按照有序插入的方式会效率更高。
page组成的双向链表
多页情况下是否对查询效率有影响呢？
Mysql会采用页目录的目录项来指向一行数据，这条数据就是存在于这个目录项中的最小数据，那么就可以通过页目录来查找所需数据。所以对于多页结构也可以采用这种方式，使用一个目录项来指向某一页，而这个目录项存放的就是这一页中存放的最小数据的索引值。其实目录项的本质也是页，普通页中存的数据是项目数据（级别是行），而目录页中存的数据是普通页的地址（级别是页）。
Mysql中索引的单双链表
于是通过索引的查找过程就是下面这张图展示的，非叶子节点的目录页（磁盘块）中key存放的是索引值，地址存放的是一个普通页的地址，这个非叶子节点的页是一个双向链表结构。而非叶子节点的页是一个单向链表，里面存放着索引值，如果是聚簇索引则数据项中存放了行数据，如果是非聚簇索引，则数据项中存放的是主键值。
索引的查找过程
所以结合底层数据结构来看，MySQL中InnoDB的索引结构，其中的每个节点就可以理解为是一个页，而叶子节点也就是数据页，除了叶子节点以外的节点就是目录页。非叶子节点只存放了索引，而只有叶子节点中存放了真实的数据，这也是符合B+树的特点的。于是将页和B+树的数据结构图结合指针展现出来的图例就如下：
图 from 云教程中心
Mysq索引l高频考察点
聚簇索引/非聚簇索引
- 主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。
- 非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。
聚簇索引查询相对会更快一些，因为主键索引树的叶子节点直接就是我们要查询的整行数据了。而非主键索引的叶子节点是主键的值，查到主键的值以后，还需要再通过主键的值再进行一次查询（这个过程叫做回表, 也就是查了两个索引树）。
为什么建议用自增型的主键索引
一般innodb表里，建议统一用auto_increment自增值作为主键值，因为这样可以保持聚簇索引直接加记录就可以，如果用那种不是单调递增的主键值，可能会导致b+树分裂后重新组织，会浪费时间。且主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。所以，从性能和存储空间方面考量，自增主键往往是更合理的选择。
什么情况下可以不用自增主键，典型的 KV 场景下，只有一个索引，该索引必须是唯一索引。那么可以考虑用业务主键作为唯一索引。
覆盖索引
如果一个索引包含（或者说覆盖）所有需要查询的字段的值，我们就称之为“覆盖索引”。我们知道InnoDB存储引擎中，如果不是主键索引，叶子节点存储的是主键+列值。最终还是要“回表”，也就是要通过主键再查找一次。这样就会比较慢覆盖索引就是把要查询出的列和索引是对应的，不做回表操作！
最左前缀原则
对多个字段同时建立的索引(有顺序，ABC，ACB是完全不同的两种联合索引。)以联合索引(a,b,c)为例，建立这样的索引相当于建立了索引a、ab、abc三个索引。
所以在建立联合索引的时候，如何安排索引内的字段顺序？
这里我们的评估标准是，索引的复用能力。因为可以支持最左前缀，所以当已经有了 (a,b) 这个联合索引后，一般就不需要单独在 a 上建立索引了。因此，第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。
索引下推
MySQL 5.6引入了索引下推优化，可以在索引遍历过程中，对索引中包含的字段先做判断，过滤掉不符合条件的记录，减少回表字数。
如果没有索引下推优化（或称ICP优化），当进行索引查询时，首先根据索引来查找记录，然后再根据where条件来过滤记录；在支持ICP优化后，MySQL会在取出索引的同时，判断是否可以进行where条件过滤再进行索引查询，也就是说提前执行where的部分过滤操作，在某些场景下，可以大大减少回表次数，从而提升整体性能。
参考列表
1.mysql中InnoDB引擎中页的概念
2.索引很难么？带你从头到尾捋一遍 MySQL 索引结构
3.终于有篇看的懂的 B 树文章了！
网友评论