百木园-与人分享,
就是让自己快乐。

MySQL实战45讲 4,5

04 | 深入浅出索引(上)

索引的出现其实就是为了提高数据查询的效率,就像书的目录一样

索引的常见模型

哈希表、有序数组和搜索树

哈希表

image

User2 和 User4 根据身份证号算出来的值都是 N,但没关系,后面还跟了一个链表。

需要注意的是,图中四个 ID_card_n hash 出来的值并不是递增的,这样做的好处是增加新的 User 时速度会很快,只需要往后追加。但缺点是,因为不是有序的,所以哈希索引做区间查询的速度是很慢的,需要全部扫描一遍。

所以,哈希表这种结构适用于只有等值查询的场景,比如 Memcached 及其他一些 NoSQL 引擎。

有序数组

有序数组在等值查询和范围查询场景中的性能就都非常优秀

image

数组就是按照身份证号递增的顺序保存的。这时候如果你要查 ID_card_n2 对应的名字,用二分法就可以快速得到,这个时间复杂度是 O(log(N))

同样可以通过二分找到大于范围和小于范围的两个值

更新数据的时候必须得挪动后面所有的记录,成本太高

有序数组索引只适用于静态存储引擎

二叉树


二叉搜索树:一棵空树,或者是具有下列性质的二叉树:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;二叉搜索树的左、右子树也分别为二叉搜索树。

平衡二叉树:平衡二叉树是在二叉搜索树的基础上引入的,指的是结点的左子树和右子树的深度差不超过 1.

多叉树:每个结点可以有多个子结点,子节点的大小从左到右依次递增。


image

二叉搜索树的特点是:每个节点的左儿子小于父节点,父节点又小于右儿子。这样如果你要查 ID_card_n2 的话,按照图中的搜索顺序就是按照 UserA -> UserC -> UserF -> User2 这个路径得到。这个时间复杂度是 O(log(N))

当然为了维持 O(log(N)) 的查询复杂度,你就需要保持这棵树是平衡二叉树。为了做这个保证,更新的时间复杂度也是 O(log(N))

一棵 100 万节点的平衡二叉树,树高 20。一次查询可能需要访问 20 个数据块

Q:为什么树高20就是20个数据块?

A:每个叶子结点就是一个块,每个块包含两个数据(?),块之间通过链式方式链接。树高20的话,就要遍历20个块。因为是二叉树结构,每次指针查找很大概率是触发随机磁盘读(比如很难刚好碰上一个节点和他的左右儿子刚好相邻)

数据库中的所有数据都存储于数据块中,而叶子节点块只是数据块的一种,因为它位于索引b*tree结构中的最末端(root(根)-->branch(分枝)-->leaf(叶子)),所以,就称为叶子节点块(leaf node block)

《个人理解》参照下面的B+树,一个叶子块中可以存放多条索引和数据

为了让一个查询尽量少地读磁盘,就必须让查询过程访问尽量少的数据块。那么,我们就不应该使用二叉树,而是要使用“N 叉”树。这里,“N 叉”树中的“N”取决于数据块的大小。

Q:B+树是一颗N叉树,N是由什么决定的?能否调整?
A:

  1. 通过修改page的大小来间接调整N的大小。一个节点上的所有数据都在一个page中,页越大,每页存放的索引就越多,N就越大。数据页调整后,如果数据页太小层数会太深,数据页太大,加载到内存的时间和单个数据页查询时间会提高,需要达到平衡才行。

  2. 修改索引的大小。每个索引包括固定字节数的Point指针和索引字段内容,索引字段越小,每页能存的索引就越多,N就越大。

以 InnoDB 的一个整数字段索引为例,这个 N 差不多是 1200。这棵树高是 4 的时候,就可以存 1200 的 3 次方个值,这已经 17 亿了。考虑到树根的数据块总是在内存中的,一个 10 亿行的表上一个整数字段的索引,查找一个值最多只需要访问 3 次磁盘。其实,树的第二层也有很大概率在内存中,那么访问磁盘的平均次数就更少了。

InnoDB 的索引模型

在 InnoDB 中,表都是根据主键顺序以索引的形式存放的,这种存储方式的表称为索引组织表

InnoDB 使用了 B+ 树索引模型,所以数据都是存储在 B+ 树中的。

假设,我们有一个主键列为 ID 的表,表中有字段 k,并且在 k 上有索引。

create table T(
id int primary key, 
k int not null, 
name varchar(16),
index (k))engine=InnoDB;

表中 R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6),两棵树的示例示意图如下。

image

索引类型分为主键索引和非主键索引

主键索引的叶子节点存的是整行数据。在 InnoDB 里,主键索引也被称为聚簇索引(clustered index)。

非主键索引的叶子节点内容是主键的值。在 InnoDB 里,非主键索引也被称为二级索引(secondary index)。

Q:基于主键索引和普通索引的查询有什么区别?

A:

  • 如果语句是 select * from T where ID=500,即主键查询方式,则只需要搜索 ID 这棵 B+ 树
  • 如果语句是 select * from T where k=5,即普通索引查询方式,则需要先搜索 k 索引树,得到 ID 的值为 500,再到 ID 索引树搜索一次。这个过程称为回表

索引维护

B+ 树为了维护索引有序性,在插入新值的时候需要做必要的维护。

以上面这个图为例,

如果插入新的行 ID 值为 700,则只需要在 R5 的记录后面插入一个新记录

如果新插入的 ID 值为 400,就相对麻烦了,需要逻辑上挪动后面的数据,空出位置

而更糟的情况是,如果 R5 所在的数据页已经满了,根据 B+ 树的算法,这时候需要申请一个新的数据页,然后挪动部分数据过去。这个过程称为页分裂

当相邻两个页由于删除了数据,利用率很低之后,会将数据页做合并。

Q:如果插入的数据是在主键树叶子结点的中间,后面的所有页如果都是满的状态,是不是会造成后面的每一页都会去进行页分裂操作,直到最后一个页申请新页移过去最后一个值?

A: 不会不会,只会分裂它要写入的那个页面。每个页面之间是用指针串的,改指针就好了,不需要“后面的全部挪动

ps:数据块和数据页的含义应该是一致的

自增主键

自增主键是指自增列上定义的主键,在建表语句中一般是这么定义的: NOT NULL PRIMARY KEY AUTO_INCREMENT。

好处:(存,查,插)

  • 插入新记录的时候可以不指定 ID 的值,系统会获取当前 ID 最大值加 1 作为下一条记录的 ID 值。每次插入一条新记录,都是追加操作,都不涉及到挪动其他记录,也不会触发叶子节点的分裂
  • 自增字段为整形或长整型,每个非主键索引的叶子节点上都是主键的值,主键长度越小,普通索引的叶子节点就越小,普通索引占用的空间也就越小。
  • 业务逻辑字段不容易保证索引树结点有序插入,这样写入成本较高。

Q:有没有什么场景适合用业务字段直接做主键的呢?

A:典型的 KV 场景

  1. 只有一个索引;

  2. 该索引必须是唯一索引

这时候我们就要优先考虑上一段提到的“尽量使用主键查询”原则,直接将这个索引设置为主键,可以避免每次查询需要搜索两棵树。

自增ID用完了怎么办?

https://www.modb.pro/db/131380

表的自增 id 达到上限后,再申请时它的值就不会改变,进而导致继续插入数据时报主键冲突的错误

索引重建

重建普通索引时,直接先删除索引,再重新创建即可。

alter table T drop index k; 
alter table T add index(k);

主键索引不能通过上面的语句去重建,因为删除主键索引后,innodb会如下处理:

  • 如果存在非空且字段类型为数值的唯一索引(INT and NOT NULL and UNIQUE INDEX), 会将第一个满足条件的索引作为主键索引, _rowid为对应主键,值与唯一索引相同。(可通过select _rowid from table查询)。
  • 如果找不到合适的索引,那么 InnoDB 会自动生成一个不可见的名为 ROW_ID 的列名为 GEN_CLUST_INDEX 的主键索引,该列是一个 6 字节的自增数值,随着插入而自增。

所以删除主键索引的结果其实是修改了主键字段,而普通索引的叶子节点存的是主键的值,所以,一旦修改了主键字段,普通索引也会有影响,叶子节点的值将被修改成新的主键字段。

当主键索引需要重建时,更好的做法是直接使用alter table t engine=innodb重建表。

05 | 深入浅出索引(下)

image

Q :执行 select * from T where k between 3 and 5,需要执行几次树的搜索操作,会扫描多少行?

A:

  1. 在 k 索引树上找到 k=3 的记录,取得 ID = 300;
  2. 再到 ID 索引树查到 ID=300 对应的 R3;
  3. 在 k 索引树取下一个值 k=5,取得 ID=500;
  4. 再回到 ID 索引树查到 ID=500 对应的 R4;
  5. 在 k 索引树取下一个值 k=6,不满足条件,循环结束。

由于查询结果所需要的数据只在主键索引上有,所以不得不回表。那么,有没有可能经过索引优化,避免回表过程呢?

覆盖索引

如果执行的语句是 select ID from T where k between 3 and 5,这时只需要查 ID 的值,而 ID 的值已经在 k 索引树上了,因此可以直接提供查询结果,不需要回表。也就是说,在这个查询里面,索引 k 已经“覆盖了”我们的查询需求,我们称为覆盖索引

由于覆盖索引可以减少树的搜索次数,显著提升查询性能,所以使用覆盖索引是一个常用的性能优化手段。

在高频请求考虑建立联合索引(例如:(身份证号、姓名)),就是用到了覆盖索引,不再需要回表查整行记录,减少语句的执行时间。

最左前缀原则

「联合索引的多个字段中,只有当查询条件为联合索引的第一个字段时,查询才能使用该索引。」

这个最左前缀可以是联合索引的最左 N 个字段

「索引可以根据字段值最左若干个字符进行模糊查询。」

分析(name,age)这个联合索引,可以看到,索引项是按照索引定义里面出现的字段顺序排序的。当你的逻辑需求是查到所有名字是“张三”的人时,可以快速定位到 ID4,然后向后遍历得到所有需要的结果。如果你要查的是所有名字第一个字是“张”的人,你的 SQL 语句的条件是\"where name like ‘张 %’\"。这时,你也能够用上这个索引,查找到第一个符合条件的记录是 ID3,然后向后遍历,直到不满足条件为止。

image

现在,假设我们有一下三种查询情景:

  • 查出用户名的第一个字是 “张” 开头的人的密码。即查询条件子句为 \"where username like \' 张 %\'\"
  • 查处用户名中含有 “张” 字的人的密码。即查询条件子句为 \"where username like \'% 张 %\'\"
  • 查出用户名以 “张” 字结尾的人的密码。即查询条件子句为 \"where username like \'% 张 \'\"

以上三种情况下,只有第 1 种能够使用(username,password)联合索引来加快查询速度。

Q:表id为主键,username为普通索引,问select id, username from user_table where username like \'%张%\' 能否使用到 (username) 索引?

A:答案是可以的,因为查询的所有字段 (id, username) 在二级索引(username)中都存在,二级索引树比主键索引树小很多,所以会直接遍历二级索引。值得注意的是,这里是遍历整个索引树,而不是在索引树中快速定位数据

前缀索引

Q:需要根据 email 字段查找用户信息的需求,当然我们可以直接给 email 字段创建一个索引,但我们仔细想想,有必要为整个 email 字段创建索引吗?

A:其实没必要的,因为邮箱地址是有一个格式的,都是 \"xxxx@xxx.com\", 所以其实 email 字段的后面几位区分度不高。这时为整个 email 字段创建索引很浪费空间,我们可以创建前缀索引,将字段的前几个字符作为索引即可。

mysql 中使用 ADD KEY (column_name (prefix_length)) 为字段创建前缀索引。

前缀索引设计的好坏在于选择合适的前缀索引长度。如果选择太长,会造成索引空间的浪费;如果选择太短,会导致索引树大量重复的 key,索引效果不理想

问题:

  • 使用前缀索引可能会增加记录扫描次数与回表次数,影响性能
  • 使用前缀索引就用不上覆盖索引对查询性能的优化了

前缀索引的区分度不够高怎么办

一个很常见的解决手段就是 Hash。

对这个超长字段 a 进行 hash(假设命名为 a_hash) 存入数据库,然后对这个 hash 值建立索引,由于 hash 值同样可能存在冲突,也就是说两个不同的 a 通过 Hash 函数得到的结果可能是相同的,所以我们在查询语句的 where 部分还需要进行一次精确判断

索引下推

对于 user_table 表,我们现在有(username,age)联合索引 如果现在有一个需求,查出名称中以 “张” 开头且年龄小于等于 10 的用户信息,语句 C 如下:

\"select * from user_table where username like \' 张 %\' and age > 10\".

语句 C 会根据(username,age)联合索引查询所有满足名称以 “张” 开头的索引,然后直接再筛选出年龄小于等于 10 的索引,之后再回表查询全行数据

image

第二种方式需要回表查询的全行数据比较少,这就是 mysql 的索引下推,在索引遍历过程中,对索引中包含的字段先做判断,直接过滤掉不满足条件的记录,减少回表次数

https://copyfuture.com/blogs-details/20211116185246587T#_157

https://mp.weixin.qq.com/s?__biz=MzI4MTc0NDg2OQ==&mid=2247483854&idx=1&sn=13a28d8754b2718d8e6a044492897b99


来源:https://www.cnblogs.com/ydssx7/p/16499069.html
本站部分图文来源于网络,如有侵权请联系删除。

未经允许不得转载:百木园 » MySQL实战45讲 4,5

相关推荐

  • 暂无文章