MySQL支持诸多存储引擎，而各种存储引擎对索引的支持也各不相同，因此MySQL数据库支持多种索引类型，如BTree索引，哈希索引，全文索引等等。为了避免混乱，本文将只关注于BTree索引，因为这是平常使用MySQL时主要打交道的索引。
关于全文索引，在另一篇文章中有所提及。
什么是索引？
索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是一种数据结构。
为了提高数据库的查询性能，需要找出比顺序查找更好的查询算法。而这些优化的查询算法往往以来特定的数据结构才能实现，比如二叉树。
因此，在数据之外，数据库系统还维护着满足特定查找算法的数据结构。这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构就是索引。
6500328-cf43fbe4084febeb.png
image.png
MySQL中的索引
实际的数据库系统通常使用B（B+）树作为索引的实现。B树是一种矮胖的M叉查找树，是磁盘存储较为缓慢这一缺陷的解决方案，广泛使用在文件系统中。
关于什么是B（B+）树，可以参考另一篇文章。
MySQL中的索引实现
在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的。但是无论是MyISAM还是InnoDB，都采用了B+树的索引实现。
MyISAM索引实现
MyISAM使用B+树作为索引结构，叶结点的data域存放的是数据记录的地址。
这里设表一共有三列，假设我们以Col1为主键，则图8是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：
同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。
--------------------- |
