索引的类别包括-

主键索引( PRIMARY ):数据列不允许重复，不允许为NULL.一个表只能有一个主键。

唯一索引( UNIQUE ):数据列不允许重复，允许为NULL值，一个表允许多个列创建唯一索引。

普通索引( INDEX ):基本的索引类型，没有唯一性的限制，允许为NULL值。

全文索引（FULLTEXT 索引在 MySQL 5.6 版本之后支持 InnoDB，而之前的版本只支持 MyISAM 表。）

等

索引的数据结构包括-

B-Tree索引

MyISAM和InnoDB都支持这种索引，因此说它是应用最广泛，最常用的一种索引方式，但是不同的存储引擎在具体实现时会稍有不同，比如MyISAM会使用前缀压缩的方式对索引进行压缩，InnoDB则不会。

B-Tree只是底层的算法实现，唯一索引，主键索引，普通索引都是基于B-Tree索引算法的，只不过又有各自的特点。

这篇文章对于B-Tree有着比较好视图理解-https://segmentfault.com/a/1190000010264071

B-Tree的缺点

即索引失效的原因-http://www.jianshu.com/p/d5b2f645d657

InnoDB索引和MyISAM索引的区别：

一是主索引的区别，InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。

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

二是辅助索引的区别：InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。

这篇文章详细讲授了B-Tree的实现原理和在各个引擎的工作情况-http://blog.csdn.net/bigtree_3721/article/details/73650601

这篇文章很好的对B-Tree和B+Tree做了分布的解释说明-https://mp.weixin.qq.com/s/U_GcVrvZQWPlK4X6Afy4-Q

在和我朋友打电话过程中有不少朋友认为所谓B-Tree就是二叉树或者红黑树

二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

哈希索引

哈希索引的实现就比较简单了，它是基于哈希表来实现的，对于要索引的列，存储引擎会计算出一一对应的哈希码，然后把哈希码存放在哈希表中作为key，value值是指向该行数据的指针。

优势:

只需比对哈希值，因此速度非常快，性能优势明显；

限制:

不支持任何范围查询，比如where price > 150，因为是基于哈希计算，支持等值比较。

哈希表是无序存储的，因此索引数据无法用于排序。

主流存储引擎不支持该类型，比如MyISAM和InnoDB。哈希索引只有Memory, NDB两种引擎支持。值得一提的是，memory引擎是支持非唯一哈希索引的。在数据库世界里是比较与众不同，如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中。

如果哈希冲突很多的话，一些索引维护操作的代价也很高，如：如果在某个选择性很低的列上建立哈希索引（即很多重复值的列），那么当从表中删除一行时，存储引擎需要遍历对应哈希值的链表中的每一行，找到并删除对应的引用，冲突越多，代价越大。

哈希索引是一种非常快的等值查找方法（注意：必须是等值，哈希索引对非等值查找方法无能为力），它查找的时间复杂度为常量，InnoDB采用自适用哈希索引技术，它会实时监控表上索引的使用情况，如果认为建立哈希索引可以提高查询效率，则自动在内存中的“自适应哈希索引缓冲区”（详见《MySQL - 浅谈InnoDB体系架构》中内存构造）建立哈希索引。

innodb引擎有一个特殊的功能叫做自适应哈希索引，当innodb注意到某些索引值被使用的非常频繁时，它会在内存中基于btree索引之上再创建一个哈希索引，这样就让btree索引也具有哈希索引的一些优点，比如：快速的哈希查找，这是一个全自动的，内部的行为，用户无法控制或者配置，不过如果有必要，可以选择关闭这个功能（innodb_adaptive_hash_index=OFF，默认为ON）。

空间数据索引(R-Tree)

空间索引可用于地理数据存储，它需要GIS相关函数的支持，由于MySQL的GIS支持并不完善，所以该索引方式在MySQL中很少有人使用。

全文索引

类似lucene分词的分词实现方式,如果使用中文的话有一个Mysql的中文分词插件Mysqlcft.

顺便记录一下几个引擎

InnoDB 支持事务，支持行级别锁定，支持 B-tree、Full-text 等索引，不支持 Hash 索引；

MyISAM 不支持事务，支持表级别锁定，支持 B-tree、Full-text 等索引，不支持 Hash 索引；

Memory 不支持事务，支持表级别锁定，支持 B-tree、Hash 等索引，不支持 Full-text 索引；

NDB 支持事务，支持行级别锁定，支持 Hash 索引，不支持 B-tree、Full-text 等索引；

Archive 不支持事务，支持表级别锁定，不支持 B-tree、Hash、Full-text 等索引；