索引实现原理
为什么需要使用索引
MySQL官方对索引的定义为：索引（Index）是帮助 MySQL 高效获取数据的数据结构。
白话文：索引就像书的目录一样可以非常快速的定位到书的页码。
如果向mysql发出一条sql语句请求，查询的字段没有创建索引的话，可能会导致全表扫描，这样的话查询效率非常低。
索引采用的数据结构
Hash算法
index=Hash(key)
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
优点:查找可以直接根据key访问
缺点: 不能进行范围查找
平衡二叉树
平衡二叉查找树，又称 AVL树。它除了具备二叉查找树的基本特征之外，还具有一个非常重要的特点：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值（平衡因子 ）不超过1。也就是说AVL树每个节点的平衡因子只可能是-1、0和1（左子树高度减去右子树高度）。
优点:平衡二叉树算法基本与二叉查找树查询相同，效率比较高
缺点:插入操作需要旋转，支持范围查询
红黑树
它根据节点的生成规则，构造出一颗自平衡的二叉树。节点的生成规则必须满足：
根节点必须是黑色
它的节点必须是红色或者黑色
每个叶子结点都是黑色的空节点
每个红色节点的两个子节点必须是黑色
从任意一个节点到叶子结点 所有路径必须包含相同数目的黑色节点。
因为有了这些规则的限制才保证从根节点到叶子结点的最长路径不会超过最短路径的2倍，也就是搜索数据时的匹配次数降低。
B树
它可以说是红黑树的一个变种，是一颗自平衡的多叉树。结点不再存储一个数据项，而是有多个数据项，数据项中包含key和value，key即数据列中的数值，value 可以是这行数据的地址，也可以是整行数据。如下图：
B+树
B+树在B树之上又做了一层优化，非叶子节点也是存储多个数据项，但是数据项中只包含了key,即索引列的数值，也就是说非叶子节点它只做索引，最终的数据都是落在叶子节点中。如下图：
MySQL为何不采用B树而采用B+树呢？正是因为B+树的非叶子节点存储的数据项只包含了key，在数据量多的情况下读取一个节点，那么就意味着读取的数据项非常多。构造出来的B+树高度相比B树更低，所以I/O的次数也就越少。由于B树存放的是key和value，当数据量非常多的情况下，读取一个节点包含的数据项不宜多。
MyISAM与InnoDB的索引实现
MyISAM索引实现
MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址
主键索引
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM主键索引的原理图：
这里设表一共有三列，假设我们以Col1为主键，上图是一个MyISAM表的主键索引示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。
辅助索引
在MyISAM中，主键索引和辅助索引在结构上没有任何区别，只是主键索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：
同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
InnoDB索引实现
InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同
主键索引
MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
上图是InnoDB主键索引的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
辅助索引
InnoDB的所有辅助索引都引用主键作为data域。例如，下图为定义在Col3上的一个辅助索引：
InnoDB 表是基于聚簇索引建立的。因此InnoDB的索引能提供一种非常快速的主键查找性能。不过，它的辅助索引也会包含主键列，所以，如果主键定义的比较大，其他索引也将很大。如果想在表上定义、很多索引，则争取尽量把主键定义得小一些。InnoDB 不会压缩索引。
MyISAM与InnoDB的索引区别
主键索引
InnoDB的数据文件本身就是索引文件，而MyISAM的索引文件和数据文件是分开的。
辅助索引
InnoDB的辅助索引data域存储相应记录主键的值而不是地址，而MyISAM的辅助索引和主索引没有多大区别。
聚集索引和非聚集索引区别
聚集索引
聚集索引表记录的排列顺序和索引的排列顺序一致，所以查询效率快，只要找到第一个索引值记录，其余就连续性的记录在物理也一样连续存放。聚集索引对应的缺点就是修改慢，因为为了保证表中记录的物理和索引顺序一致，在记录插入的时候，会对数据页重新排序。
聚集索引类似于新华字典中用拼音去查找汉字，拼音检索表于书记顺序都是按照a~z排列的，就像相同的逻辑顺序于物理顺序一样，当你需要查找a,ai两个读音的字，或是想一次寻找多个傻(sha)的同音字时，也许向后翻几页，或紧接着下一行就得到结果了。
非聚集索引
非聚集索引指定了表中记录的逻辑顺序，但是记录的物理和索引不一定一致，两种索引都采用B+树结构，非聚集索引的叶子层并不和实际数据页相重叠，而采用叶子层包含一个指向表中的记录在数据页中的指针方式。非聚集索引层次多，不会造成数据重排。
非聚集索引类似在新华字典上通过偏旁部首来查询汉字，检索表也许是按照横、竖、撇来排列的，但是由于正文中是a~z的拼音顺序，所以就类似于逻辑地址于物理地址的不对应。同时适用的情况就在于分组，大数目的不同值，频繁更新的列中，这些情况即不适合聚集索引。
根本区别
聚集索引和非聚集索引的根本区别是表记录的排列顺序和与索引的排列顺序是否一致。