概述
索引是辅助数据库存储引擎高效获取数据的数据结构。索引是在存储引擎中实现的，每种存储引擎的索引都不完全相同，并且每种存储引擎也不一定支持所有索引类型。
例如，MySQL 的 MyISAM 和 InnoDB 存储引擎只支持 B+Tree 索引，而 Memory 存储引擎可以支持 Hash 和 B+Tree 索引。
底层数据结构
B+Tree 索引
B+tree 是基于 Btree 的变体，有点是:
- B+tree 的非叶子结点只包含导航信息，不包含实际的值，因此在内存页中能够存放更多的 key
- B+tree 的所有的叶子结点和相连的节点使用链表相连，因此对整棵树的便利只需要一次线性遍历叶子结点即可
Hash 索引
所有的商业数据库系统都实现了 B+Tree 索引。并且 Oracle 和 PostgreSQL 同时都支持等值查找的哈希索引。
Hash 索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位。但是 Hash 索引本身由于其特殊性也带来了很多限制和弊端，只要有:
- Hash 索引仅仅能满足”=”、”IN”和”<=>”查询，不能使用范围查询
- Hash 索引遇到大量 Hash 值相等的情况时性能并不一定就会比 B+Tree 索引高
- Hash 索引不能利用部分索引键查询，对于组合索引，Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值
LSMTree
LSMTree 是最近几年非常流行的存储引擎，全称是 log-structured merge-tree。其核心思想是充分了利用了磁盘批量的顺序写要远比随机写性能高出很多的特点。
LSMTree 是一种写优化(即牺牲读性能)的数据结构。并且在此设计下，无法对事务有很好的支持。
Hbase、Cassandra、Leveldb 和 RocksDB 等数据库均使用了该索引方式。
MySQL 索引类型
根据叶子节点是否存储完整数据，将索引可以分为:
- 聚簇索引: 完整存储数据
- 二级索引: 也称为辅助索引，只存储索引字段和主键索引
根据字段特性，将索引可以分为:
- 主键索引
- 唯一索引
- 普通索引
- 前缀索引
- 全文索引
根据组成索引的字段个数，将索引可以分为:
- 单一索引
- 复合索引(联合索引)
索引失效原因
- 索引字段进行了隐式转换
- 索引字段使用了表达式计算
- 索引字段使用了函数
- like 后使用了左模糊匹配
- 复合索引不符合最左匹配原则
联合索引最左前缀原理
数据表联合索引情况如下:
|
| Table | Key_name | Seq_in_index | Column_name | Index_type |
|---|---|---|---|---|
| employees | PRIMARY | 1 | emp_no | BTREE |
| employees | PRIMARY | 2 | title | BTREE |
| employees | PRIMARY | 3 | from_date | BTREE |
全列匹配
|
当按照索引中所有列进行精确匹配(“=”或“IN”匹配)时，索引可以被用到。
注意，理论上索引对顺序是敏感的，但是由于 MySQL 的查询优化器会自动调整 where 子句的条件顺序以使用适合的索引，所以即使 where 中的条件顺序与联合索引不一致，索引也可以被用到。
最左前缀匹配
|
当查询条件精确匹配索引的左边连续一个或几个列时，索引可以被用到。
查询条件使用索引中列的精确匹配，但是中间某个条件未提供
|
只用到了索引的第一列，由于 title 不存在而无法和左前缀连接，因此需要对结果进行扫描过滤 from_date。
查询条件没有指定索引第一列
|
由于不是最左前缀，查询无法使用该联合索引。
匹配某列的前缀字符串
|
可以用到该联合索引。
范围查询
|
范围列可以用到索引，但是范围列后面的列无法用到该索引，需要注意与 like 匹配不同，like 后缀 % 的情况，因为 MySQL 5.6 之后，引入索引下推机制，之后列也可以用到该索引。