索引是数据库用于快速定位行的数据结构
? 索引是一种数据结构，它往往以文件形式存储，读取它需要进行I/O操作，而I/O的效率远小于内存读取，所以需要尽量少进行I/O，提升效率。
? 在磁盘读取时，根据局部性原理（即一个数据被用到时，其附近的数据常常也会被用到）计算机会进行磁盘预读。预读的大小时页的整数倍。页时计算机管理存储器的逻辑块，操作系统将主存和磁盘分割成大小一致的块，一块便是一页（大小通常为4K）。
? 设计者将树的结点大小设置成一页，根据预读原理，一次I/O操作读取一个结点。B树的特征在于，每个结点有多个key，相较于红黑树、二叉搜索树，树的高度更低。减少计算机I/O操作的次数，提升效率。
? B+树时B-树的改进版本，b+树仅在叶结点保存data的指针，这意味着一页大小的非页结点可以包含更多的key，相同keys的情况下，1)B+树较B-树生成的高度更低。另外，由于B+树的叶结点包含所有key值，并连接在一起，2)在范围查询时，遍历结点更加简洁。最后，由于所有data存储在叶结点，3)每次查询I/O操作次数是稳定的。
在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的 。
MyISAM使用B+树实现索引，叶结点的data存放的数据记录的地址。
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。MyISAM的主键索引与辅助索引的结构是相似的。因此，MyISAM可以允许表没有主键 。
InnoDB也使用B+Tree作为索引结构 。 在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
辅助索引叶结点存放的就是主键，利用辅助索引，需要进行两遍索引，一编辅助索引找到主键key值，根据key值在主索引中找到data。事实上，在InnoDB中二级索引建立时，会自动加入主键。这被称为索引扩展。例如主键为（a，b），在c上建立二级索引时，会自动扩展成（c,a,b）的联合索引。
用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
哈希索引：维护一个哈希表存储data指针。支持engine：Memory
优点：快速定位行 缺点：指针不代表数据，最终还是读取行；hash值无法用来排序；不支持部分索引，在（A，B）上建立哈希索引，查询只有列A计算hash值；只支持等值查询；
全文索引：搜索关键词，使用 MATCH AGAINST 而非 WHERE
R-tree空间数据索引主要针对GIS数据。支持engine：MyISAM
原文：https://www.cnblogs.com/DOTA-bing/p/13067626.html