MySQL原理/MySQL索引.md · Anton/Road to Advancement

# MySQL索引

## 一、索引是什么？

```
数据库索引,是数据库管理系统(DBMS)中一个排序的数据结构,以协助快速查询,
更新数据库表中数据。

数据是以文件的形式存放在磁盘上面的,每一行数据都有它的磁盘地址。如果没有索引的话,我们要从500万行数据里面检索一条数据,只能依次遍历这张表的全部数据直到找到这条数据。
但是我们有了索引之后,只需要在索引里面去检索这条数据就行了,因为它是一种
特殊的专门用来快速检索的数据结构,我们找到数据存放的磁盘地址以后,就可以拿到数据了。
```

### 索引的类型

```
在InnoDB里面,索引类型有三种,普通索引、唯一索引(主键索引是特殊的唯
索引)、全文索引。

普通(Normal):也叫非唯一索引,是最普通的索引,没有任何的限制。

唯一(Unique):唯一索引要求键值不能重复。另外需要注意的是,主键索引是
种特殊的唯一索引,它还多了一个限制条件,要求键值不能为空。主键索引用primay key 创建。

全文(Fulltext):针对比较大的数据,比如我们存放的是消息内容、一篇文章,有
几KB的数据的这种情况,如果要解决 like 查询在全文匹配的时候效率低的问题,可以创建全文索引。只有文本类型的字段才可以创建全文索引,比如char、varchar、text.
```

## 二、索引存储模型

### 1、二分查找

```
有序数组的等值查询和比较查询效率非常高,但是更新数据的时候会出现一个问题可能要挪动大量的数据(改变index),所以只适合存储静态的数据。

为了支持频繁的修改,比如插入数据,我们需要采用链表。

链表的话,如果是单链表,它的查找效率还是不够高。
```

### 2、二叉查找树

```
二叉查找树的特点是什么?

左子树所有的节点都小于父节点,右子树所有的节点都大于父节点。投影到平面以后,就是一个有序的线性表。

二叉查找树既能够实现快速查找,又能够实现快速插入。

但是二叉查找树有一个问题:
就是它的查找耗时是和这棵树的深度相关的,在最坏的情况下时间复杂度会退化成O(n)。
```

### 3、平衡二叉树-AVL

```
平衡二叉树的定义:左右子树深度差绝对值不能超过1。

左旋--右旋

不足：
当我们用树的结构来存储索引的时候,访问一个节点就要跟磁盘之间发生一次IO操作。InnoDB操作磁盘的最小的单位是一页(或者叫一个磁盘块),大小是16K(16384字节)。

如果我们一个节点只存一个键值+数据+引用,例如整形的字段,可能只用了十几个
或者几十个字节,它远远达不到16K的容量。

我们基于索引查找数据的时候,肯定是希望一次从磁盘加载很多的数据到内存中进行比较,这样就可以尽快拿到完整的数据。
如果一个节点只存1个这样的单元,就需要读更多的节点,发生更多的I/O操作。
交互次数越多,消耗的时间就越多。

怎么解决：
第一个就是让每个节点存储更多的数据。
第二个,节点上的关键字的数量越多,我们的指针数也越多,也就是意味着可以有
更多的分叉(我们把它叫做“路数”)
因为分叉数越多,树的深度就会减少(根节点是0)。
这样,我们的树是不是从原来的高瘦高瘦的样子,变成了矮胖矮胖的样子。
```

### 4、多路平衡查找树-B Tree

```
跟AVL树一样,B树在枝节点和叶子节点存储键值、数据地址、节点引用

它有一个特点:分叉数(路数)永远比关键字数多1。

不足：
在更新索引的时候会有大量的索引结构的调整,所以解释了为什么我们不要在频繁更新的列上建索引,或者为什么不要更新主键。

节点的分裂和合并,其实就是InnoDB页的分裂和合并。

如果索引键值有序,写满一页接着开辟一个新的页

如果索引键值无序,存储过程造成大量磁盘碎片,带来频繁的page分裂和合并。
```

### 5、B+树

```
MySQL中的B+Tree有几个特点:

1、它的关键字的数量是跟路数相等的;

2、B+Tree的根节点和枝节点中都不会存储数据,只有叶子节点才存储数据。
存放的数据是完整记录的地址。

3、B+Tre的每个叶子节点增加了一个指向相邻叶子节点的指针,它的最后一个
数据会指向下一个叶子节点的第一个数据,形成了一个有序链表的结构。

InnoDB中的B+Tree特性带来的优势:

1)它是B Tree的变种,B Tree能解决的问题,它都能解决。B Tree解决的两大问题：(每个节点存储更多关键字 ; 路数更多)

2)扫库、扫表能力更强(如果我们要对表进行全表扫描,只需要遍历叶子节点就可以了,不需要遍历整棵B+Tree拿到所有的数据)

3)B+Tree的磁盘读写能力相对于B Tree来说更强(根节点和枝节点不保存数据区,所以一个节点可以保存更多的关键字,一次磁盘加载的关键字更多)

4)排序能力更强(因为叶子节点上有下一个数据区的指针,数据形成了链表)

5)效率更加稳定(B+Tee永远是在叶子节点拿到数据,所以IO次数是稳定的)
```

### 6、为什么不用红黑树

```
红黑树也是BST树,但是不是严格平衡的,通过变色和旋转来保持平衡。

必须满足5个约束:
1、节点分为红色或者黑色。
2、根节点必须是黑色的。
3、叶子节点都是黑色的NULL节点。
4、红色节点的两个子节点都是黑色(不允许两个相邻的红色节点)。
5、从任意节点出发,到其每个叶子节点的路径中包含相同数量的黑色节点。

==》从根节点到叶子结点的最长路径不大于最短路径的2倍。
```

### 7、哈希索引

```
第一,它的时间复杂度是O(1),查询速度比较快。因为哈希索引里面的数据不是
按顺序存储的,所以不能用于排序。

第二,我们在查询数据的时候要根据键值计算哈希码,所以它只能支持等值查询
(=IN),不支持范围查询(><>=<=between and)

第三,如果字段重复值很多的时候,会出现大量的哈希冲突(采用拉链法解决),效率会降低。

需要注意的是,在InnoDB中,不能显式地创建一个哈希索引(所谓的支持哈希索
引指的是AHl,自适应哈希,它是InnoDB自动为buffer pool中的热点页创建的索引)。

memory存储引擎可以使用Hash索引。
```

## 三、MyISAM

```
两个文件: .MYD(数据文件)  .MYI(索引文件)

MyISAM的B+Tree里面,叶子节点存储的是数据文件对应的磁盘地址。从索引文件.MYI中找到键值后,会到数据文件.MYD中获取相应的数据记录。
```

## 四、InnoDB

```
在InnoDB的某个索引的叶子节点上,它直接存储了我们的数据。

聚集索引(聚簇索引)
就是索引键值的逻辑顺序跟表数据行的物理存储顺序是一致的。

InnoDB组织数据的方式就是(聚集)索引组织表(clustered index organize table)。

如果说一张表创建了主键索引,那么这个主键索引就是聚集索引,决定数据行的物理存储顺序。

InnoDB中,主键索引和辅助索引是有一个主次之分的。如果有主键索引,那么主键索引就是聚集索引,其他的索引统一叫做"二级索引"(secondary index)。

二级索引存储的是二级索引的键值,它的键值逻辑顺序跟物理行的顺序不一致,
而二级索引的叶子节点存的是这条记录对应的主键的值。

二级索引检索数据的流程是:

当我们用name索引查询一条记录,它会在二级索引的叶子节点找name=xxxx,拿到主键值,也就是id=xx,然后再到主键索引的叶子节点拿到数据。

为什么不存地址而是存键值?因为地址会变化。

没有主键：

1、如果我们定义了主键(PRIMARY KEY),那么InnoDB会选择主键作为聚集索引。
2、如果没有显式定义主键,则InnoDB会选择第一个不包含有NULL值的唯一索引
作为主键索引。
3、如果也没有这样的唯一索引,则InnoDB会选择内置6字节长的ROWID作为隐
藏的聚集索引,它会随着行记录的写入而主键递增。
```

## 五、索引使用

### 1、离散度

```
简单来说,如果列的重复值越多,离散度就越低,重复值越少,离散度就越高。

不建议大家在离散度低的字段上建立索引
```

### 2、联合索引最左匹配

```
在建立联合索引的时候,一定要把最常用的列放在最左边。

如果我们创建三个字段的索引index(a,b,c),相当于创建三个索引:
index(a)
index(a,b)
index(a,b,c)
```

### 3、覆盖索引

```
回表:

非主键索引,先通过索引找到主键索引的键值,再通过主键值查出索引里面没
有的数据,它比基于主键索引的查询多扫描了一棵索引树,这个过程就叫回表。

在二级索引里面,不管是单列索引还是联合索引,如果select的数据列只用从索引
中就能够取得,不必从数据区中读取,这时候使用的索引就叫做覆盖索引,这样就避免了回表。
```

### 4、索引条件下推（ICP）

```
ICP的目标是减少访问表的完整行的读数量从而减少I/O操作。

这里说的下推,意思是把过滤的动作在存储引擎做完,而不需要到Server层过滤

select * from employees where last_name='wang'and first_name LIKE'%zi';

当你把%加在前面的时候,是不能基于索引去比较的,所以只有last name(姓)这个字段能够用于索引比较和过滤。

查询过程:
1)根据联合索引查出所有姓wang的二级索引数据
2)回表,到主键索引上查询全部符合条件的数据
3)把这些数据返回给Server层,在Server层过滤出名字以zi结尾的员工。

这时候,如果满足last_name='wang'的记录有10万条,就会有99999条没有必
要读取的记录。
所以,根据first_name字段过滤的动作,能不能在存储引擎层完成呢?

这是第二种查询方法:
1)根据联合索引查出所有姓wang的二级索引数据
2)然后从二级索引中筛选出first_name以zi结尾的索引
3)然后再回表,到主键索引上查询全部符合条件的数据(1条数据),返回给Server
层。

这就是ICP,默认开启的,针对于二级索引,只要能够把条件下推给存储引擎,它
就会下推,不需要我们干预...
```

## 六、创建规则

```
1、在用于where判断,order排序 和join的(on)、group by的字段上创建索

2、索引的个数不要过多。(浪费空间,更新变慢)

3、过长的字段,建立前缀索引。

4、区分度低的字段,不要建索引。(离散度太低,导致扫描行数过多)

5、频繁更新的值,不要作为主键或者索引。(页分裂)

6、随机无序的值,不建议作为索引,例如身份证、UUD。(无序,分裂)

7、组合索引把散列性高(区分度高)的值放在前面

8、创建复合索引,而不是修改单列索引
```

## 七、用不到索引的情况

```
1、索引列上使用函数(replace\SUBSTR\CONCAT\sum count avg)、表达式
计算(+-*);

2、字符串不加引号,出现隐式转换;

3、like条件前面带%

4、负向查询
	NOT LIKE     !=     NOT IN
```

Anton/Road to Advancement

简介

发行版

贡献者

语言

近期动态

Anton/Road to Advancement .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

语言

近期动态

搜索帮助

Anton/Road to Advancement