MySQL索引

索引一直都是老生常谈的话题．之前对它也是一知半解．这两天，查询了大量资料，并在阅读了«High Performance MySQL»的相关章节后，终于对它有了一个比较清晰地认识．所以在这里记录下来．

我对MySQL并不精通，所以即使呕心沥血地写下这篇文章，其中难免还有一些错误．请各位在阅读的时候，保持怀疑的太多，去查阅更多资料．如果发现哪里有错误，请在评论区指正，大家一起进步！

实现索引的数据结构：B-Tree和B+Tree

在介绍索引之前，我们首先介绍两个重要的数据结构：B-Tree和B+Tree．因为索引的很多操作都跟它们的特性有关．

B-Tree

B-Tree的结构如下图所示：

我们可以看到，每个节点都是这种形式：

其中p_i，1 <= i <= 4表示指向子节点的指针，子节点的形式跟上面的相同．

k_i，1<= i <= 3表示第i个key，在k_i左边的p_i，其指向的子节点中的key均小于k_i，于此类似，在k_i右边的p_i+1，其指向的子节点中的key均大于k_i．

我们可以看到，B-Tree实际上就是一个扩展了的BST，即每个节点可以有多个key．

同时，它也是一棵自平衡树，这也就意味着，在进行插入或删除操作时，为了满足其特性，可能会对它的结构进行调整．那么B-Tree都有哪些特性呢？

全部叶子节点都在相同的高度上
B-Tree用属于minimum degree ‘t’来定义．这里degree跟树的degree的概念是一样的
除根节点外的其他节点，至少要包含t-1个key．根节点最少可以包含1个key
包括根节点的全部节点，最多能包含2t-1个key
一个节点的子节点的数量等于key的数量+1
一个节点中的key都是以升序存放的．k₁和k₂之间的p₂所指向的子节点包含了k₁和k₂之间的全部key
B-Tree和其它平衡BST一样，查询，插入，删除操作的时间复杂度均为O(log_n)

我们知道，B-Tree主要的应用场景就是文件系统和数据库．我们也知道，硬盘的速度是远慢于内存的，而数据库又把数据保存到硬盘中．所以，如果我们能尽可能地减少访问磁盘的次数，就能大幅提高数据库的性能．

通过使用B-Tree，并将节点的大小设置为磁盘上一页的大小，我们不就可以尽可能地减少访问磁盘的次数？

更多关于B-Tree的资料，请自行在wikipedia中查找．

B+Tree

B+Tree是对B-Tree的一种优化，它的结构跟B-Tree其实差不多．比如，在B-Tree中的那个例子，换成B+Tree就是：

我们可以看到，跟B-Tree的区别在于：

孩子节点包含了双亲节点的key
叶子节点的最右侧指针指向了其兄弟节点

我们拿一张表举个例子：

上图中的数据，包括row address，都是我随意编造的．

上图中的数据，用B-Tree表示可能是这样：

我们可以看到，每个节点，除了保存有id之外，还保存有那一行的地址．

这个地址肯定是必须的，但是我们可不可以放在其他位置呢？把它放在中间节点的话，树的深度肯定比放在叶子节点深．因为放在叶子节点的话，中间节点的key肯定多嘛！

所以，用B+Tree表示就是：

由于这个例子中，数据较少，B+Tree的优势不是太明显．

那么为什么要让叶子节点的最右侧指向其兄弟节点呢？

因为在SQL中，我们经常有范围查询的需求，这样做的话，就不用回溯了．范围查询就方便了好多，对吧？

其他数据结构

除了这两种数据结构以外，还有其他的，如哈希表等，但是这些都是用在特殊的索引中的，没有B-Tree和B+Tree通用．

索引的分类

索引主要可以按照底层数据结构，主次，用处来分类．

按照底层数据结构划分

B-Tree indexes：顾名思义，这种索引的内部的数据结构是B-Tree．实际上，大多数Storage Engine使用的实际上是B+Tree．
Hash indexes：Hash indexes的内部数据结构是哈希表，它会为索引中的每一列对应的值计算一个对应的哈希值，存放在哈希表中，用于精确匹配．
Spatial(R-Tree) indexes：这种索引是用于存储地理信息的，具体我也不太清楚
Full-text indexes：这种索引是用在全文检索中的，它是一种特殊的索引，它会在text中查找keyword，而不是把它和index中对应的列对应的值做比较．它有很多不同之处，如分词等．

按照主次划分

Clustered index(primary index)：它和Primary Index是一样的意思，就是将Primary Key相近的row放在一起．默认情况下，会为Primary Key建立Clustered index．如果这张表中并没有Primary key，则挑选第一个非空且不重复的列建立Clustered index．如果这张表中既无Primary key又无非空不重复的列，则MySQL会为我们创建一个隐藏的id并建立Clustered index．从上面我们对Clustered Index的介绍，结合B-Tree的特性，我们可以很容易地知道Clustered Index是用B-Tree indexes实现的．
Secondary Index：它和Clustered Index是相对的，除Clustered Index外的其他Index，比如UNIQUE Indexes等都属于Secondary Indexes．

按照用法划分

MultiColumn Indexes：顾名思义，这个就是在多个列上创建的索引．
Covering Indexes：其实Covering Indexes是MultiColumn Indexes的一种特殊形式，它要求索引中包含了查询条件和要查询的列，这样查询时效率相对高一些

特殊的索引

Packed Indexes：这种索引是MyISAM中提供的为了节省空间的一种索引，比如说，＇Theory＇和＇Theoristic＇会被存储为：Theo，<4, ry>，<4, ristic>．

索引的实现

索引是在Storage Engine层面实现的，而不是在Database层面实现的这里我们主要介绍B-Tree index在MyISAM和InnoDB这两种Storage Engine中的实现．

B-Tree index在MyISAM中的实现

假设有下面这种表：

其中<First_name，Last_name>是这张表的联合主键．

那么，MyISAM会建立如下图所示的索引：

上图中最重要的一点是，每个节点的key中的下半部分，是row address．那么MyISAM为什么要这样做呢？

因为在MyISAM中，数据和索引是分开存放的，即数据在一个文件中，索引在一个文件中，MyISAM会先将索引加载到内存中，然后根据Row Address去查找对应的Row.

B-Tree index在InnoDB中的实现

还是上面的那张表，InnoDB会建立如下图所示的索引：

我们可以看到，跟B-Tree index在MyISAM中的实现的差异在于：

在InnoDB中，采用B+Tree来实现
叶子节点存储的是数据而非Row Address

这是为什么呢？

因为在InnoDB中，是把索引和数据存放在一起的，所以有这种结构．

Notice

在这里我们仅仅只是介绍了B-Tree indexes的实现，其他索引的实现，比如Secondary Indexes，跟这个有一定的差距，但是差距不大，到时我们会介绍．

各种索引的优缺点

B-Tree indexes

从上面对B-Tree indexes的实现的介绍，我们可以很清楚地看到B-Tree的有点，它适用于下面的这种查询：

完全匹配
leftmost prefix匹配
Column prefix匹配
范围查询
一部分精确匹配一部分范围匹配

上面的这几种匹配都是什么意思？

假设我们有一个索引，它包含了下面几列：(first_name, last_name, country)．

当我们执行下面这条SQL时，就是完全匹配:

select * from user where first_name = ‘first_name’ and last_name = ‘last_name’ and country = ‘country’

我们可以看到，在上面的SQL中，查询条件包含了索引中的全部的列．

当我们执行下面的这个SQL，就是leftmost prefix匹配：

select * from user where first_name = ‘first_name’

我们可以看到，这条SQL中，只用到了上面的索引中的第一列．

实际上，查询条件为where first_name = … **或where first_name = … and last_name = …或where first_name = … and last_name = … and country = …**都是leftmost prefix．

当我们执行下面这条SQL，就是Column prefix:

select * from user where first_column like ‘first%’

我们可以看到，在这个模糊查询中，’%’在最右侧．

当我们执行下面这条SQL，就是范围匹配：

select * from user where first_name = … and last_name > …

在’范围查询’以及’一部分精确匹配，一部分范围匹配’这两种情况中，索引只会匹配到第一个范围查询条件．

那么，B-Tree indexes的缺点是什么呢？

细心的读者已经注意到了，上面我们写的全部SQL中的where部分，都是严格按照索引中列的顺序从左到右匹配的．这是因为，如果不满足这种条件，索引是没用的．我们考虑一下B-Tree index的实现就很容易理解．
不能跳过索引中的列进行匹配，比如，下面的where clause就不会用到索引：where first_name = … and country = …
范围查询关键字右侧的列是用到不到的．比如，如果我们的where clause 是这样的：where first_name = … and last_name like ‘A%’ and country = ‘china’，那么，即使在where clause中写了索引中全部的列，’country’也是不会被用到的．因为like是一个范围查询关键字．

Hash indexes

Hash indexes的优点是，时间复杂度仅为O(1)．这是由于哈希算法固有的特性．

另一个优点是，它并不跟B-Tree indexes一样，严格要求索引中列的顺序．

但是，它的缺点也很明显：它只能进行完全匹配．因为计算哈希值时需要索引中的全部列．

就是这个缺点导致它只能被有限的Storage Engine支持，目前只有Memory Storage Engine支持它．

另外，由于索引只包含哈希值和row address，所以这可能导致更多的I/O．

MySQL也无法用Hash Indexes来对Row进行排序．

如果冲突很多的话，维护索引的操作就会比较慢．

Covering Indexes

上文中我们也已经说过了，Covering Indexes就是包含要查询的数据的Index．比如，我们有如下索引：(first_name, last_name, age)．那么下面的SQL就会应用Covering Indexes:

select first_name, last_name, age from user where first_name = …

而下面的这条SQL就不会应用Covering Indexes:

select * from user where first_name = …

由于Covering Indexes是用B-Tree实现的，所以B-Tree indexes具有的优缺点，Covering Indexes都有．

由于要查询的数据都包含在索引中，所以，MySQL就不需要根据去读取Row的数据，直接根据索引中的数据，就能得到我们需要的全部数据，对于MyISAM这种需要再次根据Row Address来寻找的Storage Engine，这特别有用．

Secondary Indexes

Secondary Indexes也采用了B-Tree，但是它的叶子节点中既不是Row Address，也不是那一行的地址，而是那一行的primary key，所以，Secondary Indexes在查询时，需要查询两次，先找到primary key，再根据primary key去找对应的row．

用索引来排序

MySQL可以使用任何相同的索引来排序和查找Rows．

但是，只有在满足这种条件时，才能根据索引来排序结果：

order by clause中的列和索引中的列完全匹配
全部的列都能按照相同的顺序来排列
如果一个查询join了多个表，Order by clause中的列都是第一张表中的．

用索引来排序跟用索引查询有相同的限制，它必须满足leftmost prefix．

如果where　clause或join clause中也有条件，则它们中的列也算入leftmost prefix．

比如，下面两条语句都会使用索引来排序：

select * from user order by first_name asc, last_name asc select * from user where first_name = … order by first_name asc

##　参考资料

«High Performance MySQL, 3rd Edition»