为什么Mysql的常用引擎都默认使用B+树作为索引?

本文涉及的产品
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
云数据库 RDS MySQL,高可用系列 2核4GB
简介: 为了讲清楚这个问题,阿粉先带大家了解一下什么是索引。

一、前言

为了讲清楚这个问题,阿粉先带大家了解一下什么是索引。

8.jpg

我记得刚刚学习数据库的时候,老师喜欢用书本的目录来类比数据库的索引,并告诉我们索引能够像目录一样,让我们更快地找到想要找到的数据。

如果是第一次接触索引,这个比喻能够让我们有一个直观的印象。但是当深入去学习索引的时候,我们不能继续持有索引即目录的思想,我们要跳出来去思考索引的本质是什么。

9.jpg

二、索引的本质

在没有索引的情况下,我们查找数据只能按照从头到尾的顺序逐行查找,每查找一行数据,意味着我们要到到磁盘相应的位置去读取一条数据。

如果把查询一条数据分为到磁盘中查询和比对查询条件两步的话,到磁盘中查询的时间会远远大于比对查询条件的时间,这意味着在一次查询中,磁盘io占用了大部分的时间。更进一步地说,一次查询的效率取绝于磁盘io的次数,如果我们能够在一次查询中尽可能地降低磁盘io的次数,那么我们就能加快查询的速度。10.jpg

在知道了减少磁盘io能加快查询速度后,我们就要聚焦于如何减少磁盘io。如果按照原表逐行查询的话,n条数据就要查询n次,也就是O(N)的时间复杂度,为了减少磁盘io的次数,我们必须用一种查询时间复杂度更低的数据结构来保存数据。

这种查询时间复杂度低的数据结构,我们称之为索引。所以通俗来说,索引其实就是某种数据结构,能充当索引的数据结构是多种多样的。

三、索引的选择

既然索引是一种便于查询的数据结构,如果大家对数据结构有一定了解的话,大概率会首选树型结构。毕竟树型结构普遍有着O(logN)的查询时间复杂度,而且插入删除数据的性能也比较平均。(可能你会说数组,哈希表的查询速度也很高啊,这个后面也会分析)

11.jpg

虽然我们都已经知道Mysql中最常用的引擎像InnoDB和MyISAM,最终都选择了B+树作为索引,但是这里我还是打算从最常见的二叉树开始讲起,推导一下为什么最终选择了B+树作为索引,并比较一下几种树型结构在充当索引时的优劣。

二叉树

最普通的二叉树的问题在于他不能保证O(logN)的查询时间复杂度,我们看下面的图:

12.png


由于插入的元素逐渐增大,元素始终在右边进行插入,好好的一棵二叉树最终变成了一条“链表”。在这种极端的情况下,二叉树的查询时间复杂度不再是O(logN),而是退化为O(N),这样显然不符合索引的要求。

平衡二叉树(红黑树)

像红黑树这样的平衡二叉树,无论如何插入元素,他都可以通过一些旋转的方法调整树的高度,使得整棵树的查询效率维持在O(logN),如下图所示:

13.jpg

这么来说他已经符合了成为索引的必备条件,但是最终没有选择他作为索引说明还有不足的地方。仔细看看可以发现平衡二叉树的每个节点只有两个孩子节点,如果一张表的数据量特别大,整棵树的高度也会随之上升。一个千万级别的表如果用平衡二叉树作为索引的话,树高将会达到二十多层。这也就意味着做一次查询需要二十多次磁盘io,这是一个不小的开销。

那么有没有能在大数据量的情况下,还能保持一个较小树高的树型结构呢?

B树和B+树

答案就是B树。上面我们说到了平衡二叉树的瓶颈在于一个节点只有两个孩子节点,而B树一个节点可以存放N个孩子节点,这就完美解决了树高的问题,我们可以把B树称为平衡多叉树,B树作为索引如下图所示:

14.jpg

但是以B树的结构作为索引仍有可以优化的地方,我们先看看最终的B+树,再仔细分析B+树在B树的基础上作了哪些改进,为什么B+树最终能够胜任索引的工作:

15.jpg

图片来源网络

从图片中可以看到B+树同样是一棵多差平衡树,和B树一样很好地解决了树高的问题。

改进点一:

但仔细看可以发现,B树的节点中既存储索引,也存储表对应的数据;而B+树的非叶子节点是不存储数据的,只存储索引,数据全部存储在叶子节点上。

为什么要做这样的改进?我们做一次算术就知道了。

假设树高为2,主键ID为bigint类型,长度为8字节,节点指针为6字节,一行数据记录的大小为1k,一次io操作能获得一页16k的数据。

在索引为B+树的情况下,根节点能存储:16k / (6 + 8) = 1170 条索引指针;到了第一层,一共能指向 1170 * 1170 = 1368900 条索引指针;到了最底一层叶子节点,一个节点能存储16k / 1k = 16 条记录,一共能存储 1170 * 1170 * 16 = 21902400 条记录

在B树的情况下,由于非叶子节点使用了大量空间存储数据,存放的索引指针肯定就少,最终整棵树如果想要存储和B+树一样多的数据就必须要增加树高,这样一来就增加了磁盘io,所以说B+树作为索引的性能比B树高。

改进点二:

叶子节点之间使用指针连接,提高区间访问效率。如果我们要进行范围查询,可以轻松通过B+树叶子节点之间的指针进行遍历,减少了不必要的磁盘io。

总结

看到这里,相信大家对为什么Mysql的常用引擎都默认使用B+树作为索引已经有了初步的认知。我们只要牢记一点:索引是为了减少磁盘io提高查询性能而存在的。16.jpg

最后回应一下为什么不常用哈希表和数组作为索引

哈希表虽然单一个值的查询效率很高,但是撑不住范围查询,哪个公司的业务还没个范围查询呢?

而数组虽然查询的效率高,但是增加和删除的效率低,由于记录在增加和删除的时候索引也得跟着维护,这会导致大数据量的情况下,增加或删除一条记录效率较低。

相关实践学习
如何快速连接云数据库RDS MySQL
本场景介绍如何通过阿里云数据管理服务DMS快速连接云数据库RDS MySQL,然后进行数据表的CRUD操作。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助     相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
相关文章
|
2月前
|
存储 关系型数据库 MySQL
MySQL索引学习笔记
本文深入探讨了MySQL数据库中慢查询分析的关键概念和技术手段。
288 80
|
16天前
|
缓存 算法 关系型数据库
MySQL底层概述—8.JOIN排序索引优化
本文主要介绍了MySQL中几种关键的优化技术和概念,包括Join算法原理、IN和EXISTS函数的使用场景、索引排序与额外排序(Using filesort)的区别及优化方法、以及单表和多表查询的索引优化策略。
MySQL底层概述—8.JOIN排序索引优化
|
19天前
|
SQL 存储 关系型数据库
MySQL原理简介—9.MySQL索引原理
本文详细介绍了MySQL索引的设计与使用原则,涵盖磁盘数据页的存储结构、页分裂机制、主键索引设计及查询过程、聚簇索引和二级索引的原理、B+树索引的维护、联合索引的使用规则、SQL排序和分组时如何利用索引、回表查询对性能的影响以及索引覆盖的概念。此外还讨论了索引设计的案例,包括如何处理where筛选和order by排序之间的冲突、低基数字段的处理方式、范围查询字段的位置安排,以及通过辅助索引来优化特定查询场景。总结了设计索引的原则,如尽量包含where、order by、group by中的字段,选择离散度高的字段作为索引,限制索引数量,并针对频繁查询的低基数字段进行特殊处理等。
MySQL原理简介—9.MySQL索引原理
|
17天前
|
存储 关系型数据库 MySQL
MySQL底层概述—6.索引原理
本文详细回顾了:索引原理、二叉查找树、平衡二叉树(AVL树)、红黑树、B-Tree、B+Tree、Hash索引、聚簇索引与非聚簇索引。
MySQL底层概述—6.索引原理
|
2月前
|
SQL 存储 关系型数据库
MySQL秘籍之索引与查询优化实战指南
最左前缀原则。不冗余原则。最大选择性原则。所谓前缀索引,说白了就是对文本的前几个字符建立索引(具体是几个字符在建立索引时去指定),比如以产品名称的前 10 位来建索引,这样建立起来的索引更小,查询效率更快!
121 22
 MySQL秘籍之索引与查询优化实战指南
|
2月前
|
存储 关系型数据库 MySQL
浅入浅出——MySQL索引
本文介绍了数据库索引的概念和各种索引结构,如哈希表、B+树、InnoDB引擎的索引运作原理等。还分享了覆盖索引、联合索引、最左前缀原则等优化技巧,以及如何避免索引误用,提高数据库性能。
|
2月前
|
存储 关系型数据库 MySQL
MySQL中为什么要使用索引合并(Index Merge)?
通过这些内容的详细介绍和实际案例分析,希望能帮助您深入理解索引合并及其在MySQL中的
165 10
|
2月前
|
关系型数据库 MySQL 数据库连接
数据库连接工具连接mysql提示:“Host ‘172.23.0.1‘ is not allowed to connect to this MySQL server“
docker-compose部署mysql8服务后,连接时提示不允许连接问题解决
|
23天前
|
关系型数据库 MySQL 数据库
Docker Compose V2 安装常用数据库MySQL+Mongo
以上内容涵盖了使用 Docker Compose 安装和管理 MySQL 和 MongoDB 的详细步骤,希望对您有所帮助。
126 42
|
14天前
|
关系型数据库 MySQL 网络安全
如何排查和解决PHP连接数据库MYSQL失败写锁的问题
通过本文的介绍,您可以系统地了解如何排查和解决PHP连接MySQL数据库失败及写锁问题。通过检查配置、确保服务启动、调整防火墙设置和用户权限,以及识别和解决长时间运行的事务和死锁问题,可以有效地保障应用的稳定运行。
71 25