闲聊几句

数据库范式

目前关系数据库有六种范式:第一范式$(1NF)$、第二范式$(2NF)$、第三范式$(3NF)$、巴斯-科德范式$(BCNF)$、第四范式$(4NF)$和第五范式$(5NF$,又称完美范式)。

  1. 第一范式$(1NF)$:所有的域都应该是原子性的,即数据库表的每一列都是不可分割的原子数据项,而不能是集合,数组,记录等非原子数据项。
  2. 第二范式$(2NF)$:在$1NF$的基础上,非码属性必须完全依赖于候选码(在$1NF$基础上消除非主属性对主码的部分函数依赖)。
  3. 在$2NF$基础上,任何非主属性不依赖于其它非主属性(在$2NF$基础上消除传递依赖)。
  4. 在$3NF$基础上,任何非主属性不能对主键子集依赖(在$3NF$基础上消除对主码子集的依赖)

如何设计一个关系型数据库?

首先应该考虑关系数据库管理系统($RDBMS$),在 $RDBMS$ 中又包含两个重要组成部分,分别是:

  • 程序实例:其中又包括存储管理、缓存机制、$SQL$ 解析、日志管理、权限划分、容灾机制、索引管理锁管理
  • 存储(文件系统):硬盘等。

索引

索引分类

MySQL索引分类

聚簇索引与非聚簇索引

  • 聚簇索引:
    • 表数据是和主键一起存储,主键索引的叶结点存储行数据(包含了主键值),二级索引的叶结点存储行的主键值。
    • 使用$B+$树作为索引的存储结构,非叶子节点都是索引关键字,但非叶子节点中的关键字中不存储对应记录的具体内容或内容地址。叶子节点上的数据是主键与具体记录(数据内容)。
  • 非聚簇索引:
    • 表数据和索引是分成两部分存储的,主键索引和二级索引存储上没有任何区别。
    • 使用$B+$树作为索引的存储结构,所有的节点都是索引,叶子节点存储的是索引$+$索引对应的记录的地址。

聚簇索引的优缺点

  • 优点:
    • 把相关数据保存在一起,减少$I/O$次数。例如实现电子邮箱时,可以根据用户ID来聚集数据,这样只需要从磁盘读取少数的数据页就能获取某个用户的全部邮件。如果没有聚簇索引,则每封邮件都可能多一次磁盘$I/O$。
    • 数据访问更快。聚簇索引将索引和数据保存在同一个$B+Tree$中,因此从聚簇索引中获取数据通常比在非聚簇索引中查找要快。
    • 使用覆盖索引扫描的查询可以直接使用页节点中的主键值。
  • 缺点:
    • 聚簇数据最大限度地提高了$I/O$密集型应用的性能,但如果数据全部放在内存中,则访问的顺序就没那么重要了,聚簇索引也就没什么优势了。
    • 插入速度严重依赖于插入顺序。按照主键的顺序插入是加载数据到InnoDB表中速度最快的方式。但如果不是按照主键顺序加载数据,那么在加载完成后最好使用optimize table命令重新组织一下表。
    • 更新聚簇索引列的代价很高,因为会强制$InnoDB$将每个被更新的行移动到新的位置。
    • 基于聚簇索引的表插入新行,或者主键被更新导致需要移动行的时候,可能面临”页分裂(page split)“的问题。当行的主键值要求必须将这一行插入到某个已满的页中时,存储引擎会将该页分裂成两个页面来容纳该行,这就是一次分裂操作。页分裂会导致表占用更多的磁盘空间。
    • 聚簇索引可能导致全表扫描变慢,尤其是行比较稀疏,或者由于页分裂导致数据存储不连续的时候。
    • 二级索引(非聚簇索引)所占存储单元更大,因为二级索引的叶子节点包含了引用行的主键列。
    • 二级索引访问需要两次索引查找,而不是一次。即在非索引覆盖的前提下,先到二级索引查询到主键,然后再按主键去查询得到数据。

主键与唯一索引的区别是什么?

对比项 主键 唯一索引
功能 不仅是索引,还是约束。 是索引的一种
包含性 主键索引一定是唯一索引 唯一索引不一定是主键索引
空值 主键列不允许null 允许为null
外键 可以做外键 不可以
数量 只有一个主键 可以有多个唯一索引
优先级 执行计划优先级高于唯一索引 执行计划优先级低于主键
包含列 主键可以包含多个列,作为联合主键。 包含一列

索引的数据结构

  • 树结构:二叉排序树、红黑树、B-树、B+树、
  • Hash结构:BitMap 位图索引是神器
    • 缺点仅能满足 =, in 操作,不能使用范围查询
    • 无法被用来避免数据的排序操作
    • 不能利用部分索引键查询
    • 不能避免表扫描遇到大量 Hash 值相同的情况,此时性能并不一定比 B-树 高。

来自灵魂的拷问

数据库索引总结

索引的最左匹配

👩‍🏫:为什么索引是最左匹配,而不是最右匹配,不是中间匹配?

👨‍🎓:$\dots$

最左前缀匹配原则

If the table has a multiple-column index, any leftmost prefix of the index can be used by the optimizer to look up rows.

如果在一个索引中包含多个列,那么这个索引的任何最左前缀均可以被优化器用于查询行。

MySQL Documentation - Multiple-Column Indexes

假如有联合索引 (a, b, c),那么查询条件走索引的是 (a)、(a, b)、(a, b, c)。

特别注意:这里说的走索引其实是覆盖索引

覆盖索引:如果一个索引包含(或者说覆盖)所有需要查询的字段的值,成为“覆盖索引”。

EXPLAIN 命令

如果在 Extra 列中看到 “Using index“,说明 MySQL 正在使用覆盖索引。–《高性能 MySQL》 附录 D => Explain 中的列 => type 列 => index。(Page 728)

  • MySQL会一直从左向右匹配直到遇到范围查询(>, <, between, like)就停止匹配,比如 a=3 and b=4 and c>5 and d=6 , 如果建立 (a,b,c,d) 顺序的索引,则 d 是用不到索引的,因为到 c 就已经停止了,如果建立 a,b,d,c 的索引则都可以用到, a,b,d 的顺序可以任意调整。
  • =, in 可以乱序,比如建立 (a,b,c) 索引,那么 a=1 and b=2 and c=3a=1 and c=3 and b=2都可以命中索引,MySQL的查询优化器会帮助优化成索引可以识别的形式。

假如有如下这张表结构:

1
2
3
4
5
6
7
create table `student` (
`id` int(11) not null auto_increment,
`name` varchar(32) default null,
`cid` int(11) default null,
primary key (`id`),
key `name_cid_idx` (`name`, `cid`)
) engine = InnoDB auto_increment=8 default charset=utf8;

插入五条数据后表为

id name cid
1 raymond 2
8 raymond 1
9 ramona 3
10 Bezos 4
11 Bill 6

如果执行下面这条查询,可以看到用了联合索引name_cid_idx,这是没有什么疑问的。而且rows = 1filtered = 100

1
2
# 查询 1
explain select * from student where name = 'raymond' and cid = 2;

image-20200801140354338

但是如果执行了下面两条查询呢?

1
2
3
4
5
# 查询 2
explain select * from student where cid = 2;

# 查询 3
explain select * from student where cid = 2 and name = 'raymond';

查询结果分别如下(列名与上面图片相同,只放结果。) 从中可以看到,上面的查询 $2$ 使用了索引扫描(rows = 5);查询 $3$ 的结果与查询 $1$ 的结果完全相同,说明$MySQL$ 的查询优化器为我们做了调整。

1
2
3
4
1,SIMPLE,student,<null>,index,<null>,name_cid_idx,104,<null>,5,20,Using where; Using index


1,SIMPLE,student,,ref,name_cid_idx,name_cid_idx,104,"const,const",1,100,Using index

那么为什么要强调最左匹配时要进行等值查询,而遇到范围查询时就失效呢?

$MySQL$ 创建符合索引的规则时首先会对符合索引的最左边的列,也就是第一个name字段的数据进行排序,在第一个排序的基础上再对第二个字段cid进行排序。其实就相当于进行了order by name asc, cid asc这样的排序。

所以如果对上面表格中的几条数据按name进行排序的话就会变成下面图片中的样子,既然按name排序,那么cid不再有序。

  • 如果是等值的话,将是有序的。观察$4,5$列同名的raymond,可以看到cid便是有序的。
  • 如果非等值(区间或范围)的话,将是无序的。观察$1,2,3$ 列可以看到,假如查询名字首字母在B-r之间的人,cid已经乱序,而在使用索引时需要顺序查询,但是cid依次为4,6,3,不能再按序查询。

按name排序

所以,为什么$MySQL$默认是最左匹配而不是最右匹配,为还是没清楚。

密集索引与稀疏索引

密集索引文件中的每个搜索码值都对应一个索引值

稀疏索引文件只为索引码的某些值建立索引项

  • MyISAM
  • InnoDB
    • 若一个主键被定义,则该主键为密集索引
    • 若没有主键被定义,则该表的第一个唯一非空索引作为密集索引
    • 若不满足以上条件,InnoDB内部会生成一个隐藏主键(密集索引)
    • 非主键索引存储相关键位和其对应的主键值,包含两次查找

评论