同乐学堂
一、索引开发
如何进行高质量的SQL编程，对索引的掌握和理解是关键。正确地使用索引可使SQL语句运行得更快，而错误地添加和使用索引可能带来有灾难性的结果。然而，如果DBA或开发人员能够了解索引的本质，例如索引是怎么实现的，优化器是怎么使用索引的，显然这会为SQL编程带来极大的提高。此外，不要盲从于一些所谓的规律，比如联合索引（a, b），索引不会用于对b列的查询。笔者始终相信，只要理解事物的本质，那么所有的问题都会迎刃而解。
9.1 缓冲池、顺序读取与随机读取
根据存储介质的不同，可以将数据库分为基于磁盘的数据库系统、基于内存的数据库系统，以及混合型数据库系统。基于磁盘的数据库系统（disk-base database）是最为常见的一种关系型数据库，比如MySQL、Oracle、SQL Server、DB2数据库。随着内存容量的不断增加，基于内存的数据库系统（in-memory database）也变得十分流行，MySQL NDB Cluster, Oracle Ten Times等数据库厂商都提供了内存关系型数据库系统。而混合型数据库系统（hybrid database）将上述两种数据库的优点进行了结合。
毫无疑问，基于内存的数据库系统是最快的，因为数据库不需要对磁盘进行操作。磁盘的速度要远慢于内存的速度，因此基于磁盘的数据库系统一般都有缓冲池，即一块内存区域，其作用是将从磁盘上读取的指定大小数据——称为页（或块），放入缓冲池。当再次读取时，数据库首先判断该页是否在缓冲池中，如果在则直接读取缓冲池中的页，如果不在则读取磁盘上的页。对于写操作，数据库将页读入缓冲池，然后在缓冲池中对页进行修改，修改完成后的页一般被异步地写入磁盘上。对于缓冲池的维护一般采用最近最少使用（Least Recently Used, LRU）算法。由此可见，缓冲池的大小决定了数据库的性能。若数据库中的数据可以完全存放于缓冲池中，则可以认为这时数据库的性能是最优的。除了同步/异步的写磁盘操作外，所有其他操作都可以在内存中完成。
对于MySQL数据库系统，由于其有着各种不同的存储引擎，因此其缓冲池是基于存储引擎的，也就是说每个存储引擎都有自己的缓冲池。对于MyISAM存储引擎来说，变量key_buffer_size决定了缓冲池的大小。对于InnoDB存储引擎来说，变量innodb_buffer_pool_size决定了缓冲池的大小。图9-1是Percona公司CTO Vadim对缓冲池所做的性能测试
图9-1中的A点表示此时缓冲池为20GB，数据库的数据全部被缓存在缓冲池中，这时数据库的性能是最优的，测试的结果为2500TPS（transaction per second）。因为数据已经全部被缓存，继续增大缓冲池为22GB并不会对性能有多大的提升。B点表示缓冲池的大小为18 GB，此时只有一小部分的数据不能被缓存，测试的结果为900TPS。可见缓冲池大小减少了10%，性能却下降了164%。C点表示缓冲池的大小为6GB，只能缓存30%的数据，这时数据库的性能更差，测试结果为130 TPS。
备注：有些同学对测试的名词可能不了解：http://www.ha97.com/5095.html 此篇链接详细介绍了专业测试的名词。例如tps，qps等，
通过上文个人总结：经过严格的基准测试既然缓冲池决定了Mysql的性能，那我们就来研究一下它，并调整其大小，然后在进行测试。
此链接介绍了怎么调整其大小，解释的比较详细还有个人案例做枚举：https://my.oschina.net/realfighter/blog/368225
在现实的生产环境中，在大多数情况下经过线上的一段运行时间后，数据库的大小通常都会大于内存的大小。例如数据库的大小是500GB，而服务器的内存可能只有96GB或者128GB。这种情况非常正常，一般来说，对于500GB的数据库，热点的数据可能是小部分的，具体占据多大的比重，这取决于具体的应用。
在生产环境中缓冲池的大小小于数据文件的大小，因此不可避免地存在磁盘的读取操作。但是传统的机械硬盘的特性决定了顺序读取要远快于离散读取。图9-2显示了传统机械硬盘的构造。
传统机械硬盘由磁头（head）、磁道（track）、扇区（sector）、柱面（cylinder）组成。读取时需要通过磁头的移动来定位数据，这个时间称为寻道时间（seek time）。目前，一块15000转SAS传统的机械硬盘的平均寻道时间为2.58ms。需要注意的是，这指的是平均时间。根据平均寻道时间，可以大致估算IOPS（IO per second），即1000/2.58=380 IOPS，而在实际情况下单块磁盘的IOPS一般为150左右。如果数据都是顺序存放的，显然寻道时间会快很多，这时的寻道时间一般只需0.14ms。可见，比平均寻道时间提高了18倍。
在介绍完上述内容后，可以给出顺序读取、随机读取的定义。顺序读取（sequntial read）是指顺序地读取磁盘上的页。随机读取（random read）是指访问的页不是连续的，需要磁盘的磁头不断移动。这里需要注意的是，这里的“顺序”指的是逻辑上的顺序，在物理上不可能保证所有的数据都是顺序的。而为了保证顺序，数据库存储引擎一般都根据区（extent）来管理页，例如在InnoDB存储引擎中1个区是连续的64个页。因此在顺序读取数据库时，可以保证这64个页是连续的，而区与区之间的页，可能是连续的也可能是不连续的。
固态硬盘是近几年出现的一种新的存储设备，其内部由闪存（flash memory）组成。因为具有低延迟性、低功耗、轻量，以及防震性，闪存设备已在移动设备上得到了广泛的应用。而企业级的生产应用使用固态硬盘，同时通过并联多块闪存来进一步提高数据传送的吞吐量。
图9-3显示了一个双通道的固态硬盘架构，通过支持4路的闪存交叉存储来降低固态硬盘的访问延时，同时增大并发的读写操作。而通过进一步增加通道的数量，固态硬盘的性能可以有线性的提高，例如常见的Intel SSD X-25M就是10通道的固态硬盘。
硬盘有着较低的访问延时。当主机发布一个读写请求时，固态硬盘的控制器会把I/O命令从逻辑地址映射到实际的物理地址，写操作还需要修改相应的映射表信息。算上这些额外的开销，固态硬盘的访问延时一般小于0.1 ms左右，随机读取可达4000 IOPS甚至更高。即使是固态硬盘，顺序读取还是要快于随机读取。因此对于固态硬盘的优化需要不同于传统机械硬盘的思考，但是这更多的是数据库存储引擎内部需要考虑的问题。
上述巴拉巴拉一大堆读个热闹就行，不必深究，总之一句话，性能不行：机械换固态。
9.2 数据结构与算法
B+树索引是最为常见，也是在数据库中使用最为频繁的一种索引。在介绍该索引之前先介绍与之密切相关的一些算法与数据结构，这有助于读者更好地理解B+树索引的工作方式。
9.2.1 二分查找法
二分查找法（binary search）也称为折半查找法，用来查找一组有序记录数组中某一项记录。其基本思想是：将记录按有序化（递增或递减）排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。
例如对于5、10、19、21、31、37、42、48、50、52这10个数，要从中查找48这条记录，其查找过程如图9-4所示。
从图9-4可以看出，3次就找到了48这个数。如果是顺序查找，则需要8次。因此二分查找法的效率比顺序查找法要好（平均来说），如果说查5这条记录，顺序查找只需1次，而二分查找法需要4次。对于上面10个数来说，平均查找次数为（1+2+3+4+5+6+7+8+9+10）/10=5.5次，而二分查找法为（4+3+2+4+3+1+4+3+2+3）/10=2.9次。在最坏的情况下，顺序查找的次数为10，而二分查找的次数为4。
二分查找法的应用极其广泛，并且它的思想易于理解。第一个二分查找算法早在1946年就出现了，但是第一个完全正确的二分查找算法直到1962年才出现。
在B+树索引中，B+树索引只能找到某条记录所在的页，需再根据二分查找法来进一步找到记录所在页的具体位置。
9.2.2 二叉查找树和平衡二叉树
在介绍B+树前，先要了解一下二叉查找树。B+树是通过二叉查找树，再由平衡二叉树、B树演化而来。相信在任何一本有关数据结构的书中都可以找到二叉查找树的章节，二叉查找树是一种经典的数据结构。图9-5显示了一棵二叉查找树。
图9-5中的数字代表每个节点的键值。在二叉查找树中，左子树的键值总是小于根的键值，右子树的键值总是大于根的键值，因此可以通过中序遍历得到键值的排序输出。对图9-5进行中序遍历后输出：2、3、5、6、7、8。
对图9-5的这棵二叉树进行查找，如查找键值为5的记录，先找到根，其键值是6，6大于5，因此查找6的左子树，找到3；而5大于3，再找右子树……一共找了3次。如果按2、3、5、6、7、8的顺序来找同样需要3次。用同样的方法再查找键值为8的这条记录，这次用了3次查找，而顺序查找时需要6次。如果计算平均查找次数可得：顺序查找的平均查找次数为（1+2+3+4+5+6）/6=3.3次，二叉查找树的平均查找次数为（3+3+3+2+2+1）/6=2.3次。二叉查找树比顺序查找的平均效率要高。
二叉查找树可以任意构造，同样是2、3、5、6、7、8这五个数字，也可以按照图9-6的方式建立二叉查找树。
图9-6的平均查找次数为（1+2+3+4+5+5）/6=3.16次，和顺序查找差不多。显然这棵二叉查找树的效率就差很多。因此若想最大性能地构造一个二叉查找树，需要这棵二叉查找树是平衡的，因此引入了新的定义——平衡二叉树，又称为AVL树。
平衡二叉树的定义如下：首先符合二叉查找树的定义，其次必须满足任何节点的两棵子树的高度最大差为1。显然，图9-6不满足平衡二叉树的定义，而图9-5是一棵平衡二叉树。平衡二叉树在查找方面的性能是比较高的，但不是最高的，只是接近最高性能。要达到最好的性能需要建立一棵最优二叉树，但是最优二叉树的建立和维护需要大量的操作，因此一般只需建立一棵平衡二叉树即可。
平衡二叉树的查询速度的确很快，但是维护一棵平衡二叉树的代价非常大，通常需要1次或多次左旋或右旋来得到经过插入或更新操作后二叉树的平衡性。对于图9-5所示的平衡树，当我们需要插入一个新的键值为9的节点时，需要做如图9-7所示的变动。
这里通过一次左旋操作就将插入后的树重新变为平衡二叉树。但是有的情况可能需要进行多次的旋转操作，如图9-8所示。
图9-7和图9-8演示了向一棵平衡二叉树插入一个新的节点后，平衡二叉树需要做的旋转操作。除了插入操作，还有更新和删除操作，不过进行这些操作后在恢复二叉树的平衡性上没有本质的区别，它们都是通过左旋或者右旋来完成。因此对一棵平衡树的维护是有一定开销的，不过平衡二叉树多用于内存结构对象中，因此维护的开销相对较小。
9.3 B+树
B+树和二叉树、平衡二叉树都是经典的数据结构。B+树由B树和索引顺序访问方法（ISAM，是不是很熟悉？对，这也是MyISAM引擎最初参考的数据结构）演化而来，但是在实现过程中几乎没有使用B树的情况了。
相信在任何一本数据结构书中都能找到B+树的定义，其定义十分复杂，这里列出B+树的定义只会让读者感到更加困惑。因此这里只精简地给出B+树的介绍：B+树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树，在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶子节点，各叶子节点通过指针进行链接。先来看一个B+树，如图9-9所示，其高度为2，每页可存放4条记录，扇出（fan out）为5：
从图9-9可以看出，所有记录都在叶子节点上，并且是顺序存放的，如果我们从最左边的叶子节点开始顺序遍历，可以得到所有键值的顺序排序：5、10、15、20、25、30、50、55、60、65、75、80、85、90。
9.3.1 B+树的插入操作
B+树的插入要求必须保证插入后叶子节点中的记录依然顺序排列，同时需要考虑插入到B+树的3种情况，每种情况都可能导致不同的插入算法，如表9-1所示。
通过实例来分析B+树的插入。对于图9-9中的这棵B+树，我们插入28这个键值，发现当前Leaf Page和Index Page都没有满，直接插入就可以了，如图9-10所示。
不会急于进行拆分页的操作，而是将记录移到所在页的兄弟节点上。通常先判断左兄弟是否被用来做旋转操作，因此对于图9-10的情况，在插入键值70时，B+树并不会急于拆分叶子节点，而是去做旋转操作，如图9-13所示。
图 9-13 B+树的旋转操作
从图9-13可以看到，采用旋转操作使B+树减少了一次页的拆分操作，这时B+树的高度依然还是2。
9.3.2 B+树的删除操作
B+树使用填充因子（fill factor）来控制树的删除变化，填充因子可设的最小值是50%。B+树的删除操作同样必须保证删除后叶子节点中的记录依然按序排列。同插入一样，B+树的删除操作同样需要考虑以下3种情况。与插入不同的是，删除根据填充因子的变化来衡量。
接着删除键值为25的记录，这也符合表9-2讨论的第一种情况，但是该值还是Index Page中的值，因此在删除Leaf Page中的25后，还应将25的右兄弟节点28更新到Page Index中，最后可得图9-15。
9.4 B+树索引
前面讨论的都是B+树的数据结构及其一般操作，B+树索引的本质就是B+树在数据库中的实现，而B+树索引在数据库中的一个特点就是高扇出性。例如在InnoDB存储引擎中，每个页的大小为16KB。
因此在数据库中，B+树的高度一般都在2～4层，这意味着查找某一键值最多只需要2到4次IO操作，这还不错。因为现在一般的磁盘每秒至少可以做100次IO操作，2～4次的IO操作意味着查询时间只需0.02～0.04秒。
在MySQL数据库中，索引是在存储引擎层实现的，这意味着每个引擎的B+树索引的实现方式可能是不同的，取决于存储引擎实现的本身。
B+树索引可以分为聚集索引与辅助索引（非聚集索引），但是这两者本身都与之前讨论的B+树的数据结构一样，区别仅在于所存放数据的内容。
9.4.1 InnoDB B+树索引
InnoDB存储引擎是索引组织表（Index Organized Table, IOT），也就是说数据文件本身就是按照B+树方式存放数据的。其中，B+树的键值为主键，若在建立时没有显式地指定主键，则InnoDB存储引擎会自动创建一个6字节的列作为主键。因此在InnoDB存储引擎中，可以将B+树索引分为聚集索引（clustered index）和辅助索引（secondary index）。无论是何种索引，每个页的大小都为16KB，且不能更改。
聚集索引是根据主键创建的一棵B+树，聚集索引的叶子节点存放了表中的所有记录。辅助索引是根据索引键创建的一棵B+树，与聚集索引不同的是，其叶子节点仅存放索引键值，以及该索引键值指向的主键。也就是说，如果通过辅助索引来查找数据，那么当找到辅助索引的叶子节点后，很有可能还需要根据主键值查找聚集索引来得到数据，这种查找方式又被称为书签查找（bookmark lookup）。因为辅助索引不包含行记录的所有数据，这就意味着每页可以存放更多的键值，因此其高度一般都要小于聚集索引。
注意 若辅助索引是一个包含主键的联合索引，那么并不需要一个额外的列来存放主键值。辅助索引会选择通过联合索引中的主键进行查找。
图9-17显示了在InnoDB存储引擎中聚集索引和辅助索引的关系。
接着来看一张表，这里以人为方式使其每个页只能存放两个行记录，例如：
可见辅助索引idx_c是一棵高度为1的B+树，叶子节点存放了所有的索引键值及其对应的主键（-1，1），（-2，2），（-3，3），（-4，4）。由于c列是有符号的整型，因此在数据库内部用0x7FFFFFFF来表示-1。聚集索引是一棵高度为2的B+树，叶子节点存放了所有的记录（1，repeate（'a'，7000），-1）、（2，repeat（'a'，7000），-2）、（3，repeat（'a'，7000），-3）、（4，repeat（'a'，7000），-4）。
注意 《MySQL技术内幕：InnoDB存储引擎》一书中对InnoDB存储引擎的B+树索引有更为详细和深入的分析，强烈建议高级DBA和开发人员阅读此书，这对更好地理解InnoDB存储引擎的实现有着极大的帮助。
9.4.2 MyISAM B+树索引
此处介绍略，因感觉弊端太大，一般不会用MyIAM引擎。
9.5 Cardinality
9.5.1 什么是Cardinality
并不是所有在查询条件中出现的列都需要添加索引。对于什么时候添加B+树索引，一般的经验是，在访问表中很少一部分行时使用B+树索引才有意义。对于性别字段、地区字段、类型字段，它们可取值的范围很小，称为低选择性，例如：
按性别进行查询时，可取值的范围一般只有“M”和“F”，因此上述SQL语句得到的结果可能是该表50%的数据（我们假设男女比例1：1），这时添加B+树索引是完全没有必要的。相反，如果某个字段的取值范围很广，几乎没有重复，即是高选择性的，那么此时使用B+树索引是最适合的。例如姓名字段，基本上在每一个应用中都不允许出现重名。
怎样查看索引是否是高选择性的呢？可以通过SHOW INDEX语句中的Cardinality列来观察。Cardinality值非常关键，表示索引中唯一只记录数量的预估值。这里需要注意的是，Cardinality是一个预估值，而不是一个准确值，用户也不可能得到一个准确的值。在实际应用中，Cardinality/n_rows_in_table应尽可能接近1，
如果非常小，那么需要考虑是否还要建这个索引。因此在访问高选择性属性的字段，并从表中取出很少一部分数据时，对这个字段添加B+树索引是非常有必要的，例如：
SELECT*FROM member WHERE usernick='David'
表member大约有500万行数据，usernick字段上有一个唯一的索引。这时如果查找用户名为David的用户时，得到执行计划如下：
9.5.2 InnoDB存储引擎怎样统计Cardinality
上一小节介绍了Cardinality的重要性，并且告诉读者Cardinality表示索引的选择性。建立的索引是高选择性的这对数据库来说才是有意义的，但是数据库是怎样来统计Cardinality信息的呢？因为MySQL数据库中有各种不同的存储引擎，而每种存储引擎对B+树索引的实现又各不相同，所以对Cardinality的统计放在存储引擎中。
需要考虑到的是，在生产环境中，索引的更新操作可能非常频繁。如果在每次索引发生更新操作时就对其进行Cardinality的统计，那么将会给数据库带来很大的负担。另外需要考虑的是，如果一张表的数据量非常大，比如一张表有50GB的数据，那么统计一次Cardinality信息所需要的时间可能非常长。这在生产环境的应用中也是不能接受的。因此，数据库对于Cardinality的统计都是通过采样（sample）的方法来完成的。
在InnoDB存储引擎中，Cardinality统计信息的更新发生在两个操作中：INSERT和UPDATE。根据前面的叙述，不可能在每次发生INSERT和UPDATE时都去更新Cardinality的信息，这会增加数据库系统的负荷，同时对大表进行统计时，时间上也不允许。因此InnoDB存储引擎对于更新Cardinality信息的策略为：
表中1/16的数据已发生变化。
stat_modified_counter＞2 000 000 000。
第一种策略为自上次统计Cardinality信息后，表中1/16的数据已经发生变化。这时需要更新Cardinality信息。第二种策略考虑的是，如果对表中某一行数据频繁地进行更新操作，这时表中的数据实际并没有增加，发生变化的还是这一行数据，那么第一种更新策略就无法适用，故在InnoDB存储引擎内部有一个计数器stat_modified_counter，用来表示发生变化的次数，当计数器的值大于2 000 000 000时，同样需要更新Cardinality信息。
接着考虑InnoDB存储引擎内部是怎样进行Cardinality信息的统计和更新操作的呢？同样是通过采样的方法。InnoDB存储引擎只对8个叶节点进行采样。采样的过程为：
取得B+树索引中叶节点的数量，即为A。
随机取B+树索引中的8个叶节点。统计每个页不同记录的个数，即为P1，P2，……，P8。
根据采样信息给出Cardinality的预估值：Cardinality=（P1+P2+……+P8）*A/8。
通过上述的说明可以发现，在InnoDB存储引擎中，Cardinality的值是通过对8个叶节点预估而得到的，不是一个精确的值。再者，每次对于Cardinality值的统计都是通过随机读取8个叶子节点得到的，这又暗示了另一个Cardinality的现象，即每次得到的Cardinality值可能是不同的。例如：
上述这句SQL语句会触发MySQL数据库对于Cardinality值的统计，第一次运行得到的结果如图9-20所示。
在上述测试过程中，并没有INSERT、UPDATE这类操作来改变表OrderDetails中的内容，但是当第二次运行SHOW INDEX FROM语句时，Cardinality的值还是发生了如图9-21所示的变化。
可以看到，在第二次运行SHOW INDEX FROM语句时，虽然表OrderDetails本身并没有发生任何的变化，但是表OrderDetails中索引的Cardinality值都发生了变化。由于Cardinality是对随机的8个叶子节点进行分析，因此即使表没有发生变化，用户观察到的索引Cardinality值还是会发生变化的，这本身并不是InnoDB存储引擎的Bug，只是随机采用数据导致的结果。
当然，可能会有用户每次观察到的索引Cardinality值都是一样的情况，那是因为表足够小，表的叶子节点小于或等于8个。这时即使随机采样，也总是会采取到这些页，因此每次得到的Cardinality值都相同。
9.6 B+树索引的使用
9.6.1 不同应用中B+树索引的使用
在了解了B+树索引的本质和实现后，下一个问题需要考虑怎样正确地使用B+树索引?这不是一个简单的问题。笔者所总结的可能并不适用于所有的应用场，这里只是概括出一个大概的方向，在实际的生产环境中，每个DBA和开发人员还要根据具体应用来使用索引，观察索引使用的情况，判断是否需要添加索引。“Think Different”，不要盲从任何人给你的经验意见。
根据第1章的介绍，我们知道数据库中存在两种类型的应用：OLTP和OLAP应用。在OLTP应用中，查询操作只从数据库中取得一小部分数据，一般都在10条记录以下，甚至大多数情况只获取1条记录，如根据主键值来取得用户信息、根据订单号取得订单的详细信息，这都是典型OLTP应用的查询语句。在这种情况下，建立B+树索引后，对该索引的使用应该只是通过该索引取得表中小部分的数据。这时建立B+树索引才是有意义的，否则即使建立了，优化器也可能选择不使用索引。
对于OLAP应用，情况可能稍显复杂一些。不过概括来说，在OLAP应用中都需要访问表中大量的数据，并根据这些数据来产生查询的结果，而这些查询多是面向分析的查询，目的是为决策者提供支持。比如这个月每个用户的消费情况、销售额同比或环比增长的情况。因此在OLAP中添加索引依据的是宏观的信息，而不是微观信息，这是因为最终要得到的结果是提供给决策者的。例如不需要在OLAP中对姓名字段进行索引，因为很少会对单个用户进行查询。但是对于OLAP中的复杂查询，需要涉及多张表之间的联接操作，这时索引的添加是有意义的。如果联接操作使用Hash Join，那么索引可能又变得不是非常重要了，所以DBA或开发人员要认真并仔细地研究自己的应用。不过在OLAP应用中，通常会需要对时间字段进行索引，这是因为大多数统计需要根据时间维度来进行判断。
9.6.2 联合索引
联合索引是指对表上的多个列进行索引。前面讨论的情况都是只对表中的一个列进行索引。联合索引的创建方法与单个索引创建的方法一样，不同之处仅在于有多个索引列。下面的语句创建了一张t表，其中索引idx_a_b是联合索引，联合的列为（a, b）。
何时需要使用联合索引呢？在讨论这个之前，先来看一下联合索引内部的结果。从本质上来说，联合索引还是一棵B+树，不同的是联合索引的键值数量不是1，而是大于等于2。我们来讨论由两个整型列组成的联合索引，假定两个键值的名称分别为a、b，如图9-22所示。
没有什么不同，键值都是排序的，通过叶子节点可以逻辑上顺序地读出所有数据，这里是：（1，1），（1，2），（2，1），（2，4），（3，1），（3，2）。数据按（a, b）的顺序进行了存放。
因此，对于查询SELECT*FROM TABLE WHERE a=xxx and b=xxx，显然是可以使用（a, b）这个联合索引的。对于单个的a列查询SELECT*FROM TABLE WHERE a=xxx也可以使用这个（a, b）索引。但是对于b列的查询SELECT*FROM TABLE WHERE b=xxx，不可以使用这棵B+树索引。可以看到叶子节点上的b值为1、2、1、4、1、2，显然不是顺序的，因此对于b列的查询不能使用（a, b）的索引。
联合索引的另一个好处是可以对第二个键值进行排序。例如，在很多情况下我们都需要查询某个用户的购物情况，并按照时间排序，取出最近三次的购买记录，这时使用联合索引可以减少一次排序操作，因为索引本身在叶子节点已经排序了。来看一个例子，先根据如下语句来创建测试表buy_log。
userid索引和（userid, buy_date）联合索引。优化器最终的选择是userid，因为该叶子节点包含单个键值，所以一个页能存放的记录应该更多。
接着假定要取出userid为1的最近3次的购买记录，其SQL语句如下，执行计划如图9-24所示。
在Extra列可以看到Using filesort，即需要额外的一次排序才能完成查询。而这次需要排序的显然是buy_date，因为索引userid中的buy-date是未排序的。
9.6.3 覆盖索引
InnoDB存储引擎支持覆盖索引（covering index），或称索引覆盖（index coverage），即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。使用覆盖索引的好处是辅助索引不包含整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少大量的IO操作。
注意：覆盖索引技术最早在InnoDB Plugin中完成并实现。这意味着对于InnoDB版本小于1.0的，或者MySQL数据库版本为5.0或以下的，InnoDB存储引擎不支持覆盖索引特性。
对于InnoDB存储引擎的辅助索引而言，由于其中包含了主键信息，因此其叶子节点存放的数据为（primary key1，primary key2，……，key1，key2，……）。下面语句都可以仅使用一次辅助联合索引来完成查询。
覆盖索引的另一个好处是对于某些统计问题，辅助索引小于聚集索引，可以减少IO操作。还是通过上一小节创建的表buy_log进行说明，如果要进行如下的查询：
这时InnoDB存储引擎并不会选择通过查询聚集索引来进行统计，因为该表上还有辅助索引，同样的理由，因为辅助索引小于聚集索引，可以减少IO操作，故优化器的选择如图9-26所示。
通过图9-26可以看到，possible_keys列为NULL，但是实际执行时优化器却选择了userid索引，而Extra列的Using index就是代表了优化器进行了覆盖索引操作。
从图9-27可以发现，possible_keys列依然为NULL，但是key列为userid_2，即表示（userid, buy_date）的联合索引。从Extra列同样可以发现Using index提示，表示为覆盖索引。
9.6.4 优化器选择不使用索引的情况
在某些情况下，当执行EXPLAIN时，会发现优化器并没有选择索引去查找数据，而是通过扫描聚集索引，也就是直接进行全表的扫描来得到数据。这种情况多发生于范围查找、JOIN操作等，例如：
可以看到表orderdetails有（OrderID, ProductID）的联合主键，此外还有对列OrderID的单个索引。这句SQL显然是可以通过OrderID来查找数据的。然而通过EXPLAIN命令，会发现优化器并没有按照OrderID上的索引来查找数据，如图9-29所示。
在possible_keys列可以看到查询可以使用PRIMARY、OrderID、OrdersOrder_Details三个索引，但是在最后的索引中，优化器选择了PRIMARY聚集索引，而非OrderID辅助索引。
这是为什么呢？原因在于我们要选取的数据是整行信息，而OrderID索引不能覆盖到我们要查询的信息，因此在对OrderID索引进行查询到指定数据的操作后，还需要进行一次书签访问来查找整行数据的信息。虽然在OrderID的索引中数据是顺序存放的，但是再一次的书签查找数据是无序的，因此变为了磁盘上的离散读取操作。如果要求访问的数据量很小，那么优化器还是会选择辅助索引，但是当访问的数据占整个表中数据的很大一部分时（一般是20%左右），优化器会选择通过聚集索引来查找数据。在9.1节中已经提到顺序读取要远远快于离散读取。图9-30演示的是用sysbench测试的顺序读取和随机读取的速度对比，同时对比了RAID开启Write Back和Write Through的性能差异。测试的磁盘是由4块15 000转的硬盘组成的RAID10。测试文件大小为2GB，页大小64KB。
从图9-30可以发现，不管是否开启RAID卡的Write Back功能，磁盘的随机读取性能都远远小于顺序读取的性能。通过图9-30的比较也大致可以知道Write Back相对于Write Through的性能提升。
因此对于不能进行索引覆盖的情况，优化器选择辅助索引的情况是，通过辅助索引查找的数据是少量的，这是由当前传统机械硬盘的特性所决定，即利用顺序读取来替换随机读取的查找。若用户使用的磁盘是固态硬盘，随机读取操作非常快，同时有足够的自信来确认使用辅助索引可以带来更好的性能，那么可以使用关键字FORCE INDEX来强制使用某个索引，例如：
9.6.5 INDEX HINT
MySQL数据库支持INDEX HINT（索引提示），显式地告诉优化器使用哪个索引。以下两种情况可能需要用到INDEX HINT。
MySQL数据库的优化器错误地选择了某个索引，导致SQL语句运行得很慢。这种情况非常少见。优化器在绝大部分情况下工作都非常有效和正确。这时有经验的DBA或开发人员可以强制优化器使用某个索引，以达到提高SQL运行速度的目的。
某SQL语句可以选择的索引非常多，这时优化器选择执行计划时间的开销可能会大于SQL语句本身。例如，优化器分析Range查询本身就是比较耗时的操作，这时DBA或开发人员分析最优的索引选择，通过INDEX HINT来强制使优化器不进行各个执行路径的成本分析，直接执行选择指定的索引来完成查询。
在MySQL数据库中INDEX HINT的语法如下：
9.7 Multi-Range Read
MySQL数据库5.6版本开始支持Multi-Range Read（MRR）优化。MRR优化的目的就是减少磁盘的随机访问，并且将随机访问转化为较为顺序的数据访问，可为IO-bound类型的SQL查询语句带来性能的极大提升。MRR优化适用于range、ref和eq_ref类型的查询。
MRR优化有以下几个好处：
使得数据访问变得较为顺序。在查询辅助索引时，先对得到的查询结果按照主键进行排序，并按照主键排列的顺序进行书签查找。
减少缓冲池中页被替换的次数。
批量处理对键值的查询操作。
对于InnoDB和MyISAM存储引擎的范围查询和联接查询，MRR的工作方式如下：将查询得到的辅助索引键值存放于一个缓存中，这时缓存中的数据是根据辅助索引键值排序的。
将缓存中的键值根据RowID进行排序。
根据RowID的排序顺序来访问实际的数据文件。
此外，若InnoDB存储引擎或MyISAM存储引擎的缓冲池不是足够大，即不能存放下一张表中的所有数据，此时频繁的离散读取操作还会导致将缓存中的页替换出缓冲池，然后又不断地读入缓冲池。若按照主键顺序进行访问，则可以将重复行为的次数降为最低。例如下面的SQL语句：
salary上有一个辅助索引idx_s，因此除了通过辅助索引查找键值外，还需要通过书签查找来进行对整行数据的查询。当不启用MRR特性，看到的执行计划如图9-35所示。
从图9-37中可以看出表salaries上有对salary的索引idx_s。在执行上述SQL语句时，因为启用了MRR优化，所以会对查询条件进行拆分，在Extra列中可以看到Using MRR选项。是否启用MRR优化可以通过参数optimizer_switch中的标记（flag）来控制。当启用mrr为on时，表示启用MRR优化。mrr_cost_based标记表示是否通过cost based的方式来选择是否启用mrr。若将mrr设为on, mrr_cost_based设为off，则总是启用MRR优化。下面的语句可以将MRR优化总是设为开启状态。
9.8 Index Condition Pushdown
和MRR一样，Index Condition Pushdown（ICP）同样是MySQL 5.6开始支持的一种根据索引进行查询的优化方式。之前的MySQL版本不支持ICP，当进行索引查询时，首先根据索引来查找记录，然后再根据WHERE条件来过滤记录。在支持ICP后，MySQL数据库会在取出索引的同时，判断是否可以进行WHERE条件的过滤，即将WHERE的部分过滤操作放在了存储引擎层。在某些查询中，ICP会大大减少上层SQL层对于记录的索取（fetch），从而提高数据库的整体性能。
ICP优化支持range、ref、eq_ref和ref_or_null类型的查询，当前支持MyISAM和InnoDB存储引擎。当优化器选择ICP优化时，可在执行计划的Extra列看到Using index condition提示。
注意 NDB Cluster存储引擎支持Engine Condition Pushdown优化。不仅支持索引的Condition Pushdown，也可以支持非索引的Condition Pushdown，不过这是由其引擎本身的特性所决定的。MySQL 5.1版本NDB Cluster存储引擎就开始支持Engine Condition Pushdown优化。
假设某张表中有联合索引（zip_code, last_name, firset_name），并且查询语句如下：
对于上述语句，MySQL数据库可以通过索引来定位zipcode等于95 054的记录，但是索引对WHERE条件的lastname LIKE'%etrunia%'AND address LIKE'%Main Street%'没有任何的帮助。若不支持ICP优化，则数据库需要先通过索引取出所有zipcode等于95 054的记录，然后再过滤WHERE之后的两个条件。
若支持ICP优化，则在取出索引时，就会进行WHERE条件的过滤，然后再去获取记录，这将极大提高查询的效率。当然，WHERE可以过滤的条件是该索引可以覆盖到的范围。再来看上一节中的SQL语句：
若不启用MRR优化，则其执行计划如图9-38所示。
总结：总体来说，5.5可以升级到5.6玩下MRR优化了！sql语句逇执行时间提高百分之400，尼玛什么概念~。
MRR 仅仅针对 二级索引 的范围扫描 和 使用二级索引进行 join 的情况。
MRR 的优势是将多个随机IO转换成较少数量的顺序IO。所以对于 SSD 来说价值还是有的，但是相比机械磁盘来说意义小一些。
9.9 T树索引
9.9.1 T树概述
对于MySQL数据库的NDB Cluster内存存储引擎，在使用它时可将其视为内存数据库（从MySQL 5.1开始NDB Cluster引擎可以将非索引数据存放在磁盘上，这种情况又可以视为混合存储引擎）。在内存数据库中，一般使用T树（T-Tree）作为其索引的数据结构。T树是由平衡二叉树和B树发展而来。NDB Cluster存储引擎中的Order Index，也就是普通索引，使用的就是T树结构。T树的好处是节点不存放数据，只存放指针，这样能减少对内存的使用，这对内存数据库来说显得尤为重要。同时T树也是一棵平衡二叉树，以此保证查找的性能。T树中的T指的是T树中节点的形状。图9-39显示了T树节点（T-tree node）。
T树节点由3个指针、一个有序数组（array），以及控制信息组成。3个指针分别为指向父节点和左右子树的指针。有序数组保存的是数据指针，而非实际的数据。数组中的第一个数据称为最小元素（minimum element），最后一个数据称为最大元素（maximum element）。控制信息中存放了关于该T树节点的一些额外信息。T树的结构如图9-40所示。
在T树中，含有左右子树的节点称为内部节点（internal node），没有子树的节点称为叶节点（leaf node），仅有一个子树的节点称为半叶节点（half-leaf node）。对于每个内部节点，存在一个相对应的叶节点或半叶节点存放内部节点的最小值，该值称为最大下界（greatest lower bound）。同时也存在相对应的叶节点或半叶节点用于存放内部节点的最大值，该值称为最小上界（least upper bound），如图9-41所示。如果一个值x在T树的节点N上，那么称x在N的边界内，N为x的边界页。通过上述的内容，可以看出T树的节点借鉴了B树和平衡二叉树的思想。
9.9.2 T树的查找、插入和删除操作
T树的查找和二叉查找树类似，其查找算法为：
从根节点（root）开始查找，比较节点中最大值和最小值。如果查找的值在边界内，则用二叉法查找T树中的数组。
若查找的值比根节点的最小值小，则递归查找左子树。
若查找的值比根节点的最大值大，则递归查找右子树。
若不存在该值，返回为NULL。
T树的插入操作：先通过查找来定位边界页，新插入的值被插入边界页后需要对T树进行检查，看其是否平衡。如果不平衡，则需要通过旋转来保证T树的平衡。由于T树的节点可以存放多个值，因此其旋转的次数，较之平衡二叉树又减少了很多。
T树的插入算法为：
查找边界页。
如果查到边界页，则判断是否有空间插入新的值。如果有，则直接插入，插入操作完成。如果没有空间，则删除该节点的最小值，插入新值。接着查询原插入值最大下界所在的节点，将删除的值插入该节点，并成为新的最大下界值。
如果没有查到边界页，那么在最后查询的节点中尝试插入记录。若该节点有空间可以插入，则直接插入，并且该记录成为该节点的最小或最大记录值。若没有空间插入，则分配一个叶节点进行插入。
如果分配了一个叶节点，则需要检查T树是否平衡。如果不平衡，即子树高度的差值大于1，则需要进行与平衡二叉树同样的旋转操作，以保证T树重新回到平衡状态。当T树恢复到平衡状态，此次操作完成。
T树的删除操作同插入操作类似，首先需要找到边界页，然后完成删除操作，最后判断是否需要旋转来完成平衡操作。其具体步骤如下：
查找删除记录所在的边界页。如果查找失败，则报告错误并停止操作。
如果删除不会引起下溢出（underflow）问题，即删除该记录后，节点中的记录数大于所要求该节点的最小记录数，那么直接删除记录。否则，如果节点是内部节点，那么删除该记录，同时将该节点的最大下界值放回该内部节点中。如果节点是叶节点或半叶节点，则直接删除记录（叶节点允许下溢出，半叶节点还需进行下一步操作）。
如果是半叶节点，则观察半叶节点是否可以和叶节点进行合并（merge）。如果可以，则强制将两个节点合并为一个节点，并删除半叶节点。
观察删除后的节点是否是空节点，若是则删除该节点。
观察T树是否平衡，若不平衡则通过旋转操作使T树重新回到平衡状态。
9.9.3 T树的旋转
T树的旋转操作和平衡二叉树十分相似。当插入或进行触发叶的添加或删除操作时，需要重新检查树是否平衡，需要判断是否通过旋转操作来使T树重新变为平衡。检查的路径为插入的节点到根节点所有的路径，观察左右子树的高度差值是否大于1。若是，则需要执行旋转操作。对于插入操作，只需要进行一次旋转操作；对于删除操作，可能需要多次的旋转操作。图9-42显示了插入操作所触发的LL旋转和较为复杂的LR旋转操作。和平衡二叉树一样，共有四种类型的旋转，分为LL、LR、RR、RL。其中RR、RL和LL、LR是对称的，这里不进行讨论。删除操作与插入操作一样，但是，删除操作使子树的高度变矮，而不是像插入操作一样使子树变高。
T树存在一种特殊的旋转，这是平衡二叉树所不存在的一种平衡操作。当LR或RL旋转操作完成后，如果节点C是叶节点，并且A、B节点都是半叶节点，那么通常的旋转平衡操作会将C节点变成一个内部节点，如图9-43所示。
因为数据的插入总是在内部节点的最大和最小边界范围中，所以当节点C只包含一个数据时，任何数据都不会插入C节点，除非C节点通过旋转再次变为叶节点或半叶节点。这种情况会极大浪费存储空间，尤其对内存存储引擎来说。因此，在T树中有一种特殊的旋转操作，它会将节点B中的数据移动到节点C中，节点C变成满的内部节点，这个操作如图9-44所示
9.10 哈希索引
当前MySQL数据库中，Memory存储引擎支持哈希索引。InnoDB存储引擎支持自适应哈希索引，用户仅能开启该特性，不能对其进行人工干预。散列算法是一种常见算法，时间复杂度为O（1），并且不只存在于索引中，每个数据库应用中都存在该数据库结构。设想这样一个问题，当前服务器的内存为128GB，用户怎样从内存中得到某一个被缓存的页呢？内存中的查询速度很快，但是也不可能每次遍历所有内存进行查找。这时对于字典操作只需O（1）复杂度的散列算法，就能有很好的用武之处。
9.10.1 散列表
散列表（hash table）由直接寻址表改进而来。先来看直接寻址表。当关键字的全域U比较小时，直接寻址是一种简单而有效的技术。假设某应用要用到一个动态集合，其中每个元素都有一个取自全域U={0，1，……，m-1}[注释]的关键字，同时假设没有两个元素具有相同的关键字。
用一个数组（即直接寻址表）T[0..m-1]表示动态集合，其中每个位置（称槽或桶）对应全域U中的一个关键字。如图9-45所示，槽K指向集合中一个关键字为K的元素。如果该集合中没有关键字为K的元素，则T[K]=NULL。
直接寻址技术存在一个很明显的问题，如果全域U很大，在一台典型计算机的可用内存容量限制下，要存储大小为U的一张表T有点不实际，甚至是不可能的。如果实际要存储的关键字集合K相对于U来说可能很小，那么分配给T的大部分空间都要浪费掉。
因此，散列表的数据结构出现了。在散列方式下，该元素处于h（K）中，即利用散列函数h，根据关键字K计算出槽的位置。函数h将关键字全域U映射到散列表T[0..m-1]的槽位上，如图9-46所示。
散列表很好地解决了直接寻址遇到的问题，但是这样做有一个小问题，如图9-46所示，两个关键字可能映射到同一个槽上。一般将这种情况称为发生了碰撞（collision）。数据库中一般采用最简单的碰撞解决技术，即链接法（chaining）。
在链接法中，把散列到同一槽中的所有元素都放在一个链表中，如图9-47所示。每个槽中有一个指针，它指向由所有散列元素构成的链表的头，如果不存在这样的元素，则为NULL。
最后要考虑的是散列函数。散列函数h必须可以很好地进行散列。最好的情况是能避免碰撞的发生，即使不能避免，也应该使碰撞在最小程度下产生。一般都将关键字转换成自然数，然后通过除法散列、乘法散列或全域散列来实现。数据库中一般采用除法散列的方法。
[1]此处的m不是一个很大的数。
9.10.2 InnoDB存储引擎中的散列算法
InnoDB存储引擎使用散列算法来对字典进行查找，其冲突机制采用链表方式，散列函数采用除法散列方式。对于缓冲池页的散列表来说，缓冲池中的Page页都有一个chain指针，它指向相同散列函数值的页。而对于除法散列，m的取值为略大于2倍的缓冲池页数量的质数。例如，当前参数innodb_buffer_pool_size的大小为10MB，则共有640个16KB的页，对于缓冲池页内存的散列表来说，需要分配640*2=1280个槽，而1280不是质数，因此需要取比1280略大的一个质数，应该是1399，这样在启动时会分配1399个槽的散列表，用来散列查询所在缓冲池中的页。
那么InnoDB存储引擎对于页是怎么进行查找的呢？上面只是给出了一般的算法，怎么将要查找的页转换成自然数呢？其实也很简单，InnoDB存储引擎的表空间都有一个space号，我们要查找的应该是某个表空间的某个连续16KB的页，即偏移量offset。InnoDB存储引擎将space左移20位，然后加上这个space和offset，即关键字K=space＜＜20+space+offset，然后通过除法散列到各个槽中去。
9.10.3 自适应哈希索引
自适应哈希索引采用之前讨论的散列表的方式实现。不同的是，自适应哈希索引仅是数据库自身创建并使用的，DBA本身并不能对其进行干预。自适应哈希索引经散列函数映射到一个散列表中，因此对于字典类型的查找非常快速，例如SELECT*FROM TABLE WHERE index_col='xxx'，但是对于范围查找就无能为力了。通过命令SHOW ENGINE INNODB STATUS可以看到当前自适应哈希索引的使用状况，例如：
现在可以看到自适应哈希索引的使用信息，包括自适应哈希索引的大小、使用情况、每秒使用自适应哈希索引搜索的情况。需要注意的是，哈希索引只能用来搜索等值的查询，例如select*from table where index_col='xxx'，而对于其他查找类型，比如范围查找，是不能使用哈希索引的，因此，这里出现了non-hash searches/s的情况。由hash searches：non-hash searches可以大概了解使用哈希索引后的效率。
由于自适应哈希索引是由InnoDB存储引擎自己控制的，所以这些信息只供我们参考。不过可以通过参数innodb_adaptive_hash_index来禁用或启动此特性，默认为开启。
9.11 小结
本章更倾向于从内部的实现来分析索引，较之前的章节在风格上有很大的不同。这样处理是为了使读者更好地理解数据库中索引的实现，特别是B+树索引。通过这种方式，用户才能进行高质量的SQL编程，写出高质量的应用程序。
参考：Mysql技术内幕SQL编程
MySQL索引使用方法和性能优化：http://feiyan.info/16.html
MySQL索引原理及慢查询优化：http://tech.meituan.com/mysql-index.html
微信扫一扫，打赏作者吧～
