MySQL 索引 | ruofei’s blog

type

Post

status

Published

date

Mar 11, 2024

slug

mysql-index

summary

MySQL 索引相关的知识整理

索引介绍

索引是一种数据结构，它将数据按照一定的规则进行排序和组织，能够帮忙快速定位到数据记录，加快数据库表中数据的查找和访问速度。

例如：数据的目录、文件夹、标签、房号等都可以帮助我们快速定位，都可以视为索引。

能实现定位数据的之中存储结构，其设计思想是以空间换时间。

索引的种类

在MySQL中，索引是在存储引擎层实现的，而不是在服务器层实现的。所以不同存储引擎具有不同的索引类型和实现。常见的索引分类如下：

按照数据结构分类：B+tree索引、Hash索引、Full-text索引。

B+tree索引：基本所有存储引擎都支持；Hash索引：只有memory存储引擎中才支持；Full-text索引：只有InnoDB和MyISAM引擎中支持。

按照物理存储分类：聚集索引、非聚集索引。

按照字段特性分类：主键索引(PRIMARY KEY)、唯一索引(UNIQUE)、普通索引(INDEX)、全文索引(FULLTEXT)。

按照字段个数分类：单列索引、联合索引(复合索引、组合索引)。

常见的索引数据结构和区别

二叉树、红黑树、B树、B+树

区别：树的高度影响获取数据的性能（每一个数节点都是一次磁盘I）

二叉树

性质：

在二叉树中第 i 层节点数最多为 (i ≥ 1)

高度为 k 的二叉树其节点总数做多为 -1(k≥1)

对应以的非空二叉树 T，如果叶节点的个数为，而其度为2的节点数为，则：=+1

第 i 层节点数最多为 (i ≥ 1)（满二叉树）

对于具有 N 个结点的完全二叉树的高度为 (完全二叉树)

红黑树

红黑树是一种自平衡二叉查找树，每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

节点是红色或黑色。

根是黑色。

所有叶子都是黑色（叶子是NIL节点）。

每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）

从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

B树

B树是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，复杂度均为 O(n) 。总的来说，B树是一个泛化的二叉查找树，一个节点可以拥有两个以上的子节点。但其与自平衡二叉查找树不同，B树更适合大数据块的存储系统，例如：磁盘。

根据 Knuth 的定义，一个 m 阶的B树是一个有以下属性的树：

每一个节点最多有 m 个子节点

每一个非叶子节点（除根节点）最少有 m÷2 个子节点

如果根节点不是叶子节点，那么它至少有两个子节点

有 k 个子节点的非叶子节点拥有 k − 1 个键

所有的叶子节点都在同一层

🚫

MySQL 没有选择B树作为存储结构的原因：非叶子节点叶存有数据，范围查找效率低。

B+树

B+ 树是 B 树的变体，也是一种多路搜索树。m阶的 B+ 树和 B 树的主要差异如下：

在B+树中，具有n个关键字的节点含有n个子树，即每个关键字对应一个子树，而在B树中，具有n个关键字的节点含有(n+1)个子树。

在B+树中，每个节点(除根节点外)中的关键字个数n的取值范围是[m/2] <= n <= m，根节点n的取值范围2 <=n <=m；而在B树中，除根节点外，其他所有非叶子节点的关键字个数：[m/2]-1 <= n <= m-1，根节点关键字个数为1 <= n <= m-1

B+树中所有叶子节点包含了全部关键字，即其他非叶子节点中的关键字包含在叶子节点中，而在B树中，关键字是不重复的。

B+树中所有非叶子节点仅起到索引的作用，即节点中每个索引项值含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。而在B树中，每个关键字对应一个记录的存储地址。

在 B+ 树所有叶子节点链接成一个不定长的线性表。

B树和B+树的区别？MySQL为什么选择B+树作为默认的索引数据结构？

B+树结构实现数据索引具有如下优点：

非叶子节点上可以存储更多的键值，相应的树的阶数（节点的子节点数）就会更大，树也会变得更加矮胖。这样我们查找数据进行磁盘I/O的次数就会大大减少，数据查询的效率也会更快。

所有的数据记录都有序存储在叶子节点上，就会使得范围查找、排序查找、分组查找已经去重查找变得简单。

数据页之间、数据记录之间都是通过链表链接的，有了这个结构的支持就可以方便的在数据查询后进行升序或者降序操作。

如果一个表没有主键索引那还会创建B+树吗？

会的。

InnoDB是MySQL中的一种存储引擎，它会为每个表创建一个主键索引。如果表没有明确的主键索引，InnoDB会使用一个隐藏的、自动生成的主键来创建索引。这个隐藏的主键索引使用的就是B+树结构。因此，在InnoDB中，即使表没有明确的主键索引，也会创建一个B+树索引。

Hash 索引

在存储引擎中，Memory引擎支持Hash索引。

InnoDB不支持显示的创建Hash索引，只支持自适应Hash索引。

Hash 索引的优缺点

hash索引只能用于等值比较，等值查询效率非常高。

不支持范围查询，也不支持排序，应为索引列的分布是无序的

聚簇索引和非聚簇索引

也叫聚集索引和非聚集索引。

按照物理存储分类：InnoDB的存储方式是聚集索引，MyISAM的存储方式就是非聚集索引。

聚簇索引

聚簇索引将数据存储在索引树的叶子节点上。

聚簇索引可以减少一次查询，因为查询索引树的同时就能获取到数据。

聚簇索引的缺点是，对数据进行修改或者删除操作时需要更新索引树，会增加系统的开销。

聚簇索引通常用于数据库系统中，主要用于提高查询效率。

二级索引（非聚簇索引、辅助索引）

在MySQL中，创建一张表时会默认为主键创建聚簇索引，B+树将表中所有的数据组织起来，即数据就在索引主键所在的节点中，主键索引也被称为聚簇索引，索引的叶子节点存储的是整行数据。而除了聚簇索引之外的所有索引都称为二级索引，二级索引的叶子节点内存是主键的值。

回表

辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录，这种行为被称之为回表。

覆盖索引

需要查询的字段都在索引列中的情况被称之为覆盖索引。一般是只查主键、辅助索引的查询。

索引下推

索引下推（INDEX CONDITION PUSHDOWN,简称 ICP）是在 MySQL 5.6 针对扫描二级索引的一项优化改进。用来在范围查询时减少回表的次数。ICP适用于 MyISAM 和 InnoDB。

联合索引

最左前缀（最左匹配）

例如：创建(a,b,c)联合索引，相当于建了 (a),(a,b),(a,b,c)是三个索引

联合索引的优势

减少开销

建一个联合索引(a,b,c)，相当于建了 (a),(a,b),(a,b,c)三个索引。每多一个索引，都会增加写操作的开销和磁盘空间的开销。对于大数据量的表，使用联合索引会大大的较少开销。

覆盖索引

联合索引更有利于做覆盖索引。

效率高

索引的优缺点

优点：

提高检索效率。

降低排序成本，索引对应的字段会自动排序的，默认是升序asc。

缺点：

创建索引和维护索引需要耗费时间，这种时间随着数据量的增加而增加。

索引需要占用物理空间，数据量越大，占用的空间越大。

会降低表的增删改的效率，因为每次增删改索引，都需要动态维护。

索引使用的时机

适合：

较频繁的座位查询条件的字段应该创建索引。

不适合：

字段值的唯一性太差不设置单独做索引。

更新非常频繁的字段不适合。

不会出现在where句中的字段不适合。