什么是索引？
索引是一种用于快速查询和检索数据的数据结构，其本质可以看成是一种排序好的数据结构。索引是存储引擎实现的，不同索引的存储引擎不一定相同。
优点：
- 查询效率高，磁盘I/O次数低（B+树IO次数只有3~4次）；
- 每行数据索引唯一；
- 联合、分组、排序查询效率高；
缺点：
- 创建索引耗费时间；
- 维护索引耗费时间，每次增删改时要维护索引；
- 索引占用磁盘空间，索引文件可能比数据文件更占空间。例如innoDB的1个聚簇索引和多个非聚簇索引加起来肯定比原数据文件占的内存多。索引存在磁盘，可以分段加载数据页到内层。
- 联合索引查询时，没有遵循最左前缀原则将会导致索引不起作用，从而出现严重的性能问题。
索引的底层数据结构
Hash表
哈希表是键值对的集合，通过键(key)即可快速取出对应的值(value)，因此哈希表可以快速检索数据（接近 O（1））。
为何能够通过 key 快速取出 value 呢？ 原因在于 哈希算法（也叫散列算法）。通过哈希算法，我们可以快速找到 key 对应的 index，找到了 index 也就找到了对应的 value。
1. hash = hashfunc(key) 2. index = hash % array_size
但是！哈希算法有个 Hash 冲突 问题，也就是说多个不同的 key 最后得到的 index 相同。通常情况下，我们常用的解决办法是 链地址法。链地址法就是将哈希冲突数据存放在链表中。就比如 JDK1.8 之前 HashMap 就是通过链地址法来解决哈希冲突的。不过，JDK1.8 以后HashMap为了减少链表过长的时候搜索时间过长引入了红黑树。
二叉树
当二叉查找树是平衡的时候，也就是树的每个节点的左右子树深度相差不超过 1 的时候，查询的时间复杂度为 O(log2(N))，具有比较高的效率。然而，当二叉查找树不平衡时，例如在最坏情况下（有序插入节点），树会退化成线性链表（也被称为斜树），导致查询效率急剧下降，时间复杂退化为 O（N）。
红黑树
红黑树是一种自平衡二叉查找树，通过在插入和删除节点时进行颜色变换和旋转操作，使得树始终保持平衡状态。但是索引树层数会很高，查询次数和IO不如B+树
B树
多路平衡查找树，非叶节点也存数据，左小右大，一般层数比B+树深，查询速度和IO次数也就不如B+树；可以分段加载节点数据
B+树
多路平衡查找树，非叶节点存目录，叶节点存记录。查询效率更高（比B树矮胖，层数很难超过4层），IO次数也少（很难超过3次），更稳定，范围查询效率高（因为叶节点之间由双向链表链接）。可以分段加载节点数据。
索引类型
主键索引
一种特殊的唯一索引，不允许有空值。一般是在建表的时候同时创建主键索引。
普通索引
最基本的索引，它没有任何限制。仅加速查询
唯一索引
唯一索引列的值必须唯一，但允许有空值。如果是组合索引，则列值的组合必须唯一。可以在创建表的时候指定，也可以修改表结构
覆盖索引
一个索引包含（或者说覆盖）所有需要查询的字段的值。
联合索引
多列值组成一个索引，专门用于组合搜索，其效率大于索引合并。
示例：
ALTER TABLE
table_nameADD INDEX index_name(column1,column2,column3)
全文索引
全文索引（也称全文检索）是目前搜索引擎使用的一种关键技术。它能够利用分词技术等多种算法智能分析出文本文字中关键字词的频率及重要性，然后按照一定的算法规则智能地筛选出我们想要的搜索结果。一般不会使用，效率较低，通常使用搜索引擎如 ElasticSearch 代替。
