为什么MySQL不使用红黑树做索引
你好,我是猿java。
提到MySQL索引,相信使用过的小伙伴并不陌生,平常工作中,我们经常会加索引来提升查询效率,那么,为什么一个慢查询加上索引查询速度就能提升一个档次?索引后面的实现机制到底是什么?今天就让我们一起来探讨这个话题。
申明:本文说的磁盘是指普通的机械磁盘
1、索引是什么?
比如小学语言,要快速找到某篇课文,我们会通过目录,然后定位到页码,最后再定位到课文。其实,索引就是数据库的“目录”,当你的数据库中的数量达到千万级别时,如果没有这个“目录”,那么要去查找某条数据,那时间肯定会比较漫长,为了能提高查询效率,MySQL提供了索引这样一个机制。
2、索引常见的数据结构
在日常工作中,用于索引的数据结构常见的有3种:哈希表、有序数组和搜索树。下面给出一张navicat可视化工具创建索引的截图,可以看出它创建索引使用了 BTREE/HASH两种。(截图是navicat连接mysql数据库)
2.1、哈希表
哈希表是一种以key-value键值对存储数据的结构,比如:java的 hashmap, redis的key-value都是这样一种形式。hash表的实现思路也很简单:用一个哈希函数把 key 换算成数组确定的位置,然后把 value 放在数组的这个位置。
从上图我们可以看到,当key的hash值相同的时候,会采用链表的方式把value串起来。
hash表的问题
随着数据量的增多,不同key经过哈希计算后结果一样,这种情况叫做hash碰撞。处理hash碰撞的一种方法是链表,但是当数据量比较大时,链表的长度还是会比较大,性能开销就在链表查询上。
哈希表是散列存储,因此这种结构适用于只有等值查询的场景,比如 Memcached 及其他一些 NoSQL 引擎。
2.2、有序数组
如下图,如果数据按照id的升序存放到数组中,就形成了一个有序数组,这样既能根据等值查询,也方便范围查询。
有序数组问题
如果仅仅看查询效率,有序数组是比较好的数据结构,但如果有数据的插入和删除,插入和删除点后面的数据需要移动,所以整体性能会下降,因此,有序数组只适合静态存储引擎。
2.3、搜索树
2.3.1 二叉树(Binary Tree)
每个节点最多只能有两个子节点就是二叉树。
二叉树的定义很简单,它是很多其他搜索树的基础,下面给出一张二叉树的示意图
2.3.2 二叉搜索树
二叉查找树(Binary Search Tree),是一种特殊的二叉树,其的特点如下: 左子树节点比父节点小,右子树节点值比父节点大。
根据二叉搜索树的特点可以使用二分查找法,比如,在二叉查找树中查询5。
首先,从根节点开始遍历,5 > 3,可以定位5在节点3的右子树。
其次,遍历节点3的右子树,5 < 6,可以定位 5在节点6的左子树。
最后,遍历节点6的左子树,因为左子树只有一个节点5,5=5,即目标值。
二叉搜索树的问题
当数据是有序增长,极端情况下,整个二叉搜索树就会变成一棵斜树。
2.3.4 平衡二叉树
平衡二叉树(Balanced Binary Search Tree),又被称为AVL树,是为了解决二叉树退化成链表而诞生的,其特点如下: 每个节点的左子树和右子树的高度差至多等于1。 为了解决二叉搜索树在极情况下变成斜树的问题,平衡二叉树增加了 左右子树的高度差 小于等于1.
问题:
平衡二叉树追求绝对严格的平衡,平衡条件必须满足左右子树高度差不超过1,该规则在于频繁的插入、删除等操作的情景性能肯定会出现问题,因此诞生了红黑树。
2.3.5 红黑树
1 | 红黑树是一种特殊的平衡二叉树,主要特点如下: |
红黑树如下图所示:
2.3.6 B-树(Balance Tree)
1 | B-树的英文是 Balance Tree,也就是平衡的多路搜索树,它的高度远小于平衡二叉树的高度。在文件系统和数据库系统中的索引结构经常采用 B 树来实现, |
B-树示意图:
2.3.7 B+树
B+树是基于B-树做了优化,B+树和B-树的差异如下:
1 | 有k个孩子的节点就有k个关键字。也就是孩子数量=关键字数,而B-树中,孩子数量=关键字数 +1。 |
B+树示意图:
问题
上面介绍了常见的搜索树,那么MySQL是使用哪一种树作为索引机制呢?
答案是:在MySQL中,索引是在存储引擎层实现的,所以并没有统一的索引标准,
问题1:为什么MySQL选择B+树做索引而不是其它的树?
MySQL的数据都是存放在磁盘,因此磁盘IO是MySQL的性能瓶颈,而二叉树,二叉搜索树,二叉平衡树,红黑树 都属于二叉树,当MySQL表中的数据量比较大时,索引的体积也会很大,树高就会很大,内存放不下的需要从磁盘读取,树的层次太高的话,读取磁盘的次数就多了,影响MySQL的使用性能。
问题2:B+树是怎么实现索引?
我们从MyISAM和InnoD两个引擎分别讲解
MyISAM引擎
MyISAM采用的非聚簇索引,B+树的非叶子节点存储索引值和指向子节点的指针,叶子节点上存放的是索引值和数据在磁盘上的物理地址,所以通过索引定位到数据地址后,需要到磁盘上回表获取数据,索引模型示意图如下:
Innodb引擎
Innodb采用的聚簇索引(主键索引),B+树的非叶子节点(内部节点)存放的是索引值和指向子节点的指针,叶子节点上存放的是索引值和数据。
非聚簇索引,B+树的非叶子节点存储索引值和指向子节点的指针,叶子节点存放的是索引值和聚簇索引值。因此非聚簇索引需要先遍历非聚簇索引B+树定位到聚簇索引的值,再到聚簇索引上回表获取数据。
聚簇索引的优点:可以避免每棵索引树上都存放数据,使得在相同的内存空间下存放的更多的索引节点,减少磁盘IO。
聚簇索引示意图如下:
非聚簇索引示意图如下:
聚簇索引和非聚簇索引
聚簇索引:将数据存储与索引放到了一块,找到索引也就找到了数据。
索引覆盖
在当前索引树上能直接查找所需结果,不需要回表,这就是索引覆盖。
比如上面的案例:
select id from user where age = 30 and sex = ‘男’;
因为id已经在当前索引的叶子节点,所以不需要到聚簇索引上回表,因此这就是一个索引覆盖的场景。由于覆盖索引可以减少树的搜索次数,显著提升查询性能,所以使用覆盖索引是一个常用的性能优化手段。
联合索引
联合索引是指将表中多个字段联合组合成一个索引,比如:index(age, sex)
那么联合索引是如何用B+树实现的呢?
场景:查询用户表中年龄为30岁的男性
表结构:
1 | mysql> create table user( |
联合索引在 B+树索引模型示意图如下:
查询分析:
1 | 首先,从根节点根据组合索引里面的所有字段进行精确匹配查到到age=30 and sex='男'的记录有两条; |
最左前缀原则
在日常的工作中,我们发现 查询条件比较多,比如上面的用户表,有根据age和sex查询,有根据name和age查询,也有根据name和sex查询,各种查询组合,那是不是都要为它们创建一个索引呢?
答案是不一定。B+树 可以利用索引的“最左前缀”来定位记录。
最左前缀可以是联合索引的最左 N 个字段,也可以是字符串索引的最左 M 个字符
1 | 比如:联合索引index(a, b, c) |
示例:
场景:查询用户表中姓刘的男性
联合索引:index(name, sex)
B+树索引模型示意图如下:
查询分析:
1 | 首先,从根节点查到第一个'刘'开头的记录是id2,然后向后遍历,直到不满足条件为止,最后结果id2,id3两条; |
问题3:一个三层的B+树可以存放多少行数据呢?
1 | 在Innodb存储引擎里面,最小的存储单元是页(page),一个页的大小是16KB, |
LSM-Tree
B+树的数据都存储在叶子节点中,而叶子节点一般都存储在磁盘中,我们可以发现B+索引树上相邻的两个节点,其实可能在物理磁盘上不相邻的,因此,每次插入的新数据都需要随机写入磁盘,而磁盘的随机写入的性能非常慢,因此有没有更好的数据结构来解决这个问题?
答案是:LSM-Tree
LSM-Tree:Log Structured Merge Trees 日志结构组合树。LSM 树也是近年来许多火热的 NoSQL 数据库中使用的检索技术。比如,日志系统、监控系统。这些应用场景有一个共同的特点:数据会持续地大量生成,而且相比于检索操作,它们的写入操作会非常频繁。另外,即使是检索操作,往往也不是全范围的随机检索,更多的是针对近期数据的检索。
LSM-Tree的实现机制
LSM-Tree采用的是磁盘顺序写,它是一种多层结构,最上层C0位于内存中,存储最近写入的key-value数据,下面的C1~CN是位于磁盘中,每一层按key的字典顺序进行排序。
写操作:先写C0层,当C0层数据达到阈值就会把数据合并到C1层(归并排序),C1达到阈值,又把数据合并到C2,以此类推。
读请求:先读C0层,因为这个层里面的数据是最新的。如果C0没有,则一次往下找。
LSM-Tree 示意图
使用场景
HBase NoSQL数据库,LevelDB
通过今天对MySQL 索引机制,我们分析和对比了很多的数据结构,同时我们也会发现,检索是海量数据查询的一个重要课题,针对不同的场景,我们需要采用不同的数据结构。
本文为原创文章,转载请标明出处。
本文链接:https://www.yuanjava.cn/mysql/2022/01/05/mysqlindex.html
本文出自猿java的博客
学习交流
如果你觉得文章有帮助,请帮忙转发给更多的好友,或关注公众号:猿java,持续输出硬核文章。