江苏龙网

  1. 首页 > 资讯 > 科技 > >

|为什么使用B+Tree？


索引是一种支持快速查询的数据结构 ， 同时索引优化也是后端工程师的必会知识点 。 各个公司都有所谓的MySQL”军规“ ， 其实这些所谓的优化和规定 ， 并不是什么高深的技术 ， 只是要求大家正确建立和使用索引而已 。 工欲善其事必先利其器 ， 想要正确运用索引 ， 需要了解其底层实现原理 ， 本文将探索关于索引的“是什么”以及”为什么“ 。
MySQL中关于索引的概念有很多 ， 为了避免混淆 ， 在上一篇文章中关于索引在不同维度分类设计到的一些名词进行了解释 ， 如辅助索引 ， 唯一索引 ， 覆盖索引 ， B+Tree索引…., 墙裂建议不明白的小伙伴可以先去看看图解MySQL索引(上)—聊聊索引的分类 ， 本文中关于索引类型的各种定义不再复述 。
一 ， 磁盘IO问题#
1.1 磁盘IO
所谓磁盘IO ， 简单来讲就是就是将磁盘中的数据读取到内存或者是从内存写入磁盘 。 在系统开发与设计过程中 ， 磁盘IO的瓶颈往往不可忽略 ， 因为这是一个相对比较耗时的操作 。
|为什么使用B+Tree？
本文插图

上图是一个机械硬盘 ， 虽然速度不如SSD ， 但是由于价格低廉 ， 目前仍是主流的存储介质 。 它的IO操作通常需要寻道 ， 旋转和传输三个步骤 。
|为什么使用B+Tree？
本文插图

寻道 ， 是指将读写磁头移动到正确的磁道 ， 寻道时间越短 ， 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呢？
首先对于数组 ， 链表这种线性表来说 ， 适合存储数据 ， 而不是查找数据 ， 同样 ， 对于普通二叉树来说 ， 数据存储没有特定规律 ， 所以也不适合 。


推荐阅读


上一篇：IT时报|20年后，网易回家了，中概股回归三问

下一篇：艾尔数码小栈|全“芯”升级！首发天玑1000Plus，iQOO Z1强悍性能降维打击