【MySQL】索引|作用|底层数据结构|常见问题

1.概念

类似于目录，能够提高查询的速度，会占用更多的空间，也可能会拖慢增删改的速度

2.为何引入

默认情况下，进行条件查询，就是遍历表，一条一条都带入条件

引入索引，引入额外的数据结构，加快查询的速度，减少遍历表的可能性

3.使用

（1）查看索引

show index from 表名;

（2）创建索引（危险操作）

create index 索引名 on 表名（列名）;

（3）删除索引（危险操作）

drop index 索引名 on 表名;

Q1 ：为啥创建和删除索引都是危险操作？

A：因为这里的操作都会涉及大量的IO，就可能把MySQL主机搞挂了

Q2 :那怎么给以及包含大量数据的表添加索引？

A：部署新的服务器，用新的代替旧的数据库

MySQL有类似弱类型语言的特性

Q1 ：什么是强类型和弱类型语言？

A：弱类型：数据类型转换不那么严格（自动转换类型）

强类型：不能自动转换类型

eg：

 2 + "3" 如果可以直接相加，那么就是弱类型，否则为强类型

Q2 ：什么是动态语言和静态语言？

A：动态语言：变量的数据类型在运行时才能确定，即变量在声明时不需要指定数据类型，程序在运行过程中会根据变量被赋予的值来确定其类型

静态语言：编译时就必须确定

eg：int 类型程序运行过程中，变量的类型通常不能改变，那么就是静态语言，否则就是动态语言

4.使用场景

Q1 ：如果考虑对数据库的某列/某几列创建索引，需要考虑哪些？

A：

（1）数据量大否？经常对这些列进行条件查询否？

（2）数据库是否经常进行插入，修改操作？

（3）索引可能会占用磁盘空间哦~

（4）查询条件是否经常涉及排序？

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

Q2 ：什么样的查询，能够命中索引？

大前提：查询的条件和创建的索引的列是匹配的

5.底层数据结构（核心）

查询优化，首先想到 树 和 哈希表

（1）树

Q1：二叉树 / 二叉搜索树？

A1：

二叉树 ：

<1> 无序 ：查找特定节点时，需要遍历所有节点

<2>随机排布：最坏情况直接 退化成链表 ，查找效率低O(N)

二叉搜索树 ：虽然二叉搜索树对节点的排列有一定规则，即左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值，但是

<1>如果元素有序：直接 退化成链表 ，查找效率低O(N)

<2>树高度越高，I O操作越多 （数据库的数据通常存储在磁盘上，而磁盘 I/O 操作的速度相对较慢）

Q2：那 AVL树  /  红黑树呢？

首先我们考虑一下

Q3：为啥TreeMap / TreeSet不用AVL树，而用红黑树呢？

A3：

AVL树 ：是一个非常严格的平衡二叉搜索树（要求任意节点，左右子树高度差不能超过1）

红黑树 ：本质是一个没有那么严格的平衡二叉搜索树（要求更宽松）

那么显而易见，当你要求非常严格的时候，随便进行一些增删改操作，都可能会破坏平衡，从而触发旋转（每次旋转，都是有开销的）

总结 一下就是： 红黑树要求更宽松，触发旋转概率低，虽然没有AVL树那么平衡，但是查找速度并没有差多少

A2：那么对于Q2问题，我们out AVL树，再来看红黑树， 红黑树相较于哈希表可以进行范围查询 ，但是还是不太行

<1> 红黑树还是二叉搜索树，那么 树的高度越高，查询效率就越低 （数的高度每增加一层，比较次数就增加1，数据库的数据/索引都是保存在硬盘上的，上述每一次比较，就需要一次硬盘IO操作）

<2> 在红黑树中，找到中序遍历的下一个 后续元素 ，不高效，很有可能需要往父节点上一系列回溯，才能找到后继（不过这个好解决，可以通过“ 线索化 ”的方式解决，简单理解就是每个节点加上后续节点的指针，但是需要付出更多的存储空间）

（2）再来看查询O(1)的

哈希表

虽然哈希表最坏时间复杂度为O（M）（M为链表最大长度，即哈希冲突时，把哈希值相同的元素存储在同一个链表中），但是哈希表有个致命的弱点

只能查询相等情况， 无法进行范围查询 ，这样不适合数据库< >这样的范围查询

上面的结构都不是，那么还有什么呢？

还有

B树 （N叉搜索树）： 每个节点上可存储多个元素 ，延伸出多个子数（非常好的解决了红黑树数据多，数的高度变高的问题）

每个方框是一个节点，每个数字代表一个key（或者是数据库中的一行记录），n个key，n+1个子树

Q1：有人就说他每个节点（方框）中还需要拿着key进行比较，不应该效率很低吗？

A1 ：其实还是很高效的

1）每个节点上的这些key也是有序排列的，比较的时候可以直接 二分查找 .

2）B树也会控制，某个节点上保存的key不会太多，如果插入更多的元素，使key变多了，就会是节点 分裂出更多树 出来.

3）多个数据，都是放在一块 连续的存储空间 上，进行比较的时候，一次硬盘IO就能读出整个节点，就可以直接完成上述比较.（进行多次比较，实际上只有一次硬盘IO）【硬盘IO操作较内存/CPU操作很慢】

但是最终MySQL索引底层还是没有采用B树，而是

B+树

特点：

（1）N叉搜索树

（2）每个父节点中的元素都会在子节点中以最大值的方式存在

（3）叶子节点这一层通过链表连上

Q：为什么不用B树（B+树好处）?

A：

（1）

方便遍历和范围查询

好遍历整个表中的所有数据，也方便进行范围查询，叶子节点 即整个数据的全集+链表的链式结构（B树叶子节点没有这种链式节点）

（2）

每一次操作都比较稳定

任何一层操作，最终都是要落到叶子节点来完成的，那么查询任何数据，经历的硬盘IO次数都是一样的，查询操作消耗的时间都是一样的（但是 B树可能在非叶子节点就查到 了，虽然效率更高，但是有点时候查的快，有的时候慢，IO次数很大影响，不稳定）

（3）

叶子节点保存全集，非叶子节点能够在内存中进行缓存（主键索引）

由于叶子节点，是数据的全集，对应的，非叶子节点中，都是重复出现的数据.

就可以把表每一行的数据，最终都关联到叶子节点这一层.非叶子节点中只保存一个单纯的key值即可（id）

数据库每一行有很多列：student(id, name, classld, gender, score…….)

此时，比如使用id这一列来做索引.这里B+树的非叶子节点，都只需要保存一个id这样的值就行了

到了叶子节点这里，每个叶子节点不光要保存id，还要把后续的name，classld 等信息也保存起来.

咱们看到的“表格”只是一个逻辑上的结构

实际上底层的结构，就是这个B+树的结构.

就会按照主键的索引的这个B+树的叶子节点来保存每一行的数据～～

如果你的表，创建主键了，自然是通过你创建的主键的索引的B+树来组织所有行.

如果你没创建主键，mysql其实生成了一个 隐藏的主键 ，按照隐藏主键构造的树来组织.这样组织之后，非叶子节点占用的空间就比较小

（非叶子节点只存id） 此时，

非叶子节点就可以缓存到内存 中，这样查询速度又大大提高（当然，这份数据必然要在硬盘上也保存一份，为了提高查询速度，就可以把这部分结构放到内存中

总结就是说 B+树的非叶子节点只存储主键，可以缓存到内存，查询速度又大大提高， 而B树存储就得把非主键信息也保存起来，占据的空间大

针对哪个列创建索引，就是针对哪个列构建B+树(前提是Innodb存储引擎，不同存储引擎，存储的数据结构不同）

（1）主键索引：叶子节点是带有数据行

如果查主键值，就从树根节点往下层一层一层擦查询

如果查非主键值，遍历链表即可

（2）非主键索引：叶子节点，只有主键Id，如果查到了主键id，那么就要回到主键索引再去查询一次（也就是回标）

🔥6.经典问题

（1）为什么使用索引会加快查询？

（2）能简单说一下索引的分类吗？

（3）创建索引有哪些注意点？

（4）索引哪些情况下会失效呢？

（5）索引不适合哪些场景呢？

（6）索引是不是建的越多越好？

（7）为什么InnoDB要使用B+树作为索引？

（8）为什么不用普通二叉树？

（9）为什么用B+树而不用B树呢

（10）Hash 索引和B+树索引区别

（11）聚簇索引与非聚簇索引的区别

（12）回表了解吗？

回答思路：

（1）全表扫描 与 磁盘IO

（2）功能分 ，底层分 ，存储位置分

（3）合适的列 + 不要太多 + 利用前缀索引和索引列的顺序

（4）

（5）数据少 、频繁更新的列

（6）磁盘空间 + 索引可以提高效率，但是更新不方便了

（7）二叉平衡树，红黑树，B树比较

（8）退化为链表，无序遍历全表

（9）结构（链表+子节点最大值）方便遍历和范围查询 + 非叶子节点缓存 + 稳定

（10）

（11) 主键索引 VS 非主键索引

（12）同（11）