一、什么是索引？
索引：是存储引擎用于快速找到记录的一种数据结构。
索引用来快速地寻找那些具有特定值的记录。如果没有索引，执行查询时MySQL必须从第一个记录开始扫描整个表的所有记录，直至找到符合要求的记录。表里面的记录数量越多，这个操作的代价就越高。
索引对查询效率有着至关重要的影响，理解索引也是进行数据库性能调优的起点。考虑如下情况，假设数据库中一个表有10^6条记录，DBMS的页面大小为4K，并存储100条记录。如果没有索引，查询将对整个表进行扫描，最坏的情况下，如果所有数据页都不在内存，需要读取10^4个页面，如果这10^4个页面在磁盘上随机分布，需要进行10^4次I/O，假设磁盘每次I/O时间为10ms(忽略数据传输时间)，则总共需要100s(但实际上要好很多很多)。如果对之建立B-Tree索引，则只需要进行log100(10^6)=3次页面读取，最坏情况下耗时30ms。这就是索引带来的效果，很多时候，当你的应用程序进行SQL查询速度很慢时，应该想想是否可以建索引。
索引优化应该是对查询性能优化最有效的手段了，索引能够轻易将查询性能提高几个数量级，”最优“的索引有时比一个”好的“索引性能要好两个数量级。创建一个真正”最优“的索引经常要重写查询sql。
索引优点：
1. 索引大大减少了服务器需要扫描的数据量。
2. 索引可以帮助服务器避免排序和临时表格。
3. 索引可以将随机I/O变为顺序I/O。
二、索引的类型
从数据结构角度
1、B-Tree索引(O(log(n)))。
2、hash索引。
3、全文索引（FULLTEXT索引）。
4、空间数据索引（R-Tree索引）。
从物理存储角度
1、聚集索引（clustered index）
2、非聚集索引（non-clustered index）
从逻辑角度
1、主键索引：主键索引是一种特殊的唯一索引，不允许有空值
2、普通索引或者单列索引
3、多列索引（复合索引）：复合索引指多个字段上创建的索引，只有在查询条件中使用了创建索引时的第一个字段，索引才会被使用。使用复合索引时遵循最左前缀集合
4、唯一索引或者非唯一索引
5、空间索引：空间索引是对空间数据类型的字段建立的索引，MYSQL中的空间数据类型有4种，分别是GEOMETRY、POINT、LINESTRING、POLYGON。MYSQL使用SPATIAL关键字进行扩展，使得能够用于创建正规索引类型的语法创建空间索引。创建空间索引的列，必须将其声明为NOT NULL，空间索引只能在存储引擎为MYISAM的表中创建
三、索引的类型的详解
3.1MySQL提供多种索引类型（按照逻辑角度分）供选择：
3.1.1普通索引
这是最基本的索引类型，而且它没有唯一性之类的限制。普通索引可以通过以下几种方式创建：
创建索引，例如CREATE INDEX <索引的名字> ON tablename (列的列表);
修改表，例如ALTER TABLE tablename ADD INDEX [索引的名字] (列的列表);
创建表的时候指定索引，例如CREATE TABLE tablename ( [...], INDEX [索引的名字] (列的列表) );
3.1.2唯一性索引
这种索引和前面的“普通索引”基本相同，但有一个区别：索引列的所有值都只能出现一次，即必须唯一。唯一性索引可以用以下几种方式创建：
创建索引，例如CREATE UNIQUE INDEX <索引的名字> ON tablename (列的列表);
修改表，例如ALTER TABLE tablename ADD UNIQUE [索引的名字] (列的列表);
创建表的时候指定索引，例如CREATE TABLE tablename ( [...], UNIQUE [索引的名字] (列的列表) );
3.1.3主键
主键是一种唯一性索引，但它必须指定为“PRIMARY KEY”。如果你曾经用过AUTO_INCREMENT类型的列，你可能已经熟悉主键之类的概念了。主键一般在创建表的时候指定，例如“CREATE TABLE tablename ( [...], PRIMARY KEY (列的列表) ); ”。但是，我们也可以通过修改表的方式加入主键，例如“ALTER TABLE tablename ADD PRIMARY KEY (列的列表); ”。每个表只能有一个主键。
3.1.4全文索引
MySQL从3.23.23版开始支持全文索引和全文检索。在MySQL中，全文索引的索引类型为FULLTEXT。全文索引可以在VARCHAR或者 TEXT类型的列上创建。它可以通过CREATE TABLE命令创建，也可以通过ALTER TABLE或CREATE INDEX命令创建。对于大规模的数据集，通过ALTER TABLE（或者CREATE INDEX）命令创建全文索引要比把记录插入带有全文索引的空表更快。本文下面的讨论不再涉及全文索引，要了解更多信息，请参见MySQL documentation。
3.1.5单列索引与多列索引
索引可以是单列索引，也可以是多列索引。下面我们通过具体的例子来说明这两种索引的区别。
示例：假设有这样一个emp表：
创建了两个单列索引：idx_ename、idx_deptno
执行：
select * from emp where ename='RgfgEv' and deptno='102'
用explain进行分析只用到了idx_ename一个索引：
当有多个单列索引时，mysql只能用到其中那个它认为最有效率的单列索引。
创建一个组合索引：idx_name_deptno：
分别执行如下sql：
select * from emp where ename='JFWTBd' and deptno='107';
索引起作用，使用到多列索引。
执行：
select * from emp where ename='JFWTBd'
索引起作用，使用到多列索引。
执行：
select * from emp where deptno='107'
索引失效，这就是mysql遵循的最左前缀原则。
在多个列上建立独立的单列索引大部分情况下并不能提高MySQL的查询性能。
在MySQL 5.0之前版本，只能使用其中以重单列索引，然而这种情况下没有哪一个独立的单列索引是非常有效的。例如：表格file_actor，有字段film_id,actor_id上各一个单列索引。
select film_id, actor_id from film_actor where actor_id = 1or film_id = 1;
对于上面的查询，where条件，这两个单列索引不是一个好的选择。MySQL对于这个查询会进行全表扫描。除非改写成如下连个查询UNION的方式：
select film_id, actor_id from film_actor where actor_id = 1 UNION ALL select film_id, actor_id from film_actor where actor_id != 1or film_id = 1;
在MySQL 5.0及跟新版本中，查询能偶同时使用两个单列索引进行扫描，并将结果进行合并。这种算法有三个变种：
1. OR条件联合（UNION）
2. AND条件相交（intersection）
3. 组合前面两种情况的联合及相交。
索引合并策略有时候是一种优化的结果，但实际上更多时候说明表上的索引建的很糟糕：
1. 当服务器对多个索引做相交操作时（通常有多个AND条件），通常意味着需要一个包含所有相关列的多列索引，而不是多个独立的单列索引。
2. 当服务器需要多个索引做联合操作时（通常是多个OR条件），通常需要耗费大量CPU和内存资源在算法的缓存、排序、合并操作上。特别是当其中有些索引的选择性不高，需要合并扫描返回的大量数据的时候。
3. 更重要的是，优化器不会把这些计算到“查询成本（cost）”中，优化器只关心随机页面的读取。这会使查询的成本被低估，导致该执行计划还不如直接走全表扫描。
如果在EXPLAIN中看到索引合并，应该好好检查下查询和表的结构，看是不是已经使最优的。也可以通过参数optimizer_switch来关闭索引合并功能。也可以使用IGNORE INDEX提示优化器忽略某些索引。
选择合适的索引顺序：
通常将选择性最高的放在前面是最好的。这时候索引的作用只是用于优化WHERE条件查询。然而性能不只是依赖于所有素银的选择性(整体基数)，也和查询条件的具体值分布关系。
3.1.6 空间索引
使用SPATIAL参数可以设置索引为空间索引。空间索引只能建立在空间数据类型上，这样可以提高系统获取空间数据的效率。MySQL中的空间数据类型包括GEOMETRY和POINT、LINESTRING和POLYGON等。目前只有MyISAM存储引擎支持空间检索，而且索引的字段不能为空值。对于初学者来说，这类索引很少会用到。
3.2、索引的类型（从数据结构角度）
索引是在存储引擎中实现的，而不是在服务器层中实现的。所以，每种存储引擎的索引都不一定完全相同，并不是所有的存储引擎都支持所有的索引类型。
3.2.1、B-Tree索引
B-Tree：每一个叶子节点都包含指向下一个叶子节点的指针，从而方便叶子节点的范围遍历。B-Tree通常意味着所有的值都是按顺序存储的，并且每一个叶子页到根的距离相同，很适合查找范围数据。
InnoDB使用B+Tree，B+Tree是一个平衡的多叉树，从根节点到每个叶子节点的高度差值不超过1，而且同层级的节点间有指针相互链接。
在B+Tree上的常规检索，从根节点到叶子节点的搜索效率基本相当，不会出现大幅波动，而且基于索引的顺序扫描时，也可以利用双向指针快速左右移动，效率非常高。
因此，B+树索引被广泛应用于数据库、文件系统等场景。顺便说一下，xfs文件系统比ext3/ext4效率高很多的原因之一就是，它的文件及目录索引结构全部采用B+Tree索引，而ext3/ext4的文件目录结构则采用Linked list, hashed B-tree、Extents/Bitmap等索引数据结构，因此在高I/O压力下，其IOPS能力不如xfs。
假设有如下一个表：
CREATE TABLE People (
last_name varchar(50) not null,
first_name varchar(50) not null,
dob date not null,
gender enum('m', 'f') not null,
key(last_name, first_name, dob)
);
其索引包含表中每一行的last_name、first_name和dob列。其结构大致如下：
索引存储的值按索引列中的顺序排列。可以利用B-Tree索引进行全关键字、关键字范围和关键字前缀查询，当然，如果想使用索引，你必须保证按索引的最左边前缀(leftmost prefix of the index)来进行查询。
(1)匹配全值(Match the full value)：对索引中的所有列都指定具体的值。例如，上图中索引可以帮助你查找出生于1960-01-01的Cuba Allen。
(2)匹配最左前缀(Match a leftmost prefix)：你可以利用索引查找last name为Allen的人，仅仅使用索引中的第1列。
(3)匹配列前缀(Match a column prefix)：例如，你可以利用索引查找last name以J开始的人，这仅仅使用索引中的第1列。
(4)匹配值的范围查询(Match a range of values)：可以利用索引查找last name在Allen和Barrymore之间的人，仅仅使用索引中第1列。
(5)匹配部分精确而其它部分进行范围匹配(Match one part exactly and match a range on another part)：可以利用索引查找last name为Allen，而first name以字母K开始的人。
(6)仅对索引进行查询(Index-only queries)：如果查询的列都位于索引中，则不需要读取元组的值。(覆盖索引)
由于B-Tree中的节点都是顺序存储的，所以可以利用索引进行查找(找某些值)，也可以对查询结果进行ORDER BY。
当然，使用B-tree索引有以下一些限制：
(1) 查询必须从索引的最左边的列开始，否则无法使用索引。关于这点已经提了很多遍了。例如你不能利用索引查找在某一天出生的人。
(2) 不能跳过某一索引列。例如，你不能利用索引查找last name为Smith且出生于某一天的人。
(3) 存储引擎不能使用索引中范围条件右边的列。例如，如果你的查询语句为WHERE last_name="Smith" AND first_name LIKE 'J%' AND dob='1976-12-23'，则该查询只会使用索引中的前两列，因为LIKE是范围查询。
3.2.2、Hash索引
哈希索引基于哈希表实现，只有精确索引所有列的查询才有效。对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码，哈希码是一个较小的值，并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希存储在索引中，同时在哈希表中保存指向每个数据的指针。
MySQL中，只有Memory存储引擎显示支持hash索引，是Memory表的默认索引类型，尽管Memory表也可以使用B-Tree索引。Memory存储引擎支持非唯一hash索引，这在数据库领域是罕见的，如果多个值有相同的hash code，索引把它们的行指针用链表保存到同一个hash表项中。
假设创建如下一个表：
CREATE TABLE testhash ( fname VARCHAR(50) NOT NULL, lname VARCHAR(50) NOT NULL, KEY USING HASH(fname) ) ENGINE=MEMORY;
包含的数据如下：
假设索引使用hash函数f( )，如下：
f('Arjen') = 2323
f('Baron') = 7437
f('Peter') = 8784
f('Vadim') = 2458
此时，索引的结构大概如下：
哈希索引中存储的是：哈希值+数据行指针
Slots是有序的，但是记录不是有序的。当你执行
mysql> SELECT lname FROM testhash WHERE fname='Peter';
MySQL会计算’Peter’的hash值，然后通过它来查询索引的行指针。因为f('Peter') = 8784，MySQL会在索引中查找8784，得到指向记录3的指针。
因为索引自己仅仅存储很短的值，所以，索引非常紧凑。Hash值不取决于列的数据类型，一个TINYINT列的索引与一个长字符串列的索引一样大。
Hash索引有以下一些限制：
(1)由于索引仅包含hash code和记录指针，所以，MySQL不能通过使用索引避免读取记录。但是访问内存中的记录是非常迅速的，不会对性造成太大的影响。
(2)哈希索引数据并不是按照索引值顺序存储的，所以不能使用hash索引排序。
(3)Hash索引不支持键的部分匹配，因为是通过整个索引值来计算hash值的。例如，在数据列（A,B）上建立哈希索引，如果查询只有数据列A，则无法使用该索引。
(4)Hash索引只支持等值比较，例如使用=，IN( )和<=>。对于WHERE price>100并不能加速查询。
(5)访问Hash索引的速度非常快，除非有很多哈希冲突（不同的索引列值却有相同的哈希值）。当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。
(6)如果哈希冲突很多的话，一些索引维护操作的代价也会很高。当从表中删除一行时，存储引擎要遍历对应哈希值的链表中的每一行，找到并删除对应行的引用，冲突越多，代价越大。
InnoDB引擎有一个特殊的功能叫做“自适应哈希索引”。当InnoDB注意到某些索引值被使用得非常频繁时，它会在内存中基于B-Tree索引上再创建一个哈希索引，这样就像B-Tree索引也具有哈希索引的一些优点，比如快速的哈希查找。
创建哈希索引：如果存储引擎不支持哈希索引，则可以模拟像InnoDB一样创建哈希索引，这可以享受一些哈希索引的便利，例如只需要很小的索引就可以为超长的键创建索引。
思路很简单：在B-Tree基础上创建一个伪哈希索引。这和真正的哈希索引不是一回事，因为还是使用B-Tree进行查找，但是它使用哈希值而不是键本身进行索引查找。你需要做的就是在查询的where子句中手动指定使用哈希函数。这样实现的缺陷是需要维护哈希值。可以手动维护，也可以使用触发器实现。
如果采用这种方式，记住不要使用SHA1和MD5作为哈希函数。因为这两个函数计算出来的哈希值是非常长的字符串，会浪费大量空间，比较时也会更慢。SHA1和MD5是强加密函数，设计目标是最大限度消除冲突，但这里并不需要这样高的要求。简单哈希函数的冲突在一个可以接受的范围，同时又能够提供更好的性能。
如果数据表非常大，CRC32会出现大量的哈希冲突，CRC32返回的是32位的整数，当索引有93000条记录时出现冲突的概率是1%。
处理哈希冲突：当使用哈希索引进行查询时，必须在where子句中包含常量值。
3.2.3、空间(R-Tree)索引
MyISAM支持空间索引，主要用于地理空间数据类型，例如GEOMETRY。和B-TREE索引不同，这类索引无须前缀查询。空间索引会从所有到维度来索引数据。查询时，可以有效地使用任意维度来组合查询。必须使用MySQL的GIS相关函数如MBRCONTAINS()等来维护数据。MySQL的GIS支持并不完善，所以大部分人都不会使用这个特性。开源关系数据库系统中对GIS的解决方案做得比较好的是PostgreSQL的PostGIS。
3.2.4、全文(Full-text)索引
全文索引是MyISAM的一个特殊索引类型，innodb的5.6以上版本也支持，它查找的是文本中的关键词主要用于全文检索。
全文索引是一种特殊类型的索引，它查找都是文本中的关键词，而不是直接比较索引中的值。全文搜索和其他几类索引匹配方式完全不一样。它有许多需要注意的细节，如停用词、词干和复数、布尔搜索等。全文索引更类似于搜索引擎做的事情，而不是简单的WHERE条件匹配。
在相同的列上同时创建全文索引和基于值对B-Tree索引不会有冲突，全文索引适用于MATCH AGAINST操作，而不是普通的WHERE条件操作。
3.3、从物理存储角度索引分类
3.3.1、聚簇索引(Clustered Indexes)
聚簇索引保证关键字的值相近的元组存储的物理位置也相同（所以字符串类型不宜建立聚簇索引，特别是随机字符串，会使得系统进行大量的移动操作），且一个表只能有一个聚簇索引。因为由存储引擎实现索引，所以，并不是所有的引擎都支持聚簇索引。目前，只有solidDB和InnoDB支持。
3.3.2、非聚簇索引
3.3.3、聚簇索引的结构大致如下：
叶子页包含了行的全部数据，但是节点页只包含了索引列。
二级索引叶子节点保存的不是指行的物理位置的指针，而是行的主键值。这意味着通过二级索引查找行，存储引擎需要找到二级索引的叶子节点获取对应的主键值，然后根据这个值去聚簇索引中查找到对应的行。这里做了重复的工作：两次B－TREE查找而不是一次。
注：叶子页面包含完整的元组，而内节点页面仅包含索引的列(索引的列为整型)。一些DBMS允许用户指定聚簇索引，但是MySQL的存储引擎到目前为止都不支持。InnoDB对主键建立聚簇索引。如果你不指定主键，InnoDB会用一个具有唯一且非空值的索引来代替。如果不存在这样的索引，InnoDB会定义一个隐藏的主键，然后对其建立聚簇索引。一般来说，DBMS都会以聚簇索引的形式来存储实际的数据，它是其它二级索引的基础。
3.3.4、InnoDB和MyISAM的数据布局的比较
为了更加理解聚簇索引和非聚簇索引，或者primary索引和second索引(MyISAM不支持聚簇索引)，来比较一下InnoDB和MyISAM的数据布局，对于如下表：
CREATE TABLE layout_test ( col1 int NOT NULL, col2 int NOT NULL, PRIMARY KEY(col1), KEY(col2) );
假设主键的值位于1---10,000之间，且按随机顺序插入，然后用OPTIMIZE TABLE进行优化。col2随机赋予1---100之间的值，所以会存在许多重复的值。
(1) MyISAM的数据布局
其布局十分简单，MyISAM按照插入的顺序在磁盘上存储数据，如下：
注：左边为行号(row number)，从0开始。因为元组的大小固定，所以MyISAM可以很容易的从表的开始位置找到某一字节的位置。
MyISAM建立的primary key的索引结构大致如下：
注：MyISAM不支持聚簇索引，索引中每一个叶子节点仅仅包含行号(row number)，且叶子节点按照col1的顺序存储。
来看看col2的索引结构：
实际上，在MyISAM中，primary key和其它索引没有什么区别。Primary key仅仅只是一个叫做PRIMARY的唯一，非空的索引而已，叶子节点按照col2的顺序存储。
(2) InnoDB的数据布局
InnoDB按聚簇索引的形式存储数据，所以它的数据布局有着很大的不同。它存储表的结构大致如下：
注：聚簇索引中的每个叶子节点包含primary key的值，事务ID和回滚指针(rollback pointer)——用于事务和MVCC，和余下的列(如col2)。
相对于MyISAM，InnoDB的二级索引与聚簇索引有很大的不同。InnoDB的二级索引的叶子包含primary key的值，而不是行指针(row pointers)，这样的策略减小了移动数据或者数据页面分裂时维护二级索引的开销，因为InnoDB不需要更新索引的行指针。其结构大致如下：
聚簇索引和非聚簇索引表的对比：
3.3.4、按primary key的顺序插入行(InnoDB)
如果你用InnoDB，而且不需要特殊的聚簇索引，一个好的做法就是使用代理主键(surrogate key)——独立于你的应用中的数据。最简单的做法就是使用一个AUTO_INCREMENT的列，这会保证记录按照顺序插入，而且能提高使用primary key进行连接的查询的性能。应该尽量避免随机的聚簇主键，例如，字符串主键就是一个不好的选择，它使得插入操作变得随机。
四、覆盖索引(Covering Indexes)
覆盖索引是一种非常强大的工具，能大大提高查询性能。设计优秀的索引应该考虑到整个查询，而不单单的where条件部分。索引确实是一种查找数据的高效方式，但是MYSQL也可以使用索引来直接获取列的数据，这样就不再需要读取数据行。索引的叶子节点中已经包含要查询的数据，那么就没有必要再回表查询了，如果索引包含满足查询的所有数据，就称为覆盖索引。
解释一： 就是select的数据列只用从索引中就能够取得，不必从数据表中读取，换句话说查询列要被所使用的索引覆盖。
解释二： 索引是高效找到行的一个方法，当能通过检索索引就可以读取想要的数据，那就不需要再到数据表中读取行了。如果一个索引包含了（或覆盖了）满足查询语句中字段与条件的数据就叫做覆盖索引。
解释三： 是非聚集组合索引的一种形式，它包括在查询里的Select、Join和Where子句用到的所有列（即建立索引的字段正好是覆盖查询语句[select子句]与查询条件[Where子句]中所涉及的字段，也即，索引包含了查询正在查找的所有数据）。
只需要读取索引而不用读取数据有以下一些优点：
(1)索引项通常比记录要小，所以MySQL访问更少的数据；
(2)索引都按值的大小顺序存储，相对于随机访问记录，需要更少的I/O；
(3)大多数据引擎能更好的缓存索引。比如MyISAM只缓存索引。
(4)覆盖索引对于InnoDB表尤其有用，因为InnoDB使用聚集索引组织数据，如果二级索引中包含查询所需的数据，就不再需要在聚集索引中查找了。
覆盖索引不能是任何索引，只有B-TREE索引存储相应的值。而且不同的存储引擎实现覆盖索引的方式都不同，并不是所有存储引擎都支持覆盖索引(Memory和Falcon就不支持)。
对于索引覆盖查询(index-covered query)，使用EXPLAIN时，可以在Extra一列中看到“Using index”。例如，在sakila的inventory表中，有一个组合索引(store_id,film_id)，对于只需要访问这两列的查询，MySQL就可以使用索引，如下：
mysql> EXPLAIN SELECT store_id, film_id FROM sakila.inventory\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: inventory
type: index
possible_keys: NULL
key: idx_store_id_film_id
key_len: 3
ref: NULL
rows: 5007
Extra: Using index
1 row in set (0.17 sec)
（同时查询actor_id[主键]与last_name[索引字段]）在大多数引擎中，只有当查询语句所访问的列是索引的一部分时，索引才会覆盖。但是，InnoDB不限于此，InnoDB的二级索引在叶子节点中存储了primary key的值。因此，sakila.actor表使用InnoDB，而且对于是last_name上有索引，所以，索引能覆盖那些访问actor_id的查询，如：
mysql> EXPLAIN SELECT actor_id, last_name
-> FROM sakila.actor WHERE last_name = 'HOPPER'\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: actor
type: ref
possible_keys: idx_actor_last_name
key: idx_actor_last_name
key_len: 137
ref: const
rows: 2
Extra: Using where; Using index
五、利用索引进行排序
MySQL中，有两种方式生成有序结果集：
- 一是使用filesort
- 二是按索引顺序扫描
如果explain出来的type列的值为“index”，则说明MYSQL使用了索引扫描来做排序。利用索引进行排序操作是非常快的，因为只需要从一条索引记录移动到紧接着的下一条记录。但如果索引不能覆盖查询所需的全部列，那就不得不每扫描一条索引记录就回表查询一次对应的行，这基本上都是随机IO，因此按索引顺序读取的速度通常要比顺序地全表扫描慢，尤其是在IO密集型的工作负载时。
而且可以利用同一索引同时进行查找和排序操作。当索引的顺序与ORDER BY中的列顺序相同且所有的列是同一方向(全部升序或者全部降序)时，可以使用索引来排序。如果查询是连接多个表，仅当ORDER BY中的所有列都是第一个表的列时才会使用索引。其它情况都会使用filesort文件排序。
create table actor(
actor_id int unsigned NOT NULL AUTO_INCREMENT,
name varchar(16) NOT NULL DEFAULT '',
password varchar(16) NOT NULL DEFAULT '',
PRIMARY KEY(actor_id),
KEY (name)
) ENGINE=InnoDB;
insert into actor(name,password) values('cat01','1234567');
insert into actor(name,password) values('cat02','1234567');
insert into actor(name,password) values('ddddd','1234567');
insert into actor(name,password) values('aaaaa','1234567');
explain结果：
mysql> explain select actor_id from actor order by actor_id \G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: actor
type: index
possible_keys: NULL
key: PRIMARY
key_len: 4
ref: NULL
rows: 4
Extra: Using index
1 row in set (0.00 sec)
mysql> explain select actor_id from actor order by password \G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: actor
type: ALL
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 4
Extra: Using filesort
1 row in set (0.00 sec)
mysql> explain select actor_id from actor order by name \G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: actor
type: index
possible_keys: NULL
key: name
key_len: 18
ref: NULL
rows: 4
Extra: Using index
1 row in set (0.00 sec)
对于filesort，MySQL有两种排序算法。 当MySQL不能使用索引进行排序时，就会利用自己的排序算法(快速排序算法)在内存(sort buffer)中对数据进行排序，如果内存装载不下，它会将磁盘上的数据进行分块，再对各个数据块进行排序，然后将各个块合并成有序的结果集（实际上就是外排序，使用临时表）。
(1)两次扫描算法(Two passes)
实现方式是先将需要排序的字段和可以直接定位到相关行数据的指针信息取出，然后在设定的内存（通过参数sort_buffer_size设定）中进行排序，完成排序之后再次通过行指针信息取出所需的Columns。
注：该算法是4.1之前采用的算法，它需要两次访问数据，尤其是第二次读取操作会导致大量的随机I/O操作。另一方面，内存开销较小。
(2)一次扫描算法(single pass)
该算法一次性将所需的Columns全部取出，在内存中排序后直接将结果输出。
注：从 MySQL 4.1 版本开始使用该算法。它减少了I/O的次数，效率较高，但是内存开销也较大。如果我们将并不需要的Columns也取出来，就会极大地浪费排序过程所需要的内存。在 MySQL 4.1 之后的版本中，可以通过设置 max_length_for_sort_data 参数来控制 MySQL 选择第一种排序算法还是第二种。当取出的所有大字段总大小大于 max_length_for_sort_data 的设置时，MySQL 就会选择使用第一种排序算法，反之，则会选择第二种。为了尽可能地提高排序性能，我们自然更希望使用第二种排序算法，所以在 Query 中仅仅取出需要的 Columns 是非常有必要的。
当对连接操作进行排序时，如果ORDER BY仅仅引用第一个表的列，MySQL对该表进行filesort操作，然后进行连接处理，此时，EXPLAIN输出“Using filesort”；否则，MySQL必须将查询的结果集生成一个临时表，在连接完成之后进行filesort操作，此时，EXPLAIN输出“Using temporary;Using filesort”。
六、索引与加锁
索引对于InnoDB非常重要，因为它可以让查询锁更少的元组。这点十分重要，因为MySQL 5.0中，InnoDB直到事务提交时才会解锁。有两个方面的原因：首先，即使InnoDB行级锁的开销非常高效，内存开销也较小，但不管怎么样，还是存在开销。其次，对不需要的元组的加锁，会增加锁的开销，降低并发性。
InnoDB仅对需要访问的元组加锁，而索引能够减少InnoDB访问的元组数。但是，只有在存储引擎层过滤掉那些不需要的数据才能达到这种目的。一旦索引不允许InnoDB那样做（即达不到过滤的目的），MySQL服务器只能对InnoDB返回的数据进行WHERE操作，此时，已经无法避免对那些元组加锁了：InnoDB已经锁住那些元组，服务器无法解锁了。
来看个例子：
create table actor(
actor_id int unsigned NOT NULL AUTO_INCREMENT,
name varchar(16) NOT NULL DEFAULT '',
password varchar(16) NOT NULL DEFAULT '',
PRIMARY KEY(actor_id),
KEY (name)
) ENGINE=InnoDB;
insert into actor(name,password) values('cat01','1234567');
insert into actor(name,password) values('cat02','1234567');
insert into actor(name,password) values('ddddd','1234567');
insert into actor(name,password) values('aaaaa','1234567');
SET AUTOCOMMIT=0; BEGIN; SELECT actor_id FROM actor WHERE actor_id < 4 AND actor_id <> 1 FOR UPDATE;
mysql> EXPLAIN SELECT actor_id FROM test.actor
-> WHERE actor_id < 4 AND actor_id <> 1 FOR UPDATE \G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: actor
type: index
possible_keys: PRIMARY
key: PRIMARY
key_len: 4
ref: NULL
rows: 4
Extra: Using where; Using index
1 row in set (0.00 sec)
mysql>
该查询仅仅返回2---3的数据，实际已经对1---3的数据加上排它锁了。InnoDB锁住元组1是因为MySQL的查询计划仅使用索引进行范围查询（而没有进行过滤操作，WHERE中第二个条件已经无法使用索引了）：
表明存储引擎从索引的起始处开始，获取所有的行，直到actor_id<4为假，服务器无法告诉InnoDB去掉元组1。
为了证明row 1已经被锁住，我们另外建一个连接，执行如下操作：
SET AUTOCOMMIT=0; BEGIN; SELECT actor_id FROM actor WHERE actor_id = 1 FOR UPDATE;
该查询会被挂起，直到第一个连接的事务提交释放锁时，才会执行（这种行为对于基于语句的复制(statement-based replication)是必要的）。
如上所示，当使用索引时，InnoDB会锁住它不需要的元组。更糟糕的是，如果查询不能使用索引，MySQL会进行全表扫描，并锁住每一个元组，不管是否真正需要。
七、索引的优点：
最常见的B-Tree索引，按照顺序存储数据，所以MYSQL可以用来做order by和group by操作。因为数据是有序的，所以B-Tree也就会将相关的列值存储在一起。最后，因为索引中存储了实际的列值，所以某些查询只使用索引就能够完成全部查询。总结下来索引有如下三个优点：
1，索引大大减小了服务器需要扫描的数据量
2，索引可以帮助服务器避免排序和临时表
3，索引可以将随机IO变成顺序IO
索引三星系统：
一星：索引将相关的记录放到一起
二星：索引中的数据顺序和查找中的排列顺序一致
三星：索引中的列包含了查询中需要的全部列
索引是最好的解决方案吗？
索引并不总是最好的工具。总的来说只有索引帮助存储引擎快速查找到记录的好处大于其带来的额外工作时，索引才是有效的。
对于非常小的表，大部分情况下简单的全表扫描更高效；
对于中到大型的表，索引就非常有效。
但对于特大型的表，建立和使用索引的代价将随之增长。这种情况下需要一种技术可以直接区分出查询需要的一组数据，而不是一条记录一条记录地匹配。例如使用分区技术。
如果表的数量特别多，可以建立一个元数据信息表，用来查询需要用到的某些特性。例如执行那些需要聚合多个应用分布在多个表的数据的查询，则需要记录“哪个用户的信息存储在哪个表中”的元数据，这样在查询时就可以直接忽略那些不包含指定用户信息的表。
八、高性能的索引策略
5.1独立的列
独立的列是指索引列不能是表达式的一部分，也不是是函数的参数。例如以下两个查询无法使用索引：
1）表达式： select actor_id from sakila.actor where actor_id+1=5;
2）函数参数：select ... where TO_DAYS(CURRENT_DATE) - TO_DAYS(date_col)<=10;
5.2前缀索引和索引选择性
有时需要索引很长的字符列，它会使索引变大而且变慢。一个策略就是模拟哈希索引。但是有时这也不够好，那？
通常可以索引开始的几个字符，而不是全部值，以节约空间并得到好的性能。这使索引需要的空间变小，但这样也会降低索引的选择性。索引的选择性是指，不重复的索引值（基数）和数据表中的记录总数（#T）的比值，范围从1/#T之间。索引的选择性越高则查询效率越高，因为选择性高的索引可以让MYSQL在查找时过滤掉更多的行。
唯一索引的选择性是1，这是最好的索引选择性，性能也是最好的。
一般情况下某个前缀的选择性也是足够高的，足以满足查询性能。对于BLOB、TEXT或者很长的VARCHAR类型的列，必须使用前缀索引，因为mysql不允许索引它们的全文化。
可以在同一个查询中针对许多不同的前缀长度进行计算，选择选择性好的。
(用LEFT函数，left(city,4))
添加前缀索引
mysql>alter table test.test add key (city(7));
前缀索引能很好地减少索引的大小及提高速度，但是mysql不能在order by 和group by查询中使用前缀索引，也不能把它们用来覆盖索引。
有时后缀索引也挺有用，例如查找某个域名的所有电子邮件地址。mysql不支持反向索引，但是可以把反向字符串保存起来，并且索引它的前缀。可以用触发器维护这种索引。
决窍：在于要选择足够长的前缀以保证较高的选择性，同时又不能太长（以便节约空间）。前缀应该足够长，以使得前缀索引的选择性接近于索引整个列。换句话说，前缀的“基数”应该接近于完整列的“基数”。为了决定前缀的合适长度，需要找到最常见的值的列表，然后和最常见的前缀列表进行比较。例如以下查询：
select count(*) as cnt,city from sakila.city_demo group by city order by cnt desc limit 10;
select count(*) as cnt,left(city,7) as perf from sakila.city_demo group by city order by cnt desc limit 10;
直到这个前缀的选择性接近完整列的选择性。
计算合适的前缀长度的另一个方法就是计算完整列的选择性，并使前缀的选择性接近于完整列的选择性，如下：
select count(distinct city)/count(*) from sakila.city_demo;
select count(distinct left(city,7))/count(*) from sakila.city_demo;
前缀索引是一种能使索引更小、更快的有效办法，但另一方面也有其缺点：MYSQL无法使用前缀索引做order by和group by，也无法使用前缀索引做覆盖扫描。
5.3多列索引
一个多列索引与多个列索引MYSQL在解析执行上是不一样的，如果在explain中看到有索引合并，应该好好检查一下查询的表和结构是不是已经最优。
5.4选择合适的索引列顺序
对于如何选择索引的顺序有一个经验法则：将选择性最高的列放在索引最前列。
当不需要考虑排序和分组时，将选择性最高的列放在前面通常是最好的。然后，性能不只是依赖于所有索引列的选择性（整体基数），也和查询条件的具体值有关，也就是和值的分布有关。这和前面介绍的选择前缀的长度需要考虑的地方一样。可能需要根据那些运行频率最高的查询来调整索引列的顺序，让这种情况下索引的选择性最高。
使用经验法则要注意不要假设平均情况下的性能也能代表特殊情况下的性能，特殊情况可能会摧毁整个应用的性能（当使用前缀索引时，在某些条件值的基数比正常值高的时候）。
5.5单列索引、多列索引以及最左前缀 原则及使用上的特点
结合实例说明如下：现在我们想查出满足以下条件的用户id：
mysql>SELECT ｀uid｀ FROM people WHERE lname｀='Liu' AND ｀fname｀='Zhiqun' AND ｀age｀=26
因为我们不想扫描整表，故考虑用索引。
单列索引：
ALTER TABLE people ADD INDEX lname (lname);
将lname列建索引，这样就把范围限制在lname='Liu'的结果集1上，之后扫描结果集1，产生满足fname='Zhiqun'的结果集2，再扫描结果集2，找到 age=26的结果集3，即最终结果。
由 于建立了lname列的索引，与执行表的完全扫描相比，效率提高了很多，但我们要求扫描的记录数量仍旧远远超过了实际所需 要的。虽然我们可以删除lname列上的索引，再创建fname或者age 列的索引，但是，不论在哪个列上创建索引搜索效率仍旧相似。
2.多列索引：
ALTER TABLE people ADD INDEX lname_fname_age (lame,fname,age);
为了提高搜索效率，我们需要考虑运用多列索引,由于索引文件以B－Tree格式保存，所以我们不用扫描任何记录，即可得到最终结果。
注：在mysql中执行查询时，只能使用一个索引，如果我们在lname,fname,age上分别建索引,执行查询时，只能使用一个索引，mysql会选择一个最严格(获得结果集记录数最少)的索引。
3.最左前缀：顾名思义，就是最左优先，上例中我们创建了lname_fname_age多列索引,相当于创建了(lname)单列索引，(lname,fname)组合索引以及(lname,fname,age)组合索引。
注：在创建多列索引时，要根据业务需求，where子句中使用最频繁的一列放在最左边。
九、分析索引效率
现在我们已经知道了一些如何选择索引列的知识，但还无法判断哪一个最有效。MySQL提供了一个内建的SQL命令帮助我们完成这个任务，这就是 EXPLAIN命令。EXPLAIN命令的一般语法是：EXPLAIN 。你可以在MySQL文档找到有关该命令的更多说明。下面是一个例子：
EXPLAIN SELECT peopleid FROM people WHERE firstname='Mike' AND lastname='Sullivan' AND age='17';
这个命令将返回下面这种分析结果：
下面我们就来看看这个EXPLAIN分析结果的含义。
见explain章节
十、索引的缺点
到目前为止，我们讨论的都是索引的优点。事实上，索引也是有缺点的。
首先，索引要占用磁盘空间。通常情况下，这个问题不是很突出。但是，如果你创建每一种可能列组合的索引，索引文件体积的增长速度将远远超过数据文件。如果你有一个很大的表，索引文件的大小可能达到操作系统允许的最大文件限制。
第二，对于需要写入数据的操作，比如DELETE、UPDATE以及INSERT操作，索引会降低它们的速度。这是因为MySQL不仅要把改动数据写入数据文件，而且它还要把这些改动写入索引文件。
【结束语】在大型数据库中，索引是提高速度的一个关键因素。不管表的结构是多么简单，一次500000行的表扫描操作无论如何不会快。如果你的网站上也有 这种大规模的表，那么你确实应该花些时间去分析可以采用哪些索引，并考虑是否可以改写查询以优化应用。要了解更多信息，请参见MySQL manual。另外注意，本文假定你所使用的MySQL是3.23版，部分查询不能在3.22版MySQL上执行。
B+Tree