【MySQL】深入了解索引背后的内部结构
目录
索引的认识:
作用:
索引的使用:
索引底层的数据结构:
哈希表
AVL树
红黑树
B树:
B+树:
B+树搜索:
索引的认识:
索引是数据库中的一个数据结构,用于加速查询操作。
作用:
- 数据库中的表、数据、索引之间的关系,类似于书架上的图书、书籍内容和书籍目录的关系。
- 索引所起的作用类似书籍目录,可用于快速定位、检索数据。
- 索引对于提高数据库的性能有很大的帮助
比如一本字典,如果一一的查找,这个效率将会很低下。
但如果给它加上标签的话,就一下可以找到你想搜索的东西,所有它大大提高了我们的查询速度。
索引可以提高查询速度,但可能会拖慢增删改的速度,后续对数据进行增删改的操作,都是要同步索引的。但在实际开发中,查询的频率要远远高于增删改的操作,所以这是利大于弊
索引的使用:
//查看索引
show index from 表名;
//创建索引
//对于非主键、非唯一约束、非外键的字段,可以创建普通索引
create index 索引名 on 表名(字段名);
//删除索引
drop index 索引名 on 表名;
操作:
注意:
索引的创建也是一个危险操作!!!
针对空表或者数据量比较小的表中创建索引没有任何问题,但如果表中数据很大,此时创建索引将会引起大量的CPU/硬盘IO的消耗,可能会把MySQL直接搞挂;解法方法:
1.预测哪个索引可能会频繁使用,根据建议,提前给它创建好
2.引入新的数据库服务器,提取创建好索引,将旧的数据库服务器数据慢慢导入到新服务器中(常规做法);
索引底层的数据结构:
索引一定是引入了一些额外的数据结构,加快了查询速度!
引入索引的目的,就是通过其他的数据结构,来加快查询的速度,以便减小表的遍历!
那么哪些数据结构可以加快查询速度?
1.顺序表: 随机访问,并且插入删除效率低下 不适合加快查询速度
2.链表:从头依次遍历,更不能加快查询速度
3.哈希表
哈希表
众所周知,哈希表查询速度是最快的,构造出合适的哈希函数,可以达到O(1)查询速度,即使在极端情况下,将所有值通过哈希函数映射到一个同哈希桶上,达到O(N),这种情况一般只存在于理论上,现实中几乎不可能出现。最坏情况下,设置哈希桶上的每个链表长度为M,O(M)也是近视O(1)。
虽然哈希表的查询速度特别快,但是它只能查找特定的某个值(key),并不是一连串的范围,但数据库中一般要我们查找的情况下是一系列的范围数据,所以并不适合数据库查询;
4.树
二叉搜索树的数据 中序遍历是连续范围的数据 是有序的,可以进行范围查询,如果是一个比较平衡的二叉树搜索树 遍历速度O(logN) 最坏情况下变成一个链表,就会变成O(N)速度
AVL树
是一颗严格的二叉搜索树,左右子树高度不能超过1 所以遍历速度O(logN) 但是当你非常严格的情况下,每次进行增删改的操作,从而触发旋转操作,每次旋转,都会有开销。
红黑树
而红黑树并没有AVL树那么严格,触发旋转的概率很小,虽然没有AVL树平衡,但是查询速度也没差多少
红黑树里面的数据 中序遍历是连续范围的数据 是有序的,可以进行范围查询,但由于它是二叉类型的,如果数据量特别大,这会让树的高度变得非常高,树的高度每加一层,比较次数就会增加一次,由于数据都是保存在硬盘中,就会多要一次硬盘IO操作了,它查询的效率就会变得慢,所以并不适合大规模的数据
因此就引入了B树,它是一个N叉搜索树,同样数量的数据,需要的节点变少了,树的高度大大降低了,从而减小了遍历的次数。
B树:
以上是B树的大概形状
1.每个节点上的key是有序的,比较的时候可以直接用二分查找
2.B树会控制每个节点上的key的数量,如果key太多,就会分裂更多的叶子节点出来
3.多个数据,都是放在一块连续的存储空间上,比较的时候,使用一次IO就可以遍历完整个节点 因此B树更适合对应这种数据量的范围查找,但数据库索引的最终形态是B+树,B树的升级版
B+树:
B+树也是N叉树 对比B树 B+树做了进一步优化
1.B+树每个父节点的元素都会在子节点的最大值出现
2. B树的每个节点都包含键值(Key)和相应的值(Value)(包括叶子节点和非叶子节点)。而B+树非叶子节点只存储键值(Key)也就是ID,叶子节点存储所有的数据,并且每个叶子节点是以链表结构存储起来的,B+树可以通过简单的顺序访问叶子节点来高效地执行范围查询。
3.进行每次查询操作,都会落到最终的叶子节点上,每次经历的硬盘IO次数都是稳定的(稳定做一件事在计算机中很重要)
4. B+树的非叶子节点都存储的数据比较小,所有可以存储在内存中,进一步减小硬盘IO的次数
特性 | B树 | B+树 |
---|---|---|
数据存储位置 | 数据存储在所有节点(包括内部节点) | 数据只存储在叶子节点 |
内部节点 | 存储键和值 | 仅存储键(不存储数据) |
叶子节点链接 | 无链接 | 叶子节点通过链表连接 |
查询效率 | 适合单点查询 | 更适合范围查询 |
范围查询性能 | 较差 | 非常高效(通过叶子节点链表) |
树的高度 | 相对较高 | 较低 |
内存/磁盘利用 | 内存和磁盘利用相对较低 | 更高效,能容纳更多节点 |
Mysql中支持多种存储引擎,其中InnoDB最常用(也是面试做常考查的内容),不同的存储引擎使用的索引也是不同的
B+树搜索:
下面来介绍B+树在有无索引的情况下如何检索:
CREATE TABLE employees (
id INT PRIMARY KEY,
name VARCHAR(50),
age INT
);
在这张表中,id为主键,所有默认会创建索引,name和age列则没创建索引
1)遍历有主键索引的列
SELECT * FROM employees WHERE id = 5;
MySQL 会利用 B+ 树索引,直接从根节点开始查找,快速定位到 id = 5
的叶子节点,查询的时间复杂度为 O(log N)。
2)遍历无索引的列
SELECT * FROM EMPLOYEES WHERE NAME = 'zhangsan' ;
MySQL 只能通过全表扫描来查找数据,效率较低,尤其在表的数据量较大时。
3) 遍历有索引的列却不是主键索引
create index index_id on employees(age) ;
此时为age列创建索引
select * from employees where age = 20 ;
此时根据关于age的B+树找到对应叶子节点,但此时非主键索引的B+树的叶子节点存储的都是主键Id,因此找到Id之后,再在id主键索引的B+树中遍历 找到对应的叶子节点,此时叶子节点才正在存储我们想要找到的数据;
因此需要遍历俩次B+树,第一次找到主键Id,再在主键Id的B+树找到对应的值;
总结:
- 没有索引的情况下,MySQL 只能通过全表扫描来查找数据,效率较低,尤其在表的数据量较大时。
- 使用 B+ 树索引的情况下,MySQL 可以通过 B+ 树的查找机制(O(log N) 的复杂度)高效地定位记录,从而大大提升查询性能。B+ 树支持点查询和范围查询,尤其对于大数据量的表,具有非常重要的优化作用。