一、mysql数据结构

Mysql的两种主要的存储引擎都依赖的数据结构为B+tree，一种从B-tree改进而来的树状数据结构
本节将从几个方面来介绍：
1. 介绍B-tree和B+tree；
2. 介绍两种主要的存储引擎如何实现索引；

1.1 介绍B-tree和B+tree

1.1.1 B-tree

B-tree名为多路搜索平衡树，在此先定义一组值[key,data]，key即为键，data即为key键所指向的值。
在大多数的文献与书籍中，对于B-tree的定义有一些差别，本文中参考的是清华大学出版社的《数据结构（C语言版）》（2007年版）。

一棵m阶的 B 树，或为空树，或为满足下列特性的m叉树:

1. 树中每一个结点至多有m棵子树；
2. 若根结点不是叶子结点，则至少有两棵子树；
3. 除根结点之外的所有非终端结点至少有⌈m/2⌉棵子树；
   4.所有的非终端结点中包含下列信息数据(n,A{0} ,K{1},A{1},K{2} ,A{2},...,K{n},A{n})， 其中：K{i}（i=1,...,n）为关键字，且K{i}<K{i+1}（i=1,...,n-1);A{i}（i=0,...,n）为指向子树根结点的指针，且指针A_{i-1}所指子树中所有结点的关键字均小于K{i}（i=1,...,n），A{n} 所指子树中所有结点的关键字均大于K{n} ，n（⌈m/2⌉−1≤n≤m−1）为关键字的个数；
4. 所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。

B-tree示例图：

B-tree

1.1.2 B+tree

B+tree是B-tree的变体，对于阶数为m的树其中改变的地方有：

1. B+tree中每个结点关键字个数范围变为⌈m/2⌉≤n≤m，即结点的最左边不是子树指针而是关键字key；
2. 内节点不存储data，只存储key；叶子节点不存储指针，并且所有的关键字key都会在叶子结点再存储一遍
3. 一般B+tree都带有每个叶子节点的指向相邻叶子节点的顺序指针

在做了以上改变后，B+tree的查找则都必须要查找到叶结点，而B-tree则可能在某个内结点即停止查找；还有B+tree的查找可以有根结点和起始叶结点两个出发点。
B+tree示例图：

B+tree

1.2 两种存储引擎如何实现索引

目前比较主流的存储引擎貌似是MyISAM和InnoDB两种，这里先介绍这两个

1.2.1 MyISAM实现索引

MyISAM是MySQL的默认数据表类型，基于了传统的ISAM类型，ISAM是Indexed Sequential Access Method（有索引的顺序访问方法）的缩写，MyISAM使用B+tree存储引擎结构，叶节点的data域存放的是数据记录的地址。
MyISAM采用的是索引文件和数据文件分离存储，索引文件中存储的是数据文件中相应数据的地址，只对索引采取B+tree数据结构。

`MyISAM`索引原理图

这里使用别人已有的教学例子

设表共有三列，假设我们以Col1为主键，则上图是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如图

辅助索引原理图
这样在利用索引查询时，会按照B+tree的查询算法进行查找，当查找到指定的key时，则会读取到相应叶结点的data域，根据其中的地址信息取出相应的数据。

1.2.2 InnoDB实现索引

InnoDB使用的也是B+tree数据结构存储器引擎，但是和MyISAM差别比较大。
首先InnoDB的数据文件本身就是索引文件。即数据文件就按照B+tree的结构存储，这棵树的key即是InnoDB中的主键，这棵树的叶结点对应的data域存储的是完整的数据记录。

辅助索引原理图
这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键，对比MyISAM，MyISAM则不是非要主键，MyISAM的索引叫做非聚集索引，如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
第二点不同，在InnoDB中的辅助索引和MyISAM中的辅助索引也不一样，InnoDB的辅助索引也采用的B+tree结构存储，但是辅助索引树的叶结点的data域则存储的是相应的主键值，而不是像MyISAM存储地址。
例如用上述图中的第三列做InnoDB的辅助索引，则得下图：
辅助索引原理图
聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。但这样的好处是，如果辅助索引data存放的数据指针，当数据移动或者数据页分裂时，需要更新data域行指针的值，这就增加维护成本。data存在主键的值，就没有这个问题。数据移动和数据页分裂，主键索引会自动更新。data关联主键的值，不需要更新，相当于增加一个间接层。这个间接层对性能的影响也很小，因为通过主键定位记录是非常快的。

由此我们清楚了InnoDB的主键最好使用单调有序的字段，并且不适合太长的字段，因为每个辅助索引都存储主索引字段，太长的主键会造成辅助索引空间太大，一般使用的是自增的整型字段。

二、 索引分类

2.1 B-Tree索引及B+Tree索引

前面已经介绍了InnoDB及MyISAM两种最常用的存储引擎所基于的数据结构---B-Tree和B+Tree，以及是如何存储索引和键值的，基于这两种数据结构的索引就是B-Tree索引及B+Tree索引。
本文的示例数据表People，创建如下表：

建表语句

接着介绍下对于这种索引有效的查询类型。

全值匹配

全值匹配指的是和索引中的所有列进行匹配，以上面的例子即为可查询姓zhang,名san，出生于1960-01-01的人

匹配最左前缀

即只使用索引的第一列，上述例子中即可用索引查询姓zhang的人

匹配列前缀

也可以只匹配某一列的值得开头部分。上述例子中即可用索引查询姓氏中以zh开头的信息。也是只使用了索引的第一列。

匹配范围值

前面提到的索引即可范围查询按字母顺序姓氏在Li和zhang之间的人。同样是只使用了第一列

精确匹配某一列并范围匹配另外一列

上述例子中即可精确匹配所有姓氏为zhang，并且按字母顺序名字在san到si之中的信息。
即第一列surname全匹配，第二列name范围匹配。

只访问索引的查询

B-Tree通常可以支持“只访问索引的查询”，即查询只需要访问索引，而无需访问数据行。

上述中创建的索引叫做多列索引，对应的另一类即为单列索引，在‘高性能索引策略/多列索引’中会详细介绍。

2.2 哈希索引 及 R-Tree索引

hash 哈希索引基于哈希表实现，只有精确匹配索引所有列的查询才有效。对于每一行数据，存储引擎都会对所有的索引列计算一个哈希吗（hash code），哈希吗是一个较小的值，并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。 在MySQL中，只有Memory引擎显式支持哈希索引。 InnoDB引擎有一个特殊的功能叫做“自适应哈希”，当InnodeDB注意到某些索引值被使用的非常频繁时，它会在内存中基于B-Tree索引之上在创建一个哈希索引，这样就让B-Tree索引也具有哈希索引的一些优点，比如快速的哈希查找。

空间数据索引（R-Tree） MyISAM表支持空间索引，可以用做地理数据存储。和B-Tree索引不同，这类索引无须前缀查询。空间索引会从所有维度来索引数据。查询时，可以有效地使用任意维度来组合查询。必须使用mysql的GIS相关函数如MBRCONTAINS()等来维护数据。mysql的GIS支持并不完善，所以大部分人都不会使用这个特性。开源数据库中对GIS的解决方案做的比较好的是PostgreSQL的postGIS。

2.3 关于B-tree索引的限制

1. 最左前缀匹配原则，即必须按照多列索引的最左列开始查找，或者每一列索引的最左前面的几个字符匹配查找，如果不是按照索引的最左列开始查找，则无法使用索引。例如上面的例子中无法用索引查找名为san的数据。类似的，也无法查找姓氏以某个字母为结尾的数据。
2. 不能跳过索引中的列，例如上述例子中的索引无法用于查询surname = peng and birthday = 1994-05-17;的信息，因为没有指定name条件。
3. 如果查询中有某一个列的范围查询，则其右边所有列都无法使用索引进行优化查找。例如上述表中，条件为where surname = peng and name = tu% and birthday = 1994-05-17的查询无法利用到birthday索引，因为name列有个模糊查询，属于范围查询，但是范围查询前面的列是可以利用索引的。

由此可以得出，类似的在where条件查询中想进行模糊查询时，aaa%则可以利用上索引，而%aaa%以及%aaa则无法利用上索引，以及范围查询条件最好放到后面，或者范围查询列值的数量有限时，可以通过使用多个等于条件来代替范围查询。
还有，尽可能将需要做范围查询的列放到索引的后面，这样优化器能使用尽可能多的索引列。 索引的顺序很重要。

三、 高性能的索引策略

3.1 独立的列

‘独立的列’是指索引列不能是表达式的一部分，也不能是函数的参数。
例如：mysql> select x from table where x+1 = 5;
虽然可以很容易的分辩出x的值为4，但是Mysql则无法利用该索引（如果x是索引的话）。尽量养成简化where的习惯，始终将索引单独的的放在符号的一侧，这样Mysql才可以利用上索引。

3.2 索引选择性 和 前缀索引

先介绍索引选择性
索引的选择性是指，不重复的索引值和数据表的记录总数（T）的比值，范围在 1/T 到 1 之间。不重复的索引值也称为基数（cardinality）。因为选择性高的索引可以让Mysql在查找时过滤掉更多的行，所以索引的选择性越高则查询效率越高。唯一索引的基数即为数据的条数，其选择性为1，所以唯一索引的性能最好。
对于TEXT或是VARCHAR类型的列，当这个列中的值长度很大又必须利用其进行查询时，就必须使用这个列的前几位值以作索引，即前缀索引，因为整个列的值当做索引时B+tree会占用非常大的空间，查找也不方便。
而制定前缀索引时要注意的一点就是这个前缀索引的选择性需要和整个列的选择性接近，这样性能不会影响太多，同时还不能太长而占用太多空间。
这有一种寻找最佳前缀索引的方式，即根据选择性的定义来进行计算其完整列的选择性及其前缀的选择性以便对比。
假设：有一个表中的某一列，名为session，其值为十六进制的ID
首先进行完整列的选择性的计算
mysql> SELECT COUNT(DISTINCT session) / COUNT( * ) FROM table;
如果是唯一ID，则其值应为1，然后计算这个列的前缀长度为x的选择性，
mysql> SELECT COUNT(DISTINCT LEFT( session , x )) / COUNT( * ) FROM table;
得到一个小数值，可以改变x的值来计算不同前缀的选择性，最后在多个值中，综合考虑选择性接近性和前缀长度的两个方面，可以选出一个较为合适的前缀索引。
创建一个前缀长度为x的索引：
mysql> ALTER TABLE table ADD KEY (session (x) );

小贴士：例如某个列的值存的是邮箱时，可以先字符串反转，或者根据@标识符前后颠倒，再存入数据库，再建立前缀索引，这样就可以根据前缀索引快速查出特定邮箱域名的所有信息了。

3.3 多列索引

在Mysql执行查询时，如果是使用多列索引，则会先查询符合第一列索引的数据集，然后再在这一部分数据集中查询出符合第二列的数据，以此类推，这样在不用扫描数据的情况下就能选出数据；
而如果一个多列索引拆分成多个单列索引的话，Mysql在执行查询时，只会从中选出一个限制最严格的索引以供使用，其他的索引就浪费了，所以在上述情况中多列索引性能要好
注：在Mysql 5.0之后，Mysql添加了‘索引合并’策略，一定程度上可以使用表上的多个单列索引来定位数据。
实际上，Mysql 5.0之后有种算法可以查询能够同时使用这两个单列索引进行扫描，并将结果合并。
这种算法的三个变种: or条件的联合(union)， and条件的相交(intersection) 及 组合前两种情况的联合及相交
例如:

`and`优化

可见在Extra列中，显示为两种索引的相交优化。
虽说如此，这种处理会带来一些负面影响:

• 当服务器需要对多个索引做联合操作时，即有多个or条件时，通常需要消耗CPU和内存资源在算法的缓存、排序和合并操作上。当其中一些索引的选择性不高而导致数据量很大时此情况更甚。
• 其次，这些优化计算所消耗的成本是不会被优化器计入“查询成本”中，当消耗了更多的CPU和内存资源而不知晓时，还是蛮可怕的。
• 还有一个数据库服务器有多个任务需要查询时，这种优化会影响查询的并发性，降低效率。

此外，这种优化有使用限制，例如，我的where条件中的使用的是a_id和b_id两种单列索引，也只有在查询这两列的值的情况下才会运用到优化，当查询这两列之外的值时就无法使用优化。如下图:

优化失效

查询多一个gender字段时，Extra列显示并无优化策略。相同模式的sql语句，可能有时能使用索引，有时不能使用索引。是否能使用索引，取决于mysql查询优化器对统计数据分析后，是否认为使用索引更快。
所以相比之下，对于一些常用多个需要联合查询的条件创建一个多列索引更好些。

3.4 选择合适的索引列顺序

这一节主要是针对 B-Tree索引，常用的存储引擎即为InnoDB和MyISAM。

一条经验法则(从书上学来的)，即 : 将选择性最高的列放到索引放到索引的最前列。
按照上述的关于选择性的介绍中，可以用一条sql计算出所有的需要用到的索引的相对应的选择性，又或者在知道了该表中的大致数据记录数的情况下，用show index from table来查看所有的索引对应的基数值(Cardinality)，也能大致比较出索引选择性的高低。

查看索引

上图可见People表中所有索引的基数。
也就是提醒大家，别忘了where子句中的排序、分组和范围条件等因素，说不定你就在这踩了坑。

3.5 覆盖索引

如果一个索引包含了所有需要查询的字段的值，就称之为“覆盖索引”。
覆盖索引有以下几点好处:

• 覆盖索引对于I/O密集型的应用很有帮助，因为数据量比较小则可以放入主存中，加快读取速度
• 如MyISAM存储引擎在内存中只缓存了引擎，数据则依赖操作系统缓存，所以只查询索引值会飞快
• InnoDB存储引擎使用的聚簇索引，覆盖索引更有用。因为InnoDB的二级索引的B-Tree的叶结点存储的是对应的一级索引，所以如果二级索引覆盖了所要查询的值则会少一次利用一级索引查询。效率提升很多。

当发起一个索引覆盖查询时，在Extra列中可见“Using index”的信息。
例如:

覆盖索引

建立的多列索引包含了所要查询的字段，索引可直接查询Using index而提升速度。
注:
其一:当查询中使用了一个 * 时，肯定是无法使用覆盖索引的；
其二:如果不符合最左前缀匹配原则，也无法使用索引覆盖。

3.6 冗余索引

冗余即多余
例如，创建了key (a_id, b_id)索引时，如果再创建一个key (a_id)就是多余的，因为它只是多列索引的前缀而已
但是当创建key (b_id)时，就不属于冗余索引了，因为上述的多列索引是无法单独使用b_id 作索引查询。
理论上冗余索引会带来一定程度上的查询影响，与当前条查询语句相关的索引数量越多，效率越低，原因在于优化器需要从information_schema中获取相关索引的metadata信息并分析，索引数量越多，这个过程越漫长。虽然一般来说这个影响不太大。

四、总结

索引太复杂，原理要理解，创建需谨慎，使用多思考。
(这句是给我自己说的)

以上。

参考文献：
[1]：《数据结构（C语言版）》（2007年版），清华大学出版社，编著者为严蔚敏，吴伟民。
[2]：http://blog.codinglabs.org/articles/theory-of-mysql-index.htm
[3]：《高性能MySQL》，电子工业出版社，Baron Schwartz，Peter Zaitsev，Vadim 著；宁海元，周振兴，彭立勋等 译