MySQL 索引

索引是针对查询操作引入的优化手段，可以通过索引来加快查询速度，避免针对表进行遍历

1. 代价：

1. 占用更多的空间。生成索引，需要一些列的数据结构以及一系列的额外数据，存储在硬盘中
2. 可能回降低插入修改删除的速度

2. 使用场景

• 数据量较大，经常需要对这些列进行条件查询

• 该数据库表的插入及对这些列的修改频率较低

  如果非条件查询列，或经常做插入修改，或磁盘空间不足，不考虑创建索引

3. 操作

3.1 查看索引

show index from 表名;

3.2 创建索引

会对现有的表中的数据进行重组

create index 索引名 on 表名(列名);

3.3 删除索引

drop index 索引名 on 表名;

一个索引只针对一个列来指定，只有针对这一列进行条件查询的时候，查询速度才能够被索引优化

删除索引和创建索引都是危险操作！！！

4. 索引的原理

哈希表只能进行精准匹配，无法进行范围查询、模糊匹配

红黑树可以精准匹配、范围查询，一定程度的模糊匹配（可以进行’李*‘，但不能高校进行’*李’）

是二叉树，随着数据的增多，树的高度也会变得很大，查询的时候，io访问次数就会更多

数据库的索引用的是改进的树形结构，B+树（N叉搜索树），分叉增多，树的高度减小

MySQL 内部负责存储数据的模块称为存储引擎，存储引擎提供了很多版本的实现，Innodb 是当前最常用的，他的索引构建方式就是 B+ 树

4.1 B树

N叉搜索树，每个节点上有 N 个 key，划分出了 N + 1 个区间，进行查询的时候，可以直接从根节点出发，判定当前要查的数据在节点上的哪个区间中，决定下一步往哪里走。进行添加/删除元素可能涉及到节点的拆分和节点的合并。

4.2 B+树

是针对数据库量身定做的树，对B树进行了改进。

B+ 树也是一个 N 叉搜索树，一个节点上存 N 个 key，划分出 N 个子区间，每个节点上 N 个 key 中，最后一个key就相当于当前子树的最大值。父节点上的每个 key 都会以最大值的身份在子节点的对应区间中存在（key 可能会重复出现），这样，叶子节点这层包含了整个数据集，用链表将叶子节点连接起来，便可以非常方便的完成数据集的遍历。要去查询某个范围的数据，可分别找到最小值和最大值，通过该段链表遍历即可获得该范围得所有数据。

时间复杂度：$logn$

4.2.1 优点

1. N 叉搜索树，树的高度相对二叉树来说更低，降低了 IO 次数

2. 非常擅长范围查询

3. 所有查询最终都需要落到叶子节点，每次查询的时间开销是稳定的

   B 树，要查询的元素如果在根节点或者层次较高的节点，就能非常快的拿到元素，但如果要查的元素在叶子节点，花费时间就较多（不稳定）。

   B+ 树，所有查询都要到达叶子层，无论查询哪个元素，时间都差不多（稳定）

4. 叶子节点是全集，会把行数据只存储在叶子节点上，非叶子节只存储用来排序的 key（构建索引的字段）

   叶子节点会比较占用空间，非叶子节点占用空间很少，可以缓存到内存中

   硬盘上存着非叶子节点，但当进行查询的时候，可以把这些非叶子节点加载到内存中，整体查询的比较过程便可以在内存中进行，进一步减少了 IO 次数

（不同数据库，会对 B+ 树有一定的优化）