开发: 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索引原理分析 -> 正文阅读

[大数据]mysql第五话 - mysql索引原理分析

在工作中听到最多的一句话，sql查询太慢怎么办？加个索引吧！ 今天来探索一下mysql的索引原理。

1.索引是什么?

可以毫不夸张的说，系统中sql的快慢，是能直接决定你系统的快慢的。但是sql的快慢就看索引的好坏了。
索引是数据库系统中的一个排序的数据结构，以助于快速查询和更新数据表中的数据。
索引的作用是做数据的快速检索。
列如字典中的key值，一本书的目录，一个饭店的菜单等等。

2.索引划分

PRIMARY 主键索引，唯一且not null

ALTER TABLE `table`
	ADD PRIMARY KEY (`id`);

unique 唯一索引

ALTER TABLE `table`
	ADD UNIQUE INDEX `name` (`name`);

key 普通索引

ALTER TABLE `table`
	ADD INDEX `name` (`name`);

fulltext 大文本索引

ALTER TABLE `user_info`
	ADD FULLTEXT INDEX `book_names` (`book_names`);

spatial 空间索引
空间索引是对空间数据类型的字段建立的索引，创建空间索引的列，必须将其声明为NOT NULL，空间索引只能在存储引擎为MYISAM的表中创建

3.索引数据结构选型

各种二叉树数据结构在线演示传送门，下面贴的传送门均来源此地址

3.1 哈希表(Hash)

innoDB自适应的。
哈希算法：也叫散列算法，就是把任意值(key)通过哈希函数计算得到固定长度的key地址，通过这个地址可以定位到具体数据的数据行。
hash图
以上数据均属虚构！例如有这样的一条sql查询：

select * from user where id = 7

通过id这个索引key进行hash函数计算定位到14这个桶0x72，这个地址就是存储id=7数据的物理地址，取值复杂度为O(1)
但是Hash有个众所周知的问题就是哈希碰撞。也就是不同key值可能会计算得出同一个结果，解决哈希碰撞的一个常见处理方式就是链式寻址法
如果是一条 id>7的范围性查询，hash寻址法就失效了，等同于全表扫描了。

3.2 二叉查找树(BST)

二叉树特点：

1.二叉树的时间复杂度为 O(logn)
2.二叉树一个节点只能由两个子节点
3.左子节点小于父节点，右子节点大于父节点

二叉树图
随着数据的插入，形成了上面的二叉树结构。
二叉树是一种快速查找的结构，时间复杂度是O(logn)。例如检索id=7的数据，先取出6的右子节点，然后再取出8的左子节点，时间上能节省一半。

但是普通的二叉树有个致命的缺点，极端情况下回蜕变成线性链表，查询也变成复杂度O(n)，检索速度大大降低
二叉退化
在mysql中主键自增是很常见的情况，如果采用二叉树作为索引的数据结构，必然会出现这种情况。

3.3 AVL树和红黑树

二叉查找树存在不平衡问题，因此在可以通过节点上自动旋转来让二叉树始终保持基本平衡的状态，基于这种思路的自调整平衡状态的二叉树就有AVL树和红黑树。

3.3.1 红黑树

传送门，红黑树动画在线演示
红黑树的特点：

1.每个节点都是黑色或者红色
2.根节点是黑色
3.每个叶子节点是黑色
4.如果一个节点是红色的，那它的子节点一定是黑色
5.从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点

右倾红黑树

从上图可以看出问题，新增id为16或者查找id=15的时候需要计算节点数为6次，而且数据库主键一般都是自增百万千万的，“右倾“这种趋势是一值存在的，不管是插入还是新增都有一定的性能影响。

3.3.2 AVL树

官方：AVL是一个绝对平衡的二叉树。
通过自动旋转调整为绝对平衡的二叉树，因此在调整二叉树的形态上调整会消耗更多的性能。
传送门，AVL树动画在线演示
平衡二叉树
鉴于二叉树的特性，AVL树不存在红黑树的“右倾”问题，这从根本上解决了红黑树的问题
AVL树特点：

1.不错的查找性能(O(logn))，不存在极端低效查找
2.可以实现范围查询，数据排序

但是数据库的查询瓶颈在于磁盘IO，如果使用的是AVL树，查询大数据ID时存在的IO次数还是会有很多次，这是不能接受的。

3.4 B树

磁盘IO有个特点，就是读取1B和读取1KB数据所消耗的时间是一致的。为了减少磁盘IO，我们可以在一个树节点上多存储一点数据，每次磁盘IO就多加载一点到内存，这就是B树，B+树的设计原理。
传送门，B树动画在线演示

如上图：三阶的B树，查询id=7的数据只需要进行两次IO，查询结果是优于AVL树的。
基于每次磁盘IO读取数据大小不同但时间一致的情况，每个节点适当的增加key的存储，也是能达到优秀的检索速度的。
下图为4阶的B树。
在这里插入图片描述
B树的优点：

1.B树的检索复杂度为O(h*logn)，h为树高，n为关键节点个数
2.能有效的检索磁盘IO
3.支持范围查找

3.5 B+树

B+树是B树的一种变体，目前mysql的索引数据结果正是B+树，相比B树B+树有什么不同呢？
先看图：
B+树
从上图和经过多方资料查阅：

B树的每个叶子节点都会存有数据，而B+树的非叶子节点存的是指针地址，只有叶子节点存的是数据，这里的数据基于存储引擎的不同存储的数据也不同。
B+树的叶子节点是用了一个链表串联起来的，便于范围查找。

而这个链表本身就是有序的，在数据范围查询时，效率有效的提升。所有说作为Mysql的索引的数据结构最为合适。

4.Mysql中 InnoDB和Myisam引擎索引的实现

4.1 Myisam引擎

先回顾一下Myisam引擎的特点，查询基于内存，性能极佳，但是不支持事务。
创建代码：

CREATE TABLE `test_myisam` (
	`id` BIGINT NOT NULL AUTO_INCREMENT,
	`name` VARCHAR(50) NULL,
	`status` INT NULL,
	PRIMARY KEY (`id`)
)
COLLATE='utf8_general_ci'
ENGINE=MyISAM
;

查看生成目录

show global variables like '%datadir%'

来到对应目录可以看到有以下文件，frm是每个表都有的存储的是表基本信息。

test_myisam.frm 创建表的语句
test_myisam.MYD 表中的数据文件(myisam data)
test_myisam.MYI 表里面的索引文件(myisam index)

4.2 myisam底层索引的实现

Myisam使用的是索引文件和数据文件分开的形式，这种叫做非聚集索引。
Myisam采用非聚集索引方式，即数据页和索引落在了不同的两个文件上，那么索引树的叶子节点存储的就是数据页中的物理地址，只用拿到这个这个物理地址就能拿到想要的数据了。接下来看图更加明确：
myisam
当再添加其他字段为索引时，会再次生成对应字段的索引树，叶子节点存储该数据的物理地址.
多索引查询

4.3 InnoDB引擎

InnoDB引擎的特点：默认存储引擎，事务安全特性、奔溃恢复能力、行级别锁、一致性非锁定性读
创建代码：

CREATE TABLE `test_innoDB` (
	`id` BIGINT NOT NULL AUTO_INCREMENT,
	`name` VARCHAR(50) NULL,
	`status` INT NULL,
	PRIMARY KEY (`id`)
)
COLLATE='utf8_general_ci'
;

来到对应目录可以看到有以下文件，frm是每个表都有的存储的是表基本信息。

test_innodb.frm 创建表的语句
test_innodb.ibd 表中的数据+索引

4.4 innoDB底层索引的实现

索引即数据数据即索引。如果在有主键的情况下会根据主键建立聚集索引。如果没有主键的情况下就看索引逻辑顺序和数据行的存储顺序一致的字段建立聚集索引。
看图分析，以id作为聚集索引的两种查询：
innoDB多索引
如上图所示，InnoDB 是聚集索引方式，所以索引和数据会存储在一个文件里面。
那么如果把name也添加为索引了呢，那就是右图那种索引数，物理地址指向的是聚集索引的地址，再根据聚集索引树查找到指定的数据。