数据查找

  1. 在没有索引的情况下查找记录(查询条件为非主键),mysql会从第一个数据页开始遍历,直到找到相应的记录为止,这个过程时间复杂度是o(n),当数据量是亿级时,会非常的损耗性能。
  2. 在这里不止是遍历数据页,数据页中还有槽(记录的地址偏移量),因为普通字段没有记录在槽中,所以还要遍历查找,可想而知是有多损耗性能。
  3. 因为innodb会给主键建聚簇索引,所以普通查找的时候遍历的是B+树。

索引

innodb中的索引方案

我们从第1条记录到第n(+∞)条记录的插入来分析:
前提:

  1. 主键自己生成不采用自增主键
  2. 数据储存级别到页,不讨论行级数据储存(航记录可以看之前博客)
  3. 只考虑主键,不考虑其他列索引
  4. 索引树分层讲解,层级倒序,第一层代表最底层

第一层:

  • 当第一条记录进来的时候会分配一个16kb数据页,然后根据主键大小顺序的储存在数据页中。
  • 如何保证数据的顺序性?
    • 我们先假设有x个页,每个页的记录数为y。
    • x个页的数据都是顺序存储的,但是第x*y+1条数据主键值小于第x*y-1条数据;如果忽略顺序存储,则该条数据(x*y+1)应该存储在第x+1页的第一条,但是为了保证顺序性会将第x*y+1条数据挪到第x*y-1的位置,x*y-1这条记录会挪到x*y的位置,x*y这条记录会挪到第x+1页的第一条记录;这个“挪位置”的过程称之为页分裂;在忽略页的情况下这种数据插入可以跟插入排序类比较

第二层:

  • 索引是什么?
    • 在我们创建好第一层的基础上将底层每个页中的页码和记录的最小主键值抽象为一条记录,类似于我们要储存的记录但是只有两个列,即储存用户记录数据的页码和每页记录最小主键值然后再分配一个页将该条记录插进去,所有这种页中记录头字段的record_type均为1,称为索引页。
  • 索引页和普通数据页的区别?
    • 普通数据页储存用户真实记录,索引页储存数据页页码个最小主键值,其他的都一样。
    • 当数据量比较大的时候,第二层索引页量级也会同比上升,所以这个时候就会出现第三层,同样是将第二层索引页的页码和最小值封装成记录然后将记录插入分配的数据页中,直到最后只有一个数据页为止。这样就形成了一个B+树
  • 实际上如何插入?
    • 前面分析B+树是如何形成的,但是分析思路跟实际操作是相悖的,实际真实数据的插入是从根节点开始的,从第一条记录的诞生开始B+树的根节点就已经确定了,根节点刚开始就是普通的数据页,当数据量大于16kb的时候,会再申请一个数据页将根节点中的数据复制到新申请的数据页中,然后根节点存放新数据页的页码和最小主键值,当数据量增长的时候,数据页会一直分裂,然后直到存储下所有的数据为止。(数据的插入和页分裂思想可以参考二叉树的生成)

索引分类

聚簇索引: 拥有顺序储存用户完整记录的叶子节点且拥有顺序储存索引记录的非叶子节点的B+树称为聚簇索引,数据初始化的时候引擎会自动给我们创建一个聚簇索引

二级索引:二级索引跟聚簇索引的创建同理,但是二级索引的叶子节点储存的是主键的索引列的值(排序字段是以索引列为主),因为索引列的字段有可能不唯一所以,为了方便排序非叶子节点也会储存主键值,索引列值相同的时候就比较主键值得大小

联合索引:当我们创建联合索引的时候会根据我们申明的索引列,进行多列排序,首先会根据最左边的列进行排序,当值相等的时候再根据第二列排序,按照这个规则,当我们使用联合索引去查询记录,如果我们没有按照索引的排序规则查询那么服务器就会遍历索引,我们称之为左前缀原则

myisam中的索引方案

myisam中的索引也是树组成的,但是不同于innodb的是,叶子节点并不储存真实记录而是储存真实记录的主键+行号;
真实记录储存在数据文件中,该文件中储存记录是一行行的,可以通过行号访问到一条记录且储存的记录并没有按照主键排序。

Memory引擎的索引

我们经常会听到hash索引和B+树索引的区别,但是在日常开发中我们经常会使用的是innodb引擎所以基本不怎么接触到hash索引,

  1. 只有Memory引擎显示支持哈希索引。
  2. 这也是Memory引擎表的默认索引类型,Memory引擎同时也支持B-Tree索引。
  3. Memory引擎是支持非唯一哈希索引的。
  4. 如果多个列的哈希值相同,索引会以链表的方式存放多个记录指针到同一个哈希条目中

查询方案

MySQL执行查询语句的方式称之为访问方法或者访问类型

查询方法 描述 拟化复杂度(n为索引值,且常数不能忽略) 特殊情况 查询语句
const 通过主键或者唯一二级索引与常数的等值查找 o(1) 因为唯一二级索引列并不限制 NULL 值的数量,所以可能访问到多条记录,查询方法不能为const select * from table where id/unique_key
ref 通过普通二级索引与常数的等值查找 o(n) key IS NULL这种形式的搜索条件最多只能使用ref的访问方法
对于某个包含多个索引列的二级索引来说,只要是最左边的连续索引列是与常数的等值比较就可能采用ref的访问方法
select * from table where key = value /unique_key is null
ref_or_null 通过普通二级索引等值查询,同时还想查询该列的空值记录 o(3n) 有空值记录所以记录数要乘2 select * from table where key = value or key is null
range 通过聚簇或二级索引和范围数查找 o(2n) select * from table where key in (val1,val2,val3)
index 通过遍历二级索引查找 o(n^2) 假设key2和key3是联合索引idx_key2_key3,因为没有左前缀匹配索引会遍历索引树 select key1_val,key2_val,key3_val from table where key3 = key3_val
all 扫描全表查询 o(n^x) 这里的x代表量级很大 select * from table
索引合并 描述 注意
Intersection 1.二级索引列是等值匹配的情况,对于联合索引来说,在联合索引中的每个列都必须等值匹配,不能出现只匹配部分列的情况
2.主键可以是范围匹配
只有在回表数据量太大的情况下mysql优化器才会进行此次合并
Union 1.二级索引列是等值匹配的情况,对于联合索引来说,在联合索引中的每个列都必须等值匹配,不能出现只出现匹配部分列的情况
2.主键列可以是范围匹配
3.使用Intersection索引合并的搜索条件
查询语句出现or情况下
Sort-Union 按照二级索引记录的主键值进行排序,之后按照Union索引合并方式执行

优化案例分析

案例1:回表次数判断

1
select * from table where key1= val1 and key2 > val2

如果对索引合并的概念模糊不清的话,也许会说当前操作会回表两次,key1和key2索引树各回一次?
答:当前语句只会回表一次,先查找key1索引树匹配到相应id的完整记录,然后再按照条件2过滤掉完整记录。(索引下推)

案例2:索引列和常值匹配索引失效

哪个索引失效?

1
2
select * from table where key1 = val1 and common_field = common_field_val
select * from table where key1 = val1 or common_field = common_field_val

Q1:既然我们知道B+树可以直接在页子节点遍历,那样是不是速度很快?
A1:我们在上一节说过,底层的叶子节点组成的是一个双向链表,链表有什么特点?对,物理空间不连续,所以我们遍历B+树叶子节点的时候,就是在随机IO,可以想象一下性能如何?
Q2:按照A1的回答,那根据主键查范围值是很慢咯?
A2:其实不然,具体情况和mysql表空间有直接关系;mysql会申请一块连续空间叫区,区由64个页组成;为了节省空间B+树的叶子节点和非叶子节点是放在不同区中的,将存放叶子节点和非叶子节点的区的集合叫做段。对上述有疑问的话看看第三节的表空间结构可以帮助理解
Q3:mysql中的索引树为啥要用B+树?
A3:通常与B+树相提并论的是B树,为啥不适用B树呢?
首先我们应该了解下B树的特点:多路、每个节点即保存索引也保存数据、搜索相当于二分查找;相比较而言B+树只有叶子节点保存数据,且叶子节点增加了相邻节点的指向指针;至此我们可以知道,B树查找时不用扫描到叶子节点,而B+树需要找到叶子节点,因此B+树更稳定;其次,B+树非叶子节点存放的知识索引,因此可以存放更多数据,使得树深度更小(深度代表的IO次数,深度越大IO次数越多);所以像其他的二叉搜索树就更不用想了,当数据量级上去之后深度增加,IO次数飙升,性能大幅缩水