「SQL」SQL 学习笔记

索引

索引分类

从索引的类型上来看,分为主键索引,唯一索引,普通索引和组合索引,

  • 主键索引的值需具备唯一、非空,且一个表中主键索引唯一。
  • 唯一索引的值需具备唯一,非空。一个表允许多个唯一索引。
  • 普通索引的值没有限制。一个表允许多个普通索引。
  • 组合索引的值由多列组成,适合于多个列一起作为查询条件的情况。组合索引具有顺序性,ABC 三个条件的组合索引只能匹配 A、AB、ABC 三种情况,要根据查询频率进行考虑。

从索引和存储的关系上来看,分为聚簇索引和非聚簇索引。

在创建索引时可以选择聚簇索引或非聚簇索引。

  • 聚簇索引是将表的数据按照主键的顺序进行排序并存储的一种索引方式。

  • 非聚簇索引是索引顺序和数据存储顺序无关的一种索引方式。

    对于聚簇索引的 B+树,树的叶子结点中直接存储着数据行,对于非聚簇索引的 B+树,树的叶子结点中存储着指向聚簇索引 B+树叶子结点的指针。

索引原理

传统的查询方法需要顺序遍历全表,通过索引可以将指定列的值组合成查询效率更高的数据结构,比如 B+树,存储为索引文件,在查询时只需要遍历指定的索引文件即可。

B+ 树是一种多路搜索树,基本结构类似于 B 树,

  • 结点包括根结点、内部结点和叶子结点,但内部结点不存储数据,只存储索引。
    • B+树内部结点不存储数据,单个结点可以存储更多的关键字,因此减少了查询次数。
    • B+树只有叶子结点持有数据,查询时可以将根结点和内部结点读取到内存中,而叶子结点仍保存在外存中,这样既可以利用内存的高速,又可以利用外存的大容量。
    • 索引值相同的结点一般按照主键顺序存储在同一个叶子结点中。
  • 每个结点可以存储多个行数据的关键字及其所在行的指针,关键字一般按照一定顺序排列。
    • 关键字按照一定顺序排列可以方便地实现范围查询和排序。
  • 叶子结点组织成一张双向链表,方便遍历全表和实现范围查询。

如何选择索引?

  • 索引应该建立在查询频繁的字段
    • 索引用来加速查询,查询频率低的字段加速效果差。
  • 索引不应该建立在更新频繁的字段
    • 在更新数据时也要维护索引
  • 索引的个数应该适量:索引本身需要占用空间,在插入和更新数据时也要维护索引。
  • 数据熵低的字段不建议创建索引:索引一般使用 B+树,数据熵过低的如性别这类,B+树能提升的效率极其有限
  • 对于组合条件查询,应当使用组合索引代替多个单列索引
    • 对于 A&B&C 三个条件,如果使用组合索引,查询时只需要查询一个索引,如果使用多个单列索引,查询时需要查询三个索引。
  • 不建议用无序的值作为索引

MySQL 索引

MySQL 默认使用 B+树作为索引,一般一个结点使用一个磁盘块,假设磁盘块的大小为 16KB,如果使用 bigint(8B)作为索引,指针大小设置为 6B,那么一个非叶子结点可以存储 16KB/14B 约 1170 个指针,在这种情况下一张两千万左右的表查询数据最多访问 3 次磁盘。

B+树 vs 普通二叉树

普通二叉树在最坏的情况下会退化为链表,时间复杂度退化为 On。

B+树 vs 平衡二叉树

平衡二叉树一个结点只能存储一条数据,相比于 B+树一个非叶子结点可以存储多条索引数据,B+树的树高度更低,读取磁盘的次数更低。

B+树 vs B树

  • B+树的非叶子结点不存储数据,因此一个结点可以存储更多的关键字。
  • B+树只有叶子结点存储数据,因此 IO 次数是稳定的。
  • B+树的叶子结点组织成了一张双向链表,遍历全表时只需要遍历叶子结点链表即可,不需要用树的遍历。
  • B+树的叶子结点是双向链表,持有前驱和后继的指针,排序能力更强。

回表

回表指的是通过非聚簇索引进行查询时,如果叶子结点中的数据不能满足查询数据列的需求,需要通过行指针返回表数据中进行二次检索。

比如创建了 d 和 e 的组合索引,那么:

  • 在进行诸如 SELECT d, e from d<2 and e>3 的条件查询时,则不需要回表操作,因为组合索引已经覆盖了待查询的列:d, e,称查询列覆盖了索引;
  • 在进行 SELECT d, f from d<2 and e>3 的条件查询时,则需要回表,因为组合索引 d,e 中不含有 f 列的数据。

比如分别创建了 d 和 e 的唯一索引,那么:

  • 在进行诸如 SELECT d, e from d<2 and e>3 的条件查询时,仍需要回表操作,因为最后一个查询条件 e>3 所指向的索引中不含有待查询列 d 的数据;
  • 在进行诸如 SELECT e from d<2 and e>3 的条件查询时,则不需要回表操作,因为最后一个查询条件 e>3 所指向的索引中含有待查询列 e 的数据,称查询列覆盖了索引。

组合索引的最左匹配原则

在组合索引中,查询时只有使用了最左边的索引列来查询,才能命中索引。比如创建了一个组合索引为 ABC,那么只有 A、AB、ABC 才能命中索引。

索引一般使用 B+树组织,B+树中的关键字按照一定顺序排序,组合索引的关键字则按照 ABC 的自然顺序组合排序,类似于 Java 的 Comparable 接口,使用多个关键字进行排序。

锁分类

从锁的粒度上来看,分为表锁、行锁和页锁:

  • 表锁:开销小,加锁快;锁定粒度大,发生锁冲突概率高,并发度最低;不会出现死锁
  • 行锁:开销大,加速慢;锁定粒度小,发生锁冲突概率低,并发度最高;会出现死锁
  • 页锁:开销和加速速度介于行锁和表锁之间;锁定粒度、发生锁冲突概率、并发度介于行锁和表锁之间;会出现死锁

从锁的操作看,分为共享锁和排他锁:

  • 共享锁:又称读锁,相互不阻塞
  • 排他锁:又称写锁,排他锁是阻塞的

行锁实现

行锁的实现根据查询和插入操作的不同分为:

  • Record Lock 记录锁:使用唯一性的索引进行等值匹配到一条记录时,对该条记录加锁;
  • Gap Lock 间隙锁:使用等值查询或者范围查询没有匹配到任何一条记录时,对对应的左开右开间隙空间加锁;
  • Next-key Lock 临键锁:使用等值查询或者范围查询匹配到任何一条记录时,对对应记录的左开右闭间隙空间加锁,并包含最后一条记录右边的临键区间。
  • Insert Intention Lock 插入意向锁: