什么是索引

索引是储存引擎用于快速找到记录的一种数据结构

1.索引是一种数据结构
2.作用相当于书籍目录
在MySQL中，假设我们有一种记录表

id	name	age
1	huyuan	10
2	huiui	18
3	lumingfei	20
4	chuzihang	15

需求：查找到年龄为15的人

1. 没有索引
   遍历所有的数据去做逐一的对比，时间复杂度为O(n)
   我们如果在插入数据的过程中，额外维护一个数组，将age字段有序的储存，得到如下数组[10,15,18,20]。
   有序就意味着我们可以使用二分查找更快的找到我们的age这样的话时间复杂度就到了O(logn)但是这只是做到了对age的快速查找。假如age和整体数据相互关联，那我们就可以找到数据了。
   PS：Mysql中的索引不是使用的数组，而是B+树

索引能为我们带来什么

如上面所说，索引能帮助我们快速的查找数据，其次因为索引中的值是顺序储存，那么可以帮助我们进行orderby操作。而且索引中国也是储存了真正的值的，因此有一些问题的查询直接在索引中完成（索引覆盖）

借用官方的总结索优点

• 减少查询所需扫描的次数
• 减少服务器的排序操作和创建临时表的操作（加快了groupby和orderby等操作）
• 将服务器的所以IO变为顺序IO（加快查询速度）

索引有哪些缺点

首先索引也是数据，所以他本身需要储存空间。其次，在更新，插入，删除时索引也需要进行维护，因此会带来额外的时间开销。

• 索引占用磁盘或者内存空间
• 减慢了插入更新的操作速度

实际上，在一定的数据范围内，建立索引带来的开销是远远小于他所带来的好处的，但是我们仍要防止索引的滥用

索引的种类

对于Mysql来说，在服务器层并不实现索引，而是交给储存引擎来实现的。显然不同的引擎索引类型也就不尽相同。以InnoDB为例，他所使用的就是B+树索引。

MySQL主要有四种索引

• B-/B+树索引
• 哈希索引
• 空间数据索引
• 全文索引

B+树索引和B-树索引

B-树

B-树也叫B树，他是一个多路平衡二叉树。B树与B+树本身都是有最简单的二叉树变换而来的,对于一颗M阶的B树又以下性质：
首先本身是没有B-树这个概念是对B-Tree的错误翻译导致，事实上指的就是Binary-Tree 平衡树的缩写。

• 每个节点最多含有m - 1 个关键字
• 根节点最少有1个关键字
• 非根节点至少有m / 2个关键字
• 每个节点中的关键字都按照从大到小的顺序排序，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
• 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。
• 每个节点都存在索引和数据，也就是对应的key和value。
  这们说可能对他仍然是一头雾水，脑子里对他没有概念。静下来学习数据结构本身就是学习他的性质的一个过程，不同的性质适应于不同的应用场景，从整体结构来看B树可以看作是一个矮胖的二叉搜索树，从本质来说就是相反设法的降低整棵树的高度从而降低了查找时间。

这样做到底为什么能够提升查找效率？

1. 中间节点不保存数据，那么就可以保存更多的索引，减少数据库磁盘IO的次数。
2. 因为中间节点不保存数据，所以每一次的查找都会命中到叶子节点中，而叶子节点是出于在同一层，因此查询的性能更加稳定。
3. 所有的叶子节点按顺序链接成了链表，因此可以方便的进行范围查找。

对于查找过程中的磁盘IO操作以及内存操作做一个简单的说明

image
假如我们现在需要查找
3号文件那么我们首先从根目录开始访问磁盘块1然后访问内存发现9<17所以我根据P1指针找到了并访问磁盘块2
之后再访问内存发现8<9<12找到了并访问磁盘块6然后再访问内存找到了文件9
在这个过程中一共进行了3次磁盘IO和3次内存查找，但是每次内存查找都是O(lgn).也就是说3Olg(n)，这就也就意味着随着我们B树的高度分叉越多他每一个节点的关键值越多就会导致内存的查找越慢，但是我们磁盘的访问次数也就会越小，树的高度也就越低。
所以我们通过开多叉尽可能的在一个合适的范围内降低数的高度，同时保证有序优化了访问内存时算法的查找复杂度。
但是我们一定要明白内存IO 和 磁盘 IO 差的差不多四个数量级 也就是说内存一秒钟干的事磁盘要接近四天，当然这里不包括SSD，到这里我们大致了解了B树的查找过程，也明白了它的性质对于查找场景给我们带来的好处。

如何创建高性能的索引？

---

前缀索引和索引选择性

我们先大概了解一下索引的工作步骤，数据库使用索引的工作步骤:

1. 在索引的B+树上找到对应的值，比如找到学校名称为河南科技学院的一条记录，并且拿到这条数据在磁盘上的地址
2. 根据地址去磁盘上取得数据
   下面我们做一个假设，假如我们的数据表中前两个字为河南的学校有且只有一条，那么河南作为河南科技学院前缀的同时也可以唯一标识它，作为他的索引。
   这意味着什么呢，原本使用“河南科技学院”我们才可以得到的一条记录，现在通过河南就可以查到，这大大的缩短了我们储存索引的空间。
   前缀索引：在对一个比较长的字符串进行索引时，可以仅索引开始的一部分字符，这样可以大大的节约索引空间，从而提高索引的效率，但是这样也会降低索引的选择性。
   索引的选择性：不重复的值/所有的值，可以看出索引的选择性为0-1，最高的就是该列唯一，没有重复值。
   对于索引的选择测试

select 
    count(distinct left(school_name,3))/count(*) as sch3, 
    count(distinct left(school_name,4))/count(*) as sch4,
    count(distinct left(school_name,5))/count(*) as sch5,
    count(distinct school_name)/count(*) as original
from 
    user;
```PS: left()的作用是切割字符串 distinct表示唯一```

通过适当的增加前缀的长度便于我们找到最优的前缀索引。

联合索引

一般我们都是有对多个列进行索引的需求，因为查询的需求多种多样，这个时候我们可以选择建立多个独立的索引或者建立一个联合索引。大多数时候都是联合索引更加合适一些。

假设我们要执行这个语句：select * from user where school_name = '河南' and student = '飞猪', 假如我们没有使用索引那么我们会有两种方案查询

• 先把所有school_name = '河南'的查询出来，之后再筛选
• 先把所有student = '学生'的查询出来，之后再筛选
  之后mysql的优化器会自动选择一个它认为最优的方案（不一定最优）。
  那么如果我们分别对以上两个字段添加索引，从理论上来讲他会命中我们的两个索引，但是事情情况确实不确定的。

根据官方文档介绍MySQL5.0之后的版本支持合并索引，也就是可以同时使用两个索引。但是Mysql的优化器会认为我查询两次B+树的过程并没有我查询一次B+树加上一次筛选。因此大多数情况MySQL 都只会有一个索引生效
创建联合索引的语法:alter table user add index school_student(`school_name`,`student`).

PS：使用联合索引的时候，有一个非常重要的点就是所有的索引列只可以进行最左前缀匹配，例如上面的联合索引如果我只单纯的使用student作为查询条件的时候是不可以使用的
根据这一原则，我们在建立联合索引的时候将选择性高的列放在联合索引的前面

最左前缀索引原理

当数据列有序的时候,mysql可以使用索引,那么假设我们建立了school_age索引,示例数据如下:

school	age
a	12
b	12
b	14
b	15
c	1

在这份数据集中，school字段是完全有序的，索引school可以使用。
但是从全表来看，age字段不是有序的，因此无法直接使用索引，那假如当school确定的时候，对于age而言就是有序的了，这就是最左前缀索引的原理。

---

注意:这里会有一个误区，就是我们是不是只能对有序字段加索引呢？当然不是！这里面所说的有序都是相对的。
我们只能对有序的字段使用索引，这里可以这样理解，前面我们也说过B树的一个性质就是有序，所以在生成联合索引的时候他的排序规则就是最左原则也就是在左侧的有序基础上再有序这样建立起来的一个B树，所以最左原理也就很很清晰了。
例如:联合索引（a,b,c）
假如我们给定调教 a = 1 and c =2 这种情况下只有第一重索引可以生效，因为第三重索引是建立第二重字段有序的基础上的。说到这里，大家再也不用死记硬背所谓的最左前缀索引原理了。

---