复试--关系型数据库

大数据框架：节省创建工程时间

大数据计算框架，大数据存储框架

负载均衡：分散到多个服务器上

Hadoop：

1.Hadoop Common：核心，对其他模块支撑，包含对底层文件、网络访问、数据类型的支持，以及对象序列化反序列化操作等。

2.Hadoop Distributed File System（HDFS）:分布式文件系统，存储大量数据。

3.Hadoop YARN：任务调度与资源管理

4.Hadoop MapReduce：基于YARN的并行大数据处理组建。

Hadoop- Hadoop MapReduce：

解决并行任务的模型，将任务分散到多个计算节点，最后合并结果。（并发计算后汇总结果）

流程：输入文件 -> Map -> 中间结果 ->Reduce -> 结果

Map: 读输入文件，并构造KEY-VALUE文件

Reduce：读中间结果，对不同的key分给不同的Reduce程序。

两类进程：MRAppMaster，Yarnchild

运行流程：

启动mr，启动MRAppMster，根据任务信息，计算maptast实例数量。

启动maptask。

关系型数据库：

许多表组成

关系：表；

元组：行；

属性：列；

域：属性的可能集合

码

超码：一个或多个属性的组合，这些组合可以在一个关系中唯一标识一个元组。

候选码：最小的超码（去除超码中无关信息）

主码：被选中的候选码

外码：关系模式（表1）中包含关系模式（表2）的主

码，该属性是表1参超表2的外码

设一个关系为R(U)，X和Y为属性集U上的子集，若X→Y且X不包含Y，则X→Y为非平凡函数依赖。

平凡函数依赖：Y是X的子集，且有X→Y，一组属性决定所有子集。（职工号,性别）→职工号”和“（职工号,性别）→性别”,因为对于任何给定的一个元组中的职工号和性别的组合值。

函数依赖：关系中对于属性（组）Ｘ的每一个值，属性（组）Ｙ只有唯一的值与之对应，则称Ｙ函数依赖于Ｘ，或称Ｘ函数决定Ｙ，记为Ｘ→Ｙ。

部分函数完全依赖：A→B,又有A的真子集A’,有A’→B,则A→B为部分函数依赖，否则为完全函数依赖。

非平凡函数依赖：Y不是X的子集，且有X→Y。

关系代数：

抽象的查询语言

传统：并、差-、交∩、笛卡儿积×

选择：select σ

投影：project ΠA®

自然连接：join R AθB

除：同时从行和列的角度 R÷S

范式：

某一级别关系模式的集合（低级到高级过程成为规范化）

第一范式： 属性不可再分

第二范式：没有部分依赖，非主属性完全依赖域主键

第三范式：非主属性不传递依赖主键

标准语言SQL:

核心功能；L:Language

(Data Definition L)定义(

CREATE

,

DROP

,

ALTER

)

(Query L)查询(

SELECT

)

(Data Manipulation L)操作(

INSERT

,

UPDATE

,

DELETE

)元组

(Data Control L)控制(

GRANT

,

REVOKE

)

DDL: 三级模式模式、外模式、内模式基本对象为：表、视图、索引。 数据定义功能：定义表，定义视图，定义索引，定义数据库。

ALTER TABLE <表名>
[ADD <新列名><数据类型>[完整性约束]]
[DROP<完整性约束名><完整性约束名>]
[MODIFY<列名> <数据类型><数据类型>]；

建立/删除 索引：
CREATE [UNIQUE] INDEX 索引名 
ON 基本表名(列名[次序][,列名[次序]]…)
DROP INDEX <表名>.<索引名>;
           

QL:

将字符串转换为日期类型数据：CAST

[WHERE <条件表达式>]
[GROUP BY <列名1>[HAVING <条件表达式>]]
[ORDER BY <列名2>[ASC|DESC]];

CAST函数将该条件写成
InDate>=CAST（'2004-12-31'AS DateTime）

IN谓词实际上是多个OR
集函数：
COUNT([DISTINCT|ALL] *) 统计元组个数 
COUNT([DISTINCT|ALL] <列名>) 统计一列中值的个数 
SUM([DISTINCT|ALL] <列名>) 计算一列值的总和（此列必须是数值型） 
AVG([DISTINCT|ALL] <列名>) 计算一列值的平均值（此列必须是数值型） 
MAX([DISTINCT|ALL] <列名>) 求一列值中的最大值 
MIN([DISTINCT|ALL] <列名>) 求一列值中的最小值 

GROUP组进行筛选 HAVING
           

视图： 逻辑表

CREATE VIEW <视图名>[(<列名１>,<列名２>,…)]
AS <查询子句> [WITH CHECK OPTION]
           

WITH CHECK OPYION子句是为了防止用户通过视图对数据进行增加、删除、修改时

DCL:

并发控制：多个用户修改

GRANT 授权

GRANT <权限> [，<权限>]…[ON <对象类型><对象名>]
TO <用户>[，<用户>]…[WITH GRANT OPTION];
           

WITH GRANT OPTION 还可以传播权限

REVOKE 收回权限

REVOKE <权限>[,<权限>]... 
[ON <对象类型> <对象名>] 
FROM <用户>[,<用户>] ... ;
           

事务

事务：是满足ACID特性的一组操作。

ACID:原子性(atomicity)，一致性(consistency)，隔离性(Isolation)，持久性(Durability)。

四个特性不是平级关系：①只有满足一致性，事务执行结果才正确。②无并发时，事务串行，满足隔离性，如果满足原子性，一定满足一致性。③并发时，事务并行，不仅需要满足原子性还需要满足隔离性，才能满足一致性。④持久性是应付数据库崩溃。

一致性问题：①丢失数据：第二次事务修改覆盖了第一次，写后写。②脏数据：写后读，读时修改。③不可重复读：读后写。④幻影读：读后写，读时插入。

封锁

行封锁，表封锁。只锁定修改的部分，锁定的数据量越少，锁争用可能小越小，并发程度越高，但（获取、释放、检查锁状态）增加系统开销，封锁时需要权衡锁开销和并发程度。

锁类型：

排它锁（Exclusive），X锁，写锁。

共享锁（Shared），S锁，读锁。

事务对数据对象A加了 X 锁之后，其他事务不能对A加任何锁。（其他事务不能读和写）

事务对数据对象A加了 S 锁之后，只能读取。但其他事务也可以加S锁，不能加X锁。（别人都可以读）

意向锁（Intention Locks）。IX/IS：表级别的锁：事务稍后会将表中某行加上X或者S锁。

即：事务获得某行对象的S锁之前，必须获得表的IS及其以上锁。事务获得某行对象X锁之前，必须获得表的IX锁。

封锁协议：

三级封锁：

一级封锁协议：事务修改数据A时加X锁，事务结束时释放：解决丢失修改。

二级：一级基础上，读取时加S锁，读取完释放。防止修改时读取，解决丢失修改和读脏数据。

三级：二级基础上，事务结束才释放S，防止读取时修改，解决丢失修改，读脏数据以及不可重复读。

两段锁：事务开始和直到ROLLBACK和COMMIT之前都是加锁阶段。

索引

数据结构：

B+：非叶子结点不保存数据，只是索引。所有数据保存在叶子结点中。并且叶子节点可以顺序指针访问。

B-：所有叶子结点位于同一层，多路平衡查找树。

MySQL中称索引为键(KEY)：

索引结构类型

（1）B+Tree索引是默认，适用于全键值，键值范围和键前缀（最左前缀）。

（2）hash索引，只支持精确查找，失去有序，不能部分和范围查找。

（3）全文索引，倒排索引，关键词到文档的映射。

（4）空间数据索引，必须使用GIS相关的函数维护。

优点：减少扫描行数。避免排序和分组需要创建的临时表。随机I/O变为顺序I/O，因为B+是有序的，相邻数据存储在一起。 非常适合用于排序、分组、范围搜索创建索引。

缺点：降低INSERT/UPDATE效率，可能重建索引。

优化策略：①独立的列，不能是表达式或者函数参数。②多个列作为条件查询时多列索引比单列更好。③前缀索引：BLOB,TEXT,VARCHAR类型的列，指定前缀长度。④覆盖索引：只缓存索引，数据用OS缓存。只访问索引可以不系统调用，省时。

使用场景：① 非常小的表，全表扫描更高效。②中大型的表，建立索引非常有效。③特大型的表：使用分区技术。 直接分区需要查询的一组数据。

分区技术：

水平分区和垂直分区。

• 水平分区一定要通过某个属性列分区。

• 垂直分区：减少表的宽度。

  分区类型：range,list,hash,key

//范围
parition by range(属性列){
	patition p1 values less than()//范围A
}
parition by list(属性列){
	patition p1 values in ()//分区依据
}
HASH分区使用的用户定义的表达式
partition by hash(year(birthdate))
partitions 4;
KEY分区的哈希函数是由MySQL 服务器提供
partition by key(birthdate)
partitions 4;

复合分区
partition by range(salary)
subpartition by hash(year(birthdate))
subpartitions 3
(
partition p1 values less than (2000),
partition p2 values less than maxvalue
);

分解分区：
alter table [] reorganize patition p1 into{
parition p1 values than (); // 分解成A组
}
合并分区
reorganize partition p1,p3 into
(partition p1 values less than (1000));
           

B(B- ) , B+, AVL

平衡二叉树物理结构上使用数组存储的，逻辑上相邻的结点在物理上比较远，不符合局部性原理。

B数：有序数组+平衡多叉树。每个结点可以以存储多个关键字，磁盘读取操作次数就会减少，树的深度也会小。所以B树比AVL更适合。

B+树：有序数组链表+平衡多叉树。