MySQL索引深入剖析学习笔记

一、索引是什么

1,索引图解

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


索引

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


创建索引

在InnoDB中,索引有三种,普通索引、唯一索引(主键索引是特殊的唯一索引)、全文索引。
  • 普通(Normal):也叫非唯一索引,是普通的索引,没有任何限制。
  • 唯一(Unique):唯一索引要求键值不能重复,主健索引是一种特殊的唯一索引,它多了一个限制条件,要求健值不能为空。主健索引用primay key创建。
  • 全文(Fulltext):针对比较大的数据,比如存放消息内容、文章,有几KB数据的情况下要解决like查询在全文匹配效率低的问题,可以创建全文索引。只有文本类型的字段才能创建全文索引,比如char、varchar、text。
create table 'fulltext_test'(
    'content' varchar(50) default null,
    fulltext key 'content'('content')
);

语法:

select * from fulltext_test where match(content) against('简书' in natural language mode);

MyISAM和InnoDB支持全文索引。

二,索引存储模型

索引的可视化演示:
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

1,二分查找

二分查找,又叫折半查找。如果数据经过排序的话,这种方式效率比较高。可考虑使用有序数组作为索引的数据结构。
有序数组的等值查询和比较查询效率非常高,但是更新的时候要挪动大量的数据(改变index),只适合存储静态的数据。
为支持频繁的修改,比如插入数据,需要使用链表。链表的话,如果是单链表,查询效率不够高。
支持二分查找的链表,BST(Binary Search Tree)即二叉查找树诞生了。

2,二叉树(BST Binary Search Tree)

二叉查找树的特点:左子树的所有节点都小于父节点,右子数所有节点都大于父节点。投影到平面就是一个有序的线性表。


二叉查找树

二叉查找树既能实现快速查找,又能实现快速插入。它的查找耗时是和树的深度有关,在最坏的情况下会退化成O(n),此时变成了链表,又称斜树。


斜树

左右子树深度差太大,不平衡。有没有左右子树深度相差不那么大,更加平衡的树呢?
这就是平衡二叉树,叫做Balanced binary serach tress,或者AVL树。
3,平衡二叉对(AVL Tree)(左旋、右旋)

平衡二叉树,AVL Trees(Balanced binary search trees):左右子树的深度差绝对值不超过1。


左旋

右旋

在平衡二叉树中,一个节点,它的大小是固定的单位,作为索引应该存储什么内容?
索引要存你建立索引的字段的值,叫做健值,比如id的值,还要完整记录在磁盘上的地址。由于AVL树是二叉树,还要存储左右子树的指针。


AVL树的存储

AVL树存储索引数据,索引的数据,是放在硬盘上的。查看数据和索引的大小。

select concat(round(sum(data_length/1024/1024),2),'MB') as data_len,
concat(round(sum(index_length/1024/1024),2),'MB') as index_len
from information_schema.tables
where table.schema='dbname' and table_name='tablename';

当用树的结构来存储索引的时候,访问一个节点要跟磁盘发生一次IO操作。InnoDB操作磁盘的最小单位是一页,大小是16KB。如果一个节点只存一个健值+数据地址+引用,可能只用十几个字节或者几十个字节,远不到16KB的容量,如果一个节点只存1个这样的数据,就需要读更多的节点,发生更多的I/O操作。
要解决这个问题,1,让每个节点存储更多的数据。2,节点上的关键字的数量越多,指针也越多,意味着有更多的分叉。分叉越多,树的深度会减少。这时的树不再是二叉树,而是多路。

4,多路平衡查找树(B Tree) (分裂、合并)

Balanced Tree,即多路平衡查找树,叫做B Tree。
跟AVL树一样,B树在枝节点和叶子节点存储健值、数据地址、节点引用。
分叉数永远比关键字数多1.


B Tree

B Tree是怎么实现一个节点存储多个关键字的,还保持平衡的呢?和AVL有什么区别?


B Tree的分裂

如果执行节点的删除,会执行合并的操作。这里的分裂和合并和AVL的左旋和右旋是不一样的。
在更新索引的时候,会有大量的索引的结构的调整,所以不要在频繁更新的列上建索引,或者不要更新主健。
节点的分裂和合并,其实就是InnoDB页的分裂和合并。
如果索引无序,存储过程造成大量的磁盘碎片,带来频繁的page的分裂和合并。
5,B+树(加强版多路平衡查找树)
InnoDB中B+树的存储结构

MySQL中B+Tree的特点:
1,它的关键字的数量是跟路数相等的。
2,B+ Tree的根节点和枝节点中都不会存储数据,只有叶子节点才存储数据。
3,B+ Tree的每个叶子节点增加了一个指向相邻叶子节点的指针,它的最后一个数据会指向下一个叶子节点的第一个数据,形成一个有序链表的结构。

B+ Tree的数据搜寻过程:
1,在根节点找到键值,由于不是叶子节点,在继续往下搜寻,直到在叶子节点上找到数据。
2,如果是范围查询,当找到一个数据后,只需要顺着节点和指针顺序就可以一次性访问到所有的数据节点,极大地提高了区间查询效率。
InnoDB中的B+ Tree的优势:
1,它是B Tree的变种,B Tree能解决的问题,它都能解决。B Tree解决的问题(每个节点存储更多的关键字;路数更多)
2,扫库、扫表能力更强(如果要进行全表扫描,只需要遍历叶子节点就可以了,不需要遍历整棵B+ Tree拿到所有的数据)
3,B+ Tree的磁盘读写能力相对于B Tree更强(根节点和枝节点不保存数据,所以一个节点可以保存更多的关键字,一次磁盘加载的关键字更多)
4,排序能力更强(叶子节点上有下一个数据区的指针,数据形成了链表)
5,效率更加稳定(B+ Tree永远在叶子节点拿到数据,所以IO次数是稳定的)
一张千万级的表,查询数据只需要访问3次磁盘。InnoDB中B+ Tree的深度一般为1-3层。

6,为什么不用红黑树

红黑树也是BST树,但不是严格平衡的,通过变色和旋转来保持平衡。
满足5个约束:

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


    红黑树

可推导出,从根节点到叶子节点的最长路径(红黑相间的路径)不大于最短路径(全是黑色节点)的2倍。
为什么不用红黑树? 1,只有两路; 2,不够平衡。
红黑树一般放在内存中使用。如Java的TreeMap,可以实现一致性哈希。

7,索引方式:真的用的B+ Tree吗?

navicat工具中,创建索引,索引方式有两种。
Hash: 以KV的形式检索数据,会根据索引字段生成哈希码和指针,指针指向数据


哈希索引

哈希索引的特点:
1,时间复杂度为O(1),查询速度比较快。哈希索引不是按顺序存储的,不能用于排序。
2,查询时根据键值计算哈希码,只支持等值查询(= in),不支持范围查询(> < >= between and)。
3,字段重复比较多的时候,会有大量的哈希冲突,效率会降低。

在InnoDB中,不能显式地创建一个哈希索引(所谓的支持哈希索引指的是AHI,自适应哈希,它是InnoDB自动为buffer pool中的热点页创建的索引)。memory存储引擎可以使用Hash索引。

三、B+ Tree的落地形式

1,MySQL架构
MySQL是一个支持插件式存储引擎的数据结构。在MySQL中每个表在创建的时候都能指定它所使用的存储引擎。
2,MySQL数据存储文件
MySQL的数据都是文件的形式存放在磁盘中的,查看数据目录的地址:

show variables like 'datadir';

每个数据库有一个目录,有一个自己的文件夹。每个表有一些跟表名对应的文件。InnoDB的表有两个文件(.frm和.ibd),MyISAM的表有三个文件(.frm、.MYD、.MYI)。.frm是MySQL里表结构定义的文件。

MyISAM

一个是.MYD文件,D代表Data,是MyISAM的数据文件,存放数据记录。
一个是.MYI文件,I代表Index,是MyISAM的索引文件,存放索引,比如在id上创建一个主键索引,主健索引就在这个索引文件中。一个索引会有一个B+ Tree。所有的B+ Tree都在myi文件里面。
在MyISAM里,索引和数据是两个独立的文件。
怎么根据索引找到数据?
MyISAM的B+ Tree里面,叶子节点存储的是数据文件对应的磁盘地址。所以从索引文件.MYI中找到健值后,会到数据文件.MYD中获取对应的数据记录。


MyISAM索引
InnoDB

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


InnoDB索引

一张InnoDB表可能有多个索引,数据肯定只有一份,数据在哪个索引的叶子节点上呢?
聚集索引,就是索引键值和逻辑顺序跟表数据行的物理存储顺序是一致的。InnoDB组织数据的方式就是聚集索引组织表(clustered index organize table)。如果一张表创建了主健索引,那主健索引就是聚集索引,决定数据行的物理存储顺序。
主建索引之外的索引,不会在叶子节点上存放完整的记录。


二级索引

InnoDB中,主健索引和辅助索引有主次之分。如果有主健索引,那么主健索引就是聚集索引。其它索引统一叫做“二级索引”(secondary idnex)。
二级索引存储的是二级索引的健值,二级索引的叶子节点存的是这条记录对应的主健的值。

二级索引检索流程:在二级索引的叶子节点上拿到主健值,然后再到主健索引的叶子节点拿到数据。不存地址而存健值 ,是因为地址会变化。
如果表没有主健怎么办?完整记录放在哪个叶子节点?或者表根本没有索引,数据放在哪?
1,如果我们定义了主健(primary key),那么InnoDB会选择主健作为聚集索引。
2,如果没有显示主健,则InnoDB会选择第一个不包含有NULL值的唯一索引作为主健索引
3,如果也没有唯一索引,则InnoDB会选择内置6字节长的ROWID作为隐藏的聚集索引,它会随着行记录的写入而主健递增。

四,索引的使用原则

索引使用误区:索引越多越好。

1,列的离散度

列的离散度的公式: count(distinct(column_name)):count(*),列的全部不同值和所有数据行的比例。数据行相同的情况下,分子越大,离散度越高。如果列的重复值越多,离散度就越低,重复值越少,离散度就越高。不建议在离散度低的字段上建立索引。如果在B+ Tree里面的重复值太多,MySQL的优化器发现走索引跟使用全表扫描差不多的时候,就算建了索引,也不一定会走索引。

2,联合索引最左匹配

联合索引在B+ Tree中是复合的数据结构,它是按照从左到右的顺序来建立搜索树的。在建立联合索引的时候,把最常用的列放在最左边。使用右边的字段,无法使用索引。
比如创建三个字段的索引index(a,b,c),相当于创建了三个索引:
index(a), index(a,b), index(a,b,c)。

3,覆盖索引

回表:非主健索引,我们先通过索引找到主健索引的健值,再通过主健值查出索引里面没有的数据,它比主健索引的查询多描述了一颗索引树,这个过程就叫回表。


回表

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

-- 创建联合索引
ALERT TABLE USER DROP INDEX cominx_name_phone;
ALERT TABLE USER add INDEX 'cominx_name_phone'('name','phone');
覆盖索引

这三个查询语句属于覆盖索引:

EXPLAIN select name,phone from user where name ='简书' and phone='13000000000';
EXPLAIN select name from user where name ='简书' and phone='130000000';
EXPLAIN select phone from user where name ='简书' and phone='130000000';

select *,不是覆盖索引。如果改成只用where phone= 查询呢,按之前的分析是使用不到索引的,实际上可以用到覆盖索引,优化器觉得用索引更快,还是用到了索引。
覆盖索引减少了IO次数,减少了数据的访问量,可以大大地提升查询效率。

4,索引条件下推(ICP)

索引条件下推(Index Condition Pushdown),5.6以后完善的功能。只适合用于二级索引。ICP的目标是减少访问表完整行的读数据从而减少I/O操作。
这里说的下推,意思是把过滤的动作在存储引擎做完,而不需要到Server层过滤。
比如查询:

select * from employees whrere last_name = 'wang' and first_name like '%zi';

因为字符是从左往右排序的,当把%放在前面的时候,是不能基于索引去比较的,只有last_name这个字段能够用于索引比较和过滤。
查询过程是这样的:
1,根据联合索引查出所有的姓的二级索引数据。
2,回表,到主健索引上查询全部符合条件的数据
3,把这几条数据返回给server层,在server层过滤出名字以zi结尾的员工。


索引条件下推

索引的比较是在存储引擎进行的,数据记录的比较,是在server层进行的。当条件不能用于索引过滤时,server层不会把条件传递给存储引擎,所以取了没有必要的记录。
所以过滤动作能不能在存储引擎完成呢?
1,根据索引查出所有姓的二级索引数据。
2,然后从二级索引中筛选出以zi结尾的索引
3,然后回表,到主健索引上查询符合条件的数据,返回给server


索引条件下推

ICP默认是开启的,也就是针对二级索引,只要能够把条件下推给存储引擎,就会下推,不需要我们干预:
set optimizer_switch='index_condition_pushdown=on';

此时的执行计划,using index condition:


索引条件下推

关闭ICP:

set optimizer_switch='index_condition_pushdown=off';

查看参数:

show variable like 'optimizer_switch';

执行sql,using where:


Using where

Using where 代表从存储引擎取回的数据不全部满足条件,需要在server层过滤。

五,索引的创建和使用

1,索引的创建
  • 在用于where 判断 order 排序和join 的 on,group by 的字段上创建索引
  • 索引的个数不要过多---浪费空间,更新变慢
  • 过长的字段,建立前缀索引
create table 'pre_test'(
  'content' varchar(20) default null,
   key 'pre_idx'('conent'(6))
) engine = innodb defualut charset=utf8m4;
  • 区分度低的字段,不要建索引---离散度太低,扫描的行数过多
  • 频繁更新的值,不要作为主健或索引----页分裂
  • 随机无序的值,不建议作为索引,如身份证、UUID---无序、分裂
  • 组合索引把散列性高的值放在前面
  • 创建复合索引,而不是修改单列索引
2,什么时候用不到索引
  • 索引列表上使用函数(replace,substr,concat, sum,count,avg),表达式,计算(+ - * /)
  • 字符串不加引号,出现隐式转换
  • like 条件前面带 %
  • 负向查询, not like 不能, !- <> 和not in 在某些情况下可以。

用不用索引,最终都是优化器说了算。优化器是基于什么的优化器?
基于cost开销(Cost Base Optimizer),它不是基于规则(Rule-Based Optimizer),也不是基于语义。怎么开销小怎么来。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,552评论 5 474
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,666评论 2 377
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,519评论 0 334
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,180评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,205评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,344评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,781评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,449评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,635评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,467评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,515评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,217评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,775评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,851评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,084评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,637评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,204评论 2 341

推荐阅读更多精彩内容