数据库工程师备考资料思维导图模板_ProcessOn思维导图、流程图

1.计算机硬件

系统的组成

CPU

运算器

执行逻辑和算数运算

ALU：算数逻辑单元

AC：累加器，用于计算累加

DR、PSW

控制器

决定计算机运行自动化，包括指令、中断、时序和总线控制逻辑

IR：指令寄存器

暂存指令

PC：程序计数器

存放下一条指令的地址

AR：地址寄存器

保存当前访问的内存地址

ID：指令译码器

把指令转换成控制信号

指令：对机器进行程序控制的最小单位

操作码

操作数

寄存器组

通用寄存器

专用寄存器

内部总线

数据总线

传送数据

双向的

地址总线

传送地址信息

单向的

控制总线

传送控制信号、时序信号、状态信息等

内部单向，整体双向

储存器

内部储存

外部储存

输入/输出设备

外设

进制转换

N进制转十进制

按照N的不同次方算权值，往左加一往右减一

十进制转N进制

整除取余法，一直除以N，余数从下往上算

计算机体系结构和储存系统

指令集

复杂指令集：CISC

简单指令集：RISC

流水线技术

流水线周期：各子任务中最慢的子任务执行时间

流水线执行N条指令的时间：T = 执行一条指令的时间 +（N-1）*流水线周期

吞吐率：单位时间里执行的指令数

存储系统

高速缓存Cache

介于CPU和内存之间

调和CPU和内存存取速度之间的差异

CPU读取时先看cache里有没有

地址映像

直接映像

主存的块与cache块对应关系固定，只能去存块号相同的

容易地址冲突

全相联影响

主存和cache都分成相同大小的块，随便存

利用率高但是变换成本高

组相联映像

前两种折衷，先cache分组，组直接映像、块全相联映像

主存组内的块随便存到cache对应的组内的块

输入输出技术

程序控制方式

无条件传送：外设总是准备好，无条件，随时接收和提供数据

程序查询方式：CPU利用程序查询外设状态是否准备好了

中断方式：CPU不等待、不执行查询程序，外设好了以后向CPU发送中断请求

DMA方式：主存和外设之间进行，由DMA硬件执行完成

通道方式和外围处理机方式

安全性&可靠性

对称加密

加解密使用相同的密钥

非对称加密

公钥和私钥

加密模型：公钥加密、私钥解密

认证模型（确认发送者身份）：私钥加密，公钥解密

信息摘要

哈希函数（Hash）

原文经过hash后产生摘要，摘要和原文一起传过去，接收者对原文再做一次hash与摘要进行对比，确保原文没有被篡改

数字签名和数字加密

数字签名：信息摘要用私钥加密，和原文一起发过去，接收者用公钥确认发送者以后与原文hash对比

数字加密：先用对称加密原文，然后把公钥用接收者的公钥做非对称，接收者先用自己私钥解密公钥，然后用公钥解密原文

计算机可靠性

t0到某时刻t时间段内正常运行的概率

串联可靠性：R = R1 X R2 X R3 …… X RN

并联可靠性：R = 1 - (1-R1)(1-R2)……(1-RN)

逻辑运算

与（AND）

或（OR）

异或(XOR)

相异为真,相同为假

非(NOT)

2.程序语言基础

编译程序和解释程序

解释程序

直接解释执行源程序

按源程序中语句执行顺序，逐条翻译并立即执行

编译程序

将源程序翻译成目标代码再执行

分为编译阶段和运行阶段

程序语言的数据成分和控制成分

常量和变量

是否可以改变

全局变量和局部变量

数据类型

基本类型

特殊类型

用户定义类型

构造类型

指针类型

抽象数据类型

控制成分

顺序结构：按顺序依次执行

选择结构：多分枝选择

循环结构：重复结算，初始化、循环体和循环条件

编译程序的过程

六个阶段

词法分析

识别单词符号

语法分析

分析短语和句子，是否复合语法规则

语义分析

分析语法结构，检查静态语义错误（类型分析和检查）

中间代码生成

代码优化

提升时间和空间的效率

目标代码生成

符号表和出错处理

中缀、前缀和后缀表达式

中缀

运算符放在中间，通常使用的表达式

前缀（波兰式）

运算符写在前面，不能用括号

后缀（逆波兰式）

运算符写在后面

3.数据结构与算法

线性结构

线性表

n个元素的有限序列

可以随机存取元素，按序号查找速度快

缺点：插入和删除需要移动元素

链表

用节点来存储元素

数据域+指针域

指针域放下个元素的地址

缺点：不能随机存取，只能按顺序访问元素

栈

后进先出

分为栈顶和栈底，top和bottom指针

储存空间预先申请或定义，可能会栈满

队列

先进先出

队头和队尾两个指针，front和rear指针

串

一串文字或符号的简称

作为整体处理

数组和矩阵

数组

适合顺序存储结构

以行或列为主序（m行，n列）

矩阵

对称矩阵

三对角矩阵

稀疏矩阵

三元组（i, j, aij）

数和二叉树

树

度：孩子节点的个数

叶子节点：度为零的节点

内部节点：度不为零的节点

层次：根是第一层，依此类推

树的高度：最大层次数

二叉树

有左右两颗子树，子树也为二叉树

满二叉树：每个非叶子节点都有两个子节点的二叉树

完全二叉树：每个节点的编号都和满二叉树一样

遍历

中序：左、根、右

前序：根、左、右

后序：左、右、根 

层序：从上至下，从左往右

最优二叉树

带权路径长度最短的树

带权路径长度：权 * 路径长度

构造最优二叉树

选最小的2个，权值相加作为父节点，然后用这个父节点作为新的元素

二叉查找树

左边所有的节点都小于根节点并且右子树都大于根节点

子树都是查找树

对二叉查找树做中序遍历，可以得到一个递增节点序列

图

图G是非空顶点集合V和顶点表示的边E组成的

有向图

有向边称为弧

起点为弧尾，终点是弧头

无向图

用圆括号表示

度：顶点相关的边数

分为出度和入度

路径

两个顶点之间的边的连线

路径长度为经历的边数

有向图中需要考虑方向

常用算法

排序算法

直接插入排序

与前面的元素挨个比较，找到位置后插入，后面的记录依次后移

冒泡排序

1、2相比，如果逆序，就交换，然后比较2、3，依此类推

简单选择排序

通过n-1次关键之间比较，从n-i+1个记录中选出最小记录和i个记录交换，当i等于n时完成有序排列

希尔排序

先分成若干子序列，分别进行直接插入，整个序列基本有序时，再对全体进行直接插入排序

快速排序

堆排序

先排成大小顶堆，输出堆顶以后再进行堆排序

归并排序

两两归并为一组，再四个记录归并一组，依此类推

4.操作系统

基本概念

组织软硬件资源、组织计算机工作流程、控制程序执行、提供接口

进程管理

三个状态：运行、就绪、阻塞

进程间同步

在系统中需要相互合作或协同工作的进程

进程间互斥：多个进程为了使用临界资源而互斥执行

临界资源

有些资源一次只能给一个进程使用‘

PV操作

实现进程同步与互斥的常用方法

S为可用资源数

互斥的时候S设置为1

P操作表示申请一个资源

S=S-1

V操作表示释放一个资源

S=S+1

PV成对出现

死锁

两个以上的进程都要对方已经占有的资源导致无法继续下取

系统中n个进程共享资源，当每个进程都要k个资源时，至少需要的资源数为： M = (k-1) * n + 1

银行家算法

进程资源图

R→P 代表已分配了多少

P→R 代表申请使用资源

储存管理

设备管理

文件管理

作业管理

5.计算机网络

6.数据库基础

数据抽象

物理层

在存储器中如何存储

索引

储存文件

逻辑层

描述数据库中存什么数据以及数据之间的关系

基本表

视图层

描述数据库的某个部分

视图

三级模式

外模式（视图）

也叫用户模式或子模式

用户与数据库系统的接口

概念模式（基本表）

也叫模式

数据库中数据的逻辑结构和特征描述

只涉及型的描述，不涉及具体值

内模式（索引）

也叫储存模式

描述数据物理结构和储存方式

定义内部记录类型、索引、文件组织方式等

两级映像

模式/内模式映像

外模式/模式映像

数据的独立性

数据的物理独立性

内模式发生改变时，数据的逻辑结构不变

数据的逻辑独立性

应用于数据库的逻辑结构是相互独立的

数据逻辑结构变化后，用户程序可以不修改，需要修改模式/内模式之间的映像

E-R模型

实体-联系模型

实体：由一组属性来表示，其中有一个属性可以唯一标识（主键）

联系

用菱形表示

一对一

一对多

多对多

二元联系

属性

简单属性和复合属性

单值属性和多值属性

NULL属性

派生属性

弱实体

一个实体的存在必须以另一个实体为前提

用双边矩形表示

关系用双边

特殊化

一些实体既有共性又有特殊性

数据模型构成三要素

数据结构

数据操作

完整性约束

7.关系数据库

相关名词

关系

类似变量

关系模式

雷系类型定义

属性

域

取值范围

候选码

可以决定所有属性的码

可以被选为主键或者联合主键的属性集合

主码

主键

主属性

候选码里面的主键

非主属性

外码

全码

所有的属性组都是候选码

关系数据库模式

关系的三种类型

基本关系

实际存在表

查询表

查询出来的表（select）

视图表

关系的完整性约束

实体完整性

主属性不能为空

参照完整性

依赖的属性必须完整

用户定义完整性

关系运算

并 Union

R∪S 就是把所有的数据聚合到一块

交 Intersection

R∩S就是把相同的数据拿出来

差 Difference

R-S就是在R中但是不在S中的数据

投影 Projection

依据条件生成原关系的部分列

重复的元组会被移除

选择 Selection

依据条件生成原关系的部分子元组集合

笛卡尔积 cross join

叉乘

行乘列

自然连接 join

inner join

用两个关系中相同的字段去连接

θ连接

先得到R和S的积，在寻找满足条件的元组

θ为=的时候，是等值连接

外连接

左外连接

以左表为主要的关系，Null值填充

先做自然连接，然后再找没出现的元组

右外连接

与左外连接相反

全外连接

左右外连接的并集

除 ÷

1、找相同的属性列

2、找相同属性列的值

3、不是相同属性列，其他列的值

4、其他列的值一样的，就在结果中

元组演算

原子公式

R(t)

R是关系名，t是元组变量

指一个元组

t[i]

指元组中的一个分量

可以加上θ

t[i]和u[j]

t和u代表两个不同关系里的分量

公式定义

全程量词 ALL

全部都要满足才能被选中

存在量词 Exist

只要存在一个条件满足就可以被选中

技巧

化繁为简

慢慢分析

查询优化

笛卡尔积、连接运算最耗费时间和空间

提早执行选择运算

合并乘积和后面的选择运算为连接运算

将投影和后面的运算同时进行

将投影运算与其后的二目运算同时进行

规范化

第一范式 1NF

关系的每一个分量都是不可再分的数据项

存在问题

数据冗余

更新异常

插入异常

删除异常

第二范式 2NF

关系R属于1NF，且每个非主属性都完全依赖于码

当1NF消除了非主属性对码的部分函数依赖

部分函数依赖就是码的部分属性可以决定一个属性

完全函数依赖就是只有码里所有的属性才能决定属性

第三范式 3NF

关系模式R（U，F）中不存在码X，属性组及非主属性Z，使得X→Y，Y→Z成立

当2NF消除了非主属性对码的传递函数依赖

巴斯克范式 BCNF

关系模式R属于1NF，X→Y且Y不是X的子集时，X必含有候选码

当3NF消除了主属性对候选码的部分函数依赖和传递函数依赖

有如下性质

所有非主属性对每一个候选码都是完全函数依赖

所有主属性对每一个不包含它的码，也是完全函数依赖

没有任何属性完全函数依赖于非候选码的任何一组属性

第四范式 4NF

限制关系模式的属性间不允许有非平凡且非函数依赖的多值依赖

如果X→→Y，U=X+Y+Z，如果Z为空，就是第四范式（平凡），否则就不是（非平凡）

总结

1NF：属性不可再分

2NF：消除了非主属性对候选码的部分函数依赖

3NF：消除了非主属性对候选码的传递依赖

BCNF：消除了主属性对候选码的部分函数依赖和传递依赖

4NF：属性间没有非平凡且非函数依赖的多值依赖

Armstrong公理

Armstrong公里

自反律

大集合决定子集

增广律

左右两边同时加上一个属性，依然成立

传递律

A→B，B→C则A→C

合并规则

A→B，A→C则A→BC

伪传递律

A→B，CB→D则CA→D

分解规则

A→B，C是B的子集，则A→C

函数依赖的闭包

关系模式R（U，F）中为F所逻辑蕴含的函数依赖的全体称为F的闭包，记为F+

属性的闭包

属性闭包为所有能有X决定的属性集合

先把X写下来，然后找X里的属性可以直接推出的属性，把这些属性写在一起以后，继续推

求候选码

分类

L：只出现在依赖集左侧

R：只出现依赖集右侧

LR：两边都出现

NLR：左右都没出现的

结论

若X是L类属性，则X必为任意候选码的成员，若X闭包属性为U，则X是唯一的候选码

若X是R类属性，则X不是R任意候选码的成员

若X是NLR类属性，则X必为任意候选码的成员、

若X是L类和NLR类属性组成的属性集，若X的闭包属性为U，则X是唯一的候选码

步骤

将属性分类

L：一定是

R：一定不是

LR：有可能

NLR：一定是

将L和NLR组合起来，设为P，求他的闭包属性集，如果是全集，那么他就是候选码

如果P的闭包属性不是全集，则依次将LR和P组合起来求闭包，如果闭包是U，就是候选码

最小函数依赖集

满足以下条件就是最小函数依赖集

所有函数的依赖右侧只有一个属性

没有冗余的函数依赖

所有函数依赖的左侧没有冗余的属性

无损连接

一个关系分解成若干子模式，通过自然连接和投影等运算，可以还原成原来的关系

U1 ∩ U2 → U1 - U2 或 

U1 ∩ U2 → U2 - U1

8.SQL

核心动词

Select 查询

Create、Drop、Alter

Insert、Update、Delete

Grant、Revoke

索引

作用

保证记录唯一性

加快数据检索速度

加快表之间的连接

减少分组和排序的时间

优化隐藏器，提高系统性能

建立

INDEX<索引名>ON<表名>

物理层面。内模式

分组查询

group by

having

加条件

集合操作

Union 并

Union ALL 不去掉重复行

Intersect 交

Except 差

外连接

嵌入式SQL

前面要加EXEC SQL

主变量（共享变量），用DECLARE 声明，使用的时候前面加“：”

游标

CURSOR FOR 后面跟select 语句

存储过程

IN 输入型参数

OUT 输出型参数

IN OUT 两者都可

11.数据库设计

联系向关系模式的转换

一对一联系

联系转换成独立的关系模式，取名为联系的名称，关系模式的属性包括该联系所关联的两个实体的码及联系的属性，关系的码取自任一方的实体的码

联系归并到两个实体的任意一方

一对多联系

联系转成独立的关系模式

码是多方实体的码

联系归并到两个实体的多方

属性中增加一方实体的码

码保持不变

多对多联系

转成独立的关系模式

码是两方码的属性组

12.事务

信息

是操作序列，这些操作，要么都做，要么都不做

BEGIN TRANSACTION 事务开始

END TRANSACTION 事务结束

COMMIT

看要不要写commit work

已经提交的不能撤销

ROLLBACK 回滚

看要不要写rollback work

特性

原子性

要么都做要么都不做

一致性

数据不会因为事务的执行而遭受破坏

隔离性

一个事务的执行不能被其他事务干扰

并发事务在执行过程中对统一数据进行操作，是互相隔离的

持久性

事务一旦提交，改变是永久的

并发控制

事务调度

串行调度

一个事务所有操作执行完成再执行另一个

并发调度

利用分时的方法同时处理多个事务

T0和T1拆分着执行

并发是否正确，判断是否与任意一次串行的结果一致

三个问题

丢失修改

两个事务修改同一个数据，导致一个事务被另一个事务覆盖

读脏数据

读取了其他事务修改的值，但该修改后来又被撤销了

不可重复读

事务对同一个数据两次读取结果不同，原因两次读取之间被另一事务修改了

并发调度的可串行性

多个事务的并发执行是正确的，当且仅当其结果与某一次序的串行执行他们的结果相同，称这种策略为可串行化的调度

可串行性是事务正确性的准则

可恢复调度

当事务T1要读事务T0写的数据时，T0事务必须先于T1提交

并发控制技术

排它锁 X锁

写锁

事务T加上X锁以后，只有T可以读取和修改，其他事务也不能加锁

共享锁 S锁

读锁

加了以后只能读取不能修改

其他事务也可以通过加S锁来读取

有了S锁，就不能加X锁修改

封锁协议

一级封锁协议

事务T在修改数据之前必须先加X锁

事务结束才能释放

解决了丢失修改的问题

二级封锁协议

在一级协议上增加读取前必须加上S锁

读完即可释放

解决了脏数据问题

三级封锁协议

在一级协议上增加读取前必须加上S锁

事务结束才释放

解决了不可重复读的问题

两段锁协议

定义

同一事务对任何数据进行读写之前必须对该数据加锁

在释放一个封锁指后，该事务不再申请和获得任何其他封锁

获得封锁：扩展阶段

释放封锁：收缩阶段

遵循两段锁协议，一定是可串行化的

不遵循，可能是串行化，也可能不是

也可能产生死锁

事务的隔离级别

Read Uncommit 读未提交

最低级别，任何情况都无法保证

Read Commited 读已提交

避免读脏数据

repeatable read 可重复读

避免读脏数据、不可重复读

Serializable 串行化

最高级别

幻读

事务A查到N条数据，然后事务B又插了M条数据

A再次查询发现数据变成N+ M条了,就产生幻读了

数据库故障

种类

事务故障

执行的时候,事务本身的故障

逻辑错误

系统错误(如死锁等)

UNDO恢复

系统故障

软硬件引起的,丢失了内存中的信息

UNDO+REDO

UNDO 未完成的事务

REDO 已提交的事务

介质故障

存储介质发生故障(物理层面)

重装数据库

数据库备份

静态\动态转储

海量\增量转储

日志文件

数据库镜像

数据库恢复

恢复的两个操作

撤销事务(UNDO)

反向扫描日志

查找更新操作,进行逆操作,用日志记录中更新前的值写入数据库

插入的记录删除,删除的记录插入

一直到事务开始标志

重做事务(REDO)

已提交的事务重新执行

正向扫描日志

重新执行操作,到事务结束标志

事务故障

UNDO

系统故障

UNDO撤销未完成的任务

REDO重做已提交的事务

介质故障

重装数据库

重载最近一次备份的日志

按照系统故障来恢复

检查点机制

对于检查点后提交的事务,REDO

对于检查点后没提交的事务,UNDO