MySql的索引实现原理

骑猪看日落 2022-12-21 06:11 75阅读 0赞

**目录**

简介

MySQL索引类型

Mysql中索引实现

Mysql索引缺点及使用注意

--------------------

# 简介 #

索引是为MySQL提高获取数据效率的数据结构，为了**快速查询数据**。索引是满足某种特定查找算法的数据结构，而这些数据结构会以某种方式指向数据，从而实现高效查找数据。

MySql从5.5版本开始，表的默认存储引擎从MyISAM换成InnoDB，而索引技术有不同的实现方式，包括：B-树，B+树，R-树以及散列类型。MySQL一般以B+树作为其索引结构。在了解B+树前，我们需要先了解一下B-树。

# MySQL索引类型 #

*  1、B-Tree(B树)

B树是二叉树的升级版，又叫平衡多路查找树。它和平衡二叉树的区别在于：

1.  平衡二叉树最多两个子树，而 B 树每个节点都可以有**多个子树**，M 阶 B 树表示每个节点最多有M个子树。
2.  平衡二叉树每个节点只有一个数据和两个指向孩子的指针，而 B 树每个**中间节点**有 k-1 个关键字（可以理解为数据）和 k 个子树（ k 介于阶数 M 和 M/2 之间，M/2 向上取整）。
3.  所有叶子节点均在同一层、叶子节点除了包含关键字和关键字记录的指针外也有指向其子节点的指针，只不过其指针地址都为 null 。

如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5fMDkxMQ_size_16_color_FFFFFF_t_70][]

*  2、B+Tree（B+树）

B+树数据结构是B-树实现的增强版本。B+树支持B-树索引的所有特性，

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5fMDkxMQ_size_16_color_FFFFFF_t_70 1][]

B+Tree所有叶子结点才有指向数据的指针。非叶子结点就是纯索引数据和主键。每个叶子结点都有指向下一个叶子结点的链接。

*  3、主键索引

主键索引也就是我们说的聚集索引、聚簇索引。基于主键来创建的 B+ 树索引结构，如果没有指定主键，也找不到任何一列不重复的列可以作为主键的情况下，InnoDB 会新增一个隐藏列 RowId 作为主键继而创建聚集索引，另外我推荐自增id而不是uuid，原因是自增id是有序的，新增的数据插入在上一条数据的后面，在数据分页的时候，直接写入新页就好，而uuid是无序的，不能保证大小，随意在插入数据时，也是随机的，在进行数据分页时，需要寻找合适的位置分配新的空间。

*  4、二级索引(非主键索引)

二级索引就是指除了主键索引外的索引。主键索引和所有的二级索引都是各自维护各自的 B+ 树结构，但是有个不同的地方在于，二级索引的叶子节点存储的不是数据，而是主键索引对应的主键值。即二级索引不再保存一份 data 数据，而是去主键索引中查数据。那么对于二级索引查找一条数据索要做的操作就是：

1.  首先在二级索引中找到叶子节点对应的数据主键值；
2.  根据这个主键值去聚集索引中找到真正对应的数据行。

所以这里需要两次 B+ Tree 查找。

*  5、覆盖索引

覆盖索引简单来说就是只查询索引就能获取到数据不必再回表查询，换句话说要查询的列已经被索引列覆盖。

使用覆盖索引有如下优点：

1.  索引项通常比记录要小，所以 MySQL 访问更少的数据；
2.  索引都按值的大小顺序存储，相对于随机访问记录，需要更少的 I/O；
3.  大多数据引擎能更好的缓存索引。比如 MyISAM 只缓存索引;
4.  覆盖索引对于 InnoDB 表尤其有用，因为 InnoDB 使用聚集索引组织数据，如果二级索引中包含查询所需的数据，就不再需要在聚集索引中查找了。
5.  覆盖索引不能是任何索引，只有 B Tree 索引存储相应的值。而且不同的存储引擎实现覆盖索引的方式都不同，并不是所有存储引擎都支持覆盖索引( Memory 和 Falcon 就不支持)。

*  6、联合索引

有的时候我们会对多个列建立一个索引，这种索引被称为联合索引。此时需要满足**左前匹配原则：**

假设我们在字段（name、cid、phone）建立联合索引，

*1. *遇到范围查询 ( > ,<, between, like) 就会停止匹配

>  select \* from test where name = '小红' and cid > '3' and phone='13800001111' ; \# 此时，phone无法使用索引
> 
>  select \* from test where name = '小红' and cid like  '%3' and phone='13800001111' ; \# 此时，cid 、phone无法使用索引,假设cid like  '3%' ，cid 还是可以使用索引的

2. 在索引列上做操作（函数，自定义计算）

不会使用索引

3. 查询条件包含 or

整个查询条件的索引失效

4. 字符串类型的索引字段作为查询条件时一定要用引号括起来，否则索引不生效

B+Tree 索引结构的 key 都是用数字表示的，因为数字比较省空间，就算是字符串格式的字段，最终也会被转为二进制表示。但是对于不加引号的字符串，MSYQL 会自动做一次隐式转换将字符串转为浮点类型，这就导致不匹配。

# Mysql中索引实现 #

1、MyISAM：如下图，叶子结点的data域存放的是数据的地址：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5fMDkxMQ_size_16_color_FFFFFF_t_70 2][]

上图表中共三列数据，col1为主键，表示MyISAM表的主索引示意图，在MyISAM中，主索引和辅助索引（除主键以外的其它索引）在结构上没有任何区别，只是主索引的key是唯一的，辅助索引的key可以重复。

2、InnoDB：对比MyISAM，InnoDB的主键索引与辅助索引存储方式是不同的：

**主键索引**：主键索引的叶子结点存放的是key值和数据，叶子结点载入内存时，数据一起载入，找到叶子结点的key，就找到了数据。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5fMDkxMQ_size_16_color_FFFFFF_t_70 3][]

**辅助索引**：辅助索引的叶子结点存放的是key值和对应的记录的**主键值**，使用辅助索引查询，首先检索辅助索引获取主键，然后用主键在主索引中检索获取记录。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5fMDkxMQ_size_16_color_FFFFFF_t_70 4][]

#  Mysql索引缺点及使用注意 #

创建索引会增加磁盘消耗，在高并发的情况下频繁的插入和修改会导致性能损耗。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5fMDkxMQ_size_16_color_FFFFFF_t_70]: /images/20221120/71a3d7ea63c1480897a1cda2689ebfe4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5fMDkxMQ_size_16_color_FFFFFF_t_70 1]: /images/20221120/09644d98c0814a03b03ac64c47067f0b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5fMDkxMQ_size_16_color_FFFFFF_t_70 2]: /images/20221120/5a2aa77d547449dea9244f950133095a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5fMDkxMQ_size_16_color_FFFFFF_t_70 3]: /images/20221120/4ad4d0b408db4ff1926de12065b40fac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5fMDkxMQ_size_16_color_FFFFFF_t_70 4]: /images/20221120/9c7a389f185049b8a90ddf96119e299a.png