数据库索引

数据库索引的本质是一个排序的数据结构，以协助快速查询、更新数据库表中的数据，可以理解为一种特殊的目录，实现方式通常采用B树和B+树

  上图展示了一种可能的索引方式，左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在O(log2n)的复杂度内获取到相应数据。

目前大部分数据库系统及文件系统都采用B树或其变种B+树作为索引结构

创建索引可以大大提高系统的性能：

1.通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
2.可以大大加快数据的检索速度，这也是创建索引的最主要的原因。
3.可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义。
4.在使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。
5.通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

但是盲目的增加索引也有很多不利的地方：

1.创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加。
2.索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。
3.当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度。

索引分类：

1.聚集索引（lustered index，也称聚类索引、簇集索引）
2.非聚集索引（nonclustered index，也称非聚类索引、非簇集索引）

每个表只能用一个聚集索引

区别：

聚集索引的物理地址按索引排列
非聚集索引的物理地址不按照索引排序

  如：返回某范围内的数据一项。比如某个表有一个时间列，恰好把聚合索引建立在了该列，这时查询2004年1月1日至2004年10月1日之间的全部数据时，这个速度就将是很快的，因为这本字典正文是按日期进行排序的，聚类索引只需要找到要检索的所有数据中的开头和结尾数据即可；而不像非聚集索引，必须先查到目录中查到每一项数据对应的页码，然后再根据页码查到具体内容。

何时使用聚集索引或非聚集索引：

索引使用时的常见问题：
1.主键就是聚集索引
  通常，每个表中都会建立一个ID，以区分每条数据，并且这个ID列是自动增大的，步长一般为1。如果将这个列设为主键，数据库会将此列默认为聚集索引。这样做有好处，就是可以让数据在数据库中按照ID进行物理排序。
  但是使用聚集索引的最大好处就是能够根据查询要求，迅速缩小查询范围，避免全表扫描。在实际应用中，因为 ID号是自动生成的，并不知道每条记录的ID号，所以很难在实践中用ID号来进行查询。这就使让ID号这个主键作为聚集索引成为一种资源浪费。其次，让每个ID号都不同的字段作为聚集索引也不符合“大数目的不同值情况下不应建立聚合索引”规则。

      在办公自动化系统中，无论是系统首页显示的需要用户签收的文件、会议还是用户进行文件查询等任何情况下进行数据  
  查询都离不开字段的是“日期”还有用户本身的“用户名”。  	  
　    通常，办公自动化的首页会显示每个用户尚未签收的文件或会议。虽然我们的where语句可以仅仅限制当前用户尚未签收  
  的情况，但如果您的系统已建立了很长时间，并且数据量很大，那么，每次每个用户打开首页的时候都进行一次全表扫描，这  
  样做意义是不大的，绝大多数的用户1个月前的文件都已经浏览过了，这样做只能徒增数据库的开销而已。事实上，我们完全  
  可以让用户打开系统首页时，数据库仅仅查询这个用户近3个月来未阅览的文件，通过“日期”这个字段来限制表扫描，提高查询  
  速度。如果您的办公自动化系统已经建立的2年，那么您的首页显示速度理论上将是原来速度8倍，甚至更快。
　    在这里之所以提到“理论上”三字，是因为如果聚集索引还是盲目地建在ID这个主键上时，您的查询速度是没有这么高的，  
  即使在“日期”这个字段上建立的索引（非聚合索引）。下面我们就来看一下在1000万条数据量的情况下各种查询的速度  
  表现（3个月内的数据为25万条）：
 
1.仅在主键上建立聚集索引，并且不划分时间段：
 
select gid,fariqi,neibuyonghu,title from tgongwen

用时：128470毫秒（即：128秒）

2.在主键上建立聚集索引，在fariq上建立非聚集索引：

select gid,fariqi,neibuyonghu,title from Tgongwen where fariqi> dateadd(day,-90,getdate())

用时：53763毫秒（54秒）

3.将聚合索引建立在日期列（fariqi）上：

select gid,fariqi,neibuyonghu,title from Tgongwen where fariqi> dateadd(day,-90,getdate())

用时：2423毫秒（2秒）

2.只要建立索引就能显著提高查询速度：
  事实上，可以发现上面的例子中，第2、3条语句完全相同，且建立索引的字段也相同；不同的仅是前者在fariqi字段上建立的是非聚合索引，后者在此字段上建立的是聚合索引，但查询速度却有着天壤之别。所以，并非是在任何字段上简单地建立索引就能提高查询速度。
　　从建表的语句中，可以看到这个有着1000万数据的表中fariqi字段有5003个不同记录。在此字段上建立聚合索引是再合适不过了。在现实中，我们每天都会发几个文件，这几个文件的发文日期就相同，这完全符合建立聚集索引要求的：“既不能绝大多数都相同，又不能只有极少数相同”的规则。由此看来，建立“适当”的聚合索引对于我们提高查询速度是非常重要的。

3.把所有需要提高查询速度的字段都加进聚集索引，以提高查询速度
  上面已经谈到：在进行数据查询时都离不开字段的是“日期”还有用户本身的“用户名”。既然这两个字段都是如此的重要，我们可以把他们合并起来，建立一个复合索引（compound index）。

复合索引（联合索引）：
相对于一般索引只有一个字段，复合索引可以为多个字段创建一个索引。比如，我们在（a,b,c）字段上创建一个复合索引，则索引记录会首先按照a字段排序，然后再按照b字段排序然后再是c字段，因此，联合索引的特点就是：
第一个字段一定是有序的
当第一个字段值相等的时候，第二个字段又是有序的，比如下表中当A=2时所有B的值是有序排列的，依次类推，当同一个B值得所有C字段是有序排列的
| a | b | c |
| 1 | 2 | 3 |
| 1 | 4 | 2 |
| 1 | 1 | 4 |
| 2 | 3 | 5 |
| 2 | 4 | 4 |
| 2 | 4 | 6 |
| 2 | 5 | 5 |
其实联合索引的查找就跟查字典是一样的，先根据第一个字母查，然后再根据第二个字母查，或者只根据第一个字母查，但是不能跳过第一个字母从第二个字母开始查。这也就是所谓的最左前缀原理。
对于复合索引it1abc(a,b,c)，查询语句select * from t1 where a=1 and b=2 能够使用该索引。查询语句select * from t1 where a=1 也能够使用该索引。但是，查询语句select * from t1 where b=2 不能够使用该索引，因为没有组合索引的引导列，即，要想使用b列进行查找，必需出现a等于某值。

  很多人认为只要把任何字段加进聚集索引，就能提高查询速度，也有人感到迷惑：如果把复合的聚集索引字段分开查询，那么查询速度会减慢吗？带着这个问题，我们来看一下以下的查询速度（结果集都是25万条数据）：（日期列fariqi首先排在复合聚集索引的起始列，用户名neibuyonghu排在后列）：

1.select gid,fariqi,neibuyonghu,title from Tgongwen where fariqi>''2004-5-5''

查询速度：2513毫秒

2.select gid,fariqi,neibuyonghu,title from Tgongwen where fariqi>''2004-5-5'' and neibuyonghu=''办公室''

查询速度：2516毫秒

3.select gid,fariqi,neibuyonghu,title from Tgongwen where neibuyonghu=''办公室''

查询速度：60280毫秒

  从以上试验中，可以看到如果仅用聚集索引的起始列作为查询条件和同时用到复合聚集索引的全部列的查询速度是几乎一样的，甚至比用上全部的复合索引列还要略快（在查询结果集数目一样的情况下）；而如果仅用复合聚集索引的非起始列作为查询条件的话，这个索引是不起任何作用的。当然，语句1、2的查询速度一样是因为查询的条目数一样，如果复合索引的所有列都用上，而且查询结果少的话，这样就会形成“索引覆盖”，因而性能可以达到最优。同时，无论是否经常使用聚合索引的其他列，但其前导列一定要是使用最频繁的列。

索引覆盖：
查找的目标数据， 包含在索引中，如建立idx_colum1_colum2
select colum1 from table where colum1 = ? and colum2 > ?
通过查询索引就能确定最终的数据，不用再利用叶子节点中存储的主键值去查询对应的数据

4.用聚合索引比用不是聚合索引的主键速度快

select gid,fariqi,neibuyonghu,reader,title from Tgongwen where fariqi=''2004-9-16''

使用时间：3326毫秒

select gid,fariqi,neibuyonghu,reader,title from Tgongwen where gid<=250000

使用时间：4470毫秒  

用聚合索引比用不是聚合索引的主键速度快了近1/4。

5.用聚合索引比用一般的主键作order by时速度快，特别是在小数据量情况下

select gid,fariqi,neibuyonghu,reader,title from Tgongwen order by fariqi

用时：12936毫秒  

select gid,fariqi,neibuyonghu,reader,title from Tgongwen order by gid

用时：18843毫秒  

用聚合索引比用一般的主键作order by时，速度快了3/10。事实上，如果数据量很小的话，用聚集索引作为排序列要比使用非聚集索引速度快得明显的多；而数据量如果很大的话，如10万以上，则二者的速度差别不明显。

6.日期列不会因为有分秒的输入而减慢查询速度
  下面的例子中，共有100万条数据，2004年1月1日以后的数据有50万条，但只有两个不同的日期，日期精确到日；之前有数据50万条，有5000个不同的日期，日期精确到秒。

select gid,fariqi,neibuyonghu,reader,title from Tgongwen where fariqi>"2004-1-1" order by fariqi

用时：6390毫秒

select gid,fariqi,neibuyonghu,reader,title from Tgongwen where fariqi<"2004-1-1" order by fariqi

用时：6453毫秒

MySQL索引实现

  在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的，以下为MyISAM和InnoDB两个存储引擎的索引实现方式。

MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：

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

同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

MyISAM的索引方式也叫做“非聚集索引”，之所以这么称呼是为了与InnoDB的聚集索引区分。

InnoDB索引实现

InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，下图为定义在Col3上的一个辅助索引：

这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

参考：
http://www.cnblogs.com/aspnethot/articles/1504082.html
http://blog.codinglabs.org/articles/theory-of-mysql-index.html
http://www.cnblogs.com/rush/archive/2012/04/22/2465683.html#lb3