数据库索引
概述
索引是辅助数据库存储引擎高效获取数据的数据结构。索引是在存储引擎中实现的，每种存储引擎的索引都不完全相同，并且每种存储引擎也不一定支持所有索引类型。
例如，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 后使用了左模糊匹配
- 复合索引不符合最左匹配原则