如何理解Mysql的索引及他们的原理--------二叉查找树和平衡二叉树和B树和B+树

本文涉及的产品
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
RDS MySQL Serverless 高可用系列,价值2615元额度,1个月
简介: 如何理解Mysql的索引及他们的原理--------二叉查找树和平衡二叉树和B树和B+树

1.索引是什么东西?

索引就是一个数据结构,我们把表中的记录用一个适合高效查找的数据结构来表示,目的就是让查询变得更高效。

2.它到底怎么运作的?

这个问题就说来话长了,且听我慢慢道来:

在mysql中使用最广泛的数据引擎是InnoDB 引擎,它里面用的是 B+ 树索引。

我们重点分析一下这个索引的原理:

要想理解B+树索引要先从 二叉查找树,平衡二叉树和 B 树说起因为B+树索引就是由他们演化而来:

在mysql中使用最广泛的数据引擎是InnoDB 引擎,它里面用的是 B+ 树索引。

我们重点分析一下这个索引的原理:

要想理解B+树索引要先从 二叉查找树,平衡二叉树和 B 树说起因为B+树索引就是由他们演化而来:

什么是二叉查找树?

 

满足这样条件的就叫二叉查找树:

每个节点左边节点的值都小于该节点,右边节点的值都大于该节点,没有值相等的节点,最顶端的节点也就是“45”被称为根节点。

二叉查找树的查找过程:

若根结点的值等于查找的值,成功,

否则,若小于根结点的值,递归查左子树(也就是根节点左边的所有节点形成的树)

若大于根结点的值,递归查右子树(也就是根节点右边所有节点形成的树)。

假设用二叉查找树创建book表的索引:

索引如下:

图一

此处的bid为主键,每个节点存储了主键的值和该条记录的内容。

如果我要查找bid为6的图书的信息,则先用6和根节点的主键值7比较发现比7小,

然后6再和7左边的节点5比较发现比5大找到5右边的节点6,找到了,取出6对应的记录行的值ee.

总共经历了3次比较,如果扫描全表需要经过5次比较。

什么是平衡二叉树?

如果索引是这样:

图二

想要找到主键键值为9的记录就需要6次比较,索引的优势完全体现不出来。


为什么会这样?原因就在于这棵树太高了,如果能想办法把它变得矮一点,胖一点就完美了。于是平衡二叉树闪亮登场:


平衡二叉树首先也是一个二叉树,需要满足二叉树的所有条件,然后有所改进,规定了左右子树的高度差不能超过1,如果插入数据导致高度差超过了1则自动进行调整,回复到平衡状态。这也是平衡二叉树名字的由来。


图一就是一颗平衡二叉树,图二根节点的左子树高度为0,右子树高度为5,高度差是5超过了1所以不是一颗平衡二叉树。


平衡二叉树查找效率要高于二叉树。

什么是B树?

由前面的推导我们可以看出要想查找,比较的次数最少,必须想办法降低树形结构的高度,不管是二叉树还是平衡二叉树,每个节点最多只能有两个子节点,这就注定了它的高度受限于子节点的个数,于是B树横空出世.


从上图可以看到B树的节点可以不止两个子节点,这样的好处就是树可以变得又矮又胖,矮胖的树是索引的最爱,用它做索引可以降低磁盘的IO.


B树中的每个节点根据实际情况可以包含大量的键值,数据和指针,上图所示为一个3阶的B树:


每点占用一个磁盘块的磁盘空个节间,一个节点上有两个升序排序的键值和三个指向子树根节点的指针,指针存储的是子节点所在磁盘块的地址。两个键值划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例,键值为17和35,P1指针指向的子树的数据范围为小于17,P2指针指向的子树的数据范围为17~35,P3指针指向的子树的数据范围为大于35。


模拟查找关键字29的过程:


根据根节点找到磁盘块1,读入内存。【磁盘I/O操作第1次】


比较关键字29在区间(17,35),找到磁盘块1的指针P2。


根据P2指针找到磁盘块3,读入内存。【磁盘I/O操作第2次】


比较关键字29在区间(26,30),找到磁盘块3的指针P2。


根据P2指针找到磁盘块8,读入内存。【磁盘I/O操作第3次】


在磁盘块8中的关键字列表中找到关键字29。


分析上面过程,发现需要3次磁盘I/O操作,和3次内存查找操作。由于内存中的键值是一个有序表结构,可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B树查找效率的决定因素。

什么是B+树?

想想还有没有可能进一步优化,在B树中每个节点的内容由三部分组成:键值,指针,数据,而磁盘块的容量是有限的,并不是每次读取磁盘块都会取出里面的数据,只是在最后一次读取的时候才会取出里面的数据,能不能将数据只存储在叶子节点里面,非叶子节点只存储键值和指针呢?这样就能最大化的利用磁盘块空间,一个磁盘块也就能存更多的东西了,没错,B+树就是这么干的

假设在非叶子节点不存数据以后每个节点可以存储4个键值和指针,就变成了上图的B+树

B+树相对于B树有几点不同:

  1. 非叶子节点只存储键值和指针。
  2. 所有叶子节点之间都有一个链指针。
  3. 数据记录都存放在叶子节点中。

在B+树中因为叶子节点的键值是按顺序排列的所以进行键值的范围查找效率非常高。

在B+树中由于一个节点存储了更多的键值和指针,所以同样多的内容可以降低树的高度,减少磁盘io次数,从而提高效率。


数据库的索引分为聚集索引和非聚集索引,innoDb存储引擎中的聚集索引表中的数据按主键的顺序存放,它实际上就是按主键构建的一个B+树,叶子节点存放的是数据行记录。所以数据库中的数据实际上是索引的一部分。由于实际的数据页只能按照一个顺序存放,所以每张表聚集索引只能有一个。


非聚集索引的叶子节点中存放的是键值和主键值,所以通过非聚集索引需要先查找到主键值然后通过聚集索引查询到具体的数据,因此非聚集索引的效率要低于聚集索引。非聚集索引并不会影响到数据的存储顺序,所以非聚集索引可以存在多个。

相关实践学习
如何快速连接云数据库RDS MySQL
本场景介绍如何通过阿里云数据管理服务DMS快速连接云数据库RDS MySQL,然后进行数据表的CRUD操作。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助     相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
相关文章
MySQL底层概述—8.JOIN排序索引优化
本文主要介绍了MySQL中几种关键的优化技术和概念,包括Join算法原理、IN和EXISTS函数的使用场景、索引排序与额外排序(Using filesort)的区别及优化方法、以及单表和多表查询的索引优化策略。
MySQL底层概述—8.JOIN排序索引优化
MySQL原理简介—9.MySQL索引原理
本文详细介绍了MySQL索引的设计与使用原则,涵盖磁盘数据页的存储结构、页分裂机制、主键索引设计及查询过程、聚簇索引和二级索引的原理、B+树索引的维护、联合索引的使用规则、SQL排序和分组时如何利用索引、回表查询对性能的影响以及索引覆盖的概念。此外还讨论了索引设计的案例,包括如何处理where筛选和order by排序之间的冲突、低基数字段的处理方式、范围查询字段的位置安排,以及通过辅助索引来优化特定查询场景。总结了设计索引的原则,如尽量包含where、order by、group by中的字段,选择离散度高的字段作为索引,限制索引数量,并针对频繁查询的低基数字段进行特殊处理等。
MySQL原理简介—9.MySQL索引原理
MySQL底层概述—6.索引原理
本文详细回顾了:索引原理、二叉查找树、平衡二叉树(AVL树)、红黑树、B-Tree、B+Tree、Hash索引、聚簇索引与非聚簇索引。
MySQL底层概述—6.索引原理
Docker Compose V2 安装常用数据库MySQL+Mongo
以上内容涵盖了使用 Docker Compose 安装和管理 MySQL 和 MongoDB 的详细步骤,希望对您有所帮助。
102 42
如何排查和解决PHP连接数据库MYSQL失败写锁的问题
通过本文的介绍,您可以系统地了解如何排查和解决PHP连接MySQL数据库失败及写锁问题。通过检查配置、确保服务启动、调整防火墙设置和用户权限,以及识别和解决长时间运行的事务和死锁问题,可以有效地保障应用的稳定运行。
56 25
数据库数据恢复——MySQL简介和数据恢复案例
MySQL数据库数据恢复环境&故障: 本地服务器,安装的windows server操作系统。 操作系统上部署MySQL单实例,引擎类型为innodb,表空间类型为独立表空间。该MySQL数据库没有备份,未开启binlog。 人为误操作,在用Delete命令删除数据时未添加where子句进行筛选导致全表数据被删除,删除后未对该表进行任何操作。
【深入了解MySQL】优化查询性能与数据库设计的深度总结
本文详细介绍了MySQL查询优化和数据库设计技巧,涵盖基础优化、高级技巧及性能监控。
307 0
数据库传奇:MySQL创世之父的两千金My、Maria
《数据库传奇:MySQL创世之父的两千金My、Maria》介绍了MySQL的发展历程及其分支MariaDB。MySQL由Michael Widenius等人于1994年创建,现归Oracle所有,广泛应用于阿里巴巴、腾讯等企业。2009年,Widenius因担心Oracle收购影响MySQL的开源性,创建了MariaDB,提供额外功能和改进。维基百科、Google等已逐步替换为MariaDB,以确保更好的性能和社区支持。掌握MariaDB作为备用方案,对未来发展至关重要。
76 3
MySQL崩溃保险箱:探秘Redo/Undo日志确保数据库安全无忧!
《MySQL崩溃保险箱:探秘Redo/Undo日志确保数据库安全无忧!》介绍了MySQL中的三种关键日志:二进制日志(Binary Log)、重做日志(Redo Log)和撤销日志(Undo Log)。这些日志确保了数据库的ACID特性,即原子性、一致性、隔离性和持久性。Redo Log记录数据页的物理修改,保证事务持久性;Undo Log记录事务的逆操作,支持回滚和多版本并发控制(MVCC)。文章还详细对比了InnoDB和MyISAM存储引擎在事务支持、锁定机制、并发性等方面的差异,强调了InnoDB在高并发和事务处理中的优势。通过这些机制,MySQL能够在事务执行、崩溃和恢复过程中保持
136 3
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等