索引及其背后的数据结构支持
索引
索引是存储引擎用于快速找到记录的一种数据结构。索引对于良好的性能非常关键，尤其是当表中的数据量越来越大时。
数据库查询是数据库最主要的功能之一.
如果想要理解MySQL中索引是如何工作的，最简单的方法就是去看看一本书的“目录”部分：如果想在一本书中找到某个索引，一般会先看书的“目录”，找到对应的页码。
B-Tree和B+Tree
目前大部分数据库系统及文件系统都采用B-Tree或者B+Tree作为索引结构。这是有一定原因的。首先介绍其数据结构。
B-Tree
为了描述B-Tree，首先定义一条数据记录为一个二元组[key，data]，key为记录的键值，对应不同的数据记录，key是互不相同的。data为数据记录出key外的数据。那么B-Tree是满足下列条件的数据结构：
d为大于1的一个正整数，称为B-Tree的度。
h为一个正整数，称为B-Tree的高度。
每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d.
每个叶子节点最少包含一个key和两个指针，最多包含2n-1个key和2d个指针，叶节点的指针均为null。
所有叶节点具有相同的深度，等于树高h。
key和指针互相间隔，节点两端是指针。
一个节点中的key从左到右非递减排列[非严格递增]。
所有节点组成树结构。
每个指针要么为null，要么指向另外一个节点。
如果某个指针在节点node最左边且不为null，则其指向节点的所有key小于v（key1），其中v(key1)为node的第一个key的值。(隐隐有点像二叉搜索树，左边比根节点小。右边比根节点大)
如果某个指针在节点node的最右边且不为null，则其指向节点的所有key大于v（keym），其中v(keym)为node的最后一个key的值。
如果某个指针在节点node的左右相邻key分别是keyi和keyi+1且不为null，则其指向节点的所有key小于v(keyi+1)且大于v(keyi)；
图为一个d=2的B-Tree示意图，d为2指的是每个指针有两个数据，20，49是大于15且小于56的。
B+Tree
MySQL普遍使用B+Tree实现其索引结构。与B-Tree相比，B+tree有以下不同点：
- 每个节点的指针上限为2d而不是2d+1
- 内节点不存储data，只存储key；叶子节点不存储指针；
下面是一个简单B+Tree示意：
由于并不是所有节点都具有相同的域，因此B+Tree中叶节点和内节点一般大小不同。这点与B-Tree中不同节点存放的key和指针可能数量不一致，但是每个节点的域和上限是一致的，所以在实现中B-Tree往往对每个节点申请同等大小的空间。
一般来说，B+Tree比B-Tree更适合外存储索引结构，具体原因与外存储器原理及计算机存取原理有关。
带有顺序访问指针的B+Tree
一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。
如图所示，在B+Tree中的每个叶子节点增加一个指向相邻叶子节点的指针，这样就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如图4要查询key从18到49顶点所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提高了区间查询效率。
为什么使用B+Tree
红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构，这是为什么呢？
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储在磁盘上。这样的话，索引查找过程中中就要产生磁盘IO消耗，相对于内存存取，IO存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是查找过程中磁盘IO操作次数。
根据B-Tree的定义，可知检索一次最多需要访问h个节点，数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次IO就可以完全载入了。为了达到这个目的，在实际实现中还需要如下技巧：
- 每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次IO；
- B-Tree中一次索引最多需要h-1次IO，根节点常驻内存，渐进复杂度O(h)=O(logdN).一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小，通常不超3.
综上所述，用B-Tree作为索引结构效率是非常高的。
而红黑树这种结构，h明显要深得多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用数据的局部性，所以红黑树的IO渐进复杂度为O(h),效率明显比B-Tree差很多。
除此之外，B+Tree更适合外存索引，原因和内节点出度d有关。由上面分析可以看到，d越大索引的性能越好，而出度的上限取决于节点内key和data的大小。
由于B+Tree内节点去掉了data域，因此可以拥有更大的出度，拥有更好的性能。
MySQL索引实现
不同存储引起对索引的实现方式是不同的，这里主要介绍MyISAM和InnoDB两个存储引擎的索引实现方式。
MyISAM索引实现
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：
这里假设表一共有三列，假设我们以col1为主键，则图8是一个MyISAM表的主索引示意。可以看出，MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在col2上建立一个辅助索引，则此索引的结构如下图所示：
注意看辅助索引的和主索引的差别，辅助索引叶子节点存放的key是辅助字段的值，而主索引叶子节点存放的key是主键的值。
因此MyISAM中索引检索的算法首先按照B+Tree搜索算法搜索索引，如果指定的key存在，则取出其data域的值，然后以data域的值为地址，读取相应的数据记录。
MyISAM的索引方式也叫做非聚集索引。
InnoDB索引实现
虽然InnoDB也使用B+Tree作为索引结构，但实现方式却与MyISAM截然不同。
第一个重大区别就是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据文件的地址。而在InnoDB中，表数据文件本身就是按B+tree组织的一个索引结构。这颗树的叶节点data域保存了完整的数据记录，这个索引的key是数据表的主键。
图10是InnoDB主索引(同时也是数据文件)的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键。如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。
第二个与MyISAM索引不同的是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。如下图所示：
聚集索引这种实现方式使得按主键搜索十分高效，但是辅助索引搜索需要检索两遍索引：通过辅助索引获得主键，然后用主键到主索引中检索获得记录。
了解不同存储引擎的索引实现对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是一个好主意，因为InnoDB数据本间本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
索引使用策略及优化
MySQL的优化主要分为结构优化和查询优化。本章讨论的高性能索引策略主要属于结构化优化范围。
最长前缀原理与相关优化
高效使用索引的首要条件是知道什么样的查询会使用到索引，这个问题和B+Tree中的“最左前缀原理”有关。主键有三个emp_no, title, from_date.
情况一：全列匹配
很明显，当按照索引中的所有列进行精确匹配（这里精确匹配指“=”或“IN”匹配）时，索引可以被用到。理论上索引对顺序是敏感的，但是由于MySQL的查询优化器会自动调整where子句的条件顺序以使用适合的索引。
情况二：最左前缀匹配
当查询条件精确匹配索引的左边连续一个或几个列时，索引可以被用到，但是只用到一部分，即条件所组成的最左前缀。
情况三：查询条件用到了索引中列的精确匹配，但是中间某个条件未提供。
此时索引使用情况和情况二相同，因为title未提供，所以查询只用到了索引的第一列，而后面的from_date虽然也在索引中，但是由于title不存在而无法和左前缀连接，因此需要对结果进行扫描过滤from_date（这里由于emp_no唯一，所以不存在扫描）。如果想让from_date也使用索引而不是where过滤，可以增加一个辅助索引<emp_no, from_date>，此时上面的查询会使用这个索引。除此之外，还可以使用一种称之为“隔离列”的优化方法，将emp_no与from_date之间的“坑”填上。
“填坑”后性能提升了一点。如果经过emp_no筛选后余下很多数据，则后者性能优势会更加明显。当然，如果title的值很多，用填坑就不合适了，必须建立辅助索引。
情况四：查询条件没有指定索引第一列
由于不是最左前缀，索引这样的查询显然用不到索引。
情况五：匹配某列的前缀字符串
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND title LIKE 'Senior%';
如果通配符%不出现在开头，则可以用到索引，但根据具体情况不同可能只会用其中一个前缀。
情况六：范围查询
范围列可以用到索引（必须是最左前缀），但是范围列后面的列无法用到索引。同时，索引最多用于一个范围列，因此如果查询条件中有两个范围列则无法全用到索引。
情况七：查询条件中含有函数或表达式
很不幸，如果查询条件中含有函数或表达式，则MySQL不会为这列使用索引(虽然某些在数学意义上可以使用)。由于查询条件是一个表达式，MySQL无法为其使用索引。看来MySQL还没有智能到自动优化常量表达式的程度，因此在写查询语句时尽量避免表达式出现在查询中，而是先手工私下代数运算，转换为无表达式的查询语句。
索引选择性与前缀索引
既然索引可以加快查询速率，是不是只要是查询语句就建上索引？答案是否定的，因为索引虽然加快了查询速度，但索引也是有代价的：索引文件本身要消耗存储空间，同时索引会加重插入、删除和修改记录时的负担，另外，MySQL在运行中也要消耗资源维护索引，因此索引并不是越多越好。一般两种情况下不建议建索引：
第一种情况是表记录比较少，例如一两千条甚至只有几百条记录的表，没必要建索引，让查询做全表扫描好了。至于多少条记录才算多，这个人有个人的看法，记录数不超过2000可以考虑不建索引，超过2000条才可以酌情考虑索引。
另一种不建议建索引的情况是索引的选择性较低。所谓索引的选择性是指不重复的索引值与表记录数的比值。显然选择性的取值范围为(0,1],选择性越高的索引价值越大，这是由B+Tree的性质决定。
有一种与索引选择性有关的索引优化策略叫做前缀索引，就是用列的前缀代替整个列作为索引key，当前缀长度合适时，可以做到既使得前缀索引的选择性接近全列索引，同时应为索引key变短而减少了索引文件的大小和维护开销。
前缀索引兼顾索引大小和查询速度，但是其缺点是不能用于ORDER BY和GROUP BY操作，也不能用于Covering index（即当索引本身包含查询所需全部数据时，不再访问数据文件本身）
InnoDB的主键选择与插入优化
在使用InnoDB存储引擎时，如果没有特别的需要，请永远使用一个与业务无关的自增字段作为主键。
上文讨论过InnoDB的索引实现，InnoDB使用聚集索引，数据记录本身被存于主索引的叶子节点上。这就要求同一个叶子节点内（大小为一个内存页或磁盘页）的各条数据记录按主键顺序存放，因此每当有一条新的记录插入时，MySQL会根据其主机那将其插入到适当的节点和位置，如果页面到达装载因子（InnoDB默认为15/16），则开辟一个新的页（节点）。
如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页。
这样就会形成一个紧凑的索引结构，近似顺序填满。由于每次插入时也不需要移动已有数据，因此效率很高，也不会增加很多开销在维护索引上。
如果使用非自增主键（如身份证或学号等）由于每次插入主键的值近似于随机，因此每次新记录都要被插到现有索引页的中间某个位置。
因此MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能被回写到磁盘上而从缓存中清掉，此时又要从磁盘中读回来。这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。
因此，只要可以，请尽量在InnoDB上采用自增字段作为主键。