【MySQL】索引

基本概念

概述：

索引是通过某种算法，构建出一个数据模型，用于快速找出在某个列中有一特定值的行，不使用索引，MySQL 必须从第一条记录开始读完整表，直到找出相关的行，表越大，查询数据花费的时间就越多，如果表中查询的列有一个索引，MySQL 能够快速到达一个位置去搜索数据行，而不必查看所有数据，那么将会节省很大一部分时间
索引类似一本书的目录，比如要查找 ‘student’ 这个单词，可以先找到 s 开头的页然后向后查找，这个就类似索引

索引的分类：

索引是存储引擎用来快速查找记录的一种数据结构，按照实现的方式分类，主要有 Hash 索引和 B+Tree 索引：

按照功能来分，索引分为以下几个：

索引操作

单列索引

一个索引只包含单个列，但一个表中可以有多个单列索引

普通索引

MySQL 中基本索引类型，没有什么限制，允许在定义索引的列中插入重复值和空值，纯粹为了查询数据更快一点

创建普通索引

创建表时指定索引

格式如下：

create table table_name(......index 索引名(字段名) -- 给字段创建索引
);

代码示例：

create table student(sid int primary key ,card_id varchar(20) ,name varchar(20) ,gender varchar(20) ,age int ,birth date ,phone_num varchar(20) ,score double ,index index_name(name)
);

结果如下：

创建表后创建索引

格式如下：

create index 索引名 on 表名(字段名);

代码示例：

create table student(sid int primary key ,card_id varchar(20) ,name varchar(20) ,gender varchar(20) ,age int ,birth date ,phone_num varchar(20) ,score double
);
create index index_name on student(name);

修改表结构添加索引

格式如下：

alter table 表名 add index 索引名(字段名);

代码示例：

create table student(sid int primary key ,card_id varchar(20) ,name varchar(20) ,gender varchar(20) ,age int ,birth date ,phone_num varchar(20) ,score double
);
alter table student add index index_name(name);

查看索引

查看数据库中所有索引

格式如下：

select * from mysql.`innodb_index_stats` a where a.`database_name` = '数据库名';

代码示例：

select * from mysql.`innodb_index_stats` a where a.`database_name` = 'mydatabase';

结果如下：

查看表中所有索引

格式如下：

select * from mysql.`innodb_index_stats` a where a.`database_name` = '数据库名' and a.table_name like '%表名%';

代码示例：

select * from mysql.`innodb_index_stats` a 
where a.`database_name` = 'mydatabase' 
and a.table_name like '%student%';

结果如下：

还有一个方法，会更简洁明了的显示表中的索引：

show index from 表名;

代码示例：

show index from student;

结果如下：

删除索引

格式如下：

drop index 索引名 on 表名
-- 或
alter table 表名 drop index 索引名

代码示例：

drop index index_name on student;
show index from student;

结果如下：

唯一索引

唯一索引与前面的普通索引类似，不同的是：索引列的值必须唯一，但允许有空值。如果是组合索引，则列值的组合必须唯一

创建唯一索引

创建唯一索引跟创建普通索引差不多

格式如下：

create table table_name(......unique 索引名(字段名) -- 给字段创建索引
);
-- 或
create unique index 索引名 on 表名(字段名);
-- 或
alter table 表名 add unique 索引名(字段名);

代码示例：

create table student2(sid int primary key ,card_id varchar(20) ,name varchar(20) ,gender varchar(20) ,age int ,birth date ,phone_num varchar(20) ,score double ,unique index_card_id(card_id)
);
show index from student2;

结果如下：

删除索引

格式如下：

drop index 索引名 on 表名
-- 或
alter table 表名 drop index 索引名

代码示例：

drop index index_card_id on student2;
show index from student2;

结果如下：

主键索引

每张表一般都会有自己的主键，在创建表时，MySQL 会自动在主键列上建立一个索引，这就是主键索引，主键具有唯一性并且不允许为 NULL，所以是一种特殊的唯一索引

由于 MySQL 会自动在主键列上建立主键索引，这里就不过多叙述

组合索引

组合索引也叫复合索引，指的是在建立索引的时候使用多个字段，例如同时使用身份证号和手机号建立索引，同样的可以建立为普通索引或者是唯一索引

创建组合索引

格式如下：

create [unique] index 索引名 on 表名 (字段名1,字段名2...;

代码示例：

create index index_phone_name on student(phone_num,name);
show index from student;

结果如下：

注意事项：

在往表中插入组合索引的字段值时，要符合最左原则，插入的字段值顺序要跟组合索引中的顺序一样

select * from student where name='张三';
select * from student where phone_num='12345678911';
select * from student where phone_num='12345678911' and name='张三';
select * from student where name='张三' and phone_num='12345678911';

在这四条 SQL 语句中，只有 2、3、4 可以使用索引 index_phone_name，4 能使用索引的原因是因为 MySQL 本身有一层 SQL 优化，会根据 SQL 语句来识别出来该用哪个索引，可以理解为 3 和 4 等价

全文索引

概述

全文索引的关键字是 fulltext

全文索引主要用来查找文本中的关键字，而不是直接与索引中的值相比较，它更像是一个搜索引擎，基于相似度的查询，而不是简单的 where 语句的参数匹配

用 like + % 就可以实现模糊匹配了，为什么还要全文索引？like + % 在文本比较少时是合适的，但是对于大量的文本数据检索，是不可想象的。全文索引在大量的数据面前，能比 like + % 快 N 倍，速度不是一个数量级，但是全文索引可能存在精度问题

全文索引的版本、存储引擎、数据类型的支持情况：

• MySQL 5.6 以前的版本，只有 MyISAM 存储引擎支持全文索引
• MySQL 5.6 及以后的版本，MyISAM 和 InnoDB 存储引擎均支持全文索引
• 只有字段的数据类型为 char、varchar、text 及其系列才可以建全文索引
• 在数据量较大时，先将数据放入一个没有全局索引的表中，然后再用 create index 创建 fulltext 索引，要比先为一张表建立 fulltext 然后再写入数据的速度快很多
• 测试或使用全文索引时，需先确认自己的 MySQL 版本、存储引擎和数据类型是否支持全文索引

MySQL 中的全文索引，有两个变量，最小搜索长度和最大搜索长度，对于长度小于最小搜索长度和大于最大搜索长度的词语，都不会被索引。即想对一个词语使用全文索引搜索，该词语长度必须在这两个变量的区间内。这两个的默认值可使用以下命令查看：

show variables like '%ft%';  

创建全文索引

格式如下：

-- 修改表结构添加全文索引
alter table 表名 add fulltext 索引名(字段名);-- 创建全文索引
create fulltext index 索引名 on 表名(字段名);

代码示例：

create table t_article(id int primary key auto_increment,title varchar(255),content varchar(1000),writing_date date
);
insert into t_article values(null,'Yesterday Once More','When I was young I listen to the radio','2021-10-01'),(null,'Right Here Waiting','Oceans apart, day after day,and I slowly go insane','2021-10-02'),(null,'My Heart Will Go On','every night in my dreams,I see you, I feel you','2021-10-03'),(null,'Everything I Do','look into my eyes,You will see what you mean to me','2021-10-04'),(null,'Called To Say I Love You','say love you no new year\'s day, to celebrate','2021-10-05'),(null,'Nothing\'s Gonna Change My Love For You','if I had to live my life without you near me','2021-10-06'),(null,'Everybody','We\'re gonna bring the flavor show u how.','2021-10-07');
create fulltext index index_content on t_article(content);
show index from t_article;

结果如下：

使用全文索引

使用全文索引和常用的模糊匹配使用 like + % 不同，全文索引有自己的语法格式，使用 match 和 against 关键字

格式如下：

match (col1,col2,...) against (expr [search_modifier])

代码示例：

select * from t_article where match(content) against('you');

结果如下：

空间索引

介绍

• MySQL 在 5.7 之后的版本支持了空间索引，而且支持 OpenGIS 几何数据模型
• 空间索引是对空间数据类型的字段建立的索引，MySQL 中的空间数据类型有 4 种：
  • GEOMETRY 是一种通用的空间数据类型，可代表任意的几何对象，可以说它是其他特定几何类型的父类型
  • POINT 表示二维空间中的一个点，由一对坐标值（x, y）确定，在地理信息里，通常对应着经纬度
  • LINESTRING 由一系列相连的点组成的线，这些点按顺序连接形成一条连续的路径
  • POLYGON 表示一个封闭的二维区域，由一个或多个线性环组成，其中，外环定义了区域的外部边界，内环（如果有）定义了区域内的孔洞
• MySQL 使用 SPATIAL 关键字进行扩展，使得能够用创建正规索引类型的语法创建空间索引
• 创建空间索引的列，必须将其声明为 NOT NULL
• 空间索引一般使用较少，了解即可

索引原理

概述：

• 一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上
• 这样的话，索引查找过程中就要产生磁盘 I/O 消耗，相对于内存存取，I/O 存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘 I/O 操作次数的渐进复杂度
• 换句话说，索引的结构组织尽量减少查找过程中磁盘 I/O 的存取次数

Hash 算法

哈希索引的工作原理

• 数据存储：哈希索引将索引键通过哈希函数（MySQL 使用的hash()函数）计算出一个哈希值，并将该哈希值与对应的数据指针（指向表中具体记录）存储在哈希表中。
• 查询过程：
  1. 当执行WHERE column = value的等值查询时，MySQL 先对value计算哈希值。
  2. 通过哈希值直接定位到哈希表中的存储位置，获取对应的数据指针。
  3. 根据数据指针快速找到表中的目标记录。
• 时间复杂度：理想情况下，哈希索引的查询时间复杂度为O(1)，即常数时间，因为哈希表的查找操作非常高效。

哈希索引的特点

• 优点：
  • 快速等值查询：适用于精确匹配（如 =、IN），性能极高
  • 插入和删除高效：无需维护树结构，操作相对简单
• 缺点：
  • 不支持范围查询：无法利用哈希索引进行 >、<、BETWEEN 等范围查询，因为哈希值是离散的，无法反映键值的顺序关系
  • 哈希冲突问题：不同的键可能生成相同的哈希值（哈希冲突），此时需通过链表或开放寻址法处理冲突，导致查询时间增加
  • 不支持排序：哈希表存储无序，无法直接用于 ORDER BY 操作

二叉树

二叉树基础概念
二叉树是每个节点最多有两个子节点的树状数据结构，这两个子节点通常被称作左子节点和右子节点。在二叉查找树（Binary Search Tree，BST）这种特殊的二叉树里，对于任意节点，其左子树中所有节点的值都小于该节点的值，而右子树中所有节点的值都大于该节点的值。
二叉查找树的工作原理

• 数据存储：将索引键值作为节点存储在二叉查找树中。每个节点除了保存索引键值外，还会保存指向表中对应记录的指针
• 插入操作：当要插入一个新的索引键值时，从根节点开始比较。如果新键值小于当前节点的值，就进入左子树；若大于，则进入右子树，直到找到合适的插入位置
• 查询操作：对于查找某个特定键值的操作，同样从根节点开始。将目标键值与当前节点的值进行比较，若相等则找到目标节点；若小于当前节点的值，就在左子树中继续查找；若大于，则在右子树中继续查找，直到找到目标节点或者遍历到叶子节点仍未找到
• 删除操作：删除操作相对复杂一些。若要删除的节点是叶子节点，可直接删除；若节点只有一个子节点，用该子节点替代要删除的节点；若节点有两个子节点，需要找到该节点右子树中的最小节点（或左子树中的最大节点）来替代要删除的节点，然后再删除这个最小（或最大）节点。

二叉查找树的优缺点

• 优点
  • 查找效率较高：在平均情况下，二叉查找树的插入、查找和删除操作的时间复杂度为 O(logn)，其中 n 是树中节点的数量
  • 结构简单：相较于其他复杂的索引结构，二叉查找树的逻辑简单，易于理解和实现
• 缺点
  • 极端情况下性能差：如果插入的数据有序，二叉查找树会退化为链表，此时插入、查找和删除操作的时间复杂度会变为 O(n)，效率大大降低。
  • 不适合磁盘存储：在实际的数据库应用中，数据通常存储在磁盘上。由于二叉查找树的高度可能较高，每次查询时需要多次磁盘 I/O 操作，会严重影响性能。

平衡二叉树

平衡二叉树基础概念
平衡二叉树（AVL 树）是一种自平衡的二叉查找树。在二叉查找树里，每个节点最多有两个子节点，并且左子树节点的值小于根节点，右子树节点的值大于根节点。而平衡二叉树在此基础上，还要求每个节点的左右子树的高度差（平衡因子）不超过 1。这一特性保证了树的高度始终保持在 O(logn)，从而使得插入、删除和查找操作的时间复杂度稳定在 O(logn)
平衡二叉树的工作原理

• 数据存储：和二叉查找树一样，平衡二叉树把索引键值当作节点来存储。每个节点除了保存索引键值，还会保存指向表中对应记录的指针，同时会记录该节点的平衡因子

• 插入操作

  • 插入新节点时，先按照二叉查找树的插入规则找到合适的插入位置

  • 插入新节点后，从插入节点开始向上更新各个节点的平衡因子

  • 若某个节点的平衡因子绝对值大于 1，就说明树失去了平衡，此时需要通过旋转操作（左旋、右旋、左右旋、右左旋）来恢复平衡。

• 查询操作：从根节点开始，把目标键值和当前节点的值进行比较。若相等，就找到目标节点；若小于当前节点的值，就在左子树里继续查找；若大于，就在右子树里继续查找，直至找到目标节点或者遍历到叶子节点仍未找到。由于树是平衡的，查询的时间复杂度为 O(logn)

• 删除操作

  • 先按照二叉查找树的删除规则删除目标节点
  • 删除节点后，从被删除节点的父节点开始向上更新各个节点的平衡因子
  • 若某个节点的平衡因子绝对值大于 1，同样需要通过旋转操作来恢复树的平衡

平衡二叉树用于索引的优缺点

• 优点

  • 查询效率稳定：因为树的高度始终保持在 O(logn)，所以插入、删除和查找操作的时间复杂度稳定，能保证在各种数据分布下都有较好的性能
  • 结构简单：相对于更复杂的索引结构，平衡二叉树的逻辑较为简单，易于理解和实现

• 缺点

  • 插入和删除操作代价高：每次插入或删除节点后，都可能需要进行旋转操作来维持树的平衡，这会增加额外的计算开销
  • 不适合磁盘存储：和普通二叉树类似，在实际的数据库应用中，数据一般存储在磁盘上。由于平衡二叉树的高度相对较高，每次查询时需要多次磁盘 I/O 操作，会严重影响性能

BTree 树

B-Tree

B - Tree 基本概念

B - Tree（多路平衡搜索树）是一种自平衡的树结构，常用于数据库和文件系统中作为索引。它和普通的二叉树不同，B - Tree 每个节点可以有多个子节点（“多路” 特性），并且所有叶子节点都在同一层（“平衡” 特性）

B - Tree 节点结构

一个 B - Tree 节点通常包含以下信息：

• 键值（Keys）：用于排序和查找的索引键
• 数据指针（Data Pointers）：指向存储在磁盘上的实际数据记录
• 子节点指针（Child Pointers）：指向子节点的指针

一个典型的 B - Tree 节点结构可以表示为：[键值 1, 数据指针 1, 键值 2, 数据指针 2, ..., 子节点指针 1, 子节点指针 2, ...]

B - Tree 性质

• 节点数量限制：每个节点最少包含 ⌈m/2⌉−1 个键值（m 为树的阶数），最多包含 m−1 个键值
• 子节点数量：每个节点的子节点数量比键值数量多 1，即最少有 ⌈m/2⌉ 个子节点，最多有 m 个子节点
• 根节点特殊情况：根节点至少有 2 个子节点（除非它是叶子节点）
• 所有叶子节点在同一层：这保证了树的平衡性，使得查询、插入和删除操作的时间复杂度稳定

B - Tree 的工作原理

• 查询操作

  • 从根节点开始，将目标键值与节点中的键值进行比较

  • 如果目标键值等于某个键值，则通过对应的数据指针找到实际数据记录

  • 如果目标键值小于某个键值，则通过该键值左侧的子节点指针进入子节点继续查找

  • 如果目标键值大于所有键值，则通过最后一个子节点指针进入子节点继续查找

  • 重复上述步骤，直到找到目标键值或到达叶子节点仍未找到

• 插入操作

  • 从根节点开始，按照查询的方式找到合适的叶子节点

  • 如果叶子节点的键值数量未达到上限，则将新键值插入到合适的位置

  • 如果叶子节点的键值数量达到上限，则需要进行节点分裂操作：

    • 选择中间的键值，将其提升到父节点
    • 以中间键值为界，将原节点分裂为两个节点
    • 如果父节点也因为提升操作而达到上限，则继续向上分裂，直到根节点

• 删除操作

  • 从根节点开始，找到要删除的键值所在的节点

  • 如果要删除的键值在叶子节点：

    • 若删除后节点的键值数量仍满足下限要求，则直接删除
    • 若不满足下限要求，则需要进行节点合并或借键操作：
      • 借键：从相邻的兄弟节点借一个键值
      • 合并：将当前节点与相邻的兄弟节点合并

  • 如果要删除的键值在非叶子节点：

    • 用该键值的前驱或后继键值替换它，然后删除前驱或后继键值（前驱或后继键值一定在叶子节点）

B - Tree 的优势

• 减少磁盘 I/O：由于 B - Tree 的每个节点可以存储多个键值和子节点指针，树的高度相对较低。在进行查询时，需要访问的磁盘页面数量减少，从而减少了磁盘 I/O 次数，提高了查询效率。
• 支持范围查询：B - Tree 是有序的，可以通过中序遍历的方式方便地进行范围查询。
• 自平衡：B - Tree 会自动调整节点结构，保持树的平衡，使得插入、删除和查询操作的时间复杂度稳定在 O(logn)。

B+Tree

B+Tree 是 B-Tree 的一种变体，在数据库索引中应用广泛，MySQL 的 InnoDB 和 MyISAM 存储引擎就主要用它来构建索引。下面为你详细介绍 B+Tree 的原理：

B+Tree 的结构特点

• 键值与指针分布：B+Tree 的所有数据记录（键值和对应的数据指针）都存于叶子节点，非叶子节点仅用于索引，只保存键值和指向子节点的指针，不存储数据记录
• 叶子节点连接：所有叶子节点之间通过指针相互连接，形成一个有序链表，这使得范围查询更为高效
• 节点结构：与 B-Tree 类似，B+Tree 的节点也有键值数量和子节点数量的限制，每个节点最少包含 ⌈m/2⌉−1 个键值（m 为树的阶数），最多包含 m−1 个键值；每个节点的子节点数量比键值数量多 1，最少有 ⌈m/2⌉ 个子节点，最多有 m 个子节点。根节点至少有 2 个子节点（除非它是叶子节点），且所有叶子节点在同一层

B+Tree 的工作原理

• 查询操作

  • 单点查询：从根节点开始，把目标键值和节点中的键值进行比较。若目标键值小于某个键值，就通过该键值左侧的子节点指针进入子节点继续查找；若大于所有键值，就通过最后一个子节点指针进入子节点继续查找。重复此步骤，直至到达叶子节点，在叶子节点中查找目标键值

  • 范围查询：先找到范围的起始键值所在的叶子节点，然后利用叶子节点之间的指针顺序遍历，直到找到范围的结束键值，这样就能高效地获取范围内的所有数据记录

• 插入操作

  • 从根节点开始，按查询的方式找到合适的叶子节点

  • 若叶子节点的键值数量未达到上限，就将新键值插入到合适的位置

  • 若叶子节点的键值数量达到上限，就需要进行节点分裂操作：

    • 选择中间的键值，将其提升到父节点（注意，在 B+Tree 中，中间键值会同时保留在原叶子节点和提升到父节点）
    • 以中间键值为界，把原节点分裂成两个节点
    • 若父节点也因提升操作而达到上限，就继续向上分裂，直到根节点

• 删除操作

  • 从根节点开始，找到要删除的键值所在的叶子节点

  • 若删除后节点的键值数量仍满足下限要求，就直接删除

  • 若不满足下限要求，就需要进行节点合并或借键操作：

    • 借键：从相邻的兄弟节点借一个键值
    • 合并：将当前节点与相邻的兄弟节点合并

B+Tree 用于索引的优势

• 磁盘 I/O 优化：由于非叶子节点不存储数据记录，每个节点能存储更多的键值和子节点指针，树的高度更低。在进行查询时，需要访问的磁盘页面数量减少，从而减少了磁盘 I/O 次数，提高了查询效率
• 范围查询高效：叶子节点之间的有序链表结构使得范围查询非常方便，只需找到范围的起始和结束键值，就能顺序遍历获取范围内的所有数据记录，无需像 B-Tree 那样进行多次中序遍历
• 查询稳定性：所有数据记录都在叶子节点，查询的时间复杂度稳定在 O(logn)，无论查询的是哪个键值，都需要从根节点到叶子节点进行遍历

索引的特点

索引的优点

• 大大加快数据的查询速度
• 使用分组和排序进行数据查询时，可以显著减少查询时分组和排序的时间
• 创建唯一索引，能够保证数据库表中每一行数据的唯一性
• 在实现数据的参考完整性方面，可以加速表和表之间的连接

索引的缺点

• 创建索引和维护索引需要消耗时间，并且随着数据量的增加，时间也会增加
• 索引需要占据磁盘空间
• 对数据表中的数据进行增加，修改，删除时，索引也要动态的维护，降低了维护的速度

索引的使用原则

• 更新频繁的列不应设置索引
• 数据量小的表不要使用索引（毕竟总共 2 页的文档，还要目录吗？）
• 重复数据多的字段不应设为索引（比如性别，只有男和女，一般来说：重复的数据超过百分之 15 就不该建索引）
• 首先应该考虑对 where 和 order by 涉及的列上建立索引