MySql篇-索引

B-树

定义:

1、根节点至少包含两个孩子

2、每个节点最多包含m个孩子(m >= 2),m为树的深度

3、除了根节点和叶子节点,其他节点至少有ceil(m/2)个孩子,ceil函数为取上限,例如ceil(1.2)=2,就是小数位多少,都入,不是四舍五入

4、叶子节点的高度相同

如果我们需要寻找key为28的数据,会经历3次磁盘I/O操作过程

PS:

1、我们从上图看到B树和二分搜索树有一点相似的地方,数据是有序的,也就是按照关键字进行排序

2、非叶子节点包含key和value,以及指向其子节点地址的指针

3、叶子节点只有key和value

B+树

  • 非叶子节点的子树指针与关键字个数相同
  • 非叶子节点的子树指针P[i],指向关键字值的子树
  • 非叶子节点仅用来索引,数据都保存在叶子节点中
  • 所有叶子节点均有一个链指针指向下一个叶子节点 (紫色块之间有链指针连接,从左到右升序排列)

B+树与B-树的区别

B+树是B树的一种优化
1、B树的每个结点都存储了key和data,B+树的data存储在叶子节点上。非叶子节点不存储data,这样一个节点就可以存储更多的key。可以使得树更矮,磁盘IO操作次数更少。查询效率更高
2、B+树查询路径都是从非叶子结点, 到叶子节点。 效率比较稳定
3、B+树叶子结点是一个链表, 扫描全表数据速度更快(只需要遍历叶子节点,并且范围查询也有优化)

因为B+树的这些好处,在 MySQL 中,MyISAM 引擎和 InnoDB 引擎都是使用 B+Tree 作为索引结构,

但是,两者的实现方式不太一样。MyISAM 引擎是使用的非聚簇索引,InnoDB 引擎使用的是聚簇索引

一棵B+树可以存放多少条数据?

假设B+树高度为2,一行数据记录大小为1k(实际上很多互联网业务数据就是1k左右),单个叶子节点(页)中记录数16K/1K=16

B+树存在的数据总量 = 根节点节点指针数量 * 每页保存的数据量

假设主键为bigint,长度为8字节,指针大小在InnoDB源码中为6字节,这样一共14字节,我们一个页中存放16384/14=1170。那么一棵高度为

2的B+树,能存放1170*16=18720条这样的数据。

以此类推,一个高度为3的B+树可以存放:1170117016=21902400条这样的记录。

所以在InnoDB中B+树高度一般为1-3层,它就能满足千万级的数据存储。通过主键索引查询通常只需要1-3次IO操作即可查找到数据。

索引类型

按照数据模型维度划分:

  1. B-Tree索引:B树索引是MySQL中最常见的索引类型,适用于大部分场景。它支持等值查询、范围查询和前缀匹配。
  2. 哈希索引:哈希索引是一种基于哈希表实现的索引,类似键值对的形式,一次即可定位, 等值查询非常快,但是不支持范围查询和前缀匹配
  3. 全文索引:全文索引是一种用于文本数据模糊查询的特殊索引,它基于倒排索引实现。目前只有 CHARVARCHARTEXT 列上可以创建全文索引。效率较低,通常使用搜索引擎如 ElasticSearch 代替。

从底层存储方式维度划分:

  1. 聚簇索引(聚集索引):索引结构和数据一起存放的索引,InnoDB 中的主键索引就属于聚簇索引。

  2. 非聚簇索引(非聚集索引):索引结构和数据分开存放的索引,二级索引(辅助索引)就属于非聚簇索引。MySQL 的 MyISAM 引擎,不管主键还是非主键,使用的都是非聚簇索引。

聚簇索引(密集索引)

行数据和主键索引存储在一起,辅助键索引只存储辅助键和主键,而不保存数据

InnoDB使用的是聚簇索引,行数据保存在叶子节点上。如果通过where id = 5,直接通过主键索引找到对应的关键字,然后返回行数据

如果通过where name = tom,首先通过辅助键索引找到对应id = 5,然后再通过主键索引找到行数据

PS:

1).如果存在主键,主键就是密集索引

2).如果没有主键,表中第一个唯一非空索引为密集索引

3).如果以上都没有,InnoDB生成一个隐藏主键作为密集索引,是一个6字节的列,随着数据的插入自增

所以,InnoDB必须有个密集索引,这是因为非主键索引叶子节点不保存行数据,而是保存着主键值

非聚簇索引(稀疏索引):

B+树叶子节点存储的是指向数据的指针

MyISAM使用的为非聚簇索引,主键索引保存了主键,非主键索引保存了非主键,而数据行保存在其他位置,检索的过程都是通过叶子节点内

保存的地址找到对应的数据行。

InnoDB为什么使用聚簇索引呢?

从上面索引过程我们可以看到,对于非主键查询来说,聚簇索引需要经过两次检索,好像效率更低了,那么聚簇索引的优势在哪?

1、行数据和叶子节点保存在一起,会一起被加载到内存,找到叶子节点就可以将数据库返回。

2、辅助索引的叶子节点保存主键的指针,而不使用地址值作为指针,减少了当出现行移动或者数据页分裂时辅助索引的维护工作,使用主键

值当作指针会让辅助索引占用更多的空间,InnoDB在移动行时无须更新辅助索引中的这个"指针"。也就是说行的位置(实现中通过16K的Page来定

位,后面会涉及)会随着数据库里数据的修改而发生变化(前面的B+树节点分裂以及Page的分裂),使用聚簇索引就可以保证不管这个主键B+树的

节点如何变化,辅助索引树都不受影响。

页page:

InnoDB数据通过page存储,是最小的存储单位,page默认大小为16k,文件系统最小单位块为4k,通过下面参数设置

](https://img2018.cnblogs.com/blog/1351999/201907/1351999-20190709112105625-1669802737.png)

页可以用来存储数据也可以用来存储key和指针,分别对应非叶子节点和叶子节点。通过非叶子节点的二分查找和指针确定数据在哪一页,进

而查到对应的数据。


索引概念

MySQL中InnoDB引擎要求每张表都有要有一个聚簇索引(clustered index),也称为主键索引(primary key index),它的作用是将数据按照主键值排序,方便快速地访问单条记录。除了聚簇索引外,MySQL还可以有多辅助(二级)索引(secondary index),它们的作用是加速查询和排序操作。

回表查询

InnoDB索引有聚簇索引和辅助索引。聚簇索引的叶子节点存储行记录,InnoDB必须要有,且只有一个。

辅助索引的叶子节点存储的是主键值和索引字段值,通过辅助索引无法直接定位行记录,通常情况下,需要扫码两遍索引树。先通过辅助索引定位主键值,然后再通过聚簇索引定位行记录,这就叫做回表查询,它的性能比扫一遍索引树低。

主键索引

数据表的主键列使用的就是主键索引。B+Tree的叶子节点存放的是主键字段值

通常说的主键索引就是聚簇索引。InnoDB的表要求必须要有聚簇索引:
● 如果表定义了主键,则主键索引就是聚簇索引
● 如果表没有定义主键,则第一个非空unique列作为聚簇索引
● 否则InnoDB会从建一个隐藏的row-id作为聚簇索引

检索过程: 直接通过主键索引找到存储的数据

二级索引(辅助索引)

InnoDB二级索引,也叫作辅助索引,是根据索引列构建 B+Tree结构。但在 B+Tree 的叶子节点中只存了索引列和主键的信息。二级索引占用的空间会比聚簇索引小很多, 通常创建辅助索引就是为了提升查询效率。一个表InnoDB只能创建一个聚簇索引,但可以创建多个辅助索引。

检索过程: 先通过辅助索引找到主键索引, 通过回表查询,然后再找到存储的数据

索引覆盖

在MySQL官网,类似的说法出现在explain查询计划优化章节,即explain的输出结果Extra字段为Usingindex时,能够触发索引覆盖。

只需要在一棵索引树上就能获取SQL所需的所有列数据,无需回表,速度更快,这就叫做索引覆盖。实现索引覆盖最常见的方法就是:将被查询的字段,建立到组合索引。

最左匹配原则

复合索引使用时遵循最左匹配原则,最左匹配顾名思义,就是最左优先,即查询中使用到最左边的列,那么查询就会使用到索引,如果从索引的第二列开始查找,索引将失效。

索引下推

我们以市民表的联合索引(name, age)为例。如果现在有一个需求:检索出表中“名字第一个字是张,而且年龄是 10 岁的所有男孩”。那么,SQL 语句是这么写的:

mysql> select * from tuser where name like '张%' and age=10 and ismale=1; 

你已经知道了前缀索引规则,所以这个语句在搜索索引树的时候,只能用 “张”,找到第一个满足条件的记录 ID3。当然,这还不错,总比全表扫描要好。 然后呢? 当然是判断其他条件是否满足。 在 MySQL 5.6 之前,只能从 ID3 开始一个个回表。到主键索引上找出数据行,再对比字段值。 而 MySQL 5.6 引入的索引下推优化(index condition pushdown), 可以在索引遍历过程中,对索引中包含的字段先做判断,直接过滤掉不满足条件的记录,减少回表次数。

图 3 无索引下推执行流程

图 4 索引下推执行流程

在图 3 和 4 这两个图里面,每一个虚线箭头表示回表一次。 图 3 中,在 (name,age) 索引里面我特意去掉了 age 的值,这个过程 InnoDB 并不会去看 age 的值,只是按顺序把“name 第一个字是’张’”的记录一条条取出来回表。因此,需要回表 4 次。 图 4 跟图 3 的区别是,InnoDB 在 (name,age) 索引内部就判断了 age 是否等于 10,对于不等于 10 的记录,直接判断并跳过。在我们的这个例子中,只需要对 ID4、ID5 这两条记录回表取数据判断,就只需要回表 2 次。

索引为什么会失效

  1. 列类型不匹配:如果索引列和查询条件的数据类型不匹配,例如在一个字符串类型的索引列上执行了数值比较,那么索引就会失效。
  2. 函数操作:如果查询条件中使用了函数操作,例如在索引列上使用函数操作或者使用了自定义函数,那么索引也会失效。
  3. 索引列值为空:如果查询条件中使用了IS NULL或者IS NOT NULL操作,那么如果索引列上存在NULL值,那么索引就会失效。
  4. 表达式操作:如果查询条件中使用了表达式操作,例如对索引列进行加减乘除等操作,那么索引也会失效。
  5. 隐式类型转换:如果查询条件中使用了隐式类型转换,例如在一个字符串类型的索引列上执行了数值比较,并且数据库自动将字符串转换为数字类型,那么索引也会失效。
  6. 数据量太大:如果表中的数据量太大,那么对于一些非唯一索引列,索引的查询优化器可能会认为扫描整个表比使用索引更加高效,从而导致索引失效。
  7. 索引列上存在函数:如果索引列上使用了函数,例如在索引列上使用了UPPER()函数,那么索引也会失效。
  8. 最左匹配原则:联合索引要正确使用需满足最左匹配原则,即:符合第一列才会继续判断后面的字段。
  9. 使用OR 一列不是索引

正确使用索引

  1. 索引字段占用空间越小越好, 大文本,大对象不要创建索引

  2. 索引并不是越多越好, 有维护成本,空间成本

    建议单表不超过5个索引

  3. 频繁更新的字段不适合作为索引

  4. 我们创建索引的字段应该是查询操作非常频繁的字段。

  5. 频繁需要排序的字段:索引已经排序,这样查询可以利用索引的排序,加快排序查询时间。

如何分析sql使用索引情况

在 MySQL 中可以通过 EXPLAIN 关键字模拟优化器执行 SQL语句

explain select 列名 FROM 表名 WHERE 条件 ;

EXPLAIN输出内容如下:

各个字段的含义如下:

列名 含义
id SELECT的查询序列号
select_type 主要用来说明查询的类型:普通查询、联合查询、子查询等
table 输出的行所引用的表
partitions 如果查询是基于分区表的话,显示查询将访问的分区。,对于未分区的表,值为 NULL
type 代表访问类型,是判断sql执行性能比较关键的一个字段
possible_keys MySQL可能使用的键(索引)。
key MySQL实际决定使用的键(索引)。如果没有选择索引,键是NULL。
key_len 所选索引的长度
ref 表示索引的哪一列被使用
显示使用哪个列或常数与key一起从表中选择行。
rows 预计要读取的行数
filtered 按表条件过滤后,留存的记录数的百分比
Extra 附加信息

type

联接类型。下面给出各种联接类型,按照从最佳类型到最坏类型进行排序:

type代表访问类型,是判断sql执行性能比较关键的一个字段,性能从高到低依次是:
system > const > eq_ref > ref > fulltext > ref_or_null > index_merge > unique_subquery > index_subquery > range > index > ALL

  • system:表仅有一行(=系统表)。这是const联接类型的一个特例。
  • const:表最多有一个匹配行,它将在查询开始时被读取。因为仅有一行,在这行的列值可被优化器剩余部分认为是常数。const表很快,因为它们只读取一次!
  • eq_ref:对于每个来自于前面的表的行组合,从该表中读取一行。这可能是最好的联接类型,除了const类型。
  • ref:对于每个来自于前面的表的行组合,所有有匹配索引值的行将从这张表中读取。
  • ref_or_:该联接类型如同ref,但是添加了MySQL可以专门搜索包含NULL值的行。
  • index_merge:该联接类型表示使用了索引合并优化方法。
  • unique_subquery:该类型替换了下面形式的IN子查询的ref: value IN (SELECT primary_key FROM single_table WHERE some_expr) unique_subquery是一个索引查找函数,可以完全替换子查询,效率更高。
  • index_subquery:该联接类型类似于unique_subquery。可以替换IN子查询,但只适合下列形式的子查询中的非唯一索引: value IN (SELECT key_column FROM single_table WHERE some_expr)
  • range:只检索给定范围的行,使用一个索引来选择行。
  • index:该联接类型与ALL相同,除了只有索引树被扫描。这通常比ALL快,因为索引文件通常比数据文件小。
  • ALL:对于每个来自于先前的表的行组合,进行完整的表扫描,说明查询就需要优化了。

一般来说,得保证查询至少达到range级别,最好能达到ref。

上一篇:STM32H750时钟频率和功耗以及RTC功能测试


下一篇:基于ssm + 小程序的党建考试系统实现与设计(源码+数据库+文档)