什么是索引
索引是一种高效获取数据的存储结构，例：hash、 二叉、 红黑。
若仅仅是 select from table where id=45 , 上面三种算法可以轻易实现，但若是select from table where id<6 , 就不好使了，它们的查找方式就类似于”全表扫描”，因为他们的高度是不可控的(如下图)。B+Tree的高度是可控的，mysql通常是3到5层。注意：B+Tree只在最末端叶子节点存数据，叶子节点是以链表的形势互相指向的。
Myisam引擎(非聚集索引)
若以这个引擎创建数据库表Create table user （…..），它实际是生成三个文件：
user.myi 索引文件
user.myd数据文件
user.frm数据结构类型。
如下图：当我们执行 select * from user where id = 1的时候，它的执行流程。
(1)查看该表的myi文件有没有以id为索引的索引树。
(2)根据这个id索引找到叶子节点的id值，从而得到它里面的数据地址。(叶子节点存的是索引和数据地址)。
(3)根据数据地址去myd文件里面找到对应的数据返回出来。
这里设表一共有三列，假设我们以Col1为主键，上图是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：
同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分
Innodb引擎(聚集索引)
若以这个引擎创建数据库表Create table user （…..），它实际是生成两个文件：
user.ibd 索引文件
user.frm 数据结构类型
因为innodb引擎创建表默认就是以主键为索引，所以不需要myi文件。
下图为innodb表的结构图：很显然它与myisam最大的区别是将整条数据存在叶子节点，而不是地址。(叶子节点存的是主键索引和数据信息)
若此时，你在其他列创建索引例如name，它就会另外创建一个以name为索引的索引树，(叶子节点存的是索引和主键索引)。
你在执行select * from user where name = ‘小王’，他的执行过程如下：
(1)找到name索引树
(2)根据name的值找到该树下叶子的name索引和主键值
(3)用主键值去主键索引树去叶子节点到该条数据信息
加了索引之后能够大幅度的提高查询速度，但是索引也不是越多越好，一方面它会占用存储空间，另一方面它会使得写操作变得很慢。通常我们对查询次数比较频繁，值比较多的列才建索引。
例如： select * from user where sex = “女”， 这个就不需要建立索引，因为性别一共就两个值，查询本身就是比较快的。
select * from user where user_id = 1995, 这个就需要建立索引, 因为user_id的值是非常多的。
InnoDB与MyiSam的区别
InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶结点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶结点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，图11为定义在Col3上的一个辅助索引：
这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
B+Tree的特性
(1)由图能看出，单节点能存储更多数据，使得磁盘IO次数更少。
(2)叶子节点形成有序链表，便于执行范围操作。
(3)聚集索引中，叶子节点的data直接包含数据；非聚集索引中，叶子节点存储数据地址的指针。
带有顺序访问指针的B+Tree
一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。
上图所示，在B+Tree的每个叶子结点增加一个指向相邻叶子结点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着结点和指针顺序遍历就可以一次性访问到所有数据结点，极大提到了区间查询效率。
这一节对B-Tree和B+Tree进行了一个简单的介绍，下一节结合存储器存取原理介绍为什么目前B+Tree是数据库系统实现索引的首选数据结构。
为什么使用B-Tree（B+Tree）
上文说过，红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构，这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面介绍磁盘存取原理，然后再结合这些原理分析B-/+Tree作为索引的效率。
磁盘存取原理
上文说过，索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作。与主存不同，磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的。
当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。
局部性原理与磁盘预读
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：
当一个数据被用到时，其附近的数据也通常会马上被使用。
程序运行期间所需要的数据通常比较集中。
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。
预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。
