索引是数据库对应用程序的设计和开发非常中要的一个方面。如果索引太多，应用程序的性能可能会受到影响。而索引太少，对查询性能有会产生影响。所以要找到一个合适的平衡点，这对应用程序的性能是至关重要的。
1. 为什么需要索引
数据在磁盘上是以块的形式存储的。为确保对磁盘操作的原子性，访问数据的时候会一并访问所有数据块。磁盘上的这些数据块与链表类似，即它们都包含一个数据段和一个指针，指针指向下一个节点（数据块）的内存地址，而且它们都不需要连续存储（即逻辑上相邻的数据块在物理上可以相隔很远）。
鉴于很多记录只能做到按一个字段排序，所以要查询某个未经排序的字段，就需要使用线性查找，即要访问N/2个数据块，其中N指的是一个表所涵盖的所有数据块。如果该字段是非键字段（也就是说，不包含唯一值），那么就要搜索整个表空间，即要访问全部N个数据块。
然而，对于经过排序的字段，可以使用二分查找，因此只要访问log2 N个数据块。同样，对于已经排过序的非键字段，只要找到更大的值，也就不用再搜索表中的其他数据块了。这样一来，性能就会有实质性的提升。
2. 什么是索引
索引是对记录按照一个或多个字段进行排序的一种方式。对表中的某个字段建立索引会创建另一种数据结构，其中保存着字段的值，每个值又指向与它相关的记录。即这种种数据结构按照一定顺序建立了列值与记录行之间的对应关系。这种索引的数据结构是经过排序的，因而可以对其执行二分查找。
3. 索引的原理
字段名 数据类型 在磁盘上的大小
id(Primary key) int 4字节
name char(20) 20字节
age tinyint 1字节
我们通过建立上面的表来比较在数据库中包含大数据量的情况下，分析两种查询情况:
1、查询经过排序的字段id
2、查询未经过排序的字段name
分析示例一
假设数据库表中有R = 1000万条记录，mysql数据库在磁盘上为每条记录分配的大小为B = 4 + 20 + 1 = 25字节，这样我们就可以计算这个表分块因数bfr = (B/R) = 1024/25 = 40， 也就是说，磁盘上的单位数据块上保存着40条记录，那么我们就可以得出这整个表所需要的数据块就是N = (R/bfr) = 10000000/40 = 250000。
1、使用id字段查找时的情况： 由于id字段是线性的(作为表的主键)，需要访问 N / 2 = 125000个数据块才能找到目标，但是这个字段是经过排序的，所以可以使用二分查找的方法，所以这样平均的访问log2 250000 = 17.9 = 18 个块，这很显然，是对数据库
2、使用name字段查找的情况：
由于name字段是为经过排序的，因此不可能使用二分查找，并且这个字段的值也不是唯一的，所以数据库要从表的开头查找到尾，即要访问 N = 250000个数据块。
所以，通过这个比较得知，包含索引的查询效率是更高的，那数据库性能就可以得到很好的提升。
如果一条索引记录只包含索引字段和一个指向原始记录的指针，那么这条记录肯定要比他所指向的包含更多的记录要更小，也就是所，索引本身占用的磁盘空间比原来的表更小，因此需要遍历的数据块也不搜索原来的表更少。如果下，以name字段建立索引的表模式:
字段名 数据类型 在磁盘上的大小
name char(20) 20字节
记录指针 指针类型 4字节
分析示例二
数据库中有 r = 1000 000条记录，每条索引记录要占用 R = 24字节的空间大小，那么同样适用默认的数据块大小 B = 1024字节。 那么索引的分块因数就是bfr = (B/R) = 1024 / 24 = 5。最终建立索引所生成的表的大小为 N = (r / bfr) = 1000000 /5 = 2500000个数据块。
现在，再搜索name字段就可以使用索引来提高性能，对索引使用二分查找，需要分为log2 2500000 = 18 个数据块，在加上为找到实际记录的地址还要访问一个数据块，总共要访问18 + 1 = 19 个数据块，这个与之前的250000 个数据块相比，是在是差别太大了。
4. 什么时候用索引
创建索引要额外占用磁盘空间（比如，上面例子中要额外占用277 778个数据块），建立的索引太多可能导致磁盘空间不足。因此，在建立索引时，一定要慎重选择正确的字段。
由于索引只能提高搜索记录中某个匹配字段的速度，因此在执行插入和删除操作的情况下，仅为输出结果而为字段建立索引，就纯粹是浪费磁盘空间和处理时间了；这种情况下不用建立索引。另外，由于二分查找的原因，数据的基数性（cardinality）或唯一性也非常重要。对基数性为2的字段建立索引，会将数据一分为二，而对基数性为1000的字段，则同样会返回大约1000条记录。在这么低的基数性下，索引的效率将减低至线性查找的水平，而查询优化器会在基数性小于记录数的30%时放弃索引，实际上等于索引纯粹只会浪费空间。
查询优化器的原理
查询优化中最核心的问题就是精确估算不同查询计划的成本。优化器在估算查询计划的成本时，会使用一个数学模型，该模型又依赖于对每个查询计划中涉及的最大数据量的基数性（或者叫重数）的估算。而对基数性的估算又依赖于对查询中谓词选择因数（selection factor of predicates）的估算。过去，数据库系统在估算选择性时，要使用每个字段中值的分布情况的详尽统计信息，比如直方图。这种技术对于估算孤立谓词的选择符效果很好。然而，很多查询的谓词是相互关联的，例如 select count(*) from R where R.make=’Honda’ and R.model=’Accord’。查询谓词经常会高度关联（比如，model=’Accord’的前提条件是make=’Honda’），而估计这种关联的选择性非常困难。查询优化器之所以会选择低劣的查询计划，一方面是因为对基数性估算不准，另一方面就是因为遗漏了很多关联性。而这也是为什么数据库管理员应该经常更新数据库统计信息（特别是在重要的数据加载和卸载之后）的原因。（译自维基百科：http://en.wikipedia.org/wiki/Query_optimizer。）
5. 索引优缺点
优点
- 快速存取数据，减少磁盘的I/O操作
- 保证数据记录的唯一性
- 实现表与表之间的参照完整性
- 在是用order by、group by子句进行数据检索是。利用索引可以减少排序和分组时间
缺点
- 索引创建太多查询的效率反而降低
- 索引创建太多导致数据库和系统资源浪费太多，性能下降。
