# 索引

1. 索引概述
2. 索引结构
3. 索引分类
4. 索引语法
5. SQL 性能分析
6. 索引使用
7. 索引设计原则

## 1. 索引概述

索引（index）帮助 MySQL 高效获取数据的数据结构（有序）。

索引的优缺点

| 优点                                                          | 缺点                                                                 |
| ------------------------------------------------------------- | -------------------------------------------------------------------- |
| 提高数据检索的效率，降低数据库的 IO 成本                      | 索引列也要占用空间                                                   |
| 通过索引列对数据进行排序，降低数据排序的成本，降低 CPU 的消耗 | 索引大大提高查询效率，同时却降低更新表的速度（insert,update,delete） |

## 2. 索引结构

MySQL 的索引是在存储引擎层实现的，不同的存储引擎有不同的结构

主要包含以下几种

| 索引结构    | 描述                                                                         |
| ----------- | ---------------------------------------------------------------------------- |
| B+Tree 索引 | B+树索引是最常见的索引类型，大部分引擎都支持                                 |
| Hash 索引   | 底层数据结构是用哈希表实现的，只有精确匹配索引列的查询才有效，不支持范围查询 |
| R-tree      | 空间索引是 MyISAM 引擎的特殊索引类型，主要用于地理空间数据类型，通常很少使用 |
| Full-text   | 全文索引是一种通过倒排索引，快速匹配文档的方式，类似 Lucene,Solr,ES          |

各数据库对不同类型索引的支持情况

| 索引        | innoDB       | MyISAM | Memory |
| ----------- | ------------ | ------ | ------ |
| B+Tree 索引 | 支持         | 支持   | 支持   |
| Hash 索引   | 不支持       | 不支持 | 支持   |
| R-tree      | 不支持       | 支持   | 不支持 |
| Full-text   | 5.6 之后支持 | 支持   | 不支持 |

算法可视化演示：[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html](https://www.cs.usfca.edu/~galles/visualization/Algorithms.html)

![](img/index.png)

### 2.1、二叉树

二叉树的缺点：

1. 顺序插入时，会行成一个链表，查询性能大大降低
2. 大数据量情况下，层级较深，检索速度慢

![](img/binary-tree.png)

### 2.2、红黑树

红黑树:

1. 大数据量的情况下，层级较深，检索数独慢

![](img/red-black-tree.png)

### 2.3、 B Tree

B Tree（多路平衡查找树）

以一颗最大度数（max-degree）为5（5阶）的B-Tree为例（每个节点最多存储4个Key,5个指针）

树的度数指的是一个节点的子节点个数

![](img/B-Tree.png)


### 2.4、 B+Tree

以一颗最大度数（max-degree）为 4（4 阶）的 B+Tree 为例

B Tree 和 B+Tree 的区别

1. 所有的数据都会出现在叶子节点
2. 叶子结点行成一个单向链表

![](img/B+Tree.png)

### 2.5、MySQL 索引

MySQL 索引数据结构对经典的 B+Tree 进行了优化，在原有 B+Tree 的基础之上，增加了一个指向相邻叶子节点的链表指针，就形成了带有顺序指针的 B+Tree，提高了区间访问的性能

![](img/mysql-b+tree.png)


### 2.6、Hash

哈希索引就是采用一定的hash算法，将键值换算成新的hash值，映射到对应的槽位上，然后存储在hash表中

如果两个或多个键值，映射到一个相同的槽位上，他们就产生了hash冲突（哈希碰撞），可以通过链表来解决

![](img/hash.png)

Hash索引的特点:

1. hash索引只能用于等值比较（=，in），不支持范围查询（between, >, <）
2. 无法利用索引完成排序操作
3. 查询效率高，通常只需要一次检索就可以，效率通常要高于B+Tree索引

支持Hash索引的存储引擎：Memory

InnoDB中具有自适应hash功能