一、Mysql索引的底层数据结构与算法

Mysql索引的底层数据结构与算法

前言
一、索引数据结构
- 为什么 MySQL 的索引要使用 B+ 树而不是其他树形结构?比如 B 树?
- 为什么InnoDB存储引擎选择使用B+tree索引结构？
二、索引分类
- 思考：以下SQL语句，那个执行效率高？为什么？备注：id为主键，name字段创建的有索引，age普通字段
- 一张表，有四个字段（id，username，password，status）由于数据量大，需要对以下SQL语句进行优化，该如何进行才是最优方案：select id,username,password from tb user where username ='itcast';
- 思考：InnoDB主键索引的B+tree高度为多高呢？
三、索引语法
- 3.1 创建索引
- 3.2 查看和删除索引
- 3.3 索引提示
聚集索引&聚簇索引&稀疏索引到底是什么
mysql为什么建议使用自增主键
- 3.1 业务层面
- 3.2 性能层面
联合索引底层数据结构又是怎样的
Mysql最左前缀优化原则是怎么回事

前言

索引（index）是帮助MySQL高效获取数据的一种有序数据结构。在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。

优势：

提高数据检索的效率，降低数据库的成本，减少io交互
通过索引列对数据进行排序，降低数据排序的成本，降低CPU的消耗。
劣势：
索引列也是要占用空间的。
索引大大提高了查询效率，同时却也降低更新表的速度，如对表进行INSERT、UPDATE、DELETE时，效率降低。

一、索引数据结构

数据结构学习网址

索引为什么不使用二叉树作为索引结构？
二叉树缺点：顺序插入时，会形成一个链表，查询性能大大降低。大数据量情况下，层级较深，检索速度慢。如下图

我们如果查询5这个值时，其查询了4次，这个还是数据比较少，如果数据比较多，那么就会形成很深的层级，查询性能大大降低。

那红黑树呢？

看起来，层级变少了，查询5这个值只用了2步，但是红黑树也是一种二叉树，在数据比较多，也会形成很深的层级，查询性能也会较低，只是比二叉树好点

看来层级越少，查询性能越好，那有没有什么数据结构，在大数据情况下，层次也很少呢。有，下面开始介绍B-Tree

BTree又称多路平衡查找树，叶节点具有相同的深度，叶节点的指针为空所有索引元素不重复，节点中的数据索引从左到右递增排列

B+Tree，非叶子节点不存储data，只存储索引（冗余），可以放更多的索引叶子节点包含所有索引字段，叶子节点用指针连接，提高区间访问的性能

以一颗最大度数（max-degree）为4（4阶）的b+tree为例：

为什么 MySQL 的索引要使用 B+ 树而不是其他树形结构?比如 B 树?

因为 B 树不管叶子节点还是非叶子节点，都会保存数据，这样导致在非叶子节点中能保存的指针数量变少(有些资料也称为扇出)。
指针少的情况下要保存大量数据，只能增加树的高度，导致 IO 操作变多，查询性能变低

为什么InnoDB存储引擎选择使用B+tree索引结构？

相对于二叉树，层级更少，搜索效率高；
对于B-tree，无论是叶子节点还是非叶子节点，都会保存数据，这样导致一页中存储的键值减少，指针跟着减少，要同样保存大量数据，只能增加树的高度，导致性能降低；
相对Hash索引，B+tree支持范围匹配及排序操作；

二、索引分类

在这里插入图片描述
在InnoDB存储引擎中，根据索引的存储形式，又可以分为以下两种：

聚集索引选取规则：
如果存在主键，主键索引就是聚集索引。
如果不存在主键，将使用第一个唯一（unique）索引作为聚集索引。
如果表没有主键，或没有合适的唯一索引，则nnoDB会自动生成一个rowid作为隐藏的聚集索引。

聚集索引结构图如下
在这里插入图片描述
非聚集索引结构图如下

思考：以下SQL语句，那个执行效率高？为什么？备注：id为主键，name字段创建的有索引，age普通字段

select *  from user where id =10;
select * from user where name ='Arm';
select id,name from user where name ='Arm';
select id,name,age from user where name ='Arm';

第一个SQL：id是聚集索引，他查到10这个节点时，就可以直接获取他的row
第二个SQL：name是非聚集索引，他查到Arm这个节点时，他不会直接获取他的row，而是获取他的聚集索引，如10，然后通过其聚集索引值获取他的row
第三个SQL：因为name是非聚集索引，他查到Arm这个叶子节点时，可以直接获取id，不会去继续回表查询
第四个SQL：当查到Arm这个叶子节点时，可以直接获取id，但是获取不到age的值，所以他需要通过id，继续回表查询

一张表，有四个字段（id，username，password，status）由于数据量大，需要对以下SQL语句进行优化，该如何进行才是最优方案：select id,username,password from tb user where username =‘itcast’;

对username和password创建联合索引，如果只对username创建索引，那么会产生回表查询
在业务场景中，如果存在多个查询条件，考虑针对于查询字段建立索引时，建议建立联合索引，而非单列索引。

思考：InnoDB主键索引的B+tree高度为多高呢？

在计算机中磁盘存储数据最小单元是扇区，一个扇区的大小是512字节，而文件系统（例如XFS/EXT4）他的最小单元是块，一个块的大小是4k，而对于我们的InnoDB存储引擎也有自己的最小储存单元——页（Page），一个页的大小是16K

假设：一行数据大小为1k，一页中可以存储16行这样的数据。InnoDB的指针占用6个字节的空间，主键即使为oigint，占用字节数为8。

高度为2：

n8+（n+1）6=161024，算出n约为1170
117116=18736
高度为3：

1171117116=21939856 (约 2 千万)

三、索引语法

3.1 创建索引

如果只关联一个字段，那么就是单列索引，如果关联多个字段，那么就是组合索引‘

create unique index 索引名 on 表名（字段名，字段名，字段名）//创建唯一索引  

create fulltext index 索引名 on 表名（字段名，字段名，字段名）//创建全文索引 

create  index 索引名 on 表名（字段名，字段名，字段名）//创建普通索引

当字段类型为字符串（varchar，text等）时，有时候需要索引很长的字符串，这会让索引变得很大，查询时，浪费大量的磁盘io，影响查
询效率。此时可以只将字符串的一部分前缀，建立索引，这样可以大大节约索引空间，从而提高索引效率。

create index 索引名 on 表名(字段名(n); //创建前缀索引

前缀长度n，可以根据索引的选择性来决定，而选择性是指杯重复的索引值（基数）和数据表的记录总数的比值，索引选择性越高则查询效率越高，最高为1，这是最好的索引选择性，性能也是最好的。下面以字段email为例

select count(distinct substring(email,1,5))/count(*)from tb_user

3.2 查看和删除索引

show index from 表名 #查看索引

drop index  索引名 on 表名 #删除索引

3.3 索引提示

索引提示，是优化数据库的一个重要手段，简单来说，就是在SQL语句中加入一些人为的提示来达到优化操作的目的。

在Mysql如果一个字段上存在1个以上的索引，那么Mysql会自己选一个索引生效

create index school_home_index on person(school,home)

create index school_index on person(school)

explain select * from person where  school = '海'

在这里插入图片描述
如果我们自己想指定索引生效，那么可以使用下面的语法

#建议使用索引school_index，所以有可能不用
select  *from person use index（school_index）where school = '海'

#忽略索引school_index
select * from person user ignore index（school_index）where  school = '海'

#强制使用索引school_index
select * from person user force index（school_index）where  school = '海'

聚集索引&聚簇索引&稀疏索引到底是什么

聚集索引（Clustered Index）、聚簇索引（Cluster Index）、稀疏索引（Sparse Index）是数据库中常见的索引类型。

聚集索引（Clustered Index）：
- 聚集索引是一种索引类型，它改变了数据在磁盘上的排列方式，使得数据行的物理顺序与索引键的逻辑顺序相匹配。换句话说，聚集索引中数据行按照索引键的顺序进行存储。
- 聚集索引只能有一个，因为它决定了数据行在磁盘上的排列顺序。如果表中已经有聚集索引，再创建新的聚集索引会导致表的重组，代价较高。
- 聚集索引通常应用于经常需要范围查询（Range Query）或者按顺序获取结果的列上。
非聚集索引（Non-clustered Index）：
- 非聚集索引与数据行的物理顺序无关，它将索引键与数据行的引用映射到一个独立的数据结构中。这使得非聚集索引的创建和维护成本较低。
- 一个表可以有多个非聚集索引，因为它们不会改变数据行的物理顺序。
- 非聚集索引通常用于经常需要单一值查找（Single Value Lookup）或者经常需要在列上进行排序的情况。
稀疏索引（Sparse Index）：
- 稀疏索引是一种优化索引结构，它仅记录部分数据行的索引信息，而不是每一行都有对应的索引条目。
- 稀疏索引通常应用于数据分布不均匀，但又需要索引支持的列。通过只记录部分数据行的索引信息，可以节省索引占用的空间，同时保持索引的查询效率。
- 稀疏索引在一些特定的数据库引擎中才会使用，例如 SQL Server 中的稀疏索引用于处理稀疏列（Sparse Column）。

总的来说，聚集索引、非聚集索引和稀疏索引是数据库中用于提高数据访问效率的重要工具，它们各自适用于不同的场景和需求。

mysql为什么建议使用自增主键

MySQL建议使用自增主键的原因有以下几点：

性能优化：自增主键是按顺序递增的，插入新记录时不需要进行排序操作，可以提高插入数据的速度。另外，自增主键也有利于索引的建立和查询优化。
唯一性：自增主键保证了每条记录的唯一性，避免了数据重复或冲突的情况。
简化数据维护：使用自增主键可以简化数据的维护和管理，方便进行数据的增删改查操作。
节省存储空间：自增主键通常是整型数据类型，占用的存储空间较小，可以节省数据库存储空间。

综上所述，使用自增主键可以提高数据库的性能、保证数据的唯一性、简化数据维护操作，并节省存储空间，因此在实际应用中建议使用自增主键。

3.1 业务层面

先说业务层面。

假设某个业务中的用户账号使用了自增 ID 做主键，你注意一下，我这里说的例子使用了自增 ID，但是这个 ID 被赋予了业务含义。

这个业务一直都运行的好好的。

突然有一天，公司拓展了新业务。

公司要求这个账号在新老业务上的权益不能相同，在新业务上从 0 开始计算。

根据这个需求，那么此时如果改造数据表的话，用户 ID 就不能是唯一的了，业务对唯一约束的要求变成了：account_id + business_id。

如何才能使用最小的成本，来达到业务改造的目的？

当然你可以说我们有许多方案可以用，比如新业务独立使用一张新表等等。

我们暂且不讨论其他的方案，如果当初我们没有赋予这个自增主键具体的业务含义的话，是不是问题就好解决了？

假设 account_id 只是一个唯一索引，那么我们在改造业务的时候，只需要把这个唯一索引变更为 account_id + business_id，就可以极大的减轻业务改造的成本。

因此在一般场景下，我推荐你使用无业务含义的自增 ID 作为主键。

3.2 性能层面

下面再从性能层面分析一下，这里我们使用一个生活场景来举例。

这样的场景在互联网公司中非常常见，比如购物、打车、支付等等。

这类业务有一个重要特征就是流水业务，数据热点非常集中，一般用户高频访问的数据就是最近一天、一周或一个月内。

现在我们假设你在 XX APP 看到购书满 100-50 的优惠券，仅限今天使用，然后你去抢了一张。

抢优惠券的过程分以下几步：

你点击抢券
系统在优惠券表中读取你是否有此优惠券
如果有，系统提示已领券
如果没有，查看库存
如果有库存，库存 - 1 并把领券信息写入优惠券表
在这个过程中，系统要反复读取和更新优惠券表。

如果这个表使用了自增 ID 并且数据按时间顺序递增，那么数据热点就集中在今天这个范围内。

那使用无业务含义的自增 ID 做主键会有什么好处呢？

读和更新都集中在一个范围内。

此时不管是 SELECT 还是 INSERT、UPDATE 语句都集中在表的尾部。

前面我们提到了 MySQL 有预读和刷新邻接页的特性，因此这部分热点数据的写入性能会相对较好，也能很好的缓存到 InnoDB buffer pool 中。

假设你使用了带有业务含义的主键，那插入的数据可能就会随机分布到表的各个位置，从而带来大量的随机读和刷脏页操作，拖累整个表的性能。

你可能会质疑说使用无业务含义的自增主键，会导致读取和更新时都需要走二级索引，而二级索引回表操作会有两个 IO。

如果只看单个语句的情况下确实是这样，但是互联网业务通常都是高并发的场景，我们分析问题要从点考虑到面。

通过使用自增 ID 这个特性，我们可以将活跃的数据集中到表的尾部，通过预读的特性将这条数据邻接的其他数据也 load 到 buffer pool。

那么日期比较靠近今天的优惠券信息就能缓存到 buffer pool 中，因此这部分热点数据的性能会维持在一个较佳的状态。

虽然二级索引回表会多出 1 个 IO，但是由于 buffer pool 的介入，整体看来 IO 的总量还是变少了。

假设没有使用自增 ID，我们的热点数据是离散分布在整个表中，首先 INSERT 是完全随机的，然后把热点数据全部缓存到 buffer pool 中也需要耗费更长的时间和更多的 IO，这会带来更多的性能下降。

因此我还是建议你使用无业务含义的自增 ID 作为主键。

联合索引底层数据结构又是怎样的

在这里插入图片描述

Mysql最左前缀优化原则是怎么回事

因为索引就是按着顺序建成的

MySQL最左前缀优化原则是指在使用索引进行查询时，只有索引的最左边的列被使用，才能充分利用索引的优势。换句话说，如果一个索引是由多列组成的，那么只有查询条件中涉及到索引的最左边的列，索引才会被用到。

举个例子，假设有一个索引包含两列 (col1, col2)，如果查询条件是 WHERE col1 = 'value' AND col2 = 'value'，那么这个索引就能被充分利用。但如果查询条件是 WHERE col2 = 'value'，那么这个索引就无法被利用，因为查询条件没有涉及到索引的最左边的列。

因此，在设计数据库表结构和索引时，需要考虑到最左前缀优化原则，尽量将经常用于查询的列放在索引的最左边，以提高查询性能。