innodb的数据页是按B＋树进行索引的（中间节点叫做索引页），在查找具体的行时，先通过B+树找到对应的页，然后读入页到内存，再在内存中进行查找。一般使用B+树进行数据库索引时，扇出数是很高的，因为要保证B+树的高度受控制，使每次查询不至于太多次磁盘IO操作（实际上，非叶子节点索引往往可以全内存存储），同时也使节点分裂合并操作（需要磁盘访问）不要太频繁。

 

每张表按主键唯一构造的一个索引，其叶子节点称为数据页，存放行纪录数据，叶子节点通过双向链表连接。

聚集索引使是引擎自产生的，也是查询优化器优先使用的索引结构。

可以有多个，用于主键外字段的查询优化。也是B+树组织，差别是叶子节点的每个索引只包含key（非主键）到行数据所在聚集索引页的映射（实际不可能存聚集索引页的位置，存放的是主键），该映射被称为书签（bookmark）。辅助索引是对聚集索引的索引。

 

需要说明的是，聚集索引结构（索引组织表）不是数据库必须的。比如，MS SQL server就有一种称为堆表的表类型（类似于MyISAM存储引擎），行数据的存储按插入的顺序存放（所以插入速度很快）。主键与非主键的索引都是非聚集的，且其bookmark即为“文件号：页号：槽号”，所以对非聚集的查找，可以直接索引到文件位置，查询速度会更快一些，但其显然不利于更新，因为如果数据位置因为更新发生变化，所有索引都需要更新。但聚集索引对排序和范围查找（range query）支持较好。

所以具体是建堆表还是索引组织表，取决于应用，需要考虑是否需要range query，是否数据需要经常更新等。 it all depends。

 

因为B+树结构主要用于磁盘，页的拆分操作意味着磁盘操作，所以应尽可能减少页的拆分操作，如果通过旋转操作即可插入节点，则不需要拆页（通过rerange数据在临近页中的位置），这也使每个数据或索引页尽量“饱满”。

通常并不需要为查询条件中出现的所有列创建索引，一般对搞选择性的列进行索引，而对低选择性的列如性别建立索引是没有任何意义的。衡量选择性的高低，使用数据的cardinality值/数据条目。innodb可以获得某列索引的cardnality估值。估值采用采样的方式（默认对八个数据页进行统计，可条），而且该值并不会在每次insert或update发生时同时统计，一般在1/6的数据发生修改或者总共的修改次数达到指定阈值时进行（因为时抽样，可能每次都不一样）。

 

什么时候使用索引？

数据库应用分为OLTP和OLAP两种，对OLTP，每次往往只需从数据库中取极少量数据（如根据订单号查询），此时对高选择性的查询条件建立索引很有意义；对OLAP，每次需要访问大量数据，对诸如姓名之类的字段进行索引没什么意义，但如果要作join操作，则对join key进行hash索引还是有用的（但如果使用hash join，则索引不重要），总之要看具体情况，需要理解这些操作的内在机理。

联合索引的实现原理通常就是简单的级联几个字段的值作为索引值，实际排列类似于基数排序，只有第一个字段才是真正有序的。

一种特殊的联合索引叫覆盖索引（covering index），即从辅助索引中就可以得到查询的纪录，而不需要再去聚集索引中查询。着比较适合需要查询的字段叫短的情况。再使用explain显示执行计划时，如果显示using index字样，说明应用了覆盖索引。

覆盖索引的应用示例：http://www.360doc.com/content/12/0401/19/9475597_200038861.shtml

有时后，再进行多字段查询时，也可以先使用覆盖索引缩小查询范围：http://hi.baidu.com/thinkinginlamp/item/1b9aaf09014acce0f45ba6d3