请选择 进入手机版 | 继续访问电脑版

[MySql] MySQL的索引体系 采用B+树的缘故原由 剖析

[复制链接]
查看131 | 回复23 | 2021-9-13 00:27:54 | 显示全部楼层 |阅读模式
目次

1.什么是索引?

索引是为了加速对表中数据行的检索而创建的一种分散的存储布局 。(就好像我们小时间 用的字典,有了字典查到对应的字就会变快)

2.为什么必要 索引?

起首 我们必要 相识 一些概念和知识

  1. mysql数据存储在什么地方?----磁盘
  2. 查询数据比较慢的,一样平常 环境 下是卡在哪了? ----IO
  3. (以是 我们要进步 IO的服从 ,那么怎样 进步 呢?---- 次数和量两个层面,比方 :搬砖,搬一次和搬十次耗费的力气是不一样的,一次搬一块和一次搬十块耗费的力气(占用IO资源)也是不一样的。以是 我们尽大概 的在满足 自身需求的条件 下,减少和IO的交互)
  4. 去磁盘读取数据的时间 ,是用多少读取多少嘛? ----磁盘预读
  5. 磁盘预读:内存跟磁盘在发生数据交互的时间 ,一样平常 环境 下有一个最小的逻辑单元,称为页,datapage,页一样平常 由操作体系 决定是多大,一样平常 是4k和8k,而我们在举行 数据交互的时间 ,可以取页的的整数倍来举行 读取,innodb存储引擎每次读取数据为16k
  6. 局部性原理:数据和程序都有聚集成群的倾向,同时之前被访问过的数据和大概 再次被查询,涉及空间局部性、时间局部性

通过以上几个概念我们大概知道索引是用来干嘛的了----预先计划 好索引体系 ,等我们查询数据的时间 ,减少和IO的交互来进步 我们的查询服从 。

3.怎样 计划 索引体系 ?

我们还是先明白 几个概念

  • 索引存储在哪?---- 磁盘,查询数据的时间 会优先将索引加载到内存中
  • 索引在存储的时间 必要 什么信息?必要 存什么字段值?

—— key:现实 数据行中储存的值
—— 文件地址(指针、我们必要 找到存储数据文件在哪就得靠文件地址)
—— offset:偏移量(假如 我们要取文件中的某一条数据时,就必要 用到偏移量)

  • 上面说的这种格式的数据要使用 什么样的数据布局 来储存?

—— 上面可知我们我们的数据格式是 K-V范例 的
知道K-V格式数据那我们就知道使用 什么数据布局 来储存了,有哈希表、树(二叉树二分查找树二分均衡 树红黑树B树B+树
综上所述,我们可以上面的数据布局 来计划 我们的索引体系

4.MYSQL索引体系 是什么呢?

为什么不按照上面说的格式储存呢?

众所周知,mysql的索引体系 使用 的是B+树,为什么是B+树呢?接下来我们逐个分析其他的存储布局 为什么不行。在此之前,我们还是必要 相识 两个前置知识----OLAP和OLTP

MySQL的索引体系
采用B+树的缘故原由
剖析

当我们存储的数据量越多时,对应建立的索引也会越大,当我们从磁盘读取到内存时就会产生IO题目 ,那我们又对索引建立索引嘛?不是的,以是 mysql采取的B+树

5.哈希表

在这里插入图片形貌

上面是哈希表的存储布局 ,我们来探究 这类的存储布局 的优缺点
缺点:

  • 哈希冲突会造成数据散列不匀称 ,会产生大量的线性查询,比较浪费时间
  • 不支持范围查询,当举行 范围查询的时间 ,必须要挨个遍历
  • 对于内存空间的要求比较高(要把全部数据加到到内存中)

长处 :
假如 是等值查询,那么会非常快

那么在mysql中有没有hash索引呢?

  • memory存储引擎使用 的是hash索引
  • innodb支持自顺应 hash

 6.树

6.1 二叉树

在这里插入图片形貌

二叉树本身是无序的,当我们在举行 数据查找时要挨个去跟每个节点举行 数据对比,看是否符合我们的数据要求,服从 低下

6.2 二分查找树(Binary Search Tree ,BST)

在这里插入图片形貌

二分查找树的特点:插入数据的时间 必须有序,左子树必须小于跟节点,右子树必须保证大于根节点。以是 使用 二分查找树对比二叉树来显然进步 了查询服从 。
但是假如 数据插入是递增或者递减的次序 的话,二分查找树就会退化成链表,查找服从 又降低了

在这里插入图片形貌

6.3 均衡 二叉树(Balanced Binary Tree, AVL树)

在这里插入图片形貌

根据二叉查找树的所暴暴露 的题目 ,我们通过使用 AVL树颠末 左旋或者右旋让树均衡 。但是为了保证均衡 ,在插入数据的时间 必须要旋转,通过插入性能的丧失 来补充 查询性能的提升 。读多写少的环境 还好,但是假如 我读写哀求 一样多,那就不合适了。

6.4 红黑树

在这里插入图片形貌

红黑树也是颠末 左旋和右旋让树均衡 起来,还有变色的活动 ,最长子树只要不超过最短子树的两倍即可…以是 就能让查询性能和插入性能近似取得一个均衡 ,但是随着数据的插入,发现树的深度会变深,深的深度越深,意味着IO次数越多,影响数据读取的服从 。

6.5 B树

针对红黑树暴露的题目 ,那么我们应该怎样 进步 读取的服从 呢?我们能不能从有序的二叉树,变成有序的多叉树呢,如许 我们就可以储存更多的数据

在这里插入图片形貌

Degree为4表示的是一个节点存储三个数据值,超过就要变换。那么现实 的数据是怎么存储的呢?我们必要 Key完备 的数据行

在这里插入图片形貌

上图是B树现实 存储数据的图,每个节点有三个元素key指针数据
查找实例,假如 我想找28这个数据,先从磁盘块1开始发现读取不到,经对比范围在p2指针指向的磁盘块3,还是没找到,再根据磁盘块3的p2指针指向磁盘块8找到28。我们来分析一下,每个磁盘块大小为16kb,我们查找了三个磁盘块只需读取48kb,那么三层B树能存储多少条记录呢?

我们抱负 化一下,假设key和指针不占用大小,一条数据占用1k的大小,那么磁盘1数据可以存储16条,磁盘3也是16条,磁盘8也是16条,那么我们只能存储161616=4096条记录,这显着 有点少了,而且我们是抱负 化的,现实 key和指针也是占用大小的。

于是乎我们不禁思考 ,为什么存储的数据量那么少?
我们发现每层存储的大小都被data给占用了,那么我们能不能只存储key跟指针呢?为此就引出了B+树

6.6 B+树

在这里插入图片形貌

B树到B+树的演变:非叶子节点不存储数据,叶子节点才存储数据

在这里插入图片形貌

上图我们可以假设p1和28为一组占用10字节大小,那么第一层可以存储16000/10=1600个如许 的大小,第二层也是1600,第三层data占用1kb,那就是16条,以是 总的存储1600160016=40960000(4096万)条记录

mysql索引布局 一样平常 3~4层,但是还要留意 一个题目 。假设我们就是3层存储布局 ,怎样 存储更多的数据?
刚刚我们假设的是p1和28为10字节大小,那假如 它们是1字节呢,那么存储总量是160001600010=4096000000。以是 就引申出口试 不停 被提到的建立索引用int还是var好?

答:保证key的长度越小也好,varchar小于4字节用varcahr,大于4字节用int

根据B+树的特点,存储量大,查询快,以是 mysql使用 的就是B+树

总结

至此mysql索引体系 为什么使用 的是B+树就讲述完了,假如 有什么讲错的地方渴望 能提示 我改正过来。

到此这篇关于MySQL的索引体系 采用B+树的缘故因由 分析 的文章就先容 到这了,更多干系 MySQL索引B+树内容请搜索 脚本之家从前 的文章或继续欣赏 下面的干系 文章渴望 大家以后多多支持脚本之家!


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

avatar 唰唰冷呵映 | 2021-9-19 06:48:24 | 显示全部楼层
很经典,收藏了!
回复

使用道具 举报

avatar 休闲时光8882017 | 2021-9-19 07:24:27 | 显示全部楼层
学习雷锋,好好回帖!
回复

使用道具 举报

avatar 刘和谐1 | 2021-9-21 11:07:28 | 显示全部楼层
回帖也有有水平的!
回复

使用道具 举报

avatar 阳子1989 | 2021-9-26 10:48:28 | 显示全部楼层
这么好的帖子,应该加精华!
回复

使用道具 举报

avatar 爱晚风愁制 | 2021-9-26 23:25:21 | 显示全部楼层
看在admin楼主的面子上,认真回帖!
回复

使用道具 举报

avatar 曹羁奔陈构 | 2021-9-27 16:11:16 | 显示全部楼层
今天是个特别的日子,值得纪念!
回复

使用道具 举报

avatar 123457376 | 2021-10-3 05:26:30 | 显示全部楼层
什么狗屁帖子啊,admin楼主的语文是苍老师教的吗?
回复

使用道具 举报

avatar 爱宇婷疤 | 2021-10-3 05:48:59 | 显示全部楼层
admin楼主,您提前出院了?
回复

使用道具 举报

avatar 尘埃416 | 2021-10-3 05:49:35 | 显示全部楼层
勤奋灌水,天天向上!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则