失踪人口回归, 近期换工作一波三折, 耽误了不少时间, 从今开始每周更新~
索引是一种支持快速查询的数据结构, 同时索引优化也是后端工程师的必会知识点. 各个公司都有所谓的 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 二叉搜索树退化成链表
二叉搜索树, 如果左子树不为空, 则左子树上所有节点均小于根节点, 右子树节点均大于根节点; 由其属性不难看出, 这种树非常适合数据查找. 不过有个致命的缺点是二叉搜索树的树型取决于数据的输入顺序, 极端情况下会退化成链表.
2.3 平衡二叉搜索树过于严格
为了解决上述问题, 平衡二叉搜索树就诞生了. 在保证数据顺序的基础上, 又能维持树型, 保证每个节点的左右子树高度相差不超过 1.
不过由于要维持树的平衡, 在插入数据时可能要进行大量的数据移动. 平衡搜索二叉树过于严格的平衡要求, 导致几乎每次插入和删除节点都会破坏树的平衡性, 使得树的性能大打折扣.
2.4 红黑树高度过高, 磁盘 IO 次数频繁
有没有一种数据结构, 即能够快速查找数据, 又不需要频繁的调整以维持平衡呢? 这时红黑树就闪亮登场了.
红黑树和其他二叉搜索树类似, 都是在进行插入和删除操作时通过特定操作保持二叉查找树的性质, 从而获得较高的查找性能. 与之不同的是, 红黑树的平衡性并不像平衡搜索二叉树一样严格的同时, 又能保证在, O(log n) 时间复杂度内做查找和删除.
红黑树通过改变节点的颜色, 可以有效减少节点的移动次数, 由于红黑树的实现比较复杂, 本文不再展开, 感兴趣的小伙伴可以去深入学习.
看似红黑树是一种完美的数据结构, 能够胜任索引的工作. 但 MySQL 并未使用其作为索引的实现, 主要原因在于红黑树的深度过大, 数据检索时造成磁盘 IO 频繁, 假设一个每个节点存储在一个 page 中, 树的高度为 10, 则每次检索可能就需要进行 10 次磁盘 IO.
2.5 B-Tree 不支持顺序查询
B-Tree 是一种自平衡的多叉搜索树, 一个节点可以拥有两个以上的子节点. 适合读写相对大的数据块的存储系统, 例如磁盘.
由于 MySQL 索引一般都存储在内存中, 如果使用 B-Tree 作为索引的话, 索引和数据存储在一块, 分布在各个节点中; 而内存资源往往比较宝贵, 一定内存的情况下可以存储的索引数量相对有限, 毕竟每条数据的大小一般远大于索引列的大小, 导致内存使用率不高.
数据查询过程中往往会有顺序查询, 而 B-Tree 和红黑树对于顺序查询并不友好.
2.6 为什么选 B+Tree
B+Tree 是在 B-Tree 基础上演进而来的. 与之不同的是 B+Tree 的数据页只存储在叶子节点中, 并且叶子节点之间通过指针相连, 为双向链表结构.
B+Tree 的优点可以分为以四个:
充分利用空间局部性原理, 适合磁盘存储.
树的高度很低, 能够在存储大量数据情况下, 进行较少的磁盘 IO[见下文介绍] .
能够很好支持单值, 范围查询, 有序性查询.
索引和数据分开存储, 让更多的索引存储在内存中.
三, MySQL 中索引实现
3.1 巧妙利用 B+Tree
MySQL 中的数据存储通常以 Page 为单位, 俗称数据页, 每个 Page 对应 B+Tree 的一个节点. 页是 InnoDB 磁盘管理的最小单位, 默认每个数据页的大小为 16kb, 也可以通过参数 innodb_page_size 将页的大小设置成其他值.
数据库的页大小和操作系统类似, 是指存放数据时, 每一块连续区域数据的大小. 比如一个 1M 的数据存放在数据库中时, 需要大概 64 个页来存放(1024=64*16). 如果是在操作系统上安装的数据库, 最好将数据库页大小设置为操作系统页大小的倍数, 才是最佳设置.
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 可能在缓存中), 然后在数据页中进行二分查找, 定位到对应的记录.
四, 总结
大家耳熟能详的 B+Tree 索引是一种非常优秀的数据结构, 也是面试热点问题. 本文从数据结构和磁盘 IO 两个方面分析了为什么使用 B+Tree, 以及 MySQL 的 InnoDB 存储引擎的索引实现. 在笔者面试过程中, 被问到 MySQL 索引时通常也是从底层数据结构特点以及结合磁盘 IO 两个角度去分析, 屡试不爽.
学习一门技术时, 我们不仅要知道其优点更要了解其缺点和瓶颈. 在分析 MySQL 索引的实现时, 不妨试试从其他数据结构的缺点入手! 在 Redis 中使用跳表实现了有序集合 Zset, 同样支持高效的顺序查询, 对比 MySQL 索引实现, 跳表能否替换 B+Tree? 如果不行, 是因为什么呢?
来源: https://www.cnblogs.com/liqiangchn/p/12995831.html