mysql索引为什么使用B+树
通俗易懂告诉你mysql索引为什么使用B 树?回答这个问题之前先考虑两个问题:
1.mysql为什么使用索引?
2.支持索引的数据结构都有哪些?
1.mysql为什么使用索引?
持久化存储的数据都是存储于磁盘,而从磁盘中进行读写数据都是IO操作,相对于内存数据读取,IO操作很容易出现性能瓶颈问题,为了提升数据io数据读取的性能问题,就有了索引的概念。官方介绍中索引是提升数据库读取性能的数据结构。对索引最通俗易懂、最直观的解释就是好比是新华字典中每个首字母,如果想从厚厚的一本字典中找到一个汉字,从第一页开始一直找到最后一页显然是很耗时的。但是先确定好要能找的字的第一个首字母,范围就一下子(指时间短暂或动作迅速)(指时间短暂或动作迅速)缩小了,所消耗的时间也减少了很多,这就是索引的好处。当然实际上mysql并不是按照这种实现的,不过有异曲同工之处。至于mysql中具体的索引是怎么起作用的继续往下看!
2.支持索引的数据结构都有哪些?
常见的并且有助于提升查询速度的数据结构有一下几种:
哈希表
二叉树
红黑树
B树
B 树
依次说一下每种数据结构的优缺点。
哈希表
哈希存储都不陌生,就是按照K-V键值对的方式进行读取,可以根据key直接获取value值。对于等值查询,哈希查询速度很快,但是对于范围查询的场景,哈希索引并不适合,也需要每条数据都进行查询然后判断是否符合范围,相当于全表扫描,所以不是合适的索引数据类型。
二叉树
结构特点:每个节点下面最多有两个子节点,左侧子节点大于父节点,右侧子节点小于父节点。简单来讲优点就是缩小查找的范围,减少读取的次数。下面模拟插入指定数据:15 10 17 12 9 21 16,存储之后的数据结构为:
二叉树动态插入展示
比如说查找12,只需要对比两次就可以找到12.查找速率确实能提升。但mysql为什么没有使用二叉树,原因是可能会出现“链表”数据结构,此种结构相当于“全表扫描”。比如说需要存储连续的数据:
红黑树
红黑树实际上也算是二叉树的一种,也有人称之为平衡二叉树,主要的优点是解决普通二叉树可能存在的单链表结构。存储相同数据的存储图如下:
可以看出数据存储的位置基本上一致。主要看下对于连续数据存储的情况:
红黑树动态插入展示
可以发现红黑树解决了二叉树存储可能出现的链表结构。但是mysql为什么索引不用红黑树?原因在于红黑树的问题在树的高度问题,数据量增多,树的高度就会增加,每层树的读取时就相当于一次IO操作,显然也不是最好的数据结构。继续往下看。
B树
可以说B树的出现主要是解决红黑树中树高度过高导致磁盘IO读取次数过高的问题。首先说一下mysql中磁盘最小的存储单位为页,存储大小为16Kb,相当于人民币的分。页中存储多个节点,
每个节点由三部分组成:索引字段值、字段值所对应的行详细数据、行数据所在的磁盘地址。数据结构图如下:
B 树
mysql中使用存储引擎是B 数,原因是B 树相对于B树,非叶子节点不存储行详细数据,仅储存索引字段值以及所在磁盘的地址值,会存在冗余重复的索引字段值,优点在于每页存储单位中能存储更多的索引信息,形成的B数会更加矮小更胖。参考图如下:
逻辑图如下:
假设主键为bigint类型,主键bigint占用8个字节,指针地址占用6个字节,8 6=14,所以我们可以得出,一页能存放的指针个数为16k/(8 6)约等于1170。单条行记录大小约为1k,那么一个page能存储的行记录数为16k/1k=16,所以树高3层为1170117016约等于2190w数据,完美解决树高导致IO读取次数过高问题。
说明:文章中动态页面为国外某学校网站地址,支持多种数据结构演示,地址:https://www.cs.usfca.edu/~galles/visualization/,关于索引添加之后的数据摆放顺序可以参考网站演示.
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgggbab
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13