本文是面试基础的第二篇。本篇偏理论,包括三节:
-
事务和并发
-
数据库设计
-
索引
所选的三个内容均是面试的高频考察点,需要细致地理解
No.1 事务和并发
事务:数据库操作的基本单元。对于数据库的一系列操作,要么全部成功,要么全部失败
1. 事务的ACID属性
原子性(Atomic)
一个事务包含多个操作,这些操作要么全部执行,要么全都不执行。实现事务的原子性,要支持回滚操作,在某个操作失败后,回滚到事务执行之前的状态。
回滚实际上是一个比较高层抽象的概念。大多数DB在实现事务时,是在事务操作的数据快照上进行的,执行事务时并不修改实际的数据,只有事务完成后才会提交到数据库,完成对数据库的修改。如有错,则不会提交,所以很自然的支持回滚。
而在其他支持简单事务的系统中,不会在快照上更新,而直接操作实际数据。可以先预演一边所有要执行的操作,如果失败则这些操作不会被执行,通过这种方式很简单的实现了原子性。
一致性(Consistency)
一致性是指事务使得系统从一个一致的状态转换到另一个一致状态。事务的一致性决定了一个系统设计和实现的复杂度。事务可以不同程度的一致性:强一致性:读操作可以立即读到提交的更新操作弱一致性:提交的更新操作,不一定立即会被读操作读到,此种情况会存在一个不一致窗口,指的是读操作可以读到最新值的一段时间最终一致性:是弱一致性的特例。事务更新一份数据,最终一致性保证在没有其他事务更新同样的值的话,最终所有的事务都会读到之前事务更新的最新值。如果没有错误发生,不一致窗口的大小依赖于:通信延迟,系统负载等。其他一致性变体还有:单调一致性:如果一个进程已经读到一个值,那么后续不会读到更早的值。会话一致性:保证客户端和服务器交互的会话过程中,读操作可以读到更新操作后的最新值。
隔离性(Isolation)
并发事务之间互相影响的程度,比如一个事务会不会读取到另一个未提交的事务修改的数据。在事务并发操作时,可能出现的问题有:脏读:事务A修改了一个数据,但未提交,事务B读到了事务A未提交的更新结果,如果事务A提交失败,事务B读到的就是脏数据。不可重复读:在同一个事务中,对于同一份数据读取到的结果不一致。比如,事务B在事务A提交前读到的结果,和提交后读到的结果可能不同。不可重复读出现的原因就是事务并发修改记录,要避免这种情况,最简单的方法就是对要修改的记录加锁,这会导致锁竞争加剧,影响性能。另一种方法是通过MVCC可以在无锁的情况下,避免不可重复读。幻读:在同一个事务中,同一个查询多次返回的结果不一致。事务A新增了一条记录,事务B在事务A提交前后各执行了一次查询操作,发现后一次比前一次多了一条记录。幻读是由于并发事务增加记录导致的,这个不能像不可重复读通过记录加锁解决,因为对于新增的记录根本无法加锁。需要将事务串行化,才能避免幻读。为解决上述问题,需要在并发和隔离进行平衡。事务的隔离级别从低到高有:Read Uncommitted:未提交读,最低的隔离级别,一个事务可以读到另一个事务未提交的结果。所有的并发事务问题都会发生。Read Committed:提交读。只有在事务提交后,其更新结果才会被其他事务看见。可以解决脏读问题。Repeated Read:可重复读。在一个事务中,对于同一份数据的读取结果总是相同的,无论是否有其他事务对这份数据进行操作,以及这个事务是否提交。可以解决脏读、不可重复读。Serialization:串行化。事务串行化执行,隔离级别最高,牺牲了系统的并发性。可以解决并发事务的所有问题。通常,在工程实践中,为了性能的考虑会对隔离性进行折中。
持久性(Durability)
事务提交后,对数据库的影响是永久的。
2. 四种隔离级别
在MySQL中设置隔离级别:
查看当前隔离级别:
show variables like 'transaction_isolation'
结果为可重复读
设置下次事务的隔离级别:
set transaction isolation level serializable
设置将来所有事务的隔离级别:
set session transaction isolation level serializable
设置全局事务的隔离级别:
set global transaction isolation level serializable
下面利用具体例子来解释四种隔离级别的含义,以及可能会出现的问题。假设有两个事务A和B
1. 未提交读:read uncommitted
原本A事务想读50的余额,在读的过程中因为B的修改,造成读的结果为100,但由于B事务最后回滚了,数据库中最终张三的余额还是50,即查询结果并不为数据库的最终真实结果。该现象称为脏读(dirty read)
2. 提交读:commit read
为避免脏读,最直接的做法是屏蔽掉没有提交的修改。下图中事务B真正将修改持久到数据库中后,才会对事务A产生影响。
但这又回造成新的问题。假设A事务中有两次查询,第一次查询得到结果50,第二次查询之前,B事务修改余额为100并提交,那么A事务中的第二次查询得到的结果为100。这样在同一个事务中,两次查询结果不同,该现象称为不可重复读。
3. 可重复读:repeatable read
为解决上述问题,可以给数据加上时间戳,规定每次读的都是开启事务时刻的数据库数据。这样即使在事务处理期间,数据库发生了变化,也不会对本事务产生影响。该处理方式称为快照,相当于开始事务时,对数据库进行一个记录,之后事务的进行都以之为准。
但是这又带来新的问题。可重复读意味着,A事务处理期间,数据库的任何改变都不会被感知,这种做法虽然保证了可重复读的一致性,但是也丢失了B事务的有用修改,会引起幻读现象。
4. 串行化:serialization
一张表一次只能被一个事务访问,完全没有并发。每个事务占用一张表时,会将该表上锁。表处于锁定期间,其他事务只能等待。只有当占有该表的事务结束,该表才会被释放。
因此,当两个事务互相等待时,便会造成死锁现象。
一般发生死锁的四个必要条件为:
-
互斥条件:一个资源每次只能被一个进程使用
-
占有且等待:一个进程因请求资源而阻塞时,对已获得的资源保持不放
-
不可剥夺:进程已获得的资源,在末使用完之前,不能强行剥夺
-
循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系
解决死锁的途径:
打破上述四个条件中的一个或多个。例如设置事务执行时间,一旦timeout,则该事务自动回滚并释放资源。再比如,在写并发执行的SQL语句时,尽量按照相同的处理次序,这样至多只会出现争抢,避免形成循环等待。
No.2 设计数据库
1. 基本过程
一个设计合理的数据库,将大大提高读写效率和扩展性。设计数据库,由表及里,包含四个步骤:
1. 理解需求:对象是什么,满足什么功能2. 构建概念模型:确定实体有哪些,实体之间什么关系3. 构建逻辑模型:对概念模型进行具体化,确定有哪几张表,每个表之间有哪些字段,每个表之间是什么关系4. 构建物理模型:具体的数据库表格,如果每个字段的类型,哪些是主键,外键,唯一键等等
举例:设计一个数据库,记录学生选课的信息
概念模型
数据库模型本质就是具有不同属性实体及其相互关系。对于上述问题,可以分析出:
学生实体:姓名,邮箱,注册日
期课程实体:标题,价格,教师,标签
学生实体和课程实体之间关系:多对多。因为一个学生可以选多门课,一门课会包含多个学生。
图中二者之间的连接线端点形状代表不同的关系类型。实体之间的关系类型:三种
逻辑模型
假设现在要记录某个学生参加某门课程的日期。这个时间如果放在student表,由于每个学生可能选择多门课,即有多个时间,仅根据学生信息无法确定具体对应哪个时间(student表中不记录课程信息)。若将该时间字段放在course表,也会面临同样的问题。问题的本质是,某个学生选某门课的时间,既不是student实体的属性,也不是course表的属性,而是二者关系(即enroll)的属性。解决方案是,利用第三张表,将多对多的关系,转换为两个一对多的关系。不妨建一个enrollment表,记录各个学生,各门课的选择信息。同时,每张表中补充了具体字段的类型和名称细分。有了逻辑模型,便可以明确总共有三张表,每张表有哪些字段,以及各个字段的类型。同时各个表的关系也得到体现。
物理模型:
即逻辑模型在MySQL的具体实现。对于不同的SQL软件,其逻辑模型相同,物理模型有差异。
在创建一张表时,我们依次指定各个字段名,字段类型(varchar,datetime等),能否为空,默认值等。在完成各个表的构建后,我们接着实现对各个表之间关系的指定。
原则:一张表只描述一个实体,该表中的所有字段,都只描述该实体。当涉及其他实体时,需要用外键进行连接。这样做使得各个表的边界清晰,当某个属性发生修改时,不用修改多个表。本质是尽量降低数据的重复率
主键:每行记录在表中的唯一标识
-
一个或多个属性的组合,一张表只有一个主键,其值不可为空
外键:建立表的父子关系
如students表、courses表可认为由enrollment表派生而来。前者为子表,后者为其父表
-
外键约束:当外键所依赖的父表主键对应的值发生变化时,子表是否自动同步变化。例如student表中新加入一个学生,若设置外键为casecade,则erollment表会同步加入该学生信息。同理,当删除某个学生时,erollment表也会同步删除相应学生信息
唯一键:该属性的值不重复
有时候,我们希望某个属性的值各不相同,如订单号,可以设置为唯一键
-
一个或多个属性的组合,一张表中可以有多个唯一键,其值允许为空
-
主键一定是唯一键,唯一键并不一定是主键
2. 范式
第一范式:属性的原子性
属性具有原子性,不可再分解。如:
表:字段1、 字段2(字段2.1、字段2.2)、字段3 ……
如学生(学号,姓名,性别,出生年月日),如果认为最后一列还可以再分成(出生年,出生月,出生日),它就不满足第一范式
例如:原本course表中的标签(tags)字段,每门课可能有多个tag(tag1,tag2,…),因此在该表中,tags 不能只有一列(否则可能出现A课程在tags字段下,同时有多个值)。因此,就有tag1,tag2等一系列的tags值的列,这显然不合理,因为我们可能不知道总共有几个tag,同时tags的新增和删除也会涉及全表扫描。
稍微思考可以发现,course与tag是多对多的关系,每门课有多个tags,每个tags对应多门课。因此,可以将tags从courses表中分离出来,作为一个单独的只与tag有关的表。而courses表与tags表则通过链接表course_tags表连接。如下图所示:
第二范式:记录的唯一性
表中的每行由主键唯一区分,非主属性完全依赖主键,不存在部分依赖
表:学号、课程号、姓名、学分
这个表明显说明了两个事务:学生信息, 课程信息。由于非主键字段必须依赖主键,这里学分依赖课程号,姓名依赖与学号,所以不符合二范式
可能会存在问题:
-
数据冗余: 每条记录都含有相同信息;
-
删除异常:删除所有学生成绩,就把课程信息全删除了;
-
插入异常:学生未选课,无法记录进数据库;
-
更新异常:调整课程学分,所有行都调整。
正确做法:
学生表:学号, 姓名课程表:课程号, 学分选课关系表:学号, 课程号, 成绩
第三范式:字段的冗余性
任何字段不能由其他字段派生出来,它要求字段没有冗余,即不存在传递依赖
表: 学号, 姓名, 年龄, 学院名称, 学院电话
上表存在依赖传递: (学号) → (学生)→(所在学院) → (学院电话)
可能会存在问题:
-
数据冗余: 有重复值,如某学院电话有多个,则多行记录前三个属性值都相同,只有学院电话不同;
-
更新异常: 有重复的冗余信息,修改时需要同时修改多条记录,否则会出现数据不一致的情况 。
正确做法:
学生表:学号, 姓名, 年龄, 所在学院
学院表:学院, 电话
反范式化
没有冗余的数据库设计可以做到。但是,没有冗余的数据库未必是最好的数据库,有时为了提高运行效率,就必须降低范式标准,适当保留冗余数据。具体做法是:在概念数据模型设计时遵守第三范式,降低范式标准的工作放到物理数据模型设计时考虑。降低范式就是增加字段,允许冗余,达到以空间换时间的目的。
例如:有一张存放商品的基本表,“金额”这个字段的存在,表明该表的设计不满足第三范式,因为“金额”可以由“单价”乘以“数量”得到,说明“金额”是冗余字段。但是,增加“金额”这个冗余字段,可以提高查询统计的速度,这就是以空间换时间的作法。
范式与反范式对比
范式化:适合写
优点:降低数据冗余,数据表体积小,更新快
缺点:查询需要将多个表进行连接,更难进行索引优化
反范式化:适合读
优点:减少表关联,更易索引优化
缺点:存在冗余数据和数据维护异常(数据不一致),修改成本高
3. 基本操作
1. 数据库的创建与删除
create database if not exists sql_store --创建一个名为sql_store的数据库drop database if exists sql_store --删除数据库sql_store
2. 表的创建删除与修改
声明方式与数据库的创建和删除类似,但表需要指定其中的字段。指定方式为:名称+类型+属性:
类型:如int,varchar等,varchar可在括号中分配指定容量属性:包括主键、外键、唯一键、非空、自增、默认值等等
use sql_store2; -- 建表之前一般都会检查删除原来的表drop table if exists customers; create table if not exists customers( customer_id int primary key auto_increment, first_name varchar(50) not null, points int not null default(0), email varchar(255) not null unique);
表的修改:
alter table custormers -- 在first_name后增加一个last_name字段 add last_name varchar(50) not null after firat_name, -- 修改first_name字段的类型和默认值 modify first_name varchar(55) default(''), -- 删除points字段 drop points;
3. 关系的创建与修改
下面创建一个订单表:orders。orders表通过外键custormer_id与之前创建的custormers表相关联。该关联又称为外键约束。
drop table if exists orders;create table if not exists orders( order_id int primary key, custormer_id int not null, foreign key fk_orders_custormers (custormer_id) references customers (custormer_id) on update cascade on delete no action);
(1)外键的命名中,首先是子表名,然后是父表名。orders表通过custormer_id依赖父表custormers,因此命名为fk_orders_custormers。
(2)括号中声明表中哪个字段为外键
(3)references声明依赖的哪张表的哪个字段(主键)
(4)on update和on delete用来声明,父表的对应字段变化时,子表是否要同步变化
update和delete分别指代父表的更新和删除的变化。分析可知,顾客id变化时,订单表中的id也应该同步,从而维持一致性,因此采用cascase模型;而当顾客id意外删除时,订单表应保持原来的订单信息,不能同步删除,因此采用no action模式,即什么也不做
(5)删除表时需要按照先删除子表,再删除父表的顺序。因此需要将删除orders表的语句,放在删除custormers表之前
修改主键或外键约束,同样使用alter关键字:
alter table orders add primary key (order_id), drop primary key, add foreign key fk_orders_custormers (customer_id) references customers (customer_id) on update cascade on delete no action, drop foreign key fk_orders_custorms, ;
No.3 索引
在查询数据时,如果时逐行扫描,无疑查询速度会非常慢。索引的出现,便是为了加速查询。
举例:在customers表中查询state为CA的记录
可以预先将state的值建立成有序的索引,这样先通过索引查到相应行,再依次读取customers表中的相应行即可,从而避免了全表扫描
索引优点:
- 避免全表扫描,提升查询效率
- 相比放在磁盘的数据库表,索引比较小,可以放在内存中,提升查询速度
索引缺点:
- 增加了额外的索引表,数据库体积变大
- 每次更新数据,都要同步维护索引,降低写效率
1. 索引的优化原理
查询问题,就是算法中的查找问题。查找问题最经典的解决方案,是二分查找。索引是一种有序的数据结构,其本质是一棵搜索树。为了提高平均查询性能,基本都是平衡搜索树(balance search tree)。MySQL中采用的数据结构为B树/B+树。
举例:8条数据,编号依次为1,2,…,8,如何组织索引?
数据库中的记录在磁盘中按照页式存储,由于页的大小固定(一般为16kB),因此数据分布在若干页上,为简化问题,假设每页的容量为2。如下图所示,8条数据两两组合构成了4页,每组之间通过前后指针连接。
下面建立索引。由于页号有序,我们可以依次记录每一页的起始编号,这样得到了4条索引,分别为1,3,5,7。代表所指向页中的最小编号。同样,这4条索引两两组合,共占用两页。依次类推,可以得到最上层的两个索引1,6,共占用一页。索引树建立完成,可以看到是一棵二叉搜索树,本质就是一个分级目录
此时,如查询4,从树根开始走过的路径如下。对1-8中任何一条记录的查询,操作次数不会超过三次。由上到下,每下一层,数据范围减半。这便是最典型的二分法
从上面的描述中,我们发现只有最底层的叶子节点存储数据,建立在其上的索引并不存储真实数据。
在实际中,每一页存储的数据不止两个,因此索引的数量也远远小于数据的数量。这两点使得索引需要的存储体积很小,不用放在硬盘中,而可以直接放在内存中。
上述为最简情况,可以看到具备以下三个局限:
-
单次查询的次数,取决于索引树的树高。对于二叉树来说,树高即为log2(n),其中n为数据总量。因此,索引树应该越低越好。如何降低树高?增加树的出度即可,如3叉树,4叉树等等
-
以上分析是静态的,实际中数据是动态地插入和删除,因此搜索树必须自动平衡,避免退化为链表。
-
范围查询难以实现,如查询编号在4到6之间到数据,上述方法只能拆为4,5,6三次查询
基于以上原因,索引一般采取B树或B+树。因为:
-
B/B+树出度大,因此树高小,具有更少的比较次数
-
B/B+树的节点中可以存储多个数据,可以充分利用磁盘的预读特性减少磁盘I/O
-
B/B+树是平衡树,在插入或删除时会利用旋转来使得失衡的树恢复平衡
-
B+树只需遍历叶子节点便可遍历所有数据(如上图叶子节点之间用指针互相连接),有利于范围查询,这一点B树则难以做到
例子中的编号有序,当我们指定某个字段作为索引时,MySQL会先将该字段的所有当前值构建一个B+树,后续数据的插入和删除,会对索引树进行同步处理。
2. 索引的使用和分类
在MySQL中创建一个索引:
create index idx_points on customers(points); -- 基于points字段建立表customers表的索引,索引名称为idx_points查看索引:show indexes in customers; 删除索引:drop index idx_points on customers;
索引的建立本质上就是一个对原数据进行分段分层的目录管理问题,根据某个字段建立索引,即将该列的值进行了排序。
1. 聚簇索引:索引和数据存储在一块
也叫主键索引,根据主键创建的索引,自动创建,只有一个
按照主键构造一棵B+树,若无主键,采用非空唯一键。如果仍没有,则会隐式采用某个字段。
叶子节点中存放的整张表的行记录数据。叶子节点称为数据页,每个数据页通过一个双向链表来进行链接,而且数据页按照主键的顺序进行排列。每个数据页上存放的是完整的行记录,而在非数据页的索引页中,仅存放键值及指向数据页的页号。即上面图例所示
2. 非聚簇索引:索引和数据分离
也叫辅助索引(二级索引),用户定义,可以有多个
非聚簇索引构建的B+树,只记录主键值。在进行查询时,先利用辅助索引查找到主键值,再通过主索引查找到行数据。因此需要两次索引查找
举例:学生表:,,,,其中id为主键,会自动根据id建立主索引:idx_id。用户也可以指定,根据city或者score建立辅助索引:idx_city或idx_score
非聚簇索引包含:普通索引,唯一索引,前缀索引等,这些因为只依据一个字段,因此又称为单列索引。与之相对的,是由多个字段组合构成的索引,称为组合索引。下面分两类分别介绍。
2.1 单列索引
普通索引:最基本的索引,没有任何限制,是我们大多数情况下使用到的索引
唯一索引:与普通索引类似,不同的是唯一索引的列值必须唯一,但允许为空值
全文索引:仅可以适用于MyISAM引擎的数据表;作用于CHAR、VARCHAR、TEXT数据类型的列
前缀索引:对于string类的数据,可将值的前一部分作为索引,如前5个字符。这样既可以节约空间,又可以提高查询效率。所取长度需根据具体情况来确定最优值。但无法使用前缀索引做 ORDER BY 和 GROUP BY,也无法使用前缀索引做覆盖扫描。
举例:学生表:,,,,其中name有:streadeerff,addedeasa,defwwdserfs三个记录值。假设直接指定name字段建立辅助索引,那么B+树中需要存储streadeerff,addedeasa,stfwwdserfs这三个string。但其实我们根据前三个字符即可区分,指定前缀索引长度为3,则B+树中记录的为:str,add,stf
覆盖索引:索引本身就包含所有需要查询的字段的值,sql只需要通过索引就可以返回查询所需要的数据,这样避免了查到索引后再返回表拿取数据的操作,减少I/O提高效率。
具有以下优点:
- 索引通常远小于数据行的大小,只读取索引能大大减少数据访问量。
- 一些存储引擎(例如 MyISAM)在内存中只缓存索引,而数据依赖于操作系统来缓存。因此,只访问索引可以不使用系统调用(通常比较费时)。
- 对于 InnoDB 引擎,若辅助索引能够覆盖查询,则无需访问主索引。
2.2 组合索引
采用多个字段构成索引
当查询条件涉及多个字段,而每个字段都有单列索引时,MySQL会根据书写顺序采取第一个字段对应的索引来进行查询,然后对查询结果依次扫描,效率较低
如下图中,查询涉及state字段和points字段,对应索引为idx_state和idx_points,实际MySQL采用idx_state进行查询出所有位于CA的记录,然后遍历比对其points是否大于1000
创建组合索引:idx_state_points,查询效率会大大提升
组合索引适用于多条件查询的情况,同时能缩减辅助索引数量。如上例中,有了idx_state_points,便不再需要idx_state和idx_points,减少了索引开销
组合索引顺序
应让选择性最强的索引列放在前面
如性别,只有男、女两类,那么通过性别来筛选,只能缩减为原来的1/2。而如果根据城市,假设有48个城市,那么通过城市来筛选,便可将数据规模缩减为原来的1/48。显然后者的筛选效率更高
举例:查询居住在CA,名字以A开头的顾客
组合索引1: inx_lastName_state,先根据last_name排序,再根据state排序,查询过程如左图
组合索引1: inx_state_lastName,先根据state,再根据last_name,查询过程如右图
索引失效
1. 在进行查询时,索引列不能是表达式的一部分,也不能是函数的参数,否则无法使用索引。
例如下面的查询不能使用 points 列的索引:
select customer_id FROM customers WHERE points + 1 = 5
2. 组合索引顺序与where子句顺序应相统一
当创建(a,b,c)组合索引时,相当于创建了(a)单列索引,(a,b)组合索引以及(a,b,c)组合索引
想要索引生效的话,只能使用 a和a,b和a,b,c三种组合。当然,a,c组合也可以,但实际上只用到了a的索引,c并没有用到!
举例:复合索引的结构与电话簿类似,人名由姓和名构成,电话簿首先按姓氏对进行排序,然后按名字对有相同姓氏的人进行排序。如果知道姓,电话簿将非常有用;如果知道姓和名,电话簿则更为有用,但如果只知道名不知道姓,电话簿将没有用处。
所以说创建复合索引时,应该仔细考虑列的顺序。对索引中的所有列执行搜索或仅对前几列执行搜索时,组合索引非常有用;仅对后面的任意列执行搜索时,组合索引则没有用处。
本质原因:组合索引是按照字段依次排序生成的
3. 索引总结
索引的优点
1. 大大减少了服务器需要扫描的数据行数。
2. 帮助服务器避免进行排序和分组,以及避免创建临时表(B+Tree 索引是有序的,可以用于 ORDER BY 和 GROUP BY 操作。临时表主要是在排序和分组过程中创建,不需要排序和分组,也就不需要创建临时表)
3. 将随机 I/O 变为顺序 I/O(B+Tree 索引是有序的,会将相邻的数据都存储在一起)
索引的使用条件
1. 对于非常小的表、大部分情况下简单的全表扫描比建立索引更高效;
2. 对于中到大型的表,索引就非常有效;
3. 但是对于特大型的表,建立和维护索引的代价将会随之增长。这种情况下,需要用到一种技术可以直接区分出需要查询的一组数据,而不是一条记录一条记录地匹配,例如可以使用分区技术。