开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 深入理解mysql索引机制 -> 正文阅读

[数据结构与算法]深入理解mysql索引机制

一.索引介绍

1.什么是索引

????????索引是为了加速对表中数据加速检索的一种分散存储的数据结构，旨在索引中返回查找的数据或者指向数据的指针.通说的来讲:索引就好比一本书的目录，它能让你更快的找到自己想要的内容,让获取的数据更有目的性，从而提高数据库检索数据的性能

?在上表中，如果没有索引，我们通过select * from user where id = 40需要进行全表扫描，如果有索引，我们只需要对上表进行二分查找，即找到索引对应的行数据

2.索引分类

单列索引:即一个索引只包含单个列，一个表可以有多个单列索引

组合索引:即一个索包含多个列

普通索引,唯一索引,主键索引,组合索引,前缀索引?

2.1 普通索引

这是最基本的索引，它没有任何限制,有如下几种方式创建:

// 1.创建索引
CREATE INDEX indexName ON mytable(username(length));
//如果是CHAR,VARCHAR类型,length可以小于字段实际长度;如果是BLOB和TEXT类型，必须指定length，下同

//2.修改表结构
ALTER mytable ADD INDEX [indexName] ON (username(length)); //创建表的时候直接指定
CREATE TABLE mytable(
    ID INT NOT NULL,??? 
    username VARCHAR(16) NOT NULL,?? 
    INDEX [indexName] (username(length))?? 
);

//删除索引
DROP INDEX [indexName] ON mytable;

2.2 唯一索引

它与前面的普通索引类似，不同的就是：索引列的值必须唯一，但允许有空值。如果是组合索引，则列值的组合必须唯一。有如下几种方式创建:

//创建
CREATE UNIQUE INDEX indexName ON mytable(username(length))
//修改表结构
ALTER mytable ADD UNIQUE [indexName] ON (username(length))
//创建表的时候直接指定
CREATE TABLE mytable(?? 
    ID INT NOT NULL,??? 
    username VARCHAR(16) NOT NULL,?? 
    UNIQUE [indexName] (username(length))?? 
);

2.3主键索引

它是一种特殊的唯一索引，不允许有空值。一般是在建表的时候同时创建主键索引,代码如下:

CREATE TABLE mytable(?? 
    ID INT NOT NULL,??? 
    username VARCHAR(16) NOT NULL,?? 
    PRIMARY KEY(ID)??
);

// 当然也可以用 ALTER 命令。记住：一个表只能有一个主键

2.4组合索引

为了形象地对比单列索引和组合索引，为表添加多个字段,代码如下:

//1.创建表
CREATE TABLE mytable(?? 
ID INT NOT NULL,??? 
username VARCHAR(16) NOT NULL,??
 city VARCHAR(50) NOT NULL,??
 age INT NOT NULL? 
);

//2.为了进一步榨取MySQL效率，就要考虑建立组合索引。就是将 name, city, age建到一个索引里,代码如下:
ALTER TABLE mytable ADD INDEX name_city_age (name(10),city,age);

2.5前缀索引?

根据字段的前N个字符建立索引,代码如下:

#创建前缀索引 
mysql> alter table student2 add index idx_sname2(sname(3));

3.查看索引的三种方式?

#查看索引三种方式
mysql> desc student4;
mysql> show index from student4;
mysql> show create table student4;

???4.创建索引总结

????????4.1.不要在所有字段上都创建索引
????????4.2.如果有需求字段比较多，选择联合索引
????????4.3.如果有需求字段数据比较大，选择前缀索引
????????4.4.如果可以创建唯一索引，一定创建唯一索引

5.什么情况下有索引，但用不上

索引并不是时时都会生效的，比如以下几种情况，将导致索引失效：

5.1.如果条件中有or，即使其中有部分条件带索引也不会使用(这也是为什么尽量少用or的原因)，

注意：要想使用or，又想让索引生效，只能将or条件中的每个列都加上索引

5.2.对于多列索引，不是使用的第一部分，则不会使用索引

5.3.like查询是以%开头,索引才能生效

5.4.存在索引列的数据类型隐形转换，则用不上索引，比如列类型是字符串，那一定要在条件中将数据使用引号引用起来,否则不使用索引

5.5. where 子句里对索引列上有数学运算，用不上索引

5.6. where 子句里对有索引列使用函数，用不上索引

5.7.如果mysql估计使用全表扫描要比使用索引快,则不使用索引:比如数据量极少的表

6.什么情况下不推荐使用索引

6.1 数据唯一性差（一个字段的取值只有几种时）的字段不要使用索引:

????????比如性别，只有两种可能数据,意味着索引的二叉树级别少，多是平级,这样的二叉树查找无异于全表扫描。

6.2 频繁更新的字段不要使用索引:

????????比如logincount登录次数，频繁变化导致索引也频繁变化，增大数据库工作量，降低效率。

6.3 字段不在where语句出现时不要添加索引,如果where后含IS NULL /IS NOT NULL/ like ‘%输入符%’等条件，不建议使用索引; 只有在where语句出现，mysql才会去使用索引

6.4 where 子句里对索引列使用不等于（<>），使用索引效果一般

二.深入理解mysql B+tree索引机制

Mysql数据库为什么要使用B+Tree作为索引的数据结构?

1.二叉树为什么不可以?

二叉树查找元素的复杂度为O(log2n)

二叉树查找相当于一个二分查找法，比如查找7，7小于10，则匹配根节点的左子节点，7大于5，匹配5节点的右子节点，7命中，但是现在出现一个问题，在对于ID自增的表中，主键索引则为如下图所示，成了一个线性链表，当查询节点为4的时候，则会进行全表扫描。由于该问题的存在，所以二叉查找树不适合作为索引的数据结构

2.平衡二叉查找树为什么也不可行?

为了解决二叉树存在线性链表(容易导致全表扫描)的问题，可能会利用平衡二叉查找树来解决问题,如下图: 节点的子节点高度差不能超过1，比如图中的20节点，左子节点高度为1，右子节点高度为0，子节点高度差为1，所以?满足平衡二叉查找树的规则

衡二叉查找树索引保存数据的方式有两种：

????????1.数据区保存id 对应行数据的所有内容

????????2.数据区保存的真正数据的磁盘地址

假设上图存储的是id索引，对id=8的数据进行索引:

????????1. 把根节点加载进内存，8小于10，加载根节点的左子树 ?

???????? 2. 把5加载进内存，8大于5，加载5节点的右子树 ?

???????? 3. 此时发现id命中，将对应的数据区返回

平衡二叉树的查找效率也能达到O(log2n)，而且不会出现线性链表问题，那么为什么不使用平衡二叉树作为存储索引的数据结构呢？

搜索效率不足:在树结构中，数据所处的深度，决定了搜索时的IO深度(Mysql将每个节点设置为一页大小，一次IO读取一页/一个节点)，如上图搜索节点8的数据，需要进行3次IO，如果数据量很大，树足够高，那么搜索的效率也就非常低了
查询不稳定:对于根节点，只需要1次IO即可查到，对于叶子节点或支节点，则需要多次IO。可能查询9和10节点所花费的时间会相差很多，不符合逻辑
节点存储的数据内容太少:操作系统和磁盘之间一次数据交换是以页(该树中为一个节点)为单位的，一页大小为4k，即每次IO操作会将4K数据加载进内存中。由于二叉树的每个节点只保存一个关键字，一个数据区，两个子节点的引用，并不能填满4k的大小，所以每次IO操作只加载了一个关键字，对于树足够高，且搜索的节点又恰好位于叶子节点或者支节点，那么IO的次数也会上升了(IO操作在计算机中是非常耗费时间的)

3.B tree（多路平衡查找树）

B Tree是一个绝对平衡树，即所有叶子节点都在同一高度

上图为一个2-3树（每个节点存储2个关键字，有3路），多路平衡查找树也就是多叉的意思，从上图中可以看出，每个节点保存的关键字的个数和路数关系为：关键字个数 = 路数 – 1。

假如从上图取出id = X的数据，搜索过程如下：

1.取出根磁盘块，加载40和60两个数据块

2.如果X=40，则命中，如果X<40，则走P1；如果40<X<60，则走P2；如果X>60，则走P3

3.根据以上规则命中后，接下里加载相对应的数据，数据区中存储的是具体的数据或者是指向数据的指针

为什么说BTree解决了平衡二叉树的问题？

答：B Tree能够很好的利用操作系统和磁盘的交互特性，Mysql利用磁盘的预读能力，将一页大小设置为16k，即将一个节点的大小设置为16k，一次IO将一个节点加载进内存中。假设关键字类型为int，即4字节，在不考虑子节点引用的情况下，则上图中每个节点大约可以存储(16*1024)/8=2000个关键字，路数为2001条。对于二叉树，3层高度，最多只能保存7个关键字，对于B树而言，3层高度可以存储约2000个关键字，可见一斑

注意点:

在B Tree保证树的平衡过程中，每次关键字的变化，都会导致树结构发生变化。所以在创建索引的时候要根据情况而定，而不是把所有字段都创建索引，创建冗余索引只会对数据在进行增删改的时候增加性能上的消耗

B树确实已经很好的解决了问题，我先这里先继续看一下B+Tree结构，再来讨论BTree和B+Tree的区别。

先看看B+Tree是怎样的，B+Tree是B Tree的一个变种，在B+Tree中，B树的路数和关键字的个数的关系不再成立了，数据检索规则采用的是左闭合区间，路数和关键个数关系为1比1，具体如下图所示：

在这里插入图片描述

假设寻找id=1的数据：则

1.取出根磁盘块，加载1，28，66三个关键字

2.X<=1走P1，加载1，10，20三个关键字

3.X<=1走P1，加载1，8，9三个关键字

4.已经到达叶子节点，命中1，接下来加载对应的数据，图中叶子节点对应的磁盘块存储的是具体数据

3.1 B Tree和B+ Tree区别是什么？

1.B+ Tree关键字的搜索采用的是左闭合区间，原因是要更好的支持id自增

2.B+ Tree 中根节点和支节点中没有数据区，关键字对应的数据区只保存在叶子节点中；而在B Tree中，如果在非叶子节点上命中，则?会直接返回数据

3.在B+ Tree中，叶子节点不会保存子节点的引用

4.B+ Tree中，叶子节点是顺序排列的，叶子节点有指针引用的关系

3.2 Mysql为什么最终要选用B+ Tree？

1.B Tree能解决的问题，B+ Tree也能解决，并且能更好的支持ID自增，降低树的高度，增大节点存储关键字能力

2.B+ Tree扫库扫表能力更强:对于B+ Tree只需要遍历所有叶子节点即可(数据都在叶子节点上，叶子节点相互有引用)；对于B Tree则?要遍历整棵树

3.B+ Tree磁盘读写能力更强:B+ Tree的根节点和支节点不保存数据，所以节点保存的关键字数量要比B Tree多的多；并且叶子节点不?保存子节点的引用，能用于保存更多的关键字和数据

4.B+ Tree支持天然排序功能

5.B+ Tree查询性能稳定:每次查询数据都会到叶子节点上去查找

4.Mysql 的B+ Tree具体落地形式

根据B+Tree索引结构不同的两种存储引擎（MYISAM 和 INNODB）而实现B+ Tree:

MYISAM存储引擎存储数据库数据，一共有三个文件：?Frm：表的定义文件; MYD：数据文件，所有的数据保存在这个文件中; MYI：索引文件。

Innodb存储引擎存储数据库数据，一共有两个文件(没有专门保存数据的文件)：???Frm文件：表的定义文件; Ibd文件：数据和索引存储文件,数据以主键进行聚集存储，把真正的数据保存在叶子节点中

4.1MyISAM存储引擎

数据和索引的关系如下：

如何查找数据的呢？?如果要查询id = 40的数据：先根据MyISAM索引文件（如上图左）去找id = 40的节点，通过这个节点的数据区拿到真正保存数据的磁盘地址，再通过这个地址从MYD数据文件（如上图右）中加载对应的记录。

如果有多个索引，表现形式如下：

4.2Innodb存储引擎?

Innodb主键索引为聚集索引,概念：数据库表行中数据的物理顺序和键值的逻辑顺序相同

聚簇索引：将数据存储与索引放到了一块，找到索引也就找到了数据
非聚簇索引：将数据存储于索引分开结构，索引结构的叶子节点指向了数据的对应行，myisam通过key_buffer把索引先缓存到内存中，当需要访问数据时（通过索引访问数据），在内存中直接搜索索引，然后通过索引找到磁盘相应数据，这也就是为什么索引不在key buffer命中时，速度慢的原因

Innodb以主键索引来聚集组织数据的存储，下面看看Innodb是如何组织数据的