# 为什么使用B+Tree
索引是一种支持快速查询的数据结构，同时索引优化也是后端工程师的必会知识点。各个公司都有所谓的MySQL”军规“，其实这些所谓的优化和规定，并不是什么高深的技术，只是要求大家正确建立和使用索引而已。工欲善其事必先利其器，想要正确运用索引，需要了解其底层实现原理，本文将探索关于索引的“是什么”以及”为什么“。
MySQL中关于索引的概念有很多，为了避免混淆，在上一篇文章中关于索引在不同维度分类设计到的一些名词进行了解释，如辅助索引，唯一索引，覆盖索引，B+Tree索引…., 墙裂建议不明白的小伙伴可以先去看看图解MySQL索引(上)—聊聊索引的分类 (opens new window)，本文中关于索引类型的各种定义不再复述。
# 一，磁盘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？如果不行，是因为什么呢？
