vlambda博客
学习文章列表

Mysql 索引底层原理

Mysql 索引

一. 索引的简介

  • 索引是数据库中为了加快数据库的查询速度, 另外开一个空间创建一个类似"书本目录"的结构.
  • 索引也是直接存在磁盘文件中, 因为他的体积也不小

Mysql 索引底层原理

1. 优势劣势

优势

  • 提高检索效率, 降低IO次数
  • 可以利用索引类对数据进行先排序, 提高order 操作的性能

劣势

  • 索引是需要占用空间的
  • 索引每次表数据更新的同时, 也要同步更新索引. 所以增删改操作频繁的表不适合创建索引

二. 使用方法

1. 索引的分类

  • 主键索引: 主键自动创建的唯一不为空索引 ALTER TABEL table_name ADD PRIMARY KEY (column_name);

  • 普通索引: Mysql的基本索引类型, 没有限制, 可空值可重复

    ALTER TABLE table_name ADD INDEX index_name (column_name) ;

  • 唯一索引：索引列中的值必须是唯一的，但是允许为空值

    CREATE UNIQUE INDEX index_name ON table(column_name) ;

  • 全文索引: 只能用于 CHAR,VARCHAR,TEXT 字段, 专门用于全文检索, 作用于大文本的字段. 替换掉like查询 where name like '大保健' 为 where match(name) against('大保健'); 能有效提高查询速度. 但是目前有很多全文检索中间件, 我们可以使用专业的工具lucene,es，solr , 减少对数据库的压力

  • 空间索引: 是一种支持OpenGIS几何数据模型. 的空间索引, 本文不多做介绍

  • 前缀索引: 在文本类型中, 可以指定索引列的长度

    ALTER TABLE table_name ADD INDEX index_name (column1(length));

2. 删除索引

DROP INDEX index_name ON table


三. 索引的数据结构

Mysql 索引底层原理

以下演示动图的来自 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Mysql 在读取磁盘文件时, 一次性读取一页数据, 一页数据为16k, 所以假设要把所有表数据读取到内存中将会产生多次IO操作, 这将是致命的

为了合理的减少IO次数, 我们采用树结构来帮助我们快速检索.

1. B 树

B树是一种多叉平衡查找树

  1. B树的节点中存储着多个元素，每个内节点有多个分叉。
  2. 节点中的元素包含键值和数据，节点中的键值从大到小排列。也就是说，在所有的节点都储存数 据。
  3. 父节点当中的元素不会出现在子节点中。
  4. 所有的叶子结点都位于同一层，叶节点具有相同的深度，叶节点之间没有指针连接。

B树 增删改

  • B树的插入


    Mysql 索引底层原理

  • B树移除

    Mysql 索引底层原理

  • B树查找和遍历

    Mysql 索引底层原理

B树结构来存储索引结构

Mysql 索引底层原理


例: 查找值为15的data

  1. 第一次IO 读取磁盘块1,在内存中从头遍历比较, 比较得知 15<17 , 则获取p1的指针
  2. 第二次IO 读取磁盘块2,在内存中从头遍历比较, 比较得知 15>12 , 则获取p3的 指针
  3. 第三次IO 读取磁盘块7,在内存中从头遍历比较, 取得15 = 15 获得data块

遍历大于15

  1. 查找值15: 三次IO, 遍历磁盘块7中比15大的值
  2. 磁盘块7遍历完了, 网上跳回 磁盘块2 , 从指针p3的右边开始遍历 -> 无
  3. 磁盘块2遍历完了, 网上跳回 磁盘块1 , 从指针p1的右边开始遍历 -> 17 -> p2
  4. 往下跳到磁盘块3
  5. ........ 具体过错看 B数查找和遍历

B树缺点:

  • 每个节点都有存储data数据, 假设data数据过大, 会导致每个节点能存储的度(度 = 索引), 使得树会很快长高.
  • 遍历或者或者范围查询将会很慢, 因为每次都要往上回跳遍历

2. B+ 树

在B树基础上，MySQL在B树的基础上改造，使用B+树构建索引

B树：非叶子节点和叶子节点都会存储数据

B+树：只有叶子节点才会存储数据，非叶子节点只存储键值, 最底层叶子节点包含所有索引项。叶子节点之间使用双向指针连接，最底层的叶 子节点形成了一个双向有序链表

B+树 增删改

  • B+树的插入


    Mysql 索引底层原理

  • B+树的移除



    Mysql 索引底层原理

  • B+树的查找和遍历

    Mysql 索引底层原理
    B+树结构来存储索引结构

Mysql 索引底层原理


查询: 查找值为15的data (查询和B树相同)

  1. 第一次IO 读取磁盘块1,在内存中从头遍历比较, 比较得知 15<17 , 则获取p1的指针
  2. 第二次IO 读取磁盘块2,在内存中从头遍历比较, 比较得知 15>12 , 则获取p 3的 指针
  3. 第三次IO 读取磁盘块7,在内存中从头遍历比较, 取得15 = 15 获得data块

遍历: 大于15

  1. 查找值15: 三次IO, 遍历磁盘块7中比15大的值
  2. 查找到15之后，底层的叶子节点是一个有序列表，我们从磁盘块5，键值15开始向后遍历筛选所有 符合筛选条件的数据。15 -> 磁盘块6 (17 -> 26) ->磁盘快7(....) -> .....

B+树结构解决遍历问题

由于最底层是一个有序的链表, 所以不需要向上跳回上个节点, 直接根据链表的下一块磁盘块进行查询即可.

四. Mysql对B+数索引的实现

Mysql 索引底层原理

引用以t_user_myisam为例，来说明。t_user_myisam的id列为主键，age列为普通索引。

CREATE TABLE `t_user_myisam` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`username` varchar(20) DEFAULT NULL,
`age` int(11) DEFAULT NULL,
PRIMARY KEY (`id`) USING BTREE,
KEY `idx_age` (`age`) USING BTREE
) ENGINE=MyISAM AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;
Mysql 索引底层原理

1.MyISAM索引

  1. 主键索引

MyISAM 将数据文件和索引文件分开存储
MyISAM 的B+ 树叶子节点 key: 存储的是索引值, value:存储数据的位置

Mysql 索引底层原理

表t_user_myisam的索引存储在索引文件t_user_myisam.MYI中，数据文件存储在数据文件 t_user_myisam.MYD中。

  1. 辅助索引

只是主键索引的键值是唯一的，而辅助索引的键值可以重复。

查询数据时，由于辅助索引的键值不唯一，可能存在多个拥有相同的记录，所以即使是等值查询，也 需要按照范围查询的方式在辅助索引树中检索数据。

2. InnoDB索引

每个InnoDB表都有一个聚簇索引 ，聚簇索引使用B+树构建，叶子节点存储的数据是整行记录。

一般情况下，聚簇索引等同于主键索引，当一个表没有创建主键索引时，InnoDB会自动创建一个ROWID字 段来构建聚簇索引。

InnoDB创建索引的具体规则如下：

  1. 在表上定义主键PRIMARY KEY，InnoDB将主键索引用作聚簇索引。
  2. 如果表没有定义主键，InnoDB会选择第一个不为NULL的唯一索引列用作聚簇索引。
  3. 如果以上两个都没有，InnoDB 会使用一个6 字节长整型的隐式字段 ROWID字段构建聚簇索 引。该ROWID字段会在插入新行时自动递增。

除聚簇索引之外的所有索引都称为辅助索引。

在中InnoDB，辅助索引中的叶子节点存储的数据是该行的主键值。在检索时，InnoDB使用此主键值在聚簇索引中搜索行记录。

主键索引的叶子节点会存储数据行，辅助索引只会存储主键值,  下面我们一起来看一看这两种索引的实现。

1. 主键索引

主键索引的叶子节点会存储整行数据，辅助索引只会存储主键值。所以主键索引不用再去磁盘中获取数据，所以聚簇索引通常可以节省磁盘IO操作。Mysql 索引底层原理

2. 辅助索引

3. 组合索引

创建了一个联合索引idx_abc(a,b,c)，构建的B+树索引结构。

Mysql 索引底层原理

索引树中节点中的索引项按照（a，b，c）的顺序从大到小排列 先按照a列排序，a列相同时按照 b列排序，b列相同按照c列排序。在最底端的叶子节点中，如果两个索引项的a，b，c三列都相同，索引项按照主键id排序。

例如:  where a=13 and b=16 and c=4 条件

  1. 先搜寻第一个索引 a , 拿到第二行第一个节点
  2. 当 a值匹配相等时 , 匹配第二个索引B, 此时索引B是顺序链表, 此时就需要取出所有的链表逐个比较
  3. 逐个比较链表中的值, 直到搜到符合条件的数据获得主键id, 回表查询(根据在辅助索引树中获取的主键id，到主键索引树检索数据的过程称为回表查询)
Mysql 索引底层原理

4.最左前缀匹配原则

从索引的结构不难看出, 索引的使用条件还是比较苛刻的, 必须按照先比较a->再比较b->再比较c的顺序 所以where 条件 必须满足  a 或 ab 或 abc 方能使用到索引

同时: 使用组合索引查询时，mysql会一直向右匹配直至遇到范围查询(>、 <、between、like)就停止匹配。Mysql优化器也会将书写的where条件按照abc的顺序进行优化

5. 组合索引创建原则

  1. 频繁出现在where order by和group by条件中的列，建议创建组合索引。注意: order by a,b 需要组合索引列顺序（a,b）。如果索引的顺序是（b,a），是用不到索引的。

  2. 常出现在select语句中的列，也建议创建组合索引, 可以直接从索引表中直接返回数据, 而不需要回表查询 覆盖索引:

    select a,b,c from t_multiple_index where a=13 and b=16;

    select中列数据，如果可以直接在辅助索引树上全部获取，也就是说索引树已经“覆盖”了我们的查询，这时MySQL就不会白费力气的回表查询，这种现象就是覆盖索引。
    使用explain工具查看执行计划，可以看到extra中“Using index”，代表使用了覆盖索引。

6. 索引条件下推ICP:

Index Condition Pushdown,简称ICP。是MySQL5.7对使用索引从表中检索行的一种优化。可以通过参数optimizer_switch控制ICP的开始和关闭。

ICP的目的是为了减少回表次数，可用于 InnoDB 和 MyISAM 表，对于InnoDB表ICP仅作用于辅助索引。

  • 假设不使用ICP:

例子: select * from t_multiple_index where a=13 and b>=15 and c=5 and d='pdf';

  • 当到达 a=13 and b>=15 条件时, 查询出多条索引值, 再逐条回表查询比

    剩下的c=5 d='pdf'不满足最左前缀的索引条件的比较是在存储引擎层进行的，非索引条件的比较是在Server层进行的。

  • 使用ICP:

    当到达 a=13 and b>=15 条件时, 查询出多条索引值, 再逐条ICP下推比较c=5,满足条件才回表比较剩下的d='pdf'

    所有的索引条件的比较是在存储引擎层进行的，非索引条件的比较是在Server层进行的。

五. 索引创建原则

  • 何时创建索引?

  1. 频繁出现在where 条件判断，order排序，group by分组字段

  2. select 频繁查询的列，考虑是否需要创建联合索引（覆盖索引，不回表）

  3. 多表join关联查询，on字段两边的字段都要创建索引

  • 创建时需注意

  1. 表记录很少不需创建索引 （索引是要有存储的开销）

  2. 一个表的索引个数不能过多。
    （1）空间：浪费空间。每个索引都是一个索引树，占据大量的磁盘空间。（2）时间：更新（插入/Delete/Update）需要维护索引数 查询select时也会增加优化器的选择索引的时间

  3. 区分度低的字段，不要建索引。例如: 男:1 女:2

  4. 在InnoDB存储引擎中，主键索引建议使用自增的长整型，避免使用很长的字段。

  5. 不建议用无序的值作为索引。例如身份证、UUID

  6. 尽量创建组合索引，而不是单列索引。

  7. 字符串太长时，保证区分度的情况下，可以使用前缀索引。


  • 索引失效情况分析

  1. like模糊匹配 （‘%字符串’）时 索引失效

  2. 索引字段是字符串时, 字符串要加单引号  phone = '1358888888'

  3. 遇上范围条件（bettween、<、>、in等）后, 右边条件索引将失效

  4. 不等（！= 或者 < >）判断时，会导致索引失效而转向全表扫描

  5. is null / is not null 判断时，会导致索引失效而转向全表扫描

  6. or 时，会导致索引失效而转向全表扫描

  7. 不要在索引上做计算


推荐阅读

[5.05] 暗喻幻想港中35周年限定版1.03+DLC+金手指+王中王存档 [5.05] 暗喻幻想港中35周年限定版1.03+DLC+金手指+王中王存档
使用rpm包安装MySQL5.7数据库 使用rpm包安装MySQL5.7数据库

相关文章