您当前的位置:首页 > 电脑百科 > 数据库 > MYSQL

为什么使用索引就能提升查询效率,原来与BTree有关

时间:2020-07-21 10:15:54  来源:  作者:

大家好,欢迎收看猿话!

「系统架构」为什么使用索引就能提升查询效率,原来与BTree有关

 

BTree意思是多路平衡查找树,它是一种数据结构。MySQL的InnoDB和MyISAM存储引擎,都是使用它来存储索引。BTree可细分为B-Tree和B+Tree,B+Tree是B-Tree的升级版。MySQL的InnoDB和MyISAM存储引擎使用的是B+Tree。

B-Tree

为了描述B-Tree,首先定义一条记录为一个二元组[key, data] ,key为记录的键值,对应表中的主键值,data为一行记录中除主键外的数据。对于不同的记录,key值互不相同。如下图中的紫色部分就是key,橙色部分就是一行数据,绿色部分就是指针。

「系统架构」为什么使用索引就能提升查询效率,原来与BTree有关

 

一棵m阶的B-Tree有如下特性:

  1. 每个节点最多有m个子节点。 如上图所示是一个3阶的树,那最多有3个子节点。
  2. 除了根节点和叶子节点外,其它每个节点至少有ceil(m/2)个子节点。如上图所示是一个3阶的树,那每个节点至少有2个子节点。
  3. 所有叶子节点都在同一层,且不包含其它关键字信息
  4. 每个非终端节点包含n个关键字信息(P0,P1,…Pn, k1,…kn) ,关键字的个数n满足:ceil(m/2)-1 <= n <= m-1
  5. ki(i=1,…n)为关键字,且关键字升序排序。
  6. Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki,但都大于k(i-1)
  7. 指针存储的是子节点所在磁盘块的地址

假设以根节点为例,关键字为17和35,P1指针指向的子树的数据范围为小于17,P2指针指向的子树的数据范围为17~35,P3指针指向的子树的数据范围为大于35。

当我们要查找关键字29时:

  1. 根据根节点找到磁盘块1,读入内存。【磁盘I/O操作第1次】
  2. 比较关键字29在区间(17,35),找到磁盘块1的指针P2。
  3. 根据P2指针找到磁盘块3,读入内存。【磁盘I/O操作第2次】
  4. 比较关键字29在区间(26,30),找到磁盘块3的指针P2。
  5. 根据P2指针找到磁盘块8,读入内存。【磁盘I/O操作第3次】
  6. 在磁盘块8中的关键字列表中找到关键字29。

分析上面过程,发现需要3次磁盘I/O操作,和3次内存查找操作。由于内存中的关键字是一个有序表结构,可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数,使每次磁盘I/O取到内存的数据都发挥了作用,从而提高了查询效率。

B+Tree

从上一节中的B-Tree结构图中可以看到,每个节点中不仅包含数据的key值,还有data值。而每一个页的存储空间是有限的,一般为16K(也可以调整),如果data数据较大时将会导致每个节点(即一个页)能存储的key的数量很小。当存储的数据量很大时同样会导致B-Tree的深度较大,增大查询时的磁盘I/O次数,进而影响查询效率。

为解决这个问题,在B-Tree基础上就产生了一种新的数据结构B+Tree。

「系统架构」为什么使用索引就能提升查询效率,原来与BTree有关

 

一棵m阶的B+Tree的特性和m阶的B-Tree基本相同,除了以下几点:

  1. 非叶子节点上只存储key值信息,而不存储data信息
  2. 非叶子节点的子树指针与关键字个数相同
  3. 非叶子节点的子树指针 P[i] , 指向关键字值属于 [K[i], K[i+1]) 的子树( B- 树是开区间)
  4. 所有关键字都会出现在叶子节点的链表中(稠密索引),且链表中的关键字恰好是有序的。如上图所示的升序。

虽然,MySQL的InnoDB和MyISAM存储引擎使用的都是B+Tree结构,但是它们也有不同之处:

  1. InnoDB的B+Tree索引分为聚簇索引和非聚簇索引,而MyISAM的B+Tree索引都是非聚簇索引。
  2. InnoDB的主键索引为聚簇索引,辅助索引为非聚簇索引。主键索引的叶子节点保存了完整的记录,辅助索引的叶子节点并不包含行记录的全部数据,它除了包含键值外,还包含了相应行数据的聚簇索引键。
  3. MyISAM的非聚簇索引结构都是一样的,它的叶子节点保存的都是磁盘地址,真正的数据存储在另外的地方。


Tags:查询效率   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
大家好,欢迎收看猿话! BTree意思是多路平衡查找树,它是一种数据结构。MySQL的InnoDB和MyISAM存储引擎,都是使用它来存储索引。BTree可细分为B-Tree和B+Tree,B+Tree是B-Tree的升级...【详细内容】
2020-07-21  Tags: 查询效率  点击:(97)  评论:(0)  加入收藏
数据库中可以用 datetime、bigint、timestamp 来表示时间,那么选择什么类型来存储时间比较合适呢?前期数据准备 通过程序往数据库插入 50w 数据 数据表:CREATE TABLE `users`...【详细内容】
2020-06-28  Tags: 查询效率  点击:(80)  评论:(0)  加入收藏
在一个千万级的数据库查寻中,如何提高查询效率?1、数据库设计方面:A. 对查询进行优化,应尽量避免全表扫描,首先应考虑在 where 及 order by 涉及的列上建立索引。B. 应尽量避免在...【详细内容】
2019-06-11  Tags: 查询效率  点击:(591)  评论:(0)  加入收藏
▌简易百科推荐
作者:雷文霆 爱可生华东交付服务部 DBA 成员,主要负责Mysql故障处理及相关技术支持。爱好看书,电影。座右铭,每一个不曾起舞的日子,都是对生命的辜负。 本文来源:原创投稿 *爱可生...【详细内容】
2021-12-24  爱可生    Tags:MySQL   点击:(7)  评论:(0)  加入收藏
生成间隙(gap)锁、临键(next-key)锁的前提条件 是在 RR 隔离级别下。有关Mysql记录锁、间隙(gap)锁、临键锁(next-key)锁的一些理论知识之前有写过,详细内容可以看这篇文章...【详细内容】
2021-12-14  python数据分析    Tags:MySQL记录锁   点击:(18)  评论:(0)  加入收藏
binlog 基本认识 MySQL的二进制日志可以说是MySQL最重要的日志了,它记录了所有的DDL和DML(除了数据查询语句)语句,以事件形式记录,还包含语句所执行的消耗的时间,MySQL的二...【详细内容】
2021-12-14  linux上的码农    Tags:mysql   点击:(13)  评论:(0)  加入收藏
为查询优化你的查询 大多数的MySQL服务器都开启了查询缓存。这是提高性最有效的方法之一,而且这是被MySQL的数据库引擎处理的。当有很多相同的查询被执行了多次的时候,这些查...【详细内容】
2021-12-09  元宇宙iwemeta    Tags:mysql   点击:(15)  评论:(0)  加入收藏
测试的目的和原因,公司有很多程序员,每个程序员对数据库和表结构都有自己的理解。而且每个程序员的理解往往是以效率考虑。既然都是为了效率考虑,那么我就来测试一下究竟哪种使...【详细内容】
2021-12-08  吴彬的分享    Tags:Mysql数据库   点击:(14)  评论:(0)  加入收藏
当你们考虑项目并发的时候,我在部署环境,当你们在纠结使用ArrayList还是LinkedArrayList的时候,我还是在部署环境。所以啊,技术不止境,我在部环境。今天这篇文章缕一下在同一台服...【详细内容】
2021-12-08  秃头码哥    Tags:MySQL数据库   点击:(17)  评论:(0)  加入收藏
对于数据分析来说,MySQL使用最多的是查询,比如对数据进行排序、分组、去重、汇总及字符串匹配等,如果查询的数据涉及多个表,还需要要对表进行连接,本文就来说说MySQL中常用的查询...【详细内容】
2021-12-06  笨鸟学数据分析    Tags:MySQL   点击:(21)  评论:(0)  加入收藏
在学习SQL语句之前,首先需要区分几个概念,我们常说的数据库是指数据库软件,例如MySQL、Oracle、SQL Server等,而本文提到的数据库是指数据库软件中的一个个用于存储数据的容器。...【详细内容】
2021-11-24  笨鸟学数据分析    Tags:SQL语句   点击:(23)  评论:(0)  加入收藏
概述以前参加过一个库存系统,由于其业务复杂性,搞了很多个应用来支撑。这样的话一份库存数据就有可能同时有多个应用来修改库存数据。比如说,有定时任务域xx.cron,和SystemA域...【详细内容】
2021-11-05  Java云海    Tags:分布式锁   点击:(31)  评论:(0)  加入收藏
MySQL的进阶查询 一、 按关键字排序 使用ORDERBY语句来实现排序排序可针对一个或多个字段ASC:升序,默认排序方式 【升序是从小到大】DESC:降序 【降序是从大到小】ORDER BY的...【详细内容】
2021-11-05  Java热点    Tags:SQL语句   点击:(28)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条