分布式调度 Wendy MongoDB 正则表达式 extjs6.5 软件开发 firebase shell npm scrapy NEC 小程序demo源码 多店版微信商城 nfc卡片 python编程教程 python测试 python循环语句 java简介 java集成 java正则表达式用法 java开发环境搭建 java安装配置 java编程语言 java注释规范 linux安装教程 嵌入式开发教程 垃圾邮件数据集 信息系统项目管理师教程 m4a转mp3格式转换器 adobe清理工具 小程序源码下载 iphone滚动截屏 微信小程序提示框 自动喊话器 qq免安装 淘宝自动发货软件 电子商城系统 2700U 俄罗斯方块代码 早早省
当前位置: 首页 > 学习教程  > 编程语言

mysql索引和B+Tree

2020/12/28 19:38:30 文章标签:

1.索引是什么 索引是为了加速对表中数据的检索的一种数据结构。其工作机制如下图: 上图中,如果现在有一条 sql 语句 select * from user where id 40如果没有索引的条件下,我们要找到这条记录,我们就需要在数据中进行全表扫描…

1.索引是什么

索引是为了加速对表中数据的检索的一种数据结构。其工作机制如下图:
在这里插入图片描述
上图中,如果现在有一条 sql 语句

select * from user where id = 40

如果没有索引的条件下,我们要找到这条记录,我们就需要在数据中进行全表扫描,匹配 id = 40 的数据
如果有了索引,我们就可以通过索引进行快速查找,如上图中,可以先在索引中通过 id = 40 进行二分查找,再根据定位到的地址取出对应的行数据

2.MySQL 为什么要使用 B+TREE 作为索引的数据结构

2.1 二叉树为什么不可行

对数据的加速检索,首先想到的就是二叉树,二叉树的查找时间复杂度可以达到 O(log2(n))。下面看一下二叉树的存储结构:
在这里插入图片描述
二叉树搜索相当于一个二分查找。二叉查找能大大提升查询的效率,但是它有一个问题:二叉树以第一个插入的数据作为根节点,如上图中,如果只看右侧,就会发现,就是一个线性链表结构。如果我们现在的数据只包含1, 2, 3, 4,就会出现
在这里插入图片描述
如果我们要查询的数据为 4,则需要遍历所有的节点才能找到 4,即相当于全表扫描,就是由于存在这种问题,所以二叉查找树不适合用于作为索引的数据结构

2.2 平衡二叉树为什么不可行

为了解决二叉树存在线性链表的问题,会想到用平衡二叉查找树来解决。下面看看平衡二叉树是怎样的:
在这里插入图片描述
平衡二叉查找树定义为:节点的子节点高度差不能超过1,如上图中的节点20,左节点高度为1,右节点高度0,差为1,所以上图没有违反定义,它就是一个平衡二叉树。保证二叉树平衡的方式为左旋,右旋等操作

如果上图中平衡二叉树保存的是id索引,现在要查找 id = 8 的数据,过程如下:

1.把根节点加载进内存,用 8 和 10 进行比较,发现 8 比 10 小,继续加载 10 的左子树
2.把 5 加载进内存,用 8 和 5 比较,同理,加载 5 节点的右子树
3.此时发现命中,则读取 id 为 8 的索引对应的数据

索引保存数据的方式一般有两种:

  • 数据区保存 id 对应行数据的所有数据具体内容
  • 数据区保存的是真正保存数据的磁盘地址

到这里,平衡二叉树解决了存在线性链表的问题,数据查询的效率好像也还可以,基本能达到O(log2(n)), 那为什么 mysql 不选择平衡二叉树作为索引存储结构,他又存在什么样的问题呢?

  1. 搜索效率不足。一般来说,在树结构中,数据所处的深度,决定了搜索时的IO次数(MySql中将每个节点大小设置为一页大小,一次IO读取一页
    / 一个节点)。如上图中搜索id = 8的数据,需要进行3次IO。当数据量到达几百万的时候,树的高度就会很恐怖
  2. 查询不不稳定。如果查询的数据落在根节点,只需要一次IO,如果是叶子节点或者是支节点,会需要多次IO才可以
  3. 存储的数据内容太少。没有很好利用操作系统和磁盘数据交换特性,也没有利用好磁盘IO的预读能力。因为操作系统和磁盘之间一次数据交换是以页为单位的,一页大小为
    4K,即每次IO操作系统会将4K数据加载进内存。但是,在二叉树每个节点的结构只保存一个关键字,一个数据区,两个子节点的引用,并不能够填满4K的内容。幸幸苦苦做了一次的IO操作,却只加载了一个关键字。在树的高度很高,恰好又搜索的关键字位于叶子节点或者支节点的时候,取一个关键字要做很多次的IO

那有没有一种结构能够解决二叉树的这种问题呢?有,那就是多路平衡查找树

2.3 多路平衡查找树(Balance Tree)

B Tree 是一个绝对平衡树,所有的叶子节点在同一高度,如下图所示:
在这里插入图片描述
上图为一个2-3树(每个节点存储2个关键字,有3路),多路平衡查找树也就是多叉的意思,从上图中可以看出,每个节点保存的关键字的个数和路数关系为:关键字个数 = 路数 – 1。

假设要从上图中查找 id = X 的数据,B TREE 搜索过程如下:

1.取出根磁盘块,加载 40 和 60 两个关键字
2.如果 X 等于40,则命中;如果 X 小于 40 走 P1;如果 40 < X < 60 走 P2;如果 X = 60,则命中;如果 X > 60 走 P3
3.根据以上规则命中后,接下来加载对应的数据, 数据区中存储的是具体的数据或者是指向数据的指针

为什么说这种结构能够解决平衡二叉树存在的问题呢?

B Tree 能够很好的利用操作系统和磁盘的交互特性, MySQL为了很好的利用磁盘的预读能力,将页大小设置为16K,即将一个节点(磁盘块)的大小设置为16K,一次IO将一个节点(16K)内容加载进内存。这里,假设关键字类型为 int,即4字节,若每个关键字对应的数据区也为4字节,不考虑子节点引用的情况下,则上图中的每个节点大约能够存储(16 * 1000)/ 8 = 2000个关键字,共2001个路数。对于二叉树,三层高度,最多可以保存7个关键字,而对于这种有2001路的B树,三层高度能够搜索的关键字个数远远的大于二叉树。

这里顺便说一下:在B Tree保证树的平衡的过程中,每次关键字的变化,都会导致结构发生很大的变化,这个过程是特别浪费时间的,所以创建索引一定要创建合适的索引,而不是把所有的字段都创建索引,创建冗余索引只会在对数据进行新增,删除,修改时增加性能消耗。

B树确实已经很好的解决了问题,我先这里先继续看一下B+Tree结构,再来讨论BTree和B+Tree的区别。

先看看B+Tree是怎样的,B+Tree是B Tree的一个变种,在B+Tree中,B树的路数和关键字的个数的关系不再成立了,数据检索规则采用的是左闭合区间,路数和关键个数关系为1比1,具体如下图所示:
在这里插入图片描述
如果上图中是用ID做的索引,如果是搜索X = 1的数据,搜索规则如下:

1.取出根磁盘块,加载1,28,66三个关键字
2.X <= 1 走P1,取出磁盘块,加载1,10,20三个关键字
3.X <= 1 走P1,取出磁盘块,加载1,8,9三个关键字
4.已经到达叶子节点,命中1,接下来加载对应的数据,图中数据区中存储的是具体的数据

2.4 B TREE 和 B+TREE 区别

  • B 树一个节点里存的是数据,而 B+ 树 存储的是索引(地址),所以 B 树里一个节点存不了很多个数据,但是 B+树 一个节点能存很多索引,B+ 树 叶子节点存所有的数据
  • B+ 树 的叶子节点是数据阶段用了一个链表串联起来,便于范围查找 通过 B 树和 B+ 树的对比我们看出,B+ 树 节点存储的是索引,在单个节点存储容量有限的情况下,单节点也能存储大量索引,使得整个 B+ 树高度降低,减少了磁盘 IO
  • 其次,B+ 树的叶子节点是真正数据存储的地方,叶子节点用了链表连接起来,这个链表本身就是有序的,在数据范围查找时,更具备效率。因此 Mysql 的索引用的就是 B+ 树,B+ 树 在查找效率、范围查找中都有着非常不错的性能

2.5 MySQL 为什么最终要去选择 B+Tree

  • B+Tree 是 B TREE 的变种,B TREE 能解决的问题,B+TREE也能够解决(降低树的高度,增大节点存储数据量)
  • B+Tree 扫库和扫表能力更强。如果我们要根据索引去进行数据表的扫描,对B
    TREE进行扫描,需要把整棵树遍历一遍,而B+TREE只需要遍历他的所有叶子节点即可(叶子节点之间有引用)。
  • B+TREE 磁盘读写能力更强。他的根节点和支节点不保存数据区,所以根节点和支节点同样大小的情况下,保存的关键字要比 B TREE 要多。而叶子节点不保存子节点引用,能用于保存更多的关键字和数据。所以,B+TREE 读写一次磁盘加载的关键字比 B TREE 更多。
  • B+Tree 排序能力更强。上面的图中可以看出,B+Tree 天然具有排序功能。
  • B+Tree 查询性能稳定。B+Tree 数据只保存在叶子节点,每次查询数据,查询IO次数一定是稳定的。当然这个每个人的理解都不同,因为在 B TREE 如果根节点命中直接返回,确实效率更高

3.Innodb 引擎的索引实现

InnoDB 是聚集索引方式,因此数据和索引都存储在同一个文件里。首先 InnoDB 会根据主键 ID 作为 KEY 建立索引 B+ 树,如左下图所示,而 B+ 树 的叶子节点存储的是主键 ID 对应的数据,比如在执行

select * from user_info where id=15 

这个语句时,InnoDB 就会查询这颗主键 ID 索引 B+树。这是建表的时候 InnoDB 就会自动建立好主键 ID 索引树,这也是为什么 Mysql 在建表时要求必须指定主键的原因。
当我们为表里某个字段加索引时 InnoDB 会怎么建立索引树呢?比如我们要给 user_name 这个字段加索引,那么 InnoDB 就会建立 user_name 索引 B+ 树,节点里存的是 user_name 这个 KEY,叶子节点存储的数据的是主键 KEY。注意,叶子存储的是主键 KEY!拿到主键 KEY 后,InnoDB 才会去主键索引树里根据刚在 user_name 索引树找到的主键 KEY 查找到对应的数据
在这里插入图片描述
问题来了,为什么 InnoDB 只在主键索引树的叶子节点存储了具体数据,但是其他索引树却不存具体数据呢,而要多此一举先找到主键,再在主键索引树找到对应的数据呢?
其实很简单,因为 InnoDB 需要节省存储空间。一个表里可能有很多个索引,InnoDB 都会给每个加了索引的字段生成索引树,如果每个字段的索引树都存储了具体数据,那么这个表的索引数据文件就变得非常巨大(数据极度冗余了)。从节约磁盘空间的角度来说,真的没有必要为每个字段索引树都存具体数据,通过这种看似“多此一举”的步骤,在牺牲较少查询的性能下节省了巨大的磁盘空间,这是非常有值得的


本文链接: http://www.dtmao.cc/news_show_550338.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?