MySQL 索引原理
认识索引
这里不废话，直接上我以前写的一篇博客，大家可以先去学习一下，大概了解一下索引~
索引的目的
索引存在的意义就是为了提高查询效率，这与我们查阅图书所用的目录是一个道理：先定位到章，然后定位到该章下的一个小节，然后找到页数。
相似的例子还有：
- 查字典
- 查火车车次
- 飞机航班
而他们的本质都是：通过不断地缩小想要获取数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件，也就是说，有了这种索引机制，我们可以总是用同一种查找方式来锁定数据。
硬盘
对于 MySQL 的数据，他们最后的归宿都是落入了硬盘中。
因为磁盘的 IO 开销是会大大的影响到我们的查询，所以，计算机本身也帮我们做了优化的处理。
当我们在做一次数据的读取时，计算机不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内。
通过这种读取，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。
索引的数据结构
MySQL 索引底层是使用 B+Tree 这种数据结构。
但是那么多种数据结构，为什么 MySQL 却使用了 B+Tree？
数据结构
- 数组、链表
INFO
数组、链表属于线性表，适合存储数据，但是不适合查找。
- 二叉树
INFO
二叉树的话，相对于数组、链表会好一些，但是它在存储数据时没有特定规律，所以也不合适。
- 哈希
INFO
哈希（Hash）是一种非常快的查找方法，在一般情况下这种查找的时间复杂度为O（1），即一般仅需要一次查找就能定位到数据。
哈希结构在单条数据的等值查询是性能非常优秀，但是只能用来搜索等值的查询， 对于范围查询，模糊查询（最左前缀原则）都不支持，所以不能很好的支持业务需求；所以MySQL并没有显式支持Hash索引，而是根据数据的访问频次和模式自动的为热点数据页建立哈希索引，称之为自适应哈希索引。
并且由于哈希函数的随机性，Hash索引通常都是随机的内存访问，对于缓存不友好，会造成频繁的磁盘IO。
- 二叉搜索树
INFO
二叉搜索树，如果左子树不为空，则左子树上所有节点均小于根节点，右子树节点均大于根节点；
由其属性不难看出，这种树非常适合数据查找。不过有个致命的缺点是二叉搜索树的树型取决于数据的输入顺序，极端情况下会退化成链表。
- 平衡二叉搜索树
INFO
为了解决二叉搜索树的上述问题，平衡二叉搜索树就诞生了。在保证数据顺序的基础上，又能维持树型，保证每个节点的左右子树高度相差不超过1。
**不过由于要维持树的平衡，在插入数据时可能要进行大量的数据移动。**平衡搜索二叉树过于严格的平衡要求，导致几乎每次插入和删除节点都会破坏树的平衡性，使得树的性能大打折扣。
- 红黑树
INFO
红黑树和其他二叉搜索树类似， 都是在进行插入和删除操作时通过特定操作保持二叉查找树的性质，从而获得较高的查找性能。
与之不同的是，红黑树的平衡性并不像平衡搜索二叉树一样严格的同时，又能保证在 O($\log(n)$) 时间复杂度内做查找和删除。红黑树通过改变节点的颜色，可以有效减少节点的移动次数
乍一看红黑树是一种完美的数据结构，能够胜任索引的工作。但 MySQL 并未使用其作为索引的实现，主要原因在于红黑树的深度过大，数据检索时造成磁盘 IO 频繁，假设一个每个节点存储在一个 page 中，树的高度为10，则每次检索可能就需要进行10次磁盘 IO。
- B-Tree
INFO
B-Tree 是一种自平衡的多叉搜索树，一个节点可以拥有两个以上的子节点。适合读写相对大的数据块的存储系统，例如：磁盘。
但由于 MySQL 索引一般都存储在内存中，如果使用 B-Tree 作为索引的话，索引和数据存储在一块，分布在各个节点中。而内存资源往往比较宝贵，一定内存的情况下可以存储的索引数量相对有限，毕竟每条数据的大小一般远大于索引列的大小，导致内存使用率不高。数据查询过程中往往会有顺序查询，而 B-Tree 和红黑树一样对于顺序查询并不友好。
那么有没有一种数据结构，即能够快速查找数据，又不需要频繁的调整以维持平衡，同时对磁盘IO比较友好呢？
B-Tree 能够很好的解决前面两个问题，那能不能对 B-Tree 进行演进改造，使其对磁盘 IO 访问不那么频繁呢？再这样的需求背景下，B+Tree 诞生了。
- B+Tree
INFO
B+Tree 是在 B-Tree 基础上演进而来的。与之不同的是 B+Tree 的数据页只存储在叶子节点中，并且叶子节点之间通过指针相连，为双向链表结构。
B+Tree 的优点
- 高效的查找和范围查询性能
B+Tree 的结构使得查找操作非常高效。所有的叶节点都按键值的顺序存储，并且相互链接，这使得对于范围查询（如找出所有在某个值范围内的记录）特别高效。
- 节省磁盘空间
在 B+Tree 中，只有叶节点包含数据指针或实际的数据值，而内部节点只存储键值。这样的设计减少了内部节点所需的空间，使得更多的键值可以存储在一个节点中，从而减少了磁盘I/O次数。
- 优化磁盘I/O操作
数据库系统常常运行在存储数据的磁盘驱动器上。B+Tree 的结构减少了节点分裂的频率，并且由于叶节点是顺序访问的，所以它们特别适合磁盘的顺序读取特性。
- 更好的缓存利用性
由于内部节点不包含实际数据，而只包含键值，这意味着更多的键值可以被缓存在内存中，从而减少访问磁盘的需要。
- 支持顺序和随机访问
B+Tree 通过其叶节点的链表结构支持高效的顺序访问，同时也支持随机数据访问。
- 写操作的性能
B+Tree 减少了因插入或删除操作而导致的树重新平衡的频率，这在频繁更新的数据库环境中是一个重要的优势。
MySQL 中是如何使用 B+Tree？
MySQL 中的数据存储通常以 Page（数据页） 为单位，每个 Page 对应 B+Tree 的一个节点。
TIP
页是 InnoDB 磁盘管理的最小单位，默认每个数据页的大小为 16 kb，也可以通过参数 innodb_page_size 将页的大小设置成其他值。
数据库的页大小和操作系统类似，是指存放数据时，每一块连续区域数据的大小。比如一个 1 M的数据存放在数据库中时， 需要大概 64 个页来存放（1024 = 64 * 16）。
在操作系统上安装数据库，最好将数据库页大小设置为操作系统页大小的倍数，才是最佳设置。
通常情况下，一张 MySQL 表中有成千上万条数据，而磁盘 IO 次数往往与数的高度成正比。
TIP
默认情况下一个Page的大小为16kb，由于每个Page中数据通过指针相连，且每个指针大小为6字节。在工作中，我们通常使用长度为8个字节的bigint类型作为主键id的类型。
假设每条记录长度为 1 kb（包含指针），已知每一条数据都会包含一个 6 字节的指针（数据页中每条记录都有指向下一条记录的指针，但是没有指向上一条记录的指针），所以一条索引数据大约占用 8 + 6 = 14个字节，一个 Page 中能存储 16 * 1024 / 14 ≈ 1170 条索引数据（注：InnoDB 引擎中 B+Tree 的数据页存储在叶子结点）。高度为 2 的 B+Tree 大约能存储 1170 * 16 = 18720 条这样的记录。
同理，高度为 3 的 B+Tree 大约能存储 1170 * 1170 * 16 = 21902400，大约两千万条数据。 （每个节点大约能存储 1170 条记录，概括的理解为此时 B+Tree 为 1170 叉树）
例如
要检索 id = 008 的数据，则需要进行三次磁盘 IO 找到对应的数据页（最多三次，因为 Page 可能在缓存中），然后在数据页中进行二分查找，定位到对应的记录。
在线 B+Tree
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html