本篇主要介绍数据库MySQL的索引实现原理，包括B+ Tree的原理，顺带提到了数据库的常用引擎。
数据库引擎
我们常见的数据库引擎就是InnoDB，还有另外一个常见一个引擎叫做MyISAM，这里着重介绍着两个引擎，执行show engines，可见MySQL所有的引擎如下：
InnoDB
InnoDB采用行级锁，不会记录表中的数据个数，支持外键，高并发下使用事务的首选引擎，也是5.5之后MySQL的默认引擎（之前采用MyISAM），可以通过bin-log日志回滚数据，所以它比较适合处理数据量大的数据。
PS：InnoDB最初不支持全文索引，在MySQL 5.6版本后添加了支持。
MyISAM
MyISAM跟InnoDB截然相反，它采用表锁，记录了表的条目数，SELECT COUNT可以直接查看表中数据个数，支持FULLTEXT索引，不支持外键和事务，不能进行数据恢复操作，他比较适合频繁插入的数据，或是读操作远大于写操作时。
MySQL引擎的索引分类
MySQL数据库索引基本上分为：单一索引和组合索引，其中单一索引又包括：主键索引、普通索引、唯一索引、全文索引。索引的类型跟数据库的引擎相关联，其中InnoDB实用的方式叫做聚簇索引（也被称为聚集索引），MyISAM使用的叫做非聚簇索引。在下面我将直接用数据库引擎区别索引类型。
聚集索引、非聚集索引与覆盖索引
聚集索引是指数据存储的物理位置与逻辑位置是一致的，这里是指主键的存储，因为数据顺序有且只能有一个，所以数据库中若是有聚集索引定义的都是主键，主键外其余的索引后统称辅助索引。
Innodb引擎的数据库存储数据共有两个文件，包含表的定义文件和数据/索引文件，其中数据是依赖于主键存在于主键索引的Tree结构内的，而其辅助索引中只存储了数据对应的主键值和索引（此处指涉及多列的联合索引）涉及到的字段值，这种情况被称作覆盖索引，主键的索引树就被称为聚集索引，他体现了主键索引的特殊性。当我们通过辅助索引在Innodb引擎中查找数据并且涉及了其他不包含在本索引内的非主键字段时，经历了：
遍历索引，查找对应的Key（主键）-> 遍历主键索引，找到对应的数据内容
对应的MyISAM采用的是非聚集索引，MyISAM引擎对应了三个文件，它将索引文件和数据文件拆开存储，所有索引级别是相同的，每次命中都是得到数据在数据文件中的指针，直接映射地址，所以当我们通过辅助索引在MyISAM中查找数据时，经历了：
遍历索引，查找对应的数据指针 -> 根据指针在数据文件中提取数据
我所理解的聚集索引只是指代主键存储的策略，并不能说InnoDB的主键采用了聚集索引，其余索引采用了非聚集索引，而应该是InnoDB采用了聚集索引，MyISAM采用了非聚集索引。
引擎特性&索引存储方式
知道了数据存储的特性，我们也就知道了引擎为什么会具有某些特性。比如InnoDB中因为采用了聚集索引，所以主键一般使用自增id，这种情况可以直接统计出COUNT(*)，而对应的MyISAM直接存储了每个表对应的COUNT(*)。InnoDB可以上行级锁也是由索引结构决定的，在我们进行更新操作时可以很轻易对连续的范围内数据上锁，因为数据在索引内是逻辑连续的，但是MyISAM数据是独立存储的，为了保证安全性只能使用表级锁。
优劣
既然聚集索引查询数据需要经历两次树的搜索，而且在插入数据时既然要考虑顺序，肯定也会影响效率，那为什么不干脆的一律采用非聚集索引呢？
首先我们可以很容易的总结出非聚集索引的优点：
执行辅助索引单条查找快，只需直接搜索对应的索引树就能找到数据；
插入数据更快。因为不用考虑数据的存放，我们只需组织索引的位置而不必在意数据的存储，而聚集索引需要组织数据的结构顺序，尤其当插入中间的数据时，可能要移动其余很多数据；
更节省存储空间。我们只需要在辅助索引的结构中存放内存地址，但是聚集索引可能会存储一串较长的主键值和多字段索引对应的字段数据，主键越长、索引数量越多、联合索引字段越多，二者差距也就越大。
但是同时，聚集索引也有他的优势：
查询范围内的相关数据更快，例如10-20，由于在聚集索引中数据是连续存储的，我们只需找到10的位置，就可以直接取到后面的数据；
存储在数据库中的数据能够按照主键自动保证排序，非聚集索引则不行，在需要对主键列排序的情境下，聚集索引的效率高出很多。
当某列数据发生更新时，InnoDB的辅助索引文件中其他列无需修改，因为是指向了主键，但是MyISAM可能需要修改所有的索引指向。
由于非聚集索引的存储特性，决定了在并发更新时，只能使用表级锁，因为没法知道行级锁应该上锁的范围，所以在写入频繁并发很高的系统中不适合使用MyISAM。
简单总结就是：
一般情况下，不考虑并发的话，辅助索引查询非主键的不包含在索引内的字段使用MyISAM引擎更快，包含在索引内的字段辅助索引范围查找和主键的查找都是聚集索引更快。聚集索引的辅助索引建立通常需要更多的存储空间来存放主键值，并且更新和插入中间值的主键性能较低。在并发较高的写入操作中，使用InnoDB更高效。
索引的实现原理
MySQL最常见的引擎Innodb和MyISAM使用的是基于B+Tree的索引。
B Tree
B Tree是二叉树的进阶版，是n-1 - n树（每个节点存储n-1个键值，则分出n路，n被做是树的阶数），如下图是按照字母排序定义了一个B Tree，根据所查数据向下搜索，直到命中。
所有的键值都直接存在节点内，节点关键字不允许重复。以图中D、G节点为例，三路分别满足的条件是 N<D; D<N<G ; N>G
B+ Tree
B+ Tree近似于B Tree但又不同，首先B+ Tree的键值不存在中间节点而只存储于叶子节点中，并且叶子结点关键字可以重复，同时B+Tree的相邻叶节点有连接，多路分出的规则也有所不同，以下是一个B+ Tree示意：
以图中5、10、20节点为例，三路分别满足的条件是 N>=5; 10<=N<20 ; N>=20，是左封闭的结构。
索引存储结构选择
影响一个索引效率的因素根本上讲就是I/O次数，不考虑外部因素，则应采用树结构存储索引列表，在此基础上，应尽可能的保证树的深度足够小，每次查询的时间复杂度最低。
之所以选择了B+ Tree而非B Tree，其一是B+Tree的平均效率更高且速度稳定，因为所有关键字均存储在叶子节点中，所以非叶节点看可以记录更长的关键字，平均深度相比B Tree要小，同时Data域是相连的，对于经常需要范围查找的关系型数据库可以减少大量的I/O次数，同时也具有它需要的叶节点可重复的特性。
tips
不要使用过长的主键索引
在InnoDB中，因为是聚集索引，其余索引中存储的是主键值，索引如果我们将主键设定的过于冗长，便会增大索引的存储空间，对应地，建议使用自增id作为主键。