前言

只有光头才能变强

索引和锁在数据库中可以说是非常重要的知识点了，在面试中也会经常会被问到的。

本文力求简单讲清每个知识点，希望大家看完能有所收获

声明：如果没有说明具体的数据库和存储引擎，默认指的是MySQL中的InnoDB存储引擎

一、索引

在之前，我对索引有以下的认知：

• 索引可以加快数据库的检索速度

• 表经常进行INSERT/UPDATE/DELETE操作就不要建立索引了，换言之：索引会降低插入、删除、修改等维护任务的速度。

• 索引需要占物理和数据空间。

• 了解过索引的最左匹配原则

• 知道索引的分类：聚集索引和非聚集索引

• Mysql支持Hash索引和B+树索引两种

看起来好像啥都知道，但面试让你说的时候可能就GG了：

• 使用索引为什么可以加快数据库的检索速度啊？

• 为什么说索引会降低插入、删除、修改等维护任务的速度。

• 索引的最左匹配原则指的是什么？

• Hash索引和B+树索引有什么区别？主流的使用哪一个比较多？InnoDB存储都支持吗？

• 聚集索引和非聚集索引有什么区别？

• ........

1.1聊聊索引的基础知识

首先Mysql的基本存储结构是页(记录都存在页里边)：

 image      image

• 各个数据页可以组成一个双向链表

• 而每个数据页中的记录又可以组成一个单向链表

  • 每个数据页都会为存储在它里边儿的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录

  • 以其他列(非主键)作为搜索条件：只能从最小记录开始依次遍历单链表中的每条记录。

所以说，如果我们写select * from user where username = 'Java3y'这样没有进行任何优化的sql语句，默认会这样做：

• 定位到记录所在的页

  • 需要遍历双向链表，找到所在的页

• 从所在的页内中查找相应的记录

  • 由于不是根据主键查询，只能遍历所在页的单链表了

很明显，在数据量很大的情况下这样查找会很慢！

1.2索引提高检索速度

索引做了些什么可以让我们查询加快速度呢？

其实就是将无序的数据变成有序(相对)：

 image

要找到id为8的记录简要步骤：

 image

很明显的是：没有用索引我们是需要遍历双向链表来定位对应的页，现在通过“目录”就可以很快地定位到对应的页上了！

其实底层结构就是B+树，B+树作为树的一种实现，能够让我们很快地查找出对应的记录。

参考资料：

• Mysql索引

1.3索引降低增删改的速度

B+树是平衡树的一种。

平衡树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

如果一棵普通的树在极端的情况下，是能退化成链表的(树的优点就不复存在了)

 image

B+树是平衡树的一种，是不会退化成链表的，树的高度都是相对比较低的(基本符合矮矮胖胖(均衡)的结构)【这样一来我们检索的时间复杂度就是O(logn)】！从上一节的图我们也可以看见，建立索引实际上就是建立一颗B+树。

作者：Java3y
链接：https://www.jianshu.com/p/33e877d616d5