软件设计2

1、文件管理

1.1、索引文件结构

索引文件结构中，直接索引即索引直接指向物理块，有多少个直接索引，通过直接索引就能访问多少个物理块。

一级索引，即索引节点指向的物理块用来存放地址项，一个物理块能表示多少个地址项，则一个一级索引就能表示多少个物理块。

二级索引，即索引节点指向的物理块，存放的是一级索引的地址块地址，一个物理块能表示 n 个地址项，则一个二级索引就能表示 n² 个物理块。

例题：

2、设备管理

2.1、数据传输控制方式

程序控制方式：程序控制方式也叫查询控制方式。当程序要传输数据时，CPU发出I/O指令。CPU定期地查询I/O系统，确定操作是否已经完成。由CPU主动查询I/O系统，完成主机与外部设备间的数据传输。方法简单，硬件开销小，但CPU因要不停执行查询操作，降低了效率。
程序中断方式：使用程序中断方式，当I/O系统与外部设备传输数据时，CPU无须等待，也不必去查询I/O系统的状态，当I/O系统完成了数据传输后，以中断信号通知CPU。CPU保存正在执行程序的现场，转入I/O中断服务程序完成与I/O系统的数据交换，然后返回原主程序继续执行。中断方式因为CPU无需等待而提高了效率。
DMA（直接内存存取）方式：DMA控制方式是在主存和外设之间直接建立数据通路进行数据的交换处理。DMA方式是使用DMA控制器来管理和控制数据传输的。

2.2、微内核操作系统

3、数据库系统

3.1、三级模式两级映射

数据库领域公认的标准结构是三级模式结构，它包括外模式、概念模式和内模式，有效地组织、管理数据，提高了数据库的逻辑独立性和物理独立性。外模式 --- 视图，内模式 --- 存储文件，概念模式 --- 基本表

外模式又称子模式或用户模式，对应于用户级。它是某个或某几个用户所看到的数据库的数据视图，是与某一应用有关的数据的逻辑表示。用户可以通过外模式描述语言来描述、定义对应于用户的数据记录(外模式)，也可以利用数据操纵语言(Data Manipulation Language，DML)对这些数据记录进行操作。

概念模式又称模式或逻辑模式，对应于概念级。它是由数据库设计者综合所有用户的数据，按照统一的观点构造的全局逻辑结构，是对数据库中全部数据的逻辑结构和特征的总体描述，是所有用户的公共数据视图(全局视图)。它是由数据库管理系统提供的数据模式描述语言(Data Description Language，DDL)来描述、定义的。

内模式又称存储模式，对应于物理级。它是数据库中全体数据的内部表示或底层描述，是数据库最低一级的逻辑描述，它描述了数据在存储介质上的存储方式和物理结构，对应着实际存储在外存储介质上的数据库。

总之，数据按外模式的描述提供给用户；按内模式的描述存储在磁盘上；而概念模式提供了连接这两级模式的相对稳定的中间层，并使得两级中任意一级的改变都不受另一级的牵制。

3.2、关系代数

笛卡尔积（x）也就是S1的每个记录分别跟S2的所有记录的组合。

自然连接（）：

3.3、规范化理论

超键就是能唯一确定记录的属性集，比如：学号+姓名+年龄。候选键就是超键去除掉多余属性后的属性，比如学号本身就可以确定唯一记录，所以姓名和年龄都是多余的，学号就是候选键。候选键可能有多个，比如学号、身份证号，此时可以任选一个作为数据库表的主键。

如何求候选键：

也就是，先画有向图，如果有入度为0的属性（入度为0就是说没有箭头指向它），那就找入度为0的属性，以它为起点，如果能走遍全部结点（不一定要一次性走遍），那该属性就是候选键。如果入度为0的属性不能遍历全部结点，那就找既有入度又有出度的结点，如果该结点能遍历全部属性，那该结点就是候选键。

例题：

第一题，先画出有向图，可以知道A1入度为0，以A1为起点，能走遍全部结点，所以A1就是候选键。

第二题，画出有向图，可以看到只有ABCD组合起来才能遍历全部属性，所以候选键就是ABCD。

第三题，有向图中没有入度为0的属性，那就找到既有入度又有出度的结点，可以看到A和B都能遍历所有结点，所以答案选B：A和B

3.4、范式

范式级别越高越规范，想达到高范式，必先达到低范式的要求。一个低一级的关系模式通过模式分解可以转化为若干个高一级范式的关系模式的集合，这个过程叫做规范化。

3.4.1、第一范式

属于第一范式关系的所有属性都不可再分，即数据项不可分。第一范式强调数据表的原子性，是其他范式的基础。如下图所示数据库就不符合第一范式：

上表将商品这一数据项又划分为名称和数量两个数据项，故不符合第一范式关系。改正之后如下图所示：

上表就符合第一范式关系。

但日常生活中仅用第一范式来规范表格是远远不够的，依然会存在数据冗余过大、删除异常、插入异常、修改异常的问题，此时就需要引入规范化概念，将其转化为更标准化的表格，减少数据依赖。

3.4.2、第二范式（消除了部分函数依赖）

第二范式存在数据冗余、更新异常、插入异常、删除异常的问题。如果满足第一范式，并且主键只有一个属性的那就一定是第二范式。如果主键只有一个属性值那就意味着已经消除了部分函数依赖。

比如：一个表中有学号、课程号、成绩、学分。学号+课程号组成主键，成绩完全依赖主键，而学分部分依赖主键，因为课程号就能确定学分，所以不符合第二范式。

3.4.3、第三范式（消除部分函数依赖和传递函数依赖）

满足第二范式，并且非主属性没有传递依赖于主键时，就是第三范式。

比如：学号、姓名、系号、系名、系楼层，学号是主键，此时就不满足第三范式，因为学号确定系号，系号又确定系名、系楼层，此时存在传递依赖。也就是非主属性全部都是直接依赖于主键，而不是间接依赖于主键。

3.4.4、BCNF（BC范式）

也就是说把所有的依赖集都列出来，而左边的部分必定是候选键的就满足BC范式。

例题：

候选键有SJ和TJ，所有的依赖集有：SJ -> T，T -> J，而依赖集所有的左边部分SJ是候选键，但T不是候选键，所以不满足BC范式。

3.5、并发控制

3.6、数据库完整性约束

实体完整性：实体完整性是指关系中的主属性值不能为Null且不能有相同值。

参照完整性：参照完整性是指关系中的外键必须是另一个关系的主键有效值，或者是NULL。

用户定义的完整性：

3.7、数据备份

4、计算机网络

基于TCP：HTTP、FTP、Telnet、SMTP等等

基于UDP：SNMP、DNS等等

4.1、特殊含义的IP地址

5、加密技术

5.1、对称秘钥加密算法

对称加密算法又称共享秘钥加密。

5.2、非对称秘钥加密算法

非对称秘钥加密算法又称公开秘钥加密。

例题：设计一个邮件加密系统

邮件内容大，所以使用对称加密算法加密邮件内容。对称加密算法的秘钥使用 B 的公钥进行加密，B接收到后就可以使用自己的私钥进行解密，得到对称加密的秘钥，解密出邮件内容。要想做到不可抵赖，先生成一个邮件摘要，然后使用 A 的私钥加密，B 接收到后使用 A 的公钥解密得到摘要明文，并且用邮件内容生成摘要，摘要对比正确就说明内容没有被篡改。因为是用 A 的公钥进行解密的，可以证明这个文件确确实实是 A 发送来的，因为其他人并没有 A 的私钥。