什么是索引
索引是一种数据结构，用于快速查询和检索数据，本质是一种排序好的数据结构。
底层数据结构有很多类型，常见的有B树、B+树和Hash、红黑树。
在MySQL中，Innodb和MuIsam都使用B+树作为索引结构。
索引的优缺点
优点
- 能够实现快速检索，减少IO次数
- 通过创建唯一性索引，能保证数据库表中每一行数据的唯一性。
缺点
- 创建和维护索引消耗时间。增删改时索引也需要对应的修改，会降低SQL执行效率。
- 消耗空间。（物理文件存储）
底层数据结构
Hash表
哈希表是键值对的集合。
其中使用哈希算法（散列算法）。
哈希算法
一种不可逆的加密算法，在哈希表中，key根据哈希算法得到Index即可快速找到value
Hash冲突
不同的key可能得到相同的Index。
解决方法：链地址法，即将哈希冲突数据存放在链表中。【JDK1.8之前的HashMap使用链地址法，后来引入红黑树】
MySQL中的InnoDB存储引擎不直接支持常规的哈希索引，但存在“自适应哈希索引”。本质上是每一个哈希桶为B+Tree结构，可以存储多个键值对。
缺点
不支持顺序和范围查询。
二叉查找树（BST）
- 左子树所有节点的值均小于根节点的值。
- 右子树所有节点的值均大于根节点的值。
- 左右子树也分别为二叉查找树。
查找性能与平衡程度强相关，在平衡（每个节点左右子树深度差不超过1）时，查询的时间复杂度为O（log2N），最差会退化成O（N）。
AVL树
最早的自平衡二叉查找树。查找、插入、删除的时间复杂度都是logN。
通过旋转操作保持平衡，会有较大的计算开销，降低了写操作的性能。
应用并不多。
红黑树
自平衡二叉查找树，通过颜色变换和旋转实现平衡。
查询效率稍有下降，但增删效率提高。
应用于：TreeMap、TreeSet、JDK1.8的HashMap
B树和B+树
B树全称为多路平衡查找树。
索引类型总结
按数据结构
- BTree：MySQL中默认和最常用的索引类型。
- 哈希索引
- RTree索引：仅支持geometry数据类型，优势在于范围查找。
- 全文索引：一般不会使用。对文本内容进行分词。可用于CHAR、VARCHAR、TEXT
按底层存储方式
根据索引结构和数据是否存放在一起划分。
- 聚簇索引：例如InnoDB中的主键索引
- 非聚簇索引：MyISAM引擎都用非聚簇索引。
按应用维度
- 主键索引：加速查询+列值唯一（不可以有NULL）+表中只有一个
- 普通索引：加速查询
- 唯一索引：加速查询+列值唯一（可以有NULL）
- 覆盖索引：一个索引包含所有需要查询的字段的值。
- 联合索引：多列值组成一个索引。
- 全文索引
主键索引
一张表只能有一个主键，且主键不能为null，不能重复。
二级索引
又称辅助索引/非主键索引。二级索引可以定位主键的位置。
聚簇索引与非聚簇索引
聚簇索引
索引结构与数据一起存放。
优点
- 查询速度快
- 对排序查找和范围查找优化
缺点
- 依赖于有序的数据
- 更新代价大
非聚簇索引
索引结构与数据分开存放。
二级索引即属于非聚簇索引。
叶子节点不一定存放数据的指针。
优点
更新代价小于聚簇索引
缺点
- 依赖于有序的数据（同聚簇索引）
- 可能会二次查询（回表）