创建高性能索引
索引是提高 MySQL 查询性能的一个重要途径，但过多的索引可能会导致过高的磁盘使用率以及过高的内存占用，从而影响应用程序的整体性能。
应当尽量避免事后才想起添加索引，因为事后可能需要监控大量的 SQL 才能定位到问题所在，而且添加索引的时间肯定是远大于初始添加索引所需要的时间，可见索引的添加也是非常有技术含量的。
接下来将向你展示一系列创建高性能索引的策略，以及每条策略其背后的工作原理。
但在此之前，先了解与索引相关的一些算法和数据结构，将有助于更好的理解后文的内容。
索引相关的数据结构和算法
通常我们所说的索引是指 B-Tree 索引，它是目前关系型数据库中查找数据最为常用和有效的索引，大多数存储引擎都支持这种索引。
使用 B-Tree 这个术语，是因为 MySQL 在 CREATE TABLE 或其他语句中使用了这个关键字，但实际上不同的存储引擎可能使用不同的数据结构，比如 InnoDB 就是使用的 B+Tree。
B+Tree 中的 B 是指 balance，意为平衡。需要注意的是，B+ 树索引并不能找到一个给定键值的具体行，它找到的只是被查找数据行所在的页，接着数据库会把页读入到内存，再在内存中进行查找，最后得到要查找的数据。
在介绍 B+Tree 前，先了解一下二叉查找树，它是一种经典的数据结构，其左子树的值总是小于根的值，右子树的值总是大于根的值，如下图①。
如果要在这棵树中查找值为 5 的记录，其大致流程：先找到根，其值为 6，大于 5，所以查找左子树，找到 3，而 5 大于 3，接着找 3 的右子树，总共找了 3 次。
同样的方法，如果查找值为 8 的记录，也需要查找 3 次。所以二叉查找树的平均查找次数为(3 + 3 + 3 + 2 + 2 + 1) / 6 = 2.3次。
而顺序查找的话，查找值为 2 的记录，仅需要 1 次，但查找值为 8 的记录则需要 6 次。
所以顺序查找的平均查找次数为：(1 + 2 + 3 + 4 + 5 + 6) / 6 = 3.3次，因此大多数情况下二叉查找树的平均查找速度比顺序查找要快。
创建高性能索引
索引是提高 MySQL 查询性能的一个重要途径，但过多的索引可能会导致过高的磁盘使用率以及过高的内存占用，从而影响应用程序的整体性能。
应当尽量避免事后才想起添加索引，因为事后可能需要监控大量的 SQL 才能定位到问题所在，而且添加索引的时间肯定是远大于初始添加索引所需要的时间，可见索引的添加也是非常有技术含量的。
接下来将向你展示一系列创建高性能索引的策略，以及每条策略其背后的工作原理。
但在此之前，先了解与索引相关的一些算法和数据结构，将有助于更好的理解后文的内容。
索引相关的数据结构和算法
通常我们所说的索引是指 B-Tree 索引，它是目前关系型数据库中查找数据最为常用和有效的索引，大多数存储引擎都支持这种索引。
使用 B-Tree 这个术语，是因为 MySQL 在 CREATE TABLE 或其他语句中使用了这个关键字，但实际上不同的存储引擎可能使用不同的数据结构，比如 InnoDB 就是使用的 B+Tree。
B+Tree 中的 B 是指 balance，意为平衡。需要注意的是，B+ 树索引并不能找到一个给定键值的具体行，它找到的只是被查找数据行所在的页，接着数据库会把页读入到内存，再在内存中进行查找，最后得到要查找的数据。
在介绍 B+Tree 前，先了解一下二叉查找树，它是一种经典的数据结构，其左子树的值总是小于根的值，右子树的值总是大于根的值，如下图①。
如果要在这棵树中查找值为 5 的记录，其大致流程：先找到根，其值为 6，大于 5，所以查找左子树，找到 3，而 5 大于 3，接着找 3 的右子树，总共找了 3 次。
同样的方法，如果查找值为 8 的记录，也需要查找 3 次。所以二叉查找树的平均查找次数为(3 + 3 + 3 + 2 + 2 + 1) / 6 = 2.3次。
而顺序查找的话，查找值为 2 的记录，仅需要 1 次，但查找值为 8 的记录则需要 6 次。
所以顺序查找的平均查找次数为：(1 + 2 + 3 + 4 + 5 + 6) / 6 = 3.3次，因此大多数情况下二叉查找树的平均查找速度比顺序查找要快。
平衡二叉树旋转
通过一次左旋操作就将插入后的树重新变为平衡二叉树是最简单的情况了，实际应用场景中可能需要旋转多次。
至此我们可以考虑一个问题，平衡二叉树的查找效率还不错，实现也非常简单，相应的维护成本还能接受，为什么 MySQL 索引不直接使用平衡二叉树？
随着数据库中数据的增加，索引本身大小随之增加，不可能全部存储在内存中，因此索引往往以索引文件的形式存储在磁盘上。
这样的话，索引查找过程中就要产生磁盘 I/O 消耗，相对于内存存取，I/O 存取的消耗要高几个数量级。
可以想象一下一棵几百万节点的二叉树的深度是多少？如果将这么大深度的一颗二叉树放磁盘上，每读取一个节点，需要一次磁盘的 I/O 读取，整个查找的耗时显然是不能够接受的。那么如何减少查找过程中的 I/O 存取次数？
一种行之有效的解决方法是减少树的深度，将二叉树变为 m 叉树（多路搜索树），而 B+Tree 就是一种多路搜索树。
