联博接口:图解MySQL索引(二)—为什么使用B+Tree

admin 1周前 (09-18) 科技 87 4

失踪人口回归,近期换事情一波三折,耽误了不少时间,从今开始每周更新~

索引是一种支持快速查询的数据结构,同时索引优化也是后端工程师的必会知识点。各个公司都有所谓的MySQL”军规“,实在这些所谓的优化和划定,并不是什么高深的手艺,只是要求人人准确确立和使用索引而已。工欲善其事必先利其器,想要准确运用索引,需要领会其底层实现原理,本文将探索关于索引的“是什么”以及”为什么“。

MySQL中关于索引的观点有许多,为了制止混淆,在上一篇文章中关于索引在差别维度分类设计到的一些名词举行领会释,如辅助索引,唯一索引,笼罩索引,B+Tree索引…., 墙裂建议不明白的小伙伴可以先去看看图解MySQL索引(上)—聊聊索引的分类,本文中关于索引类型的种种界说不再复述。

一,磁盘IO问题

1.1 磁盘IO

所谓磁盘IO,简朴来讲就是就是将磁盘中的数据读取到内存或者是从内存写入磁盘。在系统开发与设计历程中,磁盘IO的瓶颈往往不能忽略,由于这是一个相对对照耗时的操作。

上图是一个机械硬盘,虽然速率不如SSD,然则由于价格低廉,现在仍是主流的存储介质。它的IO操作通常需要寻道,旋转和传输三个步骤。

寻道,是指将读写磁头移动到准确的磁道,寻道时间越短,IO操作越快,现在磁盘的平均寻道时间一样平常在3-15ms左右。

旋转,是指将盘片旋转到请求数据所在的扇区,这部门所需要的时间由硬盘的设置所决议。旋转延迟由磁盘转速所决议,也就是常说的7200转和5400转等。

例如,7200转是指每分钟可以旋转7200圈,那么旋转一圈所需要的时间就是60*1000/7200 ≈ 8.33ms,而旋转延迟通常取旋转一周时间的1/2,也就是约莫4.17ms。

传输,磁盘传输的速率通常在几十到上百M每秒,假设速率为20M/s,要传输的数据为64kb,则传输时间则是 64 / 1024 / 20 * 1000 = 3.125ms。不外现在盛行的SSD传输速率大幅度提升,SATA Ⅱ可以到达300M/s,传输速率往往远小于前两步操作以是传输时间往往可以忽略不记。

机械硬盘的延续读写性能很好,但随机读写性能很差,这主要是由于磁头移动到准确的磁道上需要时间,随机读写时,磁头需要一直的移动,时间都虚耗在了磁头寻址上,以是性能不高。

上述历程是对传统机械磁盘IO延迟的大略先容,目的是告诉人人磁盘IO历程是个耗时的历程,内存操作往往与之速率不在同一个数目级。即使是现在对照盛行的SSD,想必内存中数据读取性能也差之千里。

1.2 局部性原理

由于磁盘IO是一个对照耗时的操作,而操作系统在设计时则界说一个空间局部性原则,局部性原理是指CPU接见存储器时,无论是存取指令照样存取数据,所接见的存储单元都趋于群集在一个较小的延续区域中

在操作系统的文件系统中,数据也是凭据page划分的,一样平常为4k或8k。当计算机接见一个地址数据时,不仅会加载当前数据所在的数据页,还会将当前数据页相邻的数据页一同加载到内存。而这个历程实际上只发生了1次磁盘IO,这个理论对于索引的数据结构设计异常有辅助。

二,索引数据结构演进

索引是一种支持快速查找的数据结构,在运用中往往还要求能够支持顺序查询,而常见的数据结构有许多,好比数组,链表,二叉树,散列表,二叉搜索树,平衡搜索二叉树,红黑树,跳表等。仅仅从数据结构那么为什么选择B+Tree呢?

首先对于数组,链表这种线性表来说,适合存储数据,而不是查找数据,同样,对于通俗二叉树来说,数据存储没有特定纪律,以是也不适合。

2.1 哈希索引不能知足营业需求

哈希(Hash)是一种异常快的查找方式,在一样平常情形下这种查找的时间复杂度为O(1),即一样平常仅需要一次查找就能定位到数据。在种种编程语言和数据库中应用普遍,如Java,Python,Redis中都有使用。

哈希结构在单条数据的等值查询是性能异常优异,然则只能用来搜索等值的查询, 对于局限查询,模糊查询(最左前缀原则)都不支持,以是不能很好的支持营业需求;以是MySQL并没有显式支持Hash索引,而是凭据数据的接见频次和模式自动的为热门数据页确立哈希索引,称之为自适应哈希索引。

而且由于哈希函数的随机性,Hash索引通常都是随机的内存接见,对于缓存不友好,会造成频仍的磁盘IO。

2.2 二叉搜索树退化成链表

二叉搜索树,若是左子树不为空,则左子树上所有节点均小于根节点,右子树节点均大于根节点;由其属性不难看出,这种树异常适合数据查找。不外有个致命的瑕玷是二叉搜索树的树型取决于数据的输入顺序,极端情形下会退化成链表。

阳光在线,诚信在线  第1张

2.3 平衡二叉搜索树过于严酷

为领会决上述问题,平衡二叉搜索树就诞生了。在保证数据顺序的基础上,又能维持树型,保证每个节点的左右子树高度相差不跨越1。

不外由于要维持树的平衡,在插入数据时可能要举行大量的数据移动。平衡搜索二叉树过于严酷的平衡要求,导致险些每次插入和删除节点都市损坏树的平衡性,使得树的性能大打折扣。

阳光在线,诚信在线  第2张

2.4 红黑树高度过高,磁盘IO次数频仍

有没有一种数据结构,即能够快速查找数据,又不需要频仍的调整以维持平衡呢?这时红黑树就闪亮登场了。

红黑树和其他二叉搜索树类似, 都是在举行插入和删除操作时通过特定操作保持二叉查找树的性子,从而获得较高的查找性能。与之差别的是,红黑树的平衡性并不像平衡搜索二叉树一样严酷的同时,又能保证在, O(log n) 时间复杂度内做查找和删除。

红黑树通过改变节点的颜色,可以有用削减节点的移动次数,由于红黑树的实现对照复杂,本文不再睁开,感兴趣的小伙伴可以去深入学习。

阳光在线,诚信在线  第3张

看似红黑树是一种完善的数据结构,能够胜任索引的事情。但MySQL并未使用其作为索引的实现,主要原因在于红黑树的深度过大,数据检索时造成磁盘IO频仍,假设一个每个节点存储在一个page中,树的高度为10,则每次检索可能就需要举行10次磁盘IO。

2.5 B-Tree不支持顺序查询

B-Tree是一种自平衡的多叉搜索树,一个节点可以拥有两个以上的子节点。适合读写相对大的数据块的存储系统,例如磁盘。

阳光在线,诚信在线  第4张

由于MySQL索引一样平常都存储在内存中,若是使用B-Tree作为索引的话,索引和数据存储在一块,漫衍在各个节点中;而内存资源往往对照名贵,一定内存的情形下可以存储的索引数目相对有限,究竟每条数据的巨细一样平常远大于索引列的巨细,导致内存使用率不高。

数据查询历程中往往会有顺序查询,而B-Tree和红黑树对于顺序查询并不友好

2.6 为什么选B+Tree

B+Tree是在B-Tree基础上演进而来的。与之差别的是B+Tree的数据页只存储在叶子节点中,而且叶子节点之间通过指针相连,为双向链表结构。

阳光在线,诚信在线  第5张

B+Tree的优点可以分为以四个:

  1. 充分行使空间局部性原理,适合磁盘存储。

  2. 树的高度很低,能够在存储大量数据情形下,举行较少的磁盘IO【见下文先容】。

  3. 能够很好支持单值,局限查询,有序性查询。

  4. 索引和数据离开存储,让更多的索引存储在内存中。

三,MySQL中索引实现

3.1 巧妙行使B+Tree

MySQL中的数据存储通常以Page为单元,俗称数据页,每个Page对应B+Tree的一个节点。页是InnoDB磁盘治理的最小单元,默认每个数据页的巨细为16kb,也可以通过参数innodb_page_size将页的巨细设置成其他值。

数据库的页巨细和操作系统类似,是指存放数据时,每一块延续区域数据的巨细。好比一个1M的数据存放在数据库中时, 需要也许64个页来存放(1024=64*16)。若是是在操作系统上安装的数据库,最好将数据库页巨细设置为操作系统页巨细的倍数,才是最佳设置。

阳光在线,诚信在线  第6张

3.2 树的高度-有用削减磁盘IO次数

通常情形下,一张MySQL表中有成千上万条数据,而磁盘IO次数往往与数的高度成正比。默认情形下一个Page的巨细为16kb,由于每个Page中数据通过指针相连,且每个指针巨细为6字节。

在事情中,我们通常使用长度为8个字节的bigint类型作为主键id的类型。已知,每一条数据都市包罗一个6字节的指针(数据页中每条纪录都有指向下一条纪录的指针,然则没有指向上一条纪录的指针);以是一条索引数据约莫占用8+6=14个字节,一个Page中能存储16 * 1024 / 14 ≈ 1170条索引数据。高度为2的B+Tree约莫能存储1170*16 = 18720条这样的纪录。同理,高度为3的B+Tree的B+Tree约莫能存储1170 * 1170 * 16 = 21902400,约莫两千万条数据。 (每个节点约莫能存储1170条纪录,可以理解为此时B+Tree为1170叉树)

例如,要检索id=008的数据,则需要举行三次磁盘IO找到对应的数据页(最多三次,由于Page可能在缓存中),然后在数据页中举行二分查找,定位到对应的纪录。

阳光在线,诚信在线  第7张

四,总结

人人耳熟能详的B+Tree索引是一种异常优异的数据结构,也是面试热门问题。本文从数据结构和磁盘IO两个方面剖析了为什么使用B+Tree,以及MySQL的InnoDB存储引擎的索引实现。在笔者面试历程中,被问到MySQL索引时通常也是从底层数据结构特点以及连系磁盘IO两个角度去剖析,屡试不爽。

学习一门手艺时,我们不仅要知道其优点更要领会其瑕玷和瓶颈。在剖析MySQL索引的实现时,不妨试试从其他数据结构的瑕玷入手!在Redis中使用跳表实现了有序聚集Zset,同样支持高效的顺序查询,对比MySQL索引实现,跳表能否替换B+Tree?若是不行,是由于什么呢?

阳光在线,诚信在线  第8张,

欧博注册网址

www.schltkd.com欢迎进入欧博网址(Allbet Gaming),欧博网址开放会员注册、代理开户、电脑客户端下载、苹果安卓下载等业务。

阳光在线声明:该文看法仅代表作者自己,与本平台无关。转载请注明:联博接口:图解MySQL索引(二)—为什么使用B+Tree

站点信息

  • 文章总数:199
  • 页面总数:0
  • 分类总数:8
  • 标签总数:298
  • 评论总数:452
  • 浏览总数:24012

标签列表