[MySQL]索引
索引介绍
索引是帮助数据库高效获取数据的数据结构。在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用数据， 这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。
假设我们有存了100个 1~999的数字，在没有索引的情况下，数据库会对表全表扫描，如果我要查找的记录排在表的后面，那么就需要越过大半的记录才能查找到我需要的记录。此时的查找效率会很低。
在这基础之上，如果有索引，将这些数据通过二分法插入一个二叉树中，此时我再查找这个数据，就不需要一条条记录地去比对了，此时100条记录最多查找7次就能够查找到我需要的记录，极大地提高了查找效率。(当然，数据库里的数据结构不是就只是简单的二叉树)
当然，索引也不是只有优势没有劣势。
| 优势 | 劣势 |
| 提高数据检索的效率，降低数据库的IO成本 | 索引列也是要占用空间的 |
| 通过索引列对数据进行排序，降低数据排序的成本，降低CPU的消耗。 | 索引大大提高了查询效率，同时却也降低更新表的速度， 如过对表进行INSERT、UPDATE、DELETE时，效率会降低。 |
B树数据结构
MySQL的索引是在存储引擎层实现的，不同的存储引擎有不同的索引结构，主要包含以下几种：
| 索引结构 | 描述 |
|---|---|
| B+Tree索引 | 最常见的索引类型，大部分引擎都支持 B+ 树索引 |
| Hash索引 | 底层数据结构是用哈希表实现的, 只有精确匹配索引列的查询才有效, 不支持范围查询 |
| R-tree(空间索引） | 空间索引是MyISAM引擎的一个特殊索引类型，主要用于地理空间数据类型，通常使用较少 |
| Full-text(全文索引) | 是一种通过建立倒排索引,快速匹配文档的方式。类似于Lucene,Solr,ES |
上面是MySQL中支持的所有索引，当然，没有特意指明的情况，索引一般都指B+Tree索引
B-tree
介绍B+Tree前，还要先介绍一下B-Tree结构。B-Tree，B树是一种多叉路衡查找树，相对于二叉树，B树每个节点可以有多个分支，即多叉。 以一颗最大度数 (一个节点中最多存储的指针数) 为5的b-tree为例，那这个B树每个节点最多存储4个key，5 个指针:
B-tree的特点
1.n阶的B树，每一个节点最多存储n-1个key，对应n个指针
2.若当前节点存储的key数量到达5，就会裂变，中间元素向上分裂
(例如:一个末节点的key有88、89、95、96，而上一层的key为80、100、110。这个时候添加一个97到表里，97数据会先从根节点查找到该末节点，然后将其添加到该末节点，然后95会裂变，添加到上一层中，这就是裂变)
3.在B树中，非叶子节点和叶子节点都会存放数据
这样一来，存储时使用b-tree，依旧有一定缺陷，也因此又衍生出了B+tree，也是大多数数据库主要使用的数据结构。
B-Tree的不足
所有的非叶子节点和叶子节点都会同时存放数据和指针。在硬盘中，存储空间是被划分为一个个块的，而B-Tree中的数据和指针混杂分散在每一个节点中。
IO操作时，读取数据会不连续。在查询多个连续数据时，若当前节点里没有查找完需要的数据，不能直接跳转到下一个节点，还需返回上一层节点找到下一个指针，再去访问下一个节点。底层的数据操作比较繁琐。
在添加数据时，B-Tree还会进行裂变，但B-Tree裂变时不仅影响指针还会影响数据，cpu开销比较大。
B+tree
为了改进B-Tree树的不足，又衍生出了B+Tree。B+Tree与B-Tree类似，但有很多不同，下面这是一个最大度数为4的B+Tree结构图:
其中，蓝色框框圈起来的部分，也就是非叶子节点，仅起到索引数据的作用，只以key-value形式存放指针，不存放具体的数据。
红色部分是存储数据的部分，也是该树的叶子节点 ，则存放所有具体的数据内容。并且每个叶子节点中，会存放一个指向下一个叶子节点的指针(但没有指向上一个叶子节点的指针)。
B-Tree和B+Tree的区别：
1.所有的数据都会出现在叶子节点
2.叶子节点形成一个单向链表
3.非叶子节点仅仅起到索引数据作用，具体的数据都是在叶子节点存放的
为何B+Tree比B-Tree更适合实际中操作系统的文件索引和数据库索引
1.B+Tree的磁盘读写代价更低。B+Tree的内部节点并没有指向关键字具体信息的指针。因此其内部节点相对BTree更小，如果把所有同一内部节点的关键字存放在同一个盘块中，那么盘块所能容纳的关键字数量也越多。一次性读取到内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了
2.B+Tree的查询效率更加稳定。由于非叶子节点不是最终指向文件内容的节点，而是叶子节点中关键字的索引，所以任何关键字的查找都必须走一条从根节点到叶子节点的路。所有关键字的路径长度相同，导致每个数据的查询效率相当
MySQL中的B+Tree
对比普通的B+Tree，MySQL在其基础上，添加了一个指向上一个叶子节点 (首尾相连) 的指针，也就是变成了一个双链表。
索引分类
在MySQL数据库，将索引的具体类型主要分为以下几类：主键索引、唯一索引、常规索引、全文索引。
| 分类 | 含义 | 特点 | 关键字 |
|---|---|---|---|
| 主键索引 | 针对于表中主键创建的索引 | 默认自动创建, 只能有一个 | PRIMARY |
| 唯一索引 | 避免同一个表中某数据列中的值重复 | 可以有多个 | UNIQUE |
| 常规索引 | 快速定位特定数据 | 可以有多个 | |
| 全文索引 | 全文索引查找的是文本中的关键词，而不是比较索引中的值 | 可以有多个 | FULLTEXT |
而在在InnoDB存储引擎中，根据索引的存储形式，又可以分为以下两种
| 分类 | 含义 | 特点 |
|---|---|---|
| 聚集索引 | 将数据存储与索引放到了一块，索引结构的叶子节点保存了行数据 | 必须有,而且只有一个 |
| 二级索引 | 将数据与索引分开存储，索引结构的叶子节点关联的是对应的主键 | 可以存在多个 |
聚集索引选取规则:
1.如果存在主键，主键索引就是聚集索引
2.如果不存在主键，将使用第一个唯一（UNIQUE）索引作为聚集索引
3.如果表没有主键，或没有合适的唯一索引，则InnoDB会自动生成一个rowid作为隐藏的聚集索引
聚集索引和二级索引的具体结构
聚集索引的叶子节点下挂的是这一行的数据，二级索引的叶子节点下挂的是该字段值对应的主键值。
在查询数据时，如果是通过二级索引查找数据。数据库系统会先在二级索引的目录里进行查找，获取到了对应主键值后，进行回表查询。也就拿着主键值，去聚集索引查询需要的数据。
回表查询： 这种先到二级索引中查找数据，找到主键值，然后再到聚集索引中根据主键值，获取数据的方式，就称之为回表查询。
在执行查询语句时，如果能够走聚集索引，就不必要走二级索引。
在数据库查询语句优化时，注意走聚集索引也是一个重要的优化方向。