408
一、计算机网络
1.计算机网络体系结构
协议由语法、语义和同步三部分组成。
语法：规定数据格式 语义：规定所要完成的功能 同步：规定完成的条件、时序关系。
接口是相邻两层交换信息的节点，逻辑概念。
服务是指下层为紧邻的上层提供功能调用，垂直功能。
2.ISO/OSI & TCP/IP
OSI参考模型：物理层、数据链路层、网络层、传输层、会话层、表示层、应用层。其中，低三层称为通信子网，高三层为资源子网。
1.物理层：（规定了一些物理参数和电气特性）
为数据端设备透明地传输原始比特流。
2.数据链路层： 帧，将网络层传来的IP数据报组装成帧。
封装成帧、差错控制、流量控制、传输管理etc。
3.网络层：数据报
任务：把网络层数据单元从源地址传到目的端，包括路由选择、流量控制、拥塞控制、差错控制、网际互联etc。
4.传输层：tcp/udp
负责主机两个进程之间的通信，提供端到端的可靠传输服务，端到端的服务质量控制。
difference：数据链路层提供点到点，传输层是端到端。
5.会话层：
为表示层实体和用户建立同步
6.表示层：
不同机器编码、表示方式的变化层
7.应用层：
提供不同的网络应用要求，例如WWW、HTTP、FTP服务
tcp/ip：结构如图所示
3.物理层
4.数据链路层
二、数据库原理
1.B树又称多路平衡查找树：
提高磁盘查找效率
非叶节点：
[n P0 K1 P1 K2 P2 ... Kn Pn]k表示为关键字、p表示为指针，Pi-1所指向的子树关键字均小于Ki，Pi所指向的子树的关键字均大于Ki
另：所有的叶节点都出现在同一层次上，并不带任何信息
$$
对于n个关键字，阶数为m，高度为h的B树有以下性质 \
log_m{(n+1)} \leq h \leq log_{[m/2]}((n+1)/2)+1
$$
B树的插入、删除：
插入：
1）定位
查找插入该关键字的位置，最底层非叶子节点
2）插入
插入后不会违反定义，插入后结点关键字个数在属于合法区间
删除：终端节点 ||非终端节点
1） 直接删除（不破坏定义）
2）借兄弟节点，并修改双亲节点
3）与兄弟节点合并
4） 删除非终端节点：1.先与终端节点替换再删除 2.先合并子树再执行删除
chapter1.绪论
1、数据、数据库DB，数据库管理系统DBMS,数据库系统DBS，数据库管理员DBA。
2、DBMS主要功能：数据定义、数据组织存储管理、数据操纵、数据事务管理和运行管理、数据库建立和维护、其他。
3.DBS特点：数据结构化、数据共享性高冗余度低易扩充、数据独立性（二级映像）、统一管理（安全、完整性、并发、恢复）
4.数据模型：1类-概念模型，二类-逻辑模型、物理模型
5.概念
实体、属性、码、实体型、实体集、联系
数据模型组成：数据结构、数据操作、完整性约束三部分
关系数据库的约束条件：实体完整性、参照完整性、用户定义完整性
6.DBS三级结构模式
模式（所有用户的公共数据视图）、外模式（可见视图、是模式的子集）、内模式（与数据库11对应 表示存储方式）
二级映像：外模式/模式映像、模式/内模式映像（修改映射规则）
chapter2.关系数据库
- 选择、投影、并、差、笛卡尔积、除 基本运算
- 实体完整性、参照完整性、用户定义完整性：实体完整性、参照完整性必须满足
- 实体完整性：主属性不为NULL
- 参照完整性：关系关系之间的引用中，F是关系R外码，与S上Ks对应，满足或者F上每个属性值为NULL或者=S中某个主码值
chapter4.数据库安全性
chapter5.数据库完整性
- 定义参照完整性 Foreign Key
- 参照完整性检查、处理（级联操作、No ACT、setNull）
- 断言检查
- 触发器（before/after）
chapter6.关系数据理论
- 一个关系模式是五元组$R(U,D,DOM,F)$,简化为$R<U,F>$
- 1NF每个分量是不可分的数据项
- 数据依赖:函数依赖/多值依赖
- 关系模式存在的一些问题：
- 数据冗余
- 更新异常
- 插入异常
- 删除异常
- 规范化：
- 函数依赖（平凡非平凡、完全部分）
- 码（候选码【主属性】、超码、主码）
- 范式：满足不同程度要求
- 2NF：没一个非主属性完全依赖于任何一个候选码
- 2nf异常：插入异常、删除异常、修改复杂
- 3NF：不存在传递依赖
- BCNF：3nf修正，对任意映射$X→Y$且Y不包含于X，X必定含有码
- 如图：
- 公理系统：
- 自反、增广、传递
- 合并、伪传递、分解
- 闭包
- 模式分解
- 无损连接、保持函数依赖
- 分解步骤
chapter7.数据库设计
- 需求分析设计
- 概念结构设计
- 逻辑结构设计
- 物理结构设计
- 数据库实施阶段
- 数据库运行和维护阶段
chapter10.数据库恢复技术
- 事务概念 开始、提交、回滚
- ACID:原子性、一致性、隔离性、持续性
- 封锁协议
- 一级封锁协议，在事务T修改R前必须添加X锁，直到事务结束才释放。 解决丢失修改
- 二级封锁协议在一级上增加了T对R的读取前必须增加S锁，读完释放。解决了读脏数据
- 三级封锁，在一级协议基础上增加T在读取R前增加S锁，事务结束才释放。解决了读脏数据和不可重复读
- 可串行化调度
- 可串行性是并发事物正确调度的准则
三、数据结构
1.红黑树
性质：
1.结点是红/黑色
2.根节点为黑
3.所有叶子节点都是黑色 叶子为NIL节点
4.每个红色结点的子结点都是黑色（从每个叶子到根没有连续的红色结点）
5.从一任意结点其每个叶子的所有路径黑色结点数目相同
6.从根到叶子最长路径不多于最短的可能路径的两倍长
