转自https://www.jianshu.com/p/73cd9288a652
一、常见索引类型
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+ Tree做了优化。如下图所示：
二、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次数。
数据库在插入数据时要对其进行排序，这样做的好处就是优化插入和查询的效率，在数据不断变多的情况下，MySQL会再去开辟新的页来存放新的数据，而每个页都有指向下一页的指针和指向上一页的指针，将所有页组织起来。在开辟新页的时候，我们插入的数据不一定是放在新开辟的页上，而是要进行所有页的数据比较，来决定这条插入的数据放在哪一页上，而完成数据插入之后，最终的多页结构就会像上图中画的那样。这里可以看到插入索引按照有序插入的方式会效率更高。
多页情况下是否对查询效率有影响呢？
Mysql会采用页目录的目录项来指向一行数据，这条数据就是存在于这个目录项中的最小数据，那么就可以通过页目录来查找所需数据。所以对于多页结构也可以采用这种方式，使用一个目录项来指向某一页，而这个目录项存放的就是这一页中存放的最小数据的索引值。其实目录项的本质也是页，普通页中存的数据是项目数据（级别是行），而目录页中存的数据是普通页的地址（级别是页）。
于是通过索引的查找过程就是下面这张图展示的，非叶子节点的目录页（磁盘块）中key存放的是索引值，地址存放的是一个普通页的地址，这个非叶子节点的页是一个双向链表结构。而非叶子节点的页是一个单向链表，里面存放着索引值，如果是聚簇索引则数据项中存放了行数据，如果是非聚簇索引，则数据项中存放的是主键值。
所以结合底层数据结构来看，MySQL中InnoDB的索引结构，其中的每个节点就可以理解为是一个页，而叶子节点也就是数据页，除了叶子节点以外的节点就是目录页。非叶子节点只存放了索引，而只有叶子节点中存放了真实的数据，这也是符合B+树的特点的。于是将页和B+树的数据结构图结合指针展现出来的图例就如下：
Mysq索引l高频考察点
聚簇索引/非聚簇索引
- 所谓聚簇索引，就是指
主索引文件和数据文件为同一份文件，聚簇索引主要用在Innodb存储引擎中。在该索引实现方式中B+Tree的叶子节点上的data就是数据本身，key为主键，如果是一般索引的话，data便会指向对应的主索引，如下图所示：
image.png
在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如上图中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。
- 非聚簇索引就是指B+Tree的
叶子节点上的data，并不是数据本身，而是数据存放的地址。主索引和辅助索引没啥区别，只是主索引中的key一定得是唯一的。主要用在MyISAM存储引擎中，如下图：
image.png
非聚簇索引比聚簇索引多了一次读取数据的IO操作，所以查找性能上会差
1、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码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
2、MyISAM索引实现
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：
这里设表一共有三列，假设我们以Col1为主键，则上图是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：
同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。
聚簇索引查询相对会更快一些，因为主键索引树的叶子节点直接就是我们要查询的整行数据了。而非主键索引的叶子节点是主键的值，查到主键的值以后，还需要再通过主键的值再进行一次查询（这个过程叫做回表, 也就是查了两个索引树）。
InnoDB索引和MyISAM索引的区别：
一是主索引的区别，InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。
二是辅助索引的区别：InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。
InnoDB的主索引文件上，直接存放该行数据，称为聚簇索引。次索引指向对主键的引用。
Myisam中，主索引和次索引都指向物理行。
为什么建议用自增型的主键索引
一般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 树文章了！
4.https://blog.csdn.net/weixin_39707941/article/details/110870510
