MySQL数据库的索引

数据库的索引

1、背景
2、定义和特征
3、索引的分类（功能上分类）
4、MySQL下索引的基本操作
5、索引的底层实现原理（数据结构、重点）

5.1、二叉查找树(BST)
5.2、红黑树
5.3、AVL 树
5.4、B 树（多路查找二叉树）
5.5、B+树（重中之重，五颗星）
5.6、mysql索引为什么选择B+树而不选择B树？（重点）
5.7、哈希表（Hash，也是重点）

6、索引的分类（实现上分类）

6.1、聚集索引

6.1.1、定义
6.1.2、Innodb 引擎的底层实现原理（聚集索引方式）

6.2、非聚集索引方式

6.2.1、定义
6.2.2、MyISAM 引擎的底层实现原理（非聚集索引方式）

7、索引的使用策略

7.1、什么时候要使用索引？
7.2、什么时候不要使用索引？
7.3、索引失效的情况？

参考

数据库的索引

1、背景

我以为我对Mysql索引很了解，直到我遇到了阿里的面试官

我们是怎么聊到索引的呢，是因为我提到我们的业务量比较大，每天大概有几百万的新数据生成，于是有了以下对话：

面试官： 你们每天这么大的数据量，都是保存在关系型数据库中吗？
我： 是的，我们线上使用的是MySQL数据库
面试官： 每天几百万数据，一个月就是几千万了，那你们有没有对于查询做一些优化呢？
我： 我们在数据库中创建了一些索引（我现在非常后悔我当时说了这句话）。

这里可以看到，阿里的面试官并不会像有一些公司一样拿着题库一道一道的问，而是会根据面试者做过的事情以及面试过程中的一些内容进行展开。

面试官： 那你能说说什么是索引吗？
我： （这道题肯定难不住我啊）索引其实是一种数据结构，能够帮助我们快速的检索数据库中的数据。

以上只是截取的片段，感兴趣的上面有全文链接。

对于一本书而言，通过目录，我们可以很快的找到自己想要的章节对应的位置。同样，在数据十分庞大的时候， 索引可以大大加快查询的速度 ，这是因为使用索引后可以 不用扫描全表 来定位某行的数据，而是先通过 索引表 找到该行 数据对应的物理地址 然后 访问相应的数据 。

2、定义和特征

1、定义

索引是一个排序的列表，在这个列表中存储着索引的值和包含这个值的数据所在行的物理地址。
索引是一种数据结构。数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。索引的实现通常使用 B+树 。
索引就相当于目录。为了方便查找书中的内容，通过对内容建立索引形成目录。
索引是一个文件，它是要占据物理空间的。

在这里插入图片描述
根据 Col2列 建立索引， key 是索引字段的值， value 是值所在的 磁盘文件地址 ，例如77就是一个 key 索引，0x56就是对应的 value 。通过这个地址，找到你需要查询的数据。（如果不懂？看完数据结构部分，就好明白了）

2、特征

1、索引的好处

1、提高数据检索速度，降低数据库IO成本。就是通过缩小表中需要查询的记录的数目从而加快搜索速度。
2、降低数据排序的成本，降低CPU消耗。之所以查的快，是因为先将数据排好序了。

2、索引坏处

1、占用存储空间：索引实际上是一张表，记录了主键和索引字段，一般以索引文件的形式存储在磁盘上。
2、降低更新表的速度：表的数据发生了变化，对应的索引也需要一起变更。（所以不适用 增删改频繁 的数据库）

3、索引的分类（功能上分类）

从功能上说，分为 6 种： 普通索引 ， 唯一索引 ， 主键索引 ， 复合索引 ， 外键索引 ， 全文索引 。

1、普通索引：最基本的索引，没有任何约束。

ALTER TABLE 'table_name' ADD INDEX ('column')

2、唯一索引：与普通索引类似，但具有唯一性约束。在表上一个或者多个字段组合建立的索引，这个（或这几个）字段的值组合起来在表中不可以重复。一张表可以建立任意多个唯一索引，但一般只建立一个。

ALTER TABLE 'table_name' ADD UNIQUE('column')

3、主键索引：特殊的唯一索引，不允许有空值。
- 唯一索引列允许null值，而主键列不允许为null值。一张表最多建立一个主键，也可以不建立主键。

ALTER TABLE 'table_name'


    
 ADD PRIMARY KEY('column')

4、复合索引：将多个列组合在一起创建索引，可以覆盖多个列。
- 姓 - 名 - 电话号码 。电话簿中的内容先按照姓氏的拼音排序，相同姓氏再按名字的拼音排序，这相当于在（姓，名）上建立了一个复合索引。

ALTER TABLE 'table_name' ADD INDEX('colimn1','column2')

5、外键索引：只有InnoDB类型的表才可以使用外键索引，保证数据的一致性、完整性和实现级联操作。
6、全文索引：MySQL 自带的全文索引只能用于 InnoDB、MyISAM，并且只能对英文进行全文检索，一般使用全文索引引擎（ES，Solr）。

ALTER TABLE 'table_name' ADD FULLTEXT('column')

注意：主键就是唯一索引，但是唯一索引不一定是主键，唯一索引可以为空，但是空值只能有一个，主键不能为空。

4、MySQL下索引的基本操作

1、创建索引
在创建表的时候添加索引

CREATE TABLE mytable(  
    ID INT NOT NULL,   
    username VARCHAR(16) NOT NULL,  
    INDEX [indexName] (username(length))  
);

在创建表以后添加索引

ALTER TABLE my_table ADD [UNIQUE] INDEX index_name(column_name);
或者
CREATE INDEX index_name ON my_table(column_name);

2、索引查询

具体查询：
SELECT * FROM table_name WHERE column_1=column_2;(为column_1建立了索引)
 
或者模糊查询
SELECT * FROM table_name WHERE column_1 LIKE '三%'
 
SELECT * FROM table_name WHERE column_1 LIKE '_好_'
 
如果要表示在字符串中既有A又有B，那么查询语句为：
SELECT * FROM table_name WHERE column_1 LIKE 'A%' AND column_1 LIKE 'B%';
 
SELECT * FROM table_name WHERE column_1 LIKE '[张李王]三';  //表示column_1中有匹配张三、李三、王三的都可以
SELECT * FROM table_name WHERE column_1 LIKE '[^张李王]三';  //表示column_1中有匹配除了张三、李三、王三的其他三都可以
 
//在模糊查询中，%表示任意0个或多个字符；_表示任意单个字符（有且仅有），通常用来限制字符串长度;[]表示其中的某一个字符；[^]表示除了其中的字符的所有字符
 
或者在全文索引中模糊查询
SELECT * FROM table_name WHERE MATCH(content) AGAINST('word1','word2',...);

3、删除索引

DROP INDEX my_index ON tablename；
或者
ALTER TABLE table_name DROP INDEX index_name;

5、索引的底层实现原理（数据结构、重点）

数据库中存储了大量数据，一个高效的索引能节省巨大的时间。

比如下面这个数据表，

如果 Mysql 没有实现索引算法，那么查找 id=7 这个数据，那么只能采取暴力顺序遍历查找，找到 id=7 这个数据需要 比较 7 次 ，
如果这个表存储的是 1000W 个数据，查找 id=1000W 这个数据那就要比较 1000W 次。

在这里插入图片描述

5.1、二叉查找树(BST)

二叉查找树：左子树节点均小于父节点，右子树节点均大于父节点
在这里插入图片描述
二叉 查找树 的 时间复杂度是 O(lgn) ，比如针对上面这个二叉树结构，我们需要计算 比较 3 次 就可以检索到 id=7 的数据，相对于直接遍历查询 省了一半的时间 ，从检索效率上看来是能做到高速检索的。

不足之处：主键一般默认都是自增的，产生不平衡状态
普通的二叉查找树有个致命缺点：极端情况下会 退化为线性链表 ，二分查找也会退化为 遍历查找 ，时间复杂退化为 O（N） ，检索性能急剧下降。
在这里插入图片描述
id=7 的数据的所需要计算的次数已经变为 7 了。

5.2、红黑树

红黑树： 这是一颗会自动调整树形态的树结构，比如当二叉树处于一个不平衡状态时，红黑树就会自动 左旋右旋节点 以及 节点变色 ，调整树的形态，使其保持基本的平衡状态（ 时间复杂度为 O（logn） ），也就保证了查找效率不会明显减低。

比如从 1 到 7升序插入数据节点，如果是普通的二叉查找树则会退化成链表，但是红黑树则会不断调整树的形态，使其保持基本平衡状态。如下图所示。下面这个红黑树下查找 id=7 的所要 比较的节点数为 4 ，依然保持二叉树不错的查找效率。
在这里插入图片描述
不足之处
红黑树顺序插入 1~16 个节点，查找 id=16 需要 比较的节点数为 6 次 。
观察一下这个树的形态，是不是当数据是顺序插入时，树的形态一直处于“右倾”的趋势呢？

从根本上上看，红黑树并没有 完全解决二叉查找树虽然这个“右倾”趋势 ，虽然没有二叉查找树退化为线性链表那么夸张，但是数据库中的基本主键自增操作，主键一般都是数百万数千万的，效率也很低。
在这里插入图片描述

5.3、AVL 树

AVL 树 ：自平衡二叉树。因为 AVL 树是个绝对平衡的二叉树， 左右子树高度差小于等于1

因此在调整二叉树的形态上消耗的性能会更多。当树的某个位置被删除节点，需要经过一系列左旋右旋操作维持高度平衡。
查找性能（ O（logn） ），不存在极端的低效查找的情况

AVL 树顺序插入 1~7 个节点，查找 id=7 所要 比较节点的次数为 3 。
在这里插入图片描述
AVL 树顺序插入 1~16 个节点， 查找 id=16 需要 比较的节点数为 4 。

从查找效率而言，AVL 树查找的速度要高于红黑树的查找效率（AVL 树是 4 次比较，红黑树是 6 次比较）。
从树的形态看来，AVL 树不存在红黑树的“右倾”问题。

不足之处

数据库 查询数据的瓶颈在于磁盘 IO ，就是从磁盘读取 1B 数据和 1KB 数据所消耗的时间是基本一样的。

AVL 树的每一个树节点只存储了1个数据 ，我们一次磁盘 IO 只能取出来一个节点上的数据加载到内存里，那比如 查询 id=7 这个数据 我们就要 进行磁盘 IO 三次 ，这是多么消耗时间的。 设计数据库索引时首先考虑怎么减少磁盘 IO 的次数。

磁盘结构：
在这里插入图片描述

综上所述：
BST、红黑树、AVL 突出的问题，我们需要维持基本结构平衡、需要考虑树的深度过深，可以在一个树节点上尽 可能多地存储数据，一次磁盘 IO 就多加载点数据到内存 ，这就是 B 树，B+树 的的设计原理了。

5.4、B 树（多路查找二叉树）

更详细的介绍链接
B-Tree ：一种 自平衡的树 （所有的叶子节点拥有相同的高度）类型的数据结构。但是和其它树比如 红黑树，AVL树只有两个孩子 ：左孩子和右孩子不同， B-Tree 的子节点多余或者等于2两个孩子 。
在这里插入图片描述
还是以上面 BST、红黑树、AVL 的为例：

当我们把 单个节点限制的 key 个数 设置为 6 （4左右各有三个）之后，一个存储了 7 个数据 的 B 树，查询 id=7 这个数据所要进行的 磁盘 IO 为 2 次 。
在这里插入图片描述
一个存储了 16 个数据 的 B 树，查询 id=7 这个数据所要进行的磁盘 IO 为 2 次 。相对于 AVL 树而言磁盘 IO 次数降低为一半。

总结：

优秀检索速度，时间复杂度：B 树的查找性能等于 O（h*logn），其中 h 为树高，n 为每个节点关键词的个数；
尽可能少的磁盘 IO，加快了检索速度；

mysql里也没用这种，而是用到了它的变种B+树，具体原因下面介绍完B+树以后进行对比。

5.5、B+树（重中之重，五颗星）

B+树主体特征和B树一样，主要不一样的特征如下：

1、有n棵子树的结点中含有n个关键字， 每个关键字不保存数据 ， 只用来索引 ，所有数据都保存在叶子节点，可以让 每个节点保存更多的索引 。（特别重要）
2、所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
- 也就是 所有数据（这里其实是数据的地址）都放在叶子节点 ，并且所以叶子节点用 指针（双箭头） 串起来，按顺序排列，奠定了 范围查找 的基础（特别重要）
3、所有的非终端结点可以看成是索引部分，结点中仅含其子树(根结点)中的最大(或最小)关键字。

已上图为例简述B+树的查找过程，比如 查找30 ：
1、从根节点开始。进行 第1次 磁盘IO，把它load到内存去。拿30去内存里做比对，通过二分查找，快速定位，发现在1 5和56 之间
2、进行 第2次磁盘IO 找到这一页数据，我们把它加载到内存，发现介于 20-49 之间
3、进行 第3次磁盘IO ，把这个叶子结点load到内存进行比对，发现找到，再把 30 对应的 磁盘文件地址 去磁盘上找这一行数据。

或许你会问，可不可以把 所有索引元素的数据都放到根节点 上呢？这样岂不是1次磁盘IO，加载到内存中比对即可吗？

答：肯定是不行的，因为这样在数据量巨大的情况下，会瞬间使内存使用率过高，把内存撑爆，并且也不会很快，而且1次磁盘IO也弄不了这么多数据。

5.6、mysql索引为什么选择B+树而不选择B树？（重点）

1、树的高度决定：因为B+树节点不放数据，所以可以存放更多的索引节点
在这里插入图片描述
上图是B+树的结构：
mysql认为 每个结点就是1个页 ，默认 1页的大小是16KB 。那么我们可以 估算下3层高度能存储多少数据 。

一张表假设用 bigint做主键 ， 8B大小 ， 1个地址大概是6B 。那么 1页是16KB ，可以存放 16KB/14B=1170个结点 。第二层同理 1170个 ，那么叶子结点，最多也就1KB，这个叶结点16个。那么一共放 1170x1170x16=2190 万。这样的数据量也就用了3行。经过了3次磁盘IO就找到了元素。

mysql会把根节点常驻内存，那就更快了。高版本会把所有非叶子结点加载到内存，那么可能也就1次磁盘IO把叶子结点加到内存。

这是B树的本来样子，每个索引位置存放你想要的数据，可想而知每个节点字节很更大
在这里插入图片描述
我们估算B树存储2000多万数据得多高？
每个结点16个元素，默认每个结点还是16KB，1个结点1KB大小， 16/1 = 16 ， 16^7 = 268 435 456 ，可以看到存储相同数据量，B+树仅用3层,B树最少7层。
2、B+树可以很好的支持范围查找
假设我们找 大于20小于50 范围内的数据，从根节点出发， 找到叶子结点的20 ，沿着指针方向找到50就可以了。

B树没有指针，找完20，会继续从根节点往下找，效率会低得多。

5.7、哈希表（Hash，也是重点）

哈希算法：也叫散列算法，就是把 任意值(key) 通过 哈希函数 变换为 固定长度的 key 地址 ，通过这个地址进行具体数据的数据结构。 adddress = f(key)
在这里插入图片描述
哈希算法首先计算存储 id=7 的数据的物理地址 addr=hash(7)=4231 ，而 4231 映射的物理地址是 0x77 ， 0x77 就是 id=7 存储的额数据的物理地址，通过该独立地址可以找到对应 user_name='g' 这个数据。这就是哈希算法快速检索数据的计算过程。

算法时间复杂度分析来看，哈希算法 时间复杂度为 O（1） ，检索速度非常快。

不足之处1：哈希冲突

哈希函数可能对 不同的 key 会 计算出同一个结果 ，比如 hash(7) 可能跟 hash(199) 计算出来的结果一样。

常见处理方式：拉链法，即用链表把碰撞的数据接连起来。计算哈希值之后，还需要检查该哈希值是否存在碰撞数据链表，有则一直遍历到链表尾，直达找到真正的 key 对应的数据为止。
在这里插入图片描述
不足之处2：范围查找（致命之处）

用哈希算法实现的索引，范围查找怎么做呢？

简单的思路：一次把所有数据找出来加载到内存，然后再在内存里筛选筛选目标范围内的数据。但是这个范围查找的方法也太笨重了，没有一点效率而言。

6、索引的分类（实现上分类）

为了更好的理解接下来的内容，首先对数据库存储数据文件的形式进行简要说明。

Mysql 底层数据引擎以插件形式设计，最常见的是 Innodb 引擎 和 Myisam 引擎 。
比如下面的例子，Mysql 建立表的时候就可以指定引擎，就是分别指定了 Myisam 和 Innodb（默认引擎） 作为 user2 表和 user 表的数据引擎。
在这里插入图片描述

执行这两个指令后，系统出现了以下的文件，说明这两个引擎 数据 和 索引 的 组织方式 是不一样的。

Innodb 创建表后生成的文件有：

frm :创建表的语句
idb :表里面的 数据+索引文件

== Myisam 创建表后生成的文件有==

frm :创建表的语句
MYD :表里面的 数据文件 （myisam data）
MYI :表里面的 索引文件 （myisam index）

MyISAM 引擎 把数据和索引分开了， 一人一个文件 ，这叫做 非聚集索引方式 ；
Innodb 引擎 把数据和索引放在 同一个文件 里了，这叫做 聚集索引方式 。

6.1、聚集索引

6.1.1、定义

聚集（clustered）索引，也叫聚簇索引。

定义：数据行的物理顺序与列值（一般是主键的那一列）的逻辑顺序相同，一个表中只能拥有一个聚集索引。

单单从定义来看是不是显得有点抽象，打个比方：

一个表就像是我们以前用的新华字典， 聚集索引就像是拼音目录 ，而 每个字存放的页码就是数据物理地址 ，我们如果要查询一个“哇”字，我们只需要查询“哇”字对应在新华字典拼音目录对应的页码，就可以查询到对应的“哇”字所在的位置，而拼音目录对应的A-Z的字顺序，和新华字典实际存储的字的顺序A-Z也是一样的，如果我们中文新出了一个字，拼音开头第一个是B，那么他插入的时候也要按照拼音目录顺序插入到A字的后面，现在用一个简单的示意图来大概说明一下在数据库中的样子：
在这里插入图片描述
注：第一列的地址表示该行数据在磁盘中的物理地址，后面三列才是我们SQL里面用的表里的列，其中id是主键，建立了聚集索引。

结合上面的表格就可以理解这句话了吧： 数据行的物理顺序与列值的顺序相同 ，

如果我们查询id比较靠后的数据，那么这行数据的地址在磁盘中的物理地址也会比较靠后。
而且由于物理排列方式与聚集索引的顺序相同，所以也就 只能建立一个聚集索引 了。

更精确的定义请参考

6.1.2、Innodb 引擎的底层实现原理（聚集索引方式）

InnoDB 是聚集索引方式，因此数据和索引都存储在同一个文件里。

InnoDB 会根据 主键 ID 作为 key 建立索引 B+树 ，如左下图所示，而 B+树的叶子节点 存储的是 主键 ID 对应的数据 ，
- 比如在执行 select * from user_info where id=15 这个语句时， InnoDB 就会查询这颗主键 ID 索引
  B+树，找到对应的 user_name='Bob' 。

在这里插入图片描述
常见疑问

1、当我们为表里某个字段加索引时 InnoDB 会怎么建立索引树呢？

比如我们要给 user_name 这个字段加索引：

InnoDB 会建立 user_name 索引 B+树 ，节点里存的是 user_name 这个 KEY ，叶子节点存储的数据的是主键 KEY。
- 叶子存储的是主键 KEY！！！ 拿到 主键 KEY 后， InnoDB 才会去主键索引树里根据刚在 user_name 索引树 找到的 主键 KEY 查找到对应的数据。

2、为什么 InnoDB 只在主键索引树的叶子节点存储了具体数据，但是其他索引树却不存具体数据呢，而要多此一举先找到主键，再在主键索引树找到对应的数据呢?

因为 InnoDB 需要节省存储空间。一个表里可能有很多个索引，InnoDB都会给每个加了索引的字段生成索引树，如果每个字段的索引树都存储了具体数据，那么这个表的索引数据文件就变得非常巨大（数据极度冗余了）。
从节约磁盘空间的角度来说，真的没有必要每个字段索引树都存具体数据，通过这种看似“多此一举”的步骤，在牺牲较少查询的性能下节省了巨大的磁盘空间，这是非常有值得的。

3、 MyISAM 查询性能比 InnoDB 更高？
在这里插入图片描述

聚簇索引（InnoDB）
- 辅助索引的叶子节点的data存储的是主键的值；
- 主索引的叶子节点的data存储的是数据本身，也就是说数据和索引存储在一起；
- 索引查询到的地方就是数据（data）本身，那么索引的顺序和数据本身的顺序就是相同的；
非聚簇索引（MyISAM ）
- 主索引和辅助索引的叶子节点的data都是存储的数据的物理地址 ，也就是说索引和数据并不是存储在一起的，数据的顺序和索引的顺序并没有任何关系，也就是索引顺序与数据物理排列顺序无关。

综上特点：

MyISAM 直接找到物理地址后就可以直接定位到数据记录；
InnoDB 查询到叶子节点后，还需要再查询一次主键索引树，才可以定位到具体数据。
等于 MyISAM 一步就查到了数据，但是 InnoDB 要两步，那当然 MyISAM 查询性能更高。

6.2、非聚集索引方式

6.2.1、定义

定义：该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同，一个表中可以拥有多个非聚集索引。

其实按照定义，除了聚集索引以外的索引都是非聚集索引，只是人们想细分一下非聚集索引，分成普通索引，唯一索引，全文索引。如果非要把非聚集索引类比成现实生活中的东西，那么非聚集索引就像新华字典的偏旁字典，他结构顺序与实际存放顺序不一定一致。