数据库系统工程师230418

23年 数据库系统工程师备考资料 凭借这份资料 作者已通过考试。希望对大家有所帮助！

数据库系统工程师备考·

• 计算机系统知识
  • 计算机硬件基础知识
    • 组成
      • CPU
        • 运算器
          • 功能
            • 算术运算
            • 逻辑运算
          • 组成
            • ALU (Arithmetic and Logic Unit)
              • 算术逻辑单元
                • 运算器核心模块
            • AC
              • 累加寄存器
                • ALU支撑工作区
                  • 运算不仅需要有清晰的逻辑(ALU)还要有良好的记忆力，知道自己需要对什么数据之间进行运算，而AC就是这一个个单个最小的、用于运算的数据记忆神经元。注意！！是最小的、用于运算的数据单元，要和DR或磁盘存储这些存储数据区分开来。
            • DR
              • 数据缓冲寄存器
                • CPU 磁盘或内存数据暂放区
            • PSW
              • 状态条件寄存器
                • 运算接口存放区域
                  • 和AC区分开，PSW能实现例如线程等待的一个结果暂存，唤醒时可以立马用上这个线程的处理结果。
        • 控制器
          • 功能
            • CPU管家，程序运行的核心控制模块
          • 主要组成
            • IR
              • 指令寄存器
                • 存控制指令，而不是运算指令
            • PC
              • 程序计数器
                • 下一条指令地址记录 是一个指针概念
            • AR
              • 地址寄存器
                • 保存将要访问的内存单元地址
            • 程序计数器（PC）存储当前指令执行后要从内存中取出的下一条指令的地址。 这个来自 PC 的地址被加载到地址寄存器 (AR)： AR<--PC 地址寄存器（AR）给出的来自内存位置的指令被加载到指令寄存器（IR）中： IR<--M[AR] 程序计数器递增到下一条指令的地址： PC<--PC+1
            • ID
              • 指令译码器
                • 对操作码进行识别并进行控制处理
                • 补充概念
                  • 指令
                    • 概念
                      • 对机器进行程序控制的最小单位
                    • 组成
                      • 操作码
                        • 如linux中的 mov rf等
                      • 操作数
        • 寄存器
          • 专用寄存器
            • 运算器和控制器中的寄存器
          • 通用寄存器
      • 存储器
        • 分类
          • 按寻址方式分
            • 随机存储器RAM Random Access Memory
              • 因为是随机存入 所以对任何一个存储单元的访问时间是相同的
            • 顺序存储器SAM Sequentially Addressed Memory
              • 访问数据时间与数据存储位置有关
            • 直接存储器DAM Direct Addressed Memory
              • 介于随机和顺序之间，对磁道寻址是随机，在一个磁道内是顺序寻址
          • 按工作方式分
            • 读写存储器
            • 只读存储器
              • 固定只读存储器 ROM Read Only Memory
                • 一般存放系统程序BIOS
              • 可编程的只读存储器 PROM
                • 一次性写入，不能再修改
              • 可擦除可编程的只读存储器
                • 紫外线擦除 EPROM
                • 电擦除 EEPROM
                  • 闪速存储器(闪存)
          • 按存储器位置
            • 内存
            • 外存
              • 磁盘存储器
                • 组成及概念
                  • 盘片组
                    • 盘片
                      • 磁道
                        • 盘片划分许多同心圆，最外圈为0道
                        • 扇区
                          • 圆周划分若干段的其中一段
                    • 磁头
              • 光盘存储器
      • 输入/输出设备
        • 程序控制方式
          • 需要CPU参与
            • 无条件传送
              • 如外设这种 是无条件接收和提供数据的
            • 程序查询方式
              • 多了个状态查询，如音响、打印机等 查询你有准备再传数据
            • 中断方式
              • 外设准备好就通知CPU CPU会暂停手上的活进行数据提供
          • 不需要CPU参与
            • DMA方式(直接内存存取方式)
              • 数据传输在主存和外设之间进行 由DMC控制器控制DMA硬件直接执行
            • 通道方式和外围处理机方式
      • 内部总线Bus
        • 总线：是物理层面的总线，涉及到类似水管布线之类的
        • DB
          • 数据总线
            • 特点
              • 双向的 即CPU↔内存/其他io
            • 作用
              • DB宽度决定了每次交换数据的位数
        • AB
          • 地址总线
            • 特点
              • 单项 即CPU->其他设备
            • 作用
              • AB宽度决定CPU寻址能力
        • CB
          • 控制总线
            • 特点
              • 单条来看是单向的 即CPU⇄内存/其他io 但总体来看是双向的
            • 作用
              • 用来传送控制、时序或状态信号
    • 进制转换
      • 进制缩写
        • 二进制B
        • 八进制O(字母)
        • 十进制D
        • 十六进制H
      • 转换方法
        • 基于十进制
          • 其他进制转十进制
            • 按权展开
          • 十进制转其他进制
            • 整数取余
        • 基于二进制 (八进制和十六进制与二进制的转换可以用)
          • 总结： 八进制的 每位转成3个二进制 十六进制的每位转成4个二进制 归根结底也还是十进制转二进制 所以 转二进制不会转可以用上面十进制的“整数取余法”
    • 拓展
      • 周期
        • 指令周期
          • 取指令->分析指令->执行指令 这一个完整过程所需要时间
        • 时钟周期(振荡周期)
          • 最基本、最小的时间单位。CPU完成一个最基本动作时间
        • 总线周期
          • CPU一次占用总线访问数据时间
        • CPU周期
          • CPU从内存中读取一条指令的最短时间
      • io接口功能
        • 数据缓冲和暂存
        • 设备状态检测和反馈
        • 控制和定时
        • 格式转换
  • 计算机体系结构
    • 分类
      • 宏观上按处理机的数量进行分类
        • 单处理系统
        • 并行处理与多处理系统
        • 分布式处理系统
      • 微观上按并行程度分类
    • 流水线技术
      • 流水线周期
        • 各子任务中执行时间最长的(最慢的)子任务的执行时间
          • 流水线瓶颈嘛 注意：这里说的不是同功能同类型的任务中执行最久的那一次时间，而是这一系列任务中的最长时间
      • 流水线执行完n条指令所需时间公式
        • Tn=执行一条指令所需时间+(n-1)*流水线周期
      • 吞吐率
        • 单位时间里流水线处理机流出的结果数。 对指令而言，就是单位时间里执行的指令数
  • 存储系统
    • 拓展
      • 高速缓存(Cache)
        • 是介于CPU与内存之间的一级存储器，存储内容是主存局部域的副本
        • 地址映像
          • 概念
            • CPU从内存中读取地址，那就需要先将主存地址转换成Cache存储器地址，这种地址转换即 地址映像
          • 分类
            • 直接映像
              • 内存中的块与Cache块是一一对应的
              • 主存地址
                • 主存区号
                • 区内块号
                • 块内地址
              • 缺点
                • 块冲突率高，Cache空间得不到充分利用
                  • 如 每个区的第一块都存在Cahce相同的地方
            • 全相联映像
              • 主存与Cache均分成容量相同的块，允许主存的任一块可以调入Cache的任何一个块空间中
              • 主存地址
                • 主存块号
                • 块内地址
              • 缺点
                • 无法从主存块号中直接获得所对应Cache的存储块号
            • 组相联映像
              • 前两种方式折中，加入了组概念。组是直接映像，组内块采用全相联映像
              • 主存地址
                • 区号
                • 组号
                • 主存块号
                • 块内地址
              • Cache地址
                • 组号
                • 组内块号
                • 块内地址
        • 性能分析
          • 在Cache中的表示命中， (1-HC)表示没有命中率， 没有命中时则需要到主存获取
      • 虚拟存储器实际上是一种逻辑存储器 相联存储器是一种按内容访问的存储器
        • 常用的虚拟存储器有主存+辅存组成
      • 编址
        • 1字节 = 8位 1byte = 8 bit 大写的B 表示字节 内存是按字节编址 如 求主存地址需要用几位表示：主存容量位1MB,高速缓存容量为16KB,块的大小为512B 直接映像主存地址= 主存区号+区内块号+块内地址 主存区号=1MB/16KB=有多少个区 = 2的10次方KB/2的4次方=2的（10-4=）6次方B=6位 区内块号=16KB/512B=16*2的10次方B/2的9次方B=2的（10+4-9=）5次方B=5位 块内地址=512B=2的9次方B=9位 所以 主存地址需要用 6+5+9=20位表示
        • • 拆解问法： 1.地址编号从80000H到BFFFFH且按字节编址的内存容量占多少字节(多少byte) 一个字节占一行编址格子 80000H到BFFFFH占 BFFFFH-80000H=40000H=40000Hbyte=40000个字节 2.40000个字节=多少KB（1KB=2的10次方B） 40000HB=4*16的4次方+0*16的3次方。。。=4*16的4次方=2的(2+4*4)18次方B=(2的18次方/2的10次方)KB=2的8次方KB=256KB 需要256KB/(16K*4bit)=(256*8)bit/(16*4)bit=32片 注意！！！: 1B=8bit 265KB=256K*1B
  • 安全性、可靠性与系统性能评测
    • 对称加密技术
      • 代表算法
        • DES
          • 采用替换和移位的方法加密，用56位密钥对64位二进制数据块进行加密
        • 3DES
          • 用两个56位密钥
        • RC-5
        • IDEA
          • 类似于DES,密钥长度为128位
        • AES
          • 基于排列和置换运算
      • 1.加密和解密使用相同的密钥 2.可以推导出来的
    • 非对称加密技术
      • 只有一对的公钥和私钥可以解密
      • 加密体制
        • 加密模型
          • 公钥加密，私钥解密。用于数据单向加密传输
        • 认证模型
          • 私钥加密，公钥解密。谁都可以通过公钥解密，可以确认发送者身份
      • 代表算法
        • RSA
    • 信息摘要
      • 通过生成hash值进行比较确认这个信息的身份证，是不可反推的
      • SHA-1、MD2、MD4和MD5是被广泛使用的hash函数，有128位。MD是信息摘要的英文简称
    • 数字签名和数字加密 (非对称加密的升级版)
      • 数字签名
        • 对需要加密的信息和使用hash函数生成的信息摘要一起通过私钥加密，可以验证发送者身份，但因为是加密信息和摘要一起发送，信息也是不安全的
      • 数字加密(数字信封)
        • 信息先通过对称加密得到E,E再通过公钥加密 接受者私钥解密，再使用对称密钥解密
    • 计算机可靠性
      • 计算机系统的可靠性
        • 某时段正常运行的概率
        • 串联系统可靠性
          • R=R1*R2*..RN
        • 并联系统可靠性
          • R=1-(1-R1)(1-R2)..(1-RN)
      • 计算机系统的失效率
        • 单位时间 失效元件/元件总数 的占比
      • 平均无故障时间
        • 两次故障间能正常工作时间的平均值
      • 计算机系统的可维修性
        • 故障发生到修好的时间
      • 计算机系统的可用性
        • 平均无故障时间/(平均无故障时间+计算机系统的可维修性)
• 程序语言基础知识
  • 考点
    • 编译程序和解析程序
      • 解释程序(解释器)
        • 要么直接解释执行源程序，要么将源程序翻译成某种中间代码后再执行 注意是“立即执行”
      • 编译程序(编译器)
        • 将源程序翻译成目标程序 一般分两个阶段： 编译阶段和运行阶段
        • 编译过程
      • 区别是解释程序翻译一条执行一条；而编译程序是先全部翻译再一次执行
    • 程序语言的数据成分和控制成分
      • 面向机器的语言是低级语言，如机器语言和汇编语言，可读性较差
      • 数据类型
        • 基本类型
          • 实型，字符型
        • 特殊类型
          • 空类型
        • 用户定义类型
          • 枚举类型
            • 所以数据类型也是可以命名的
        • 构造类型
          • 数组、结构、联合
        • 指针类型
          • type *
        • 抽象数据类型
          • 类类型
    • 编译程序的过程
      • 符号表管理 出错处理
        • 源程序
        • 1.词法分析
        • 2.语法分析
        • 3.语义分析
          • 主要工作是进行类型分析和检查
        • 4.中间代码生成
          • 根据 语义分析的输出生成中间代码
          • 常见的中间代码
            • 后缀式(逆波兰式)
            • 四元式(三地址码)
            • 树形
        • 前段 和高级语言相关
        • 5.代码优化
          • 优化过程可以在中间代码生成阶段进行，也可以在目标代码生成阶段进行
        • 6.目标代码生成
        • 后端 和机器相关
        • 目标代码
    • 中缀、前缀与后缀表达式
      • 根据运算符的放置位置分
        • 中缀表达式
          • 运算法写在操作数中间
        • 前缀表达式(波兰式)
          • 运算符写在操作数前面，且不适用括号
        • 后缀表达式(逆波兰式)
          • 运算符写在操作数后面，且不使用括号
      • 表达式之间的转换
    • 传值调用和引用调用
      • 传值调用
        • 信息传递是单向的，只能将实参的值传递给形参，形参不能再将值传递给实参
          • 如sum（2,3） 里的2、3实参 传给 方法形参 运行返回最终的sum求和结果
          • 实参可以是常量(表达式)，也可以是变量(数组元素)
      • 引用调用(地址调用)
        • 信息传递可以实现双向
• 数据结构与算法
  • 线性表
    • 线性表的顺序存储(顺序表)
      • 是指用一组地址连续的存储单元一次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻
      • 优缺点
        • 查找快，插入和删除操作慢，需要移动元素
    • 线性表的链式存储(链表)
      • 由 数据域+指针 组成
      • 分类
        • 单链表
        • 循环链表
        • 双链表
    • 栈
      • 顺序栈
        • 存储空间是预先申请，所以可能会出现栈满的情况 入栈前都需要判断栈是否已满
      • 链栈
    • 队列
      • 顺序队列
      • 循环队列
      • 链队列
    • 串
      • 串相等
        • 串长度相等且对应位置上的字符也相同
      • 串比较
        • 串比较是以字符ASCII码作为依据
      • 串的存储结构
        • 顺序存储
          • 是指地址连续的存储单元
        • 链式存储
          • 字符串可以采用链表作为存储结构， 当用链表存储串中的字符时，每个结点中可以存储一个字符，也可以存储多个字符
    • 数组
      • 数组是长度固定的线性表
      • 数组适合采用顺序存储结构
      • 地址计算公式
        • 1.以行为主序优先存储
          • • 解读： 1.i-1 表示 a(ij)所在的行前一行的行数 2.(i-1)*n 表示 从第一行开始到a(ij) 所在前一行的完整元素个数。(每一行有n个元素) 3.(i-1)*n+(j-1) 表示a(ij)位于所在前一个元素的地址
        • 2.以列为主序优先存储
        • 设每个数据占用L个单元，m、n为数组的行数和列数
    • 矩阵
      • 对称矩阵
        • 概念
          • a(ij)=a(ji)
        • 矩阵压缩
          • 只存储下三角的数据即可
          • 可以存放n(n+1)/2个元素
            • 等差数列的求和公式
        • 存储位置
          • B[K](k表示矩阵压缩存放在一维数组中时的位置)。K和矩阵元素a(ij)之间的关系公式(以行为主序) 不管i,j 大小，因为是对称关系，所以公式中把ij互换即可
      • 三对角矩阵
        • 概念
          • 非0元素集中在对角线两边
          • 共有3n-2个元素，因为除了第一行和最后一行只有两个元素外，其余行都是3个元素
        • 存储位置
          • k=2i+j
            • a[i,j]的存储位置的意思 1.a[i,j]前面有i行，每行除了第一行都是3个元素，所以a[i,j]前面行共有3i-1个元素 2.a[i,j]的位置有前面行的元素+前面列的元素组成 3.a[i,j]前面列的元素和a[i,j]所处于对象线的位置有关 在对角线的前面，则前面有0个元素 在对角线上，则前面有1个元素 在对角线后面，则a[i,j]前面列有2个元素 即j-i=-1时，在对角线前面，元素个数为0 j-i=0时，在对角线上，元素个数为1 j-i=1时，在对角线后，元素个数为2 综上，前面列元素个数为j-i+1 4.所以，元素个数为：3i-1+j-i+1=3i+j-i=2i+j
      • 稀疏矩阵
        • 概念
          • 非0元素个数远少于0元素个数，且非0元素分布没有规律
        • 存储位置
          • 用三元组表示即可 （i,j,a(ij）
  • 树
    • 基本概念
      • 双亲、孩子、兄弟
      • 度
        • 也叫节点的孩子节点个数
      • 叶子节点
        • 度为0的节点
      • 内部节点
        • 除叶子节点和根节点以外的节点
      • 节点的层
      • 高度/深度
        • 一个树最大层数
      • 有序/无序树
        • 节点个子树从左到右具有次序叫有序树，不能交换位置
      • 森林
        • 互不相交树的集合
    • 分类
      • 二叉树
        • 空树也是二叉树
        • 性质
          • 深度为K的二叉树至多有2^k -1个节点
            • 等比数列的求和公式
              • (a1-an*q)/(1-q)
                • q为公比
          • 对任何一棵二叉树，若其终端节点数为n0,度为2的节点数为n2,则n0=n2+1
        • 满二叉树
          • 所有节点的度都为2
        • 完全二叉树
          • 和满二叉树的编号为1-n的节点一一对应时的二叉树
          • 假设该节点序号为i,则左孩子的序号一定是2i,右孩子的序号一定是2i+1
        • 最优二叉树(哈夫曼树/霍夫曼树)
          • 概念
            • 一类带权路径长度最短的树
              • 最优长度：每个节点到根节点的路径的长度
              • 树的带权路径：从该节点到根节点之间的路径长度与该节点权的乘积
              • 树的带权路径长度：树中所有叶子节点的带权路径长度之和
          • 如何构造最优二叉树
            • 1.取到数组中最小的两个权值，相加得到一个新的双亲节点 2.双亲节点和剩余的节点组合成一个新的数组 3.重复上述过程
              • 关于4、5、6三个节点如何组成最优二叉树
          • 应用
            • 对字符集中的字符进行编码和译码
        • 二叉查找树/二叉排序树
          • 概念
            • 空树
            • 1.如果有左子树，左子树所有节点的值小于根节点 2.如果有右子树，右子树所有节点的值大于根节点 3.左右子树也是两棵二叉查找树
          • 对二叉查找树进行中序遍历，可得到一个关键码递增有序的节点序号
    • 存储结构
      • 顺序存储结构
        • 从上到下，从左到右一层一层地把元素依次放到数组中
        • 缺点：如果不是满二叉树或者完全二叉树，那会浪费存储空间
      • 链式存储
        • 适合非满二叉树或非完全二叉树的存储，可以避免顺序存储的浪费存储空间的缺点
        • 二叉链表
          • 缺点：没办法找到目标节点的双亲节点
        • 三叉链表
          • 比二叉链表多了一个双亲节点的指向，避免了二叉链表的缺陷
    • 遍历
      • 按访问根节点的次序分
        • 中序遍历法
          • 左、根、右
        • 前序遍历法
          • 根、左、右
        • 后序遍历法
          • 左、右、根
      • 按层从上往下，从左往右的顺序遍历
  • 图
    • 相关概念
      • 图
        • 有非空顶点集合和边集合组合而成(点通过线任意有向或无向的线组合成)
      • 度
        • 每个顶点所含有的边的个数
      • 出度和入度(针对有向图而言)
      • 路径
        • 有线连接着，就是顶点之间是有路径
        • 相关概念：路径长度，就是两个顶点间连线的条数
        • 注意：有向图如果没有方向就是没路径，即便有连线
      • 子图
        • 父图的一部分
      • 连通图(针对无向图而言)
        • 任意两点有路径就是连通图
      • 强连通图(针对有向图而言)
        • 任意两点有一来一回的连线
      • 网
        • 边带 权值 的图
        • 网的存储结构
          • 权值用数字表示，没连线就用无穷大符号表示
    • 表示
      • 有向图（线的集合用尖括号表示）
        • V(a)={1,2,3.4} E(a)={<1,2>,<1,3>,<4,2>,<2,4>}
      • 无向图（线的集合用圆括号表示）
    • 完全图
      • 概念
        • 每个顶点与其他n-1个顶点之间都有边
      • 分类
        • 有向完全图
          • 含有n个顶点的有向完全图共有 (n*(n-1)) 条边
            • 概率论+等差数列求和
        • 无向完全图
          • 含有n个顶点的无向完全图共有 (n*(n-1))/2 条边
            • 概率论+等差数列求和
    • 图的存储结构
      • 1.用矩阵表示，一个顶点就是一个矩阵行或列元素
      • 有向图矩阵没规律 有向图矩阵是对称矩阵
      • 2.邻接链表表示法
        • 链表中的表节点 第一个用于表示节点信息，第二个用于指向下一个节点，如果还有权值就用第三个表节点表示
        • 分类
          • 表头节点
          • 表节点
  • 算法
    • 排序算法
      • 直接插入排序
        • 比较插入排好序的元素中
      • 冒泡排序
        • 多次冒泡，两两相邻元素比较
      • 简单选择排序
        • 一次找出待排队列里的最小值，找出后剔除再找
      • 希尔排序(缩小增量排序)
        • 1.设置增量，第一次为n/2,第二次为（n/2）/2。达成缩小增量的目的
        • 2.根据增量所示的间隔取值分成组，组内元素比较排序。如图，根据下划线颜色分了组
        • 3.多次缩小增量进行排序
      • 快速排序
        • 1.初设两个位置ij,分别指向第一个记录和最后一个记录
        • 2.设枢轴记录关键字为pivot（通常为第一个记录，就是那一个值和其他值作比较的那个值）
        • 3.假设要正序排序，ij元素间轮流找 较小值(从i出发，比对pivot时找较小值)、较大值(从j出发，比对pivot时找较大值)，找到就对调位置
        • 4.直到i j相等，可以实现排好序的队列中枢轴值左边的元素都小于枢轴值右边的元素
        • 5.以上完成一趟快速排序，所有排完序要进行多趟
      • 堆排序
        • 分类
          • 小顶堆
            • 节点序号肯定比孩子节点序号要小
          • 大顶堆
            • 节点序号肯定比孩子节点序号要大，根节点序号最大
        • 1.把一个序列先排成一个大顶堆
        • 2.把堆顶元素拿出来作为最大值，其余元素再排成一个大顶堆
        • 3.依次拿出来的堆顶元素能组合成一个有序队列
      • 归并排序
        • 1.两两比较元素归并，最小能得到n/2个长度的组。不够分的单独作为一组
        • 2.组内比较排序
        • 希尔排序变种，希尔是相隔增量个元素为一组，归并则相邻两两元素为一组。因为分的组内元素越来越多，个人觉得后期排序会越来越复杂
      • • 简单、希尔、快速、堆排都是不稳定的
    • 查找算法
      • 顺序查找
      • 折半查找(二分查找)
        • 要求查找表里的元素是有序排列的
        • 折半查找二叉树(折半查找判定树)
          • 就是这种 查找法可以用二叉树表示的意思
      • 索引顺序查找
        • 顺序查找的改进
        • 将表分成若干块，每一块中的关键字不一定有序，但块之间是有序的，然后块可以组成索引块
        • 索引表由最大关键字和起始地址组成
      • 树表查找
        • 二叉查找树是一种动态查找表，表结构本身在查找过程中是动态生成的
      • 哈希查找
        • hash冲突
          • 如果关键字K1≠K2，而Hash(K1)==Hash(K2),就是哈希冲突
          • 采用哈希法需要考虑的两个问题
            • 哈希函数的构造
            • 冲突的解决
              • 开放定址法
                • 移动增量种类
                  • 线性探测再散列
                    • 和后一个比较，有冲突就继续往下挪位置的意思
                  • 二次探测再散列
                    • 和上一个的区别就是不仅可以向后移也可以向前移
                  • 随机探测再散列
                    • 和随机元素比较，冲突就移动这样
              • 链地址法
                • 概念
                  • 它将具有相同哈希函数值的记录组织成一个链表，但链域的值为NULL时，表示已没有后继记录
                  • 解决了开放定址法中，如果存在哈希冲突较多时产生多次挪动的问题
          • 哈希值取法
            • 就是对一个数进行取余，相同就放在hash列表同一个位置
      • 相关概念
        • 静态查找表
          • 只查询
        • 动态查找表
          • 增删改查
        • 关键字
          • 就是查找集合里的元素
        • 平均查找长度(ASL)
          • 关键字和给定值进行比较次数的平均值，是衡量查找算法好坏的依据
    • 图的相关算法
      • 生成树与最小生成树
        • 概念
          • 生成树
            • 如果G(V,E)是连通图，其子图包含G的所有顶点，则该子图为G的生成树(注意！！树是不连通的)
          • 最小生成树
            • 对于连通网,边带权值，生成树各边也带权值，生成树各边的权值总和称为生成树的权，权值最小生成树为最小生成树
            • 普里姆算法、克鲁斯卡尔算法都是 求最小生成树的算法
            • 一个网的生成树不止一棵，所以有最小一称
      • 普里姆算法
        • 1.以顶点为主
        • 2.找到目标顶点到其余各个顶点之间的最短路径，每次找一个
        • 3.与目标订单连接最短路径的顶点之间再组合成一个整体
        • 4.找该整体到各顶点之间的最短路径再组合成一个整体，循环一直到连接完所有顶点
      • 克鲁斯卡尔算法
        • 1.以边为主
        • 2.从1开始依次找权值最小的边及该边两边的顶点
        • 3.如果遇到闭环，那就不采用并跳过
        • 4.最终以所有顶点能连接成树结束
• 操作系统基础
  • 相关概念
    • 两个重要作用
      • 通过资源管理提高计算机系统的效率
      • 改善人机界面向用户提供友好的工作环境
    • 特征
      • 并发性
      • 共享性
      • 虚拟性
      • 不确定性
    • 功能
      • 进程管理
      • 文件管理
      • 存储管理
      • 设备管理
      • 作业管理
  • 进程
    • 组成
      • 程序
      • 数据
      • 进程控制块(PCB)
    • 基本属性
      • 可拥有资源的独立单位
      • 可独立调度和分配的基本单位
    • 状态转换
      • 运行
      • 就绪
      • 阻塞
      • 只有就绪的状态才能运行 运行阶段只要时间片到了就会进入就绪状态 阻塞要转换成就绪状态才能重新运行
      • 新建
      • 终止
      • 运行阶段才能是 终止 新建好就到就绪阶段
    • 同步与互斥
      • 相关概念
        • 同步
          • 协同工作，相互合作的过程就是同步
        • 互斥
          • 争用临界资源而互斥执行
        • 临界资源
          • 有些资源一次只能供一个进程使用
      • 实现方式
        • 信号量机制(P、V操作)
          • 概念
            • 信号量：整型变量，根据控制对象的不同被赋予不同的值
            • 共用信号量
              • 作用
                • 实现进程互斥
              • 概念
                • 初值为资源的数目
                  • 如共抢3个厕所，共用信号量可设置成3，每被占用一个厕所就-1处理
            • 私有信号量
          • 物理意义
            • 负数表示等待数，整数表示可用数
          • P、V操作
            • 注意点
              • PV是低级通信元语
              • 执行期间不可分割个，是成对出现的
            • 概念
              • P
                • 申请一个资源
              • V
                • 释放一个资源
    • 进程调度
      • 分类
        • 高级调度（长调度、作业调度、接纳调度）
          • 使一个作业成为进程，就绪准备
        • 中级调度（中程调度、兑换调度）
          • 内外存的调度，服务高级和低级调度，就绪调度使得就绪进程可以参与CPU竞争
        • 低级调度（短程调度、进程调度）
          • 就绪进程占用CPU的过程，是操作系统中最活跃和主要的调度程序
      • 进程调度算法
        • 先来先服务
          • 有利于长作业，因为会长期占用CPU
        • 时间片轮转
          • 时间片分发
        • 优先级调度
        • 多级反馈调度
          • 时间片行业优先级调度的综合与发展
    • 死锁
      • 产生死锁的4个条件
        • 互斥条件
          • 资源不能共享的意思
        • 请求保持条件
          • 资源保持占有，不会 无条件主动释放
        • 不可剥夺条件
          • 不可剥夺所以是死锁
          • 预先静态分配法可以破坏不可剥夺条件 就是一个进程所需要的资源要预先分配给它，但老师说它其实破坏的是请求保持条件
        • 环路条件
          • 相互联系的意思
      • 死锁的处理策略
        • 鸵鸟策略
          • 不理睬，不管它的意思(这算啥策略)
        • 预防策略
        • 避免策略
        • 检测与解除死锁
          • 死锁解除法
            • 资源剥夺法
            • 撤销进程法
    • 线程
      • 分类
        • 用户级线程
        • 内核支持线程
        • 线程的创建、撤销和切换是否利用系统调用来实现区分
      • 线程基本上拥有资源，只拥有一点运行中必不可少的资源(如程序计数器、一组寄存器和栈)
        • 也就意味着线程之间共享的内容不包括程序计数器、寄存器和栈
  • 存储管理
    • 相关概念
      • 逻辑地址
        • 开发人员用一个简单符号命名的地址，所以也叫符号名地址、虚拟地址、相对地址
      • 物理地址
        • 在主存中实际存储的地址，也叫绝对地址
      • 地址重定位
        • 把程序中的指令和数据的逻辑地址转换为对应的物理地址， 也是一个把外存的程序转载到内存的一个过程
        • 分类
          • 静态重定位
            • 在程序装入主存是已经完成了逻辑地址到物理地址的 转换，执行过程不会再变化
          • 动态重定位
            • 在程序运行期间完成逻辑地址到物理地址的转换
    • 分类
      • 分区存储管理
        • 概念
          • 把主存分成若干区域分配给每个作业使用
        • 组成
          • 固定分区
            • 系统生成时已经分好区，和数组一样，初始化时就已经规定好位置
          • 可变分区
            • 作业装入时进行，所以分区个数可变，分区大小和作业大小相等
          • 可重定位分区
            • 分区小碎片移动拼接成一个可用分区
      • 分页存储管理
        • 概念
          • 页
            • 将进程地址空间划分成若干个大小相等的区域，每个区域是页
          • 块
            • 将主存的空间页划分成与页大小相同的若干个物理块，叫块 或 页框
          • 分页管理
            • 在为进程分配主存时，将进程中若干页分别装入多个不相邻块中的过程
          • 缺页中断
            • 能有效降低内存使用
            • 概念
              • 1.分页存储基础上增加了请求调页功能，页面置换功能
              • 2.当某页不在使用时，就把当前页拿出内存
              • 3.因为拿出了内存，所以要访问的页面不存在主存时就产生了一个缺页中断
            • 页面置换算法
              • 最佳置换算法
                • 理想化算法，觉得被置换出去的页面永不在使用
              • 先进先出置换算法
              • 最近最少未使用算法
                • 优先淘汰访问时间最长的页面
              • 最近未用置换算法
                • 优先淘汰访问量为0的页面
          • 页表
            • 作用
              • 当进程多个页面离散分配在主存中多个物理块是，系统保证在主存中能找到进程要访问对应物理块
            • 概念
              • 根据作用，系统为每个进程建立了一张页面映射表
                • 系统只有一张页表吧
      • 分段存储管理
        • 概念
          • 1.将用户程序或作业的地址空间按内容划分为段
          • 2.段长度不等
          • 3.每个段占用一个连续分区，但各个段离散分配在主存不同分区
          • 4.为了寻址也有一张“段映射表”，也叫段表
            • 段表存储属性
              • 段号
              • 段长
              • 基址、起始地址
      • 段页式存储管理
        • 概念
          • 1.将整个主存划分成大小相等的存储块(页框)
          • 2.将用户程序按程序的逻辑关系分成段 （先分段再分页的概念）
          • 3.段内分页，这样就能避免分页地址离散的问题
          • 先分段再分页的意思
      • 虚拟存储管理
        • 概念
          • 程序局部性原理
  • 设备管理
    • i/o设备管理软件
      • 分层
        • 中断处理程序
        • 设备驱动程序
        • 和硬件打交道
        • 与设备无关的系统软件
        • 用户级软件
    • 设备管理的相关技术
      • 通道技术
      • DMA技术
      • 缓冲技术
      • Spooling技术
        • 目的
          • 缓和CPU高速性和I/O设备低速性之间的矛盾
          • 实现了设备的共享
          • 提高了CPU的作业效率
        • 就是设置一个缓冲区的意思， 原因1 输入设备信息输入过程相对CPU较慢，cpu不能等你完全输入完再执行 原因2 cpu执行完返回结果，不可能等输出设备处理完才再执行， 以上，所以输入输出都有一个通过缓输入输出程序对缓冲区进行作业信息的保存，供cpu和I/O设备之间的信息传输
    • 磁盘调度算法
      • 分类
        • 移壁调度
          • 移臂调度算法
            • 先来先服务
              • 缺点
                • 平均寻道时间变长
            • 最短寻道时间优先
            • 扫描算法
              • 优先考虑的是磁头当前移动方向
            • 单向扫描调度算法
              • 在扫描算法的基础上，规定磁头只做单向移动
        • 旋转调度
          • 旋转调度算法
            • 概念
              • 根据扇区编号区分，如果扇区编号不相同，按就近原则先到磁头位置下的扇区进行读写操作。如果扇区编号相同，则任选扇区进行读写操作
      • 磁盘数据读取时间
        • 寻道时间 + 旋转延迟 + 数据传输时间
  • 文件管理和作业管理
    • 文件管理
      • 文件目录结构
        • 一级目录结构
          • 只有一张目录表，不允许重名，不能实现文件共享
        • 二级目录结构
          • 有主文件目录和用户目录组成
        • 多级目录结构
          • 目前我们所见的win目录结构就是多级
      • 文件存储空间的管理
        • 管理方法
          • 空闲区表
            • 操作系统建立了一张记录了空闲空间表，适用于连续存储文件结构
          • 位示图
            • 在外存上建立了一张位示图，和空闲区表差不多，区别在于位示图记录了每个物理块使用情况，而空闲区表这是一段段记录的。
            • 若机器字长32，则位示图中一个字描述32个物理块情况
          • 空闲块链
            • 每个空闲物理块设置一个指针，指向下一个空闲物理块
            • 形成链表的头指针放在文件存储器的一个特定位置上
          • 成组链接法
            • 将空闲块分组，每100个空闲块为一组
            • 每组第一个空闲块记录下一组空闲快的物理盘块号和空闲块总数
    • 作业管理
      • 作业管理调度算法
        • 先来先服务
        • 短作业优先
        • 响应比高优先
          • 响应比=作业响应时间/作业执行时间=(作业等待时间+作业执行时间)/作业执行时间
        • 优先级调度算法
        • 均衡调度算法
• 网络与网络硬件基础
  • 计算机网络分类
    • 局域网(LAN)
      • 1000M左右
    • 城域网(MAN)
      • 10KM左右
    • 广域网(WAN)
      • 100KM以上
  • 网络拓扑结构
    • 概念
      • 通信线路和节点组成的网络结构外貌
    • 常见结构
      • 总线型
      • 星型
      • 环型
        • 环路封闭，扩充较难
      • 树型
      • 分布式结构
  • 网络互连设备
    • 物理层设备
      • 中继器
        • 作用
          • 在物理层上实现局域网网段互连
          • 用于扩展局域网网段的长度
        • 以太网中最多只能使用4个中继器
      • 集线器
        • 作用
          • 特殊的多路中继器，当网络中某条线路节点出现故障是，不影响网上其他节点的正常工作
        • 分类
          • 有源
            • 不对信号作处理，只负责连接多段介质
          • 无源
            • 对传输信号进行再生和放大
      • 传输单位
        • 位(比特流)
    • 数据链路层设备
      • 网桥
        • 作用
          • 连接两个局域网网段，对帧进行过滤
            • 网桥检查帧的源地址和目的地址，如果不在同一网段上，就把帧转发到另一个网段上，如果在，则不转发
          • 隔离不同网段
            • 网络段之间用网桥连接，网络段之间不会相互影响，从而提高网络可靠性
      • 交换机
        • 也叫多端口网桥
        • 按MAC地址(物理地址)进行数据转发，比网桥的转发性能要高，数据延迟要小
        • 交换技术
          • 端口交换
          • 帧交换
          • 信元交换
        • 工作过程
          • 交换机的工作过程：从某一节点收到顿后，在其内存的MAC地址表 （端口号-MAC地址）中进行查找，确认该MAC地址的网卡连接在哪一个节点， 然后将顿转发至该节点。 如果没有找到该MAC地址，就将数据包广播到所有节点，拥有该MAC的网卡收到广播后做出应答，交换机将该MAC地址添加到MAC地址列表中
            • 总结就是通过MAC地址表(端口号-MAC地址)查找节点，找不到就广播，收到响应再更新MAC地址表
      • 传输单位
        • 帧
    • 网络层互联设备
      • 路由器
        • 作用
          • 连接异种网，即使网络最低两层协议不同，也可通过支持多协议的路由器进行连接
          • 自身存储器中维护着一个路径表，记录各网络逻辑地址(IP地址)，用于选择连接路径
      • 三层交换机
        • 我理解成高级路由器
        • 包括所有交换机功能，还包含网络层部分功能。一次路由，多次交换
        • 数据包传输过程中，第一次必须通过路由功能找到转发端口 再次收到相同帧后不在调用路由选择，比通常路由器转发更快
      • 传输单位
        • 数据包
        • 帧(三层交换机在路由后的传输用帧)
    • 应用层设备
      • 网关
        • 作用
          • 主要功能是进行协议转换
        • 传输单位
          • 报文
  • 网络传输介质
    • 双绞线
    • 同轴电缆
    • 光纤
    • 微波
    • 红外线和激光
    • 卫星通信
  • 网络协议与标准
    • OSI参考模型
      • 七层结构
        • 资源子网
          • 应用层
          • 表示层
          • 会话层
        • 衔接层
          • 传输层
        • 通信子网
          • 网络层
          • 数据链路层
          • 物理层
    • TCP/IP协议簇
      • 特性
        • 逻辑编址
          • 作用
            • 为连入互联网的设备分配ip地址
          • IP地址包含：网络号+子网络号+主机号
        • 路由选择
        • 域名解析
        • 错误检测与流量控制
      • TCP/IP模型
        • 四层结构
          • 应用层
          • 传输层
          • 网际层
          • 网络接口层
      • 协议
        • IP
          • 功能
            • 封装上层(传输层)数据或同层数据到IP数据报中
            • 传送数据到最终目的
            • 数据分段(分段才能在链路层传输)
            • 确定目的地路径
        • ICMP(网络控制信息协议)
          • 就是给IP协议只管发不管接擦屁股的
          • 主要功能
            • 通告网络故障
            • 通告网络拥堵
            • 协助解决故障
        • TCP
          • 提供一个可靠的、面向连接的、全双工的数据传输服务
          • 通过发送时启动的计时器，实现重发技术
          • 因为重发机制，所以是低速的
        • UDP
          • 作用
            • 将UDP消息展示给应用层
          • 在已知网络可靠的情况下，可以选择用UDP
        • DHCP(动态主机配置协议)
          • 作用
            • 用于给计算器动态分配IP地址
              • 如配置IP时，有“固定IP”可以选，也可以选“自动获取”I[地址,这个自动获取IP地址的过程就是用DHCP协议完成
        • SOCKS
          • 防火墙相关协议
          • 工作在会话层
  • Internet基础知识
    • 域名
      • 格式
        • 计算机主机名.本地名.组名.最高层域名 www.4399.com www.hust.edu.cn
          • 最高层域名
            • cn
              • 表示中国
            • jp
              • 表示日本
            • HK
              • 表示香港
          • 组名
            • edu
              • 教育机构
            • gov
              • 政府机构
            • net
              • 网络上的组织
            • com
              • 商业型组织
          • 主机
            • www
          • 域名
            • hust.edu.cn
          • 主机域名
            • www.hust.edu.cn
    • URL
      • 格式
        • 协议://主机.域名[:端口号]/路径/文件名
        • http://www.4399.com/a3/img/b4.html
        • https
          • 在http通信的基础下，利用SSL/TLS建立全信道，加密数据包
    • IP地址
      • IP地址中，全0代表的是网络地址，全1代表的是广播地址。所以要在原有支持网络数目的基础上-2.如A类地址，最大支持126个网络就是 2^7(128)-2=126
      • a类第一个字节十进制范围是1~126
      • b类第一个字节十进制范围是128~191
      • c类第一个字节十进制范围是 192~223
      • d类是224~239
      • e类是240~255
      • 因为是由4段8位二进制位组成，所以也叫IPV4，也是版本号为4的意思
    • 子网掩码
      • 作用
        • 用于区分IP地址中哪些是网络号，哪些是主机号
        • 是结合IP地址看的，单独的子网掩码没有意义
      • 概念
        • 网络号用1表示，主机号用0表示
        • 子网掩码肯定是左边连续的1，右边连续的0。即使可变长子网掩码(VLSM)也一样
        • 留意上图网络地址位数和对应子网掩码关系就能看出
        • IP地址是有4*8=32位二进制组成，每8位之间用.隔开
      • 通常我们的IP地址一般都是C类网络地址，所以，一般子网掩码都是255.255.255.0
      • 子网掩码如何与IP结合起来用
        • 求网络号的方法
          • 转二进制后两者作逻辑与运算
        • 求主机号的方法
          • 转二进制后，子网掩码取反，两者再作逻辑与运算
      • 可变长子网掩码(VLSM)
        • 使用场景，如主机数没有这么多，ip数用不上254(2^8-2)个，可以把子网掩码左边的1稍微延长几位，这样的子网掩码就不是255.255.255.0，而有可能是255.255.255.192
          • 192换成2进制是1100 0000.左边的1延长了两位
        • 另一种表示方式：十进制IP地址/网络号的位数。如210.42.96.138/26，表示左边有26个1，剩下就是32-26=6个0 组成的ip地址
    • 子网划分
      • 注意
        • 子网位数是算到网络号位数中的
          • 如上面的210.42.96.138/26的子网号是2位(8-(32-26)=8-6=2) ta划分了主机号的位数，却是算在了网络号的位数上，24+2=26
        • 和子网掩码一样，也能借用网络号的后面几位，用于增加主机数量，这就变成了“超网”
      • 作用
        • 取主机号中的前面几位来划分子网
    • IPV6
      • 概念
        • 地址空间为128位(IPV4是32位),分成8段，每段16(128/8)个字节
        • 每段之间用:冒号隔开(IPV4是用.点隔开的)
        • 每段采用16进制(IPV4是十进制)
    • Internet服务
      • 就是端口号区分的意思
      • TCP和UDP协议端口号为16位，所以支持端口号0~65535(2^16)
      • 0-1023为公共端口
  • 信息安全与网络安全
    • 网络攻击
      • 常见的网络攻击技术
        • 篡改消息
        • 伪造
        • 重放
        • 拒绝服务(DOS)
        • 分布式拒绝服务(DDOS)
        • 窃听(截取)
        • 流量分区(通信量分析)
          • 个人觉得数据分析较合适
        • 字典攻击
          • 密码校验过程，平常3次错误输入密码，账号被锁就是这种方式
        • 社会工程学攻击
          • 类似诱导点击不安全链接
        • sql注入攻击
        • 会话劫持
          • 连接并使用完后没有切断退出关闭连接
        • 漏洞扫描
        • 缓冲区溢出
      • 主动攻击和被动攻击
        • 主动攻击篡改数据
        • 被动攻击多用于非法窃取数据
    • 防火墙技术
      • 发展阶段
        • 包过滤
          • 检查 网络层和数据链路层
        • 应用代理网关
          • 检查 应用层、传输层和网络层 的协议特征
          • 缺点
            • 难以配置，处理过程慢
        • 状态检测技术
          • 包过滤和应用代理网关的升级
    • 入侵检测与防御
      • 分类
        • 入侵检测系统(IDS)
        • 入侵防御系统(IPS)
          • 也能检测网络攻击行为，是在入侵检测系统基础上发展起来的
• 数据库技术
  • 数据库系统的三级模式结构
    • 数据抽象
      • 物理层
        • 描述数据在存储器中是如何存储的
          • 索引，存储文件
      • 逻辑层
        • 描述存储器中存储什么数据以及这些数据间的关系
          • 基本表
      • 视图层
        • 描述数据库的某个部分，就是平常的创建视图，是一个虚拟的表
    • 三级模式
      • 外模式
        • 也叫用户模式或子模式，是用户与数据库系统的接口
      • 概念模式
        • 也叫模式，是数据库中数据结构和特征描述，只涉及到型的描述，不涉及具体的值
      • 内模式
        • 也叫存储模式，数据物理结构和存储方式的描述，定义类型、索引、和文件组织方式
    • 映像
      • 三级模式之间是通过映像关联起来的
    • 数据的独立性
      • 物理独立性
        • 和模式/内模式映像有关
        • 就是说内模式的数据逻辑结构改变时，数据库应用程序的表结构不变。 谁管你内部原理是怎么映射数据结构的呢
      • 逻辑独立性
        • 和外模式/模式映像有关，逻辑层的基本表结构改变时，只是关系之间的映射调整，外部应用或用户接触不到这种由数据到你看到的表之间是怎么映射的。
  • E-R模型
    • 属性
      • 简单属性和复合属性
        • 简单属性是原子的，不可再分的
        • 复合属性可以细分为更小的部分，如通信地址可以细分为省、市、街道
      • 单值属性和多值属性
        • 指一个属性有单个或多个值，如职工家属姓名
      • NULL属性
      • 派生属性
        • 可以从其他属性得来，如工作年限
    • 扩充的ER模型
      • 弱实体
        • 一个实体的存在必须以另一个实体为前提
          • 如职工和家属中的家属就是弱实体
        • 弱实体是双边矩形，弱实体和实体之间的关系用双边菱形关联
      • 特殊化
        • 实体一方面具有一些共性，也具有格式的特殊性
          • 如学生中的研究生，研究生拿到的学位和本科生不一样，研究生还有导师。但他们都是学生
        • 子实体
          • 用矩形内多画两条竖线表示
        • 实体
          • 实体和子实体之间用圆圈关联，同时实体和圆圈之间用两条线连接
    • 同一实体的二元联系
    • 经验
      • 1.三方联系的主键判断是看其中一个主键能否确定唯一一条记录，难点是找出特殊场景下的主键判断。如疫苗供应商、医院、接种者，只需要对应接种日期的接种人身份证号就能确认接种人每次的接种情况，所以不需要组合主键(即供应商、医院、接种者三方主键作为组合候选码，当然一般情况下三方联系是这么干的，这里是特殊情况)。所以关系模式： 接种(接种者身份证号，接种日期，医院名称，供应商名称)中 主键是身份证号和接种日期的组合
      • 2.ER图注意不要有重复名称属性
      • 3.一个关系模式中有多个外键的时候，一般都是多对多的关系
      • 4.约束关系就是要标明关系模式中的主码和外码的意思
      • 5.聚合和三方联系的区别在于，聚合是有先后顺序的，一般文中会有类似先做什么，后做什么相关字眼
  • 数据模型三要素
    • 数据结构
    • 数据操纵
    • 数据约束条件/完整性约束
      • 参照完整性约束
        • 外键出处明确，外键在外表中必须有值 和弱属性一样，要参照主属性才有意义
        • 方法
          • 在列后面加References 表名(属性名)
          • 在创建表最后加，有几个外码，就写几行 Foreign Key(属性名) Refernences 表名(属性名) ON DELETE CASCADE 表示删除时，连着外键所在主表数据一起删除 ON DELETE SET NULL表示删除时，连着外键所在主表数据值置为空值
      • 实体完整性
        • 主键不能取空值的意思
        • 方法
          • 在列后面加primary key
            • 这个是列级完整性约束条件
          • 在创建表的最后加primary key(属性名1，属性名2)
            • 这个是表级完整性约束条件
            • 当主键为属性组合，就用这种，因为一般主键只有一个
              • 要区分候选码，主键，主码、主属性区别 主键只能有一个 主键就是主码
      • 用户定义完整性
        • 针对某一具体关系数据库的约束条件 如职工表最低工资不能低于3000元 是用户自己定义的
• 关系数据库概述
  • 相关名词
    • 关系
      • 实体间的联系
    • 关系模式
      • 对关系的描述
      • 医院(医院名称，地址，电话)
    • 关系模型
      • 关系模式组成的集合
    • 属性
    • 域
      • 每个属性阈值范围对应值的集合，取值范围的意思
    • 候选码/码
      • 类似于主键，但这只要是能确定唯一元祖的属性都可以称为候选码，而主键是候选码中的一个
      • 候选码是个码的集合
    • 主码
      • 主键，E-R图中的实体标识符，候选码中的一个
        • 下划实线表示
    • 主属性
      • 包含在任何候选码中的各个属性为主属性
    • 非主属性
      • 不包含在任何候选码中的属性为非主属性
    • 外码
      • 也叫外键，是其他表的主码
        • 下划虚线表示
    • 全码
      • 属性的组合是这个关系模型的候选码就是全码，也就是复合键，要注意的是，全码里的任一属性都必须是候选码，而且组合后一起组成模型中的主键，也就是主键由多个属性组成这种。单独任选一个属性作为主键都不行
    • 元祖/记录
      • 表的一行值的记录
    • 字段
    • 元数
      • 属性的个数(列数)
    • 基数
      • 记录的个数(行数)
    • n元关系
      • 元数为几，就是几元关系
        • 有几列就是几元关系？
  • 关系数据库模式
    • 关系模式可以表示为
      • R(U,D,dom,F)
      • 关系名(属性名集合，属性的域或取值范围，属性向域的映像集合，属性将数据依赖关系集合)
      • 可以简记为
        • R(U)或R(A1,A2,A3,....An)
        • R为关系名，A1,A2...An为属性名或域名
      • • Dom(PCno)=Cno 意思是PCno列的值来源于Cno列数据
  • 关系的三种类型
    • 基本关系(基本表或基表)
      • 实际存在的表，是实际存储数据的逻辑表示
    • 查询表
      • 查询结果对应的表
    • 视图表
      • 注意这是虚拟表，数据库只存放它的定义
  • 关系运算
    • 广义笛卡尔积
      • 是用元祖相乘
    • 投影及广义投影
      • 投影(select)
        • 从表中选取列的意思
        • • 选取id列和基本工资列的值
      • 广义投影运算
        • 选取列的时候可以进行算术运算
        • • 选取ID列，基本工资和奖励运算列的值
      • 结果不用去重
    • 选择（where）
      • 和广义投影运算的区别是，广义投影是列运算，而选择是行运算
      • • 注意加单引号和没加单引号的区别
    • 连接
      • 满足某些条件的笛卡尔积
      • 分类
        • θ连接
          • • 表示R和S笛卡尔集中属性a小于b的关系的元祖
          • θ是比较运算符
        • 等值连接
          • θ为等于号就是等值连接
        • 自然连接
          • 还要求比较的是相同的属性组，并且所有的属性组都要可以自然比较。 如果没有重复属性，那自然连接就是普通笛卡尔积
          • 不能相当于内连接，只是删除了重复的列属性而已
        • 外连接
        • 全外连接
          • 就是左外连接和右外连接的并集
    • 除
    • ∧
      • 这个是 并且 符号，和并集符号差不多
    • ∨
      • 这个是或符号
  • 元祖演算
    • 原子演算
      • 概念
        • 约束变量
        • 自由变量
        • 一个公式的一个元祖变量前有全称量词或存在量词符号的变量，否则就是自由变量
        • • 英文翻译对应All,Exist
      • 其它
        • 如果A1和A2是公式，那A1=>A2表示：若A1为真则A2为真
    • 域演算
  • 查询优化
    • 在关系代数运算中,笛卡尔积和连接运算是最耗费时间和空间的
      • 如自然连接这种
    • 查询优化准则
      • 提早执行选取运算
      • 合并乘积与其后的选择运算为连接运算
      • 将投影运算与其后的其他运算同时进行，以避免重复扫描关系
      • 将投影运算和其前后的二目运算结合起来，使得没有必要为去掉某些字段在扫描一遍关系
      • 在执行连接前对关系适当地预处理，就能快速找到要连接的元祖
      • 存储公共子表达式
      • 这个可能要背一下
  • 基础知识
    • 函数依赖
      • 非平凡的函数依赖
        • （学号、课程号）→个人成绩，成绩不包含在学号或课程号中。
      • 平凡的函数依赖
        • （学号、姓名）→姓名，姓名包含在学号或姓名中
      • 完全函数依赖
        • 学号和课程号能查出对应成绩，单独拿学号或单独拿课程号都能确认成绩
        • X->Y
      • 部分函数依赖
        • 学号和课程号能查出课程名称，但单独拿学号不能确认课程名称，单独拿课程号可以
        • 一般存在由两个属性组合决定另外一个属性这种就是，和上面的非平凡函数依赖有点类似。不然的话，为什么不能分开写成完全函数依赖这种呢，对吧
      • 传递函数依赖
        • 就是需要有一个中间属性作中转依赖
      • 多值依赖
        • 如课程->->参考书
          • 一门课程有多本参考书，参考书之和课程有关，所以叫多值依赖。 如果表中只有课程和参考书两列，那就是平凡的多值依赖。 如果表中除了课程和参考数还有对应教师，那就是非平凡的多值依赖
        • 多值依赖的性质
  • 规范化
    • 第一范式
      • 属性原子性
    • 第二范式
      • 在满足第一范式的情况下，保证每个非主属性完全依赖于码
    • 第三范式
      • 在满足第二范式的情况下，不存在传递依赖的关系，也就是除去外键外，不能出现其它表的属性数据。如作为外键，只需要课程id即可，不需要在选个表上在上课程名称属性数据。
    • BCNF(巴克斯范式)
      • 在满足第三范式的情况下，消除了主属性对候选码的部分函数依赖和传递函数依赖，就是BCNF，也就是主属性也要求没有传递依赖
    • 第四范式
      • 在满足BC范式的情况下，不允许有非平凡多值依赖，当有多值之后依赖时，可以单独拿出来
      • 第四范式的主键一般时组合键，因为是多值的依赖 如果关系模式里面还多了个无关的其他属性(也叫存在嵌入式的多值依赖:举例)，那就是不符合第四范式，解决方式：分解就行
        • 
    • 转换成高范式的过程叫规范化
  • Armstrong公理系统
    • • 自反律就是能推导出自己 增广律就是在等式两边加一个相同变量，则等式依旧相等 传递律就是有个中间变量传递 推理的合并和分解不用说了，看下面的合并和分解举例。 主要说说伪传递律，就是等式两边相加依旧相等的意思 蕴涵就是包含，以自反律为例，x->y为F所蕴涵，就是包含在F这个函数依赖里面的意思。 推理规则分解的时候只能拆右边的，左边的不行。 如 合并： x->y,x->z,则x->yz; y->x,z->x,则yz->x; 分解时特殊： x->yz,则x->y,x->z; 但是 xy->z时，不能等价于x->z,y->z;
    • 函数依赖的闭包
      • 就是“所有”可能的函数依赖的意思
    • 属性的闭包
      • 就是“所有”能由目标属性决定的属性的集合
        •  上图，A能确定B\C\D\A,其中，能确定D是因为AC->D,而A又能确定C
    • 候选码的求解方法
      • 第一步
        • 按属性的出现位置分类
          • L
            • 必为任一候选码成员
              • 候选码成员是组合里的某属性，并不是一定是候选码
              • 若X的闭包为全集U，则X必为R的唯一候选码
          • NLR
            • 必为任一候选码成员
              • 候选码成员是组合里的某属性，并不是一定是候选码
          • 如果是这两种组成的属性集，若X的闭包为全集U， 则X必为R的唯一候选码
          • R
            • 不是候选码成员
          • LR
      • 第二步
        • 将所有的L类和NLR类属性组合起来，再求其闭包，如果是全集U，那么候选码就是这个组合，也不用走下面第三步
      • 第三步
        • 如果L类和NLR组合起来的闭包不是全集，则依次将LR类属性跟组合的闭包再组合成新闭包(这里注意，只有在L类不能推出全集的情况下才需要组合，否则就是单独取LR类判断)，只要闭包是全集U，那还是候选码
      • 注意，只有闭包是全集才是候选码，下图可知，为什么A是L类属性，为什么候选码只有AB和AC，而没有A。候选码成员和候选码不一样
    • 最小函数依赖
      • 1.所有函数依赖的右侧只有一个属性
        • A->BC就不是，这可以分解成A->B,A->C
      • 2.没有冗余的函数依赖
        • A->E就是,因为A->D,D->E能推出A->E
      • 3.所有函数依赖的左侧没有冗余的属性
        • AC->D就是，因为A->D
      • F={A->BC,A->E,A->D,D->E,AC->D}
  • 模式分解及分解后的特性
    • 无损连接
      • 将一个关系模式分解成若干个关系模式后，通过自然连接和投影等运算仍能还原到原来的关系模式，则称这种分解为无损连接分解
      • • 
      • 熟记这个公式
    • 保持函数依赖
      • 就是求子模式的所有依赖的并集的闭包是否也是F的闭包
      • • 就是判断分解后有没丢失函数依赖， 如 第一题中，(A1,A2)就丢失了A1A2->A3的依赖，因为A3并不在这个子模式里面 第二题中，如果是分解成(A1A3A2)和(A2)那就是保持函数依赖，因为它原本的依赖没有丢失
• SQL语言
  • SQL基本组成
    • 数据控制关键字
      • Grant
        • 授权
        • 语句格式
          • • 少写了一个，视图也可以 public 表示将权限授予所有人 with grant option 表示获得了这个权限的用户还可以将权限赋给其他用户
      • Revork
        • 收回授权
        • 语句格式
          • • 视图也可以，图片上漏写了 restrict 表示只收回语句中指定用户的权限 cascase 表示除了收回指定用户的权限外，还收回该用户赋予其他用户的权限
      • 特殊举例
        • 将user1用户对供应商S的供应商编号Sno的修改权限收回 Revoke update(sno) on table S from user1
          • 对属性列进行操作的举例
  • SQL数据类型
    • numeric(p,d)
      • 定点数，P为整数位，n为小数位
    • real
      • 浮点型
  • 表的创建、修改和删除
    • 表的创建
      • 属性值上的约束
        • NULL
        • UNIQUE
          • 取值唯一
        • NOT NULL UNIQUE
          • 唯一且不为空，和主键功能一样
        • check
          • eg CHECK(Sex = '男' or Sex = '女')
    • 表的修改
      • 语句格式
  • 索引的创建和删除
    • 索引的作用
      • 在使用order by 和group by子句中进行检索数据是，可以显著减少查询中分组和排序的时间
      • 使用索引可以在检索数据的过程中使用优化隐藏器，提高系统性能
      • 创建唯一索引，可以保证数据记录的唯一性
    • 索引分类
      • 聚集索引/聚集索引
        • 索引表索引项的顺序与表中记录的物理顺序一致
      • 非聚集索引
    • 语句格式
      • • cluster是聚簇索引
  • 视图的创建和删除
    • 语句格式
      • • with check option表示对update,insert,delete操作是保证更新、插入或删除的行满足视图中的谓词条件
        • 语句中通常不允许含有order by 和distinct
  • 数据查询
    • EXISTS/NOT EXISTS
      • 和in的区别：where 后面不用加属性
    • like
      • %
        • 匹配任意长度字符串
      • _
        • 匹配任意一个字符
      • escape
        • 转义符
          • like 'ab\\' escape '\' 匹配 ab\ 开头的字符串
    • 集合操作
      • union
      • intersect
        • 交
        • select 属性 from 表1 intersect select 属性 from 表2
      • except
        • 差
        • select 属性 from 表1 except select 属性 from 表2
  • 触发器语句
    • 创建触发器时需指定
      • 触发器名称
      • 触发器要有定义表
      • 触发事件
        • on 表名前的时间
      • 触发条件
        • when条件
      • 触发动作
    • 应用
      • 针对复杂的约束，应采用触发器来实现
    • 注意点
      • 触发器可以引用当前数据库以外的对象，但只能在当前数据库中创建触发器
      • 不能在临时表或系统表上创建触发器，但触发器可以引用临时表
    • 语句格式
      • • for each row 表示为行级触发器，对每一个被隐形爱过的元祖执行一次触发过程
        • for each statement 表示为语句级触发器，对整个事件值执行一次触发过程，缺省
    • 特点
      • 触发事件只能是对数据的新增、删除或更新
      • 触发器被事件激活时不是立即执行，还需要触发触发器条件才会响应触发事件
    • • referencing new row as nrow 表示需要引用触发动作的新行的数据，只有需要引用这个行数据才需要这个哦 留意下 ATOMIC 有点事务的意思
  • 嵌入式SQL
    • 语句格式
      • EXEC SQL<sql语句>
    • SQLCA
      • 系统默认定义的全局变量
    • 主变量(共享变量)
      • 用declare声明为了与sql中的属性名区分，在应用共享变量是，前面要加“：”
        • 共享的意思是主语言如C语言也能使用 SQL本身也能使用的意思
    • 引入指示变量来解决主语言无控制的问题
  • 游标
    • • 
• 非关系型数据库NOSQL
  • 传统数据库
  • ACID理论
    • 原子性
      • atomicity
    • 一致性
      • consistency
    • 隔离性
      • isolation
    • 持久性
      • durability
    • 针对事务
  • CAP理论
    • 一致性
      • consistency
        • 强一致性
          • 保证拿到的数据是最新的
        • 弱一致性
          • 数据更新后，拿到的有可能是更新前的值
        • 最终一致性
          • 保证数据最终是一致的，最新的，有时间间隔
        • BASE理论
          • 弱一致性的理论， 只要求最终一致性
    • 可用性
      • availablity
        • 事事有响应
    • 分区容忍性
      • partition tolerance
        • 分布式系统在遇到某节点或网络分区故障的时候， 仍然能够对外提供满足一致性或可用性的服务。
    • 对于一个分布式系统，最多只能实现三选二 要求保持一致性，那就要求锁表操作； 锁表了服务就不可用了
  • • 文档存储关键字：web应用 键值存储关键字：缓存 列存储关键字：分布式 图存储关键字：社交网络，系统，复杂
• 系统开发和运行知识
  • 软件生存周期
    • 1.可行性分析与项目开发计划
    • 2.需求分析
    • 3.架构设计
    • 4.详细设计
    • 5.编码和单元测试
    • 6.综合测试
    • 7.维护
  • 软件生存周期模型
    • 瀑布模型
      • 概念
        • 将软件生存周期各个活动规定为依线性顺序连接的模型
      • 不足
        • 需求必须明确，否则会改多次
      • 优点
        • 管理成本低
    • 增量模型
      • 就是每个模块可以分批次开发
      • 优点
        • 时间成本少，还能减少用户需求变更
      • 不足
        • 增加管理成本
    • 演化模型
      • 就是一边修正一边推进开发
      • 优点
        • 不断按用户要求修正就能得到高质量产品
        • 适用于需求不明确场景
      • 不足
        • 用户接触尚未稳定的功能会有不良影响
    • 螺旋模型
      • 将瀑布模型和演化模型结合，并加入了“风险分析”
      • 阶段
        • 1.制定计划
        • 2.风险分析
        • 3.实施工程
        • 4.用户评估
      • 适用于庞大、复杂并且具有高风险的系统
    • 喷泉模型
      • 一种以用户需求为动力，以对象作为驱动的模型。就是可以多项同时交叉进行意思
      • 优点
        • 节省开发时间
      • 不足
        • 不利于项目管理，要求严格管理文档，审核难度加大
      • 和增量模型相比，起码增量是按步骤进行的，而喷泉模型是同时进行的
  • 典型的软件开发方法
    • 结构化开发方法
      • 目标分解成模块开发的意思
      • 适合于数据处理领域的问题
      • 不适合解决规模较大且复杂的项目 因为模块不好划分
    • 原型化开发方法
    • 面向对象开发方法
      • 面向对象的一个有点是复用性，如java里的继承
    • 敏捷方法
      • 支持用户后期频发修改的意思
  • 软件项目管理
    • 1.成本估算
    • 2.风险分析
    • 3.进度管理
      • Gantt图
        • 优点
          • 能看到任务之间的并行性，和进制情况，有无落后
        • 缺点
          • 不能反应各任务间的依赖关系，和项目关键点
      • 项目计划评审技术(PERT图)
        • 缺点
          • 不能反应任务间的并行性
        • 优点
          • 能确定任务之间的关系
        • 相关概念
          • 前驱，后继
          • 关键节点/关键活动
            • 松弛时间为0的节点
          • 关键路径
            • 由关键活动串联起来的路径，可能会有多条
          • 松弛时间/浮动时间
        • 注意点
          • 顶点有可能是活动，也可能是节点。所以就有节点时间和活动时间一说
  • 数据流图(DFD、分层图)
    • 注意问题
      • 画数据流而不要画控制流
        • 数据流的输入或输出是加工
      • 输出数据流不应与输入数据流同名
    • 基本概念
      • 数据流
      • 加工
      • 数据存储(文件)
      • 外部实体(宿、源)
    • 数据字典
    • 数据流图平衡原则
      • 父图与子图之间的平衡
        • 保持父图与子图的平衡。父图中某加工的输入输出数据流必须与它的子图的输入输出数据流在数量和名字上相同。如果父图中的一个输入(输出)数据流对应于子图中几个输入(或输出)数据流，而子图中组成这些数据流的数据项全体正好是父图中这一个数据流，那么他们仍然算是平衡的
      • 子图内平衡
        • 每个加工必须既有输入数据流，又有输出数据流
    • 数据流图可能出现的错误
      • 只有进没有出的 黑洞流
      • 只有出没有进的 奇迹流
      • 输入流或输出流定义混淆
      • 数据流逻辑不正确
• 数据库设计
  • 数据库设计基本步骤
    • 1.用户需求分析
    • 2.概念结构设计
      • E-R图 有想法 在建立模型或框架
      • E-R图合并会存在冲突
        • 属性冲突
        • 命名冲突
        • 结构冲突
          • 在第一个ER图中作为实体，但在另一个ER图中作为属性
    • 3.逻辑结构设计
      • 把ER图转换成数据库关系模式，就是实际建表了
      • 视图建立也是
      • 关系规范化是逻辑设计阶段进行
    • 4.物理结构设计
      • 确定数据分布，存储结构和访问方式
      • 索引是物理结构设计阶段产物
    • 5.数据库实施阶段
    • 6.数据库运行和维护阶段
  • 需求分析阶段
    • 步骤
      • 1.调查机构情况
      • 2.熟悉业务活动
      • 3.明确用户需求
      • 4.确定系统边界
        • 系统需要做什么，不需要做什么的边界分析
      • 5.分析系统功能
      • 6.分析系统数据
      • 7.编写分析报告
    • 概念
      • 需求分析阶段的成果是系统需求说明书 包括数据流图，数据字典，系统功能结构图等
      • 数据字典
        • 5部分
          • 数据项
          • 数据结构
          • 数据流
          • 数据存储
          • 处理过程
  • 数据库运行维护与管理
    • 数据库重组和重构
      • 重组是删除碎片，不改变数据库逻辑和物理结构
      • 重构是表库结构改变
    • 数据库系统的审计
      • 记录数据库资源和权限使用情况
      • 因为仅仅是记录，所以升级是被动的，只能跟踪数据库修改而不能防止
      • 审计功能开启会影响系统性能
    • 数据库的存储管理
    • 数据库的安全性管理
    • SQL语句的编码检验
      • 经常提交commit,尽早释放锁
      • 频繁执行的sql语句，常见的优化策略有：尽可能减少多表查询或建立"物化视图" 用带 in 的条件子句等价替换or子句
    • 数据安全性管理
    • 索引维护和改进
      • 看瓶颈是查询还是更新，再确定是删除还是新建索引
      • 索引种类
        • B树索引
        • 散列索引
        • 聚簇索引
        • 。。。
• 事务管理
  • 相关语句
    • BEGIN TRANSACTION
      • 开启事务
    • END TRANSACTION
      • 结束事务
    • COMMIT
      • commit work（事务隐式性时使用）
    • ROLLBACK
      • Rollback work（事务隐式性时使用）
  • 事务的状态
    • 活动状态
    • 部分提交状态
    • 失败状态
      • 这是原因
        • abort
    • 中止状态
      • 事务执行前状态，这是结果
        • rollback
    • 提交状态
    • • 并不是说end transaction后才执行commit 而是因为只有commit了才算是提交状态， 活动状态和提交状态之间需要有个部分提交状态就是end transaction
  • 事务调度
    • 串行调度
    • 并发调度
      • 注意点
        • 其实也是串行，但是以分时间片的方法交叉执行
        • 并发调度有可能是错误调度
        • 以结果和"任意一次"串行调度结果比较来判断是否是正确调度(结果导向)
          • 可串行化调度的意思(这也是串行调度和可串行化调度的区别)
        • 并发破坏的是事务的隔离性和一致性
          • 保持隔离性的加锁方式
            • 排它锁，X锁，写锁，独占锁
            • 共享锁，S锁，读锁
              • 有S锁只能进行读取，不能进行修改
              • 加了S锁就不能再加排它锁
            • 封锁协议
              • 总结来说 就是除了二级封锁协议是读取完后释放的共享锁，两外两个级别封锁协议都是在事务结束后再释放的锁。 一级和三级的区别就是一级加的是排他锁，三级是共享锁
              • • 也只有二级封锁协议是在 读完后释放
            • 两段锁协议(2PL)
              • 就是要求先加完锁后再解锁，不能解锁后再进行加锁
      • 并发操作带来的问题
        • 数据不一致性有三类
          • 丢失修改
            • 修改覆盖
          • 不可重复读
            • 重复读取造成
          • 读脏数据
            • 读取了被回滚撤销的值
    • 可恢复调度
      • commit和rollback的顺序问题
  • 事务的隔离级别
    • 读未提交
    • 读已提交
    • 可重复读
    • 串行化、序列化
      • 就是要求串行执行
    • 隔离级别逐渐提高
  • 数据读取可能碰到的问题
    • 脏读
      • 就是读取了未提交的数据
        • 解决方法
          • 读已提交
    • 不可重复读
      • 读取了多次修改的数据，所以每次结果都不一样
        • 解决方法
          • 可重复读
    • 幻读
      • 由于新增或删除数据，每次查询的"结果集"都不一样。针对结果集条数
        • 解决方法
          • 串行化
          • 或者自己加锁解决
• 数据库备份
  • 数据库系统故障的种类
    • 事务故障
      • 引起原因
        • 逻辑错误
          • 数据找不到
        • 系统错误
          • 如死锁
          • 注意！！ 系统错误不是下面介绍的系统故障
    • 系统故障
      • 软硬件故障引起，影响了内存
    • 介质故障
      • 磁盘损坏，瞬间强磁场干扰
  • 数据库备份
    • 方法
      • 静态转储和动态转储
        • 静态是指在转储期间不允许对数据库进行任何存取、修改操作
        • 动态是指在转储期间允许对数据库进行存取、修改操作
      • 海量转储和增量转储
      • 日志文件
      • 数据库镜像
  • 数据库恢复
    • 撤销事务
      • 就是将未完成的事务进行撤销，恢复到执行前
      • 通过对日志文件进行反向扫描实现
      • undo
    • 重做事务
      • 提交了但数据还在缓冲区，没来得及写进数据库保存
      • redo
      • 正向扫描实现
  • 故障恢复策略
    • 事务故障的恢复
      • 事务故障的恢复是由系统自动完成的，对用户是透明的
      • 方法
        • 撤销事务
    • 系统故障的恢复
      • 根据事务的执行情况判断解决对策
        • 对于没有提交的就撤销事务
        • 对于提交，但数据还在缓冲区没有写入数据源库的，执行redo操作
    • 介质故障的恢复
      • 数据库遭到了破坏，需要重装数据库
      • 转载故障前最近一次的日志副本，撤销和重做选择进行
    • 检查点机制
      • 有事务的开始标志但没有事务结束标志
      • 在日志中设置检查点，反向扫描日志文件
      • 对于检查点后提交的事务，执行重做
      • 对于检查点后未提交的事务，执行撤销
      • • 管你是否是检查点，都是要这么做的
  • 数据库的完整性
    • 完整性就是完整性约束
      • 如性别只能是男或女
• 云计算和大数据
  • 云计算
    • 关键特征
      • 广泛的网络接入
      • 可测量的服务
      • 多租户
      • 按需自服务
      • 快速的弹性和可扩展性
      • 资源池化
      • 关键特征
      • 虚拟化技术
      • 可靠性高
      • 性价比高
    • 分类
      • 按云部署模式和云应用范围分类
        • 公有云
        • 社区云
        • 私有云
        • 混合云
          • 以上两种或两种以上的云组成
      • 按云计算的服务层次和服务类型分类
        • 基础设施即服务(IaaS Infrastructure as a service)
          • 虚拟机 网络等基础设施
        • 平台即服务(Paas Plat as a service)
          • 提供的是 符合环境的平台
        • 软件即服务(Saas Sofeware as a service)
    • 云关键技术
      • 虚拟化技术
      • 分布式数据存储
      • 并行计算
      • 运营支撑管理
  • 大数据
    • 特征
      • 多样性
      • 速度
      • 大量
      • 价值
      • 真实性
    • 处理流程
• 数据库主流应用技术
  • 看教材
• 标准化与知识产权
• 其他
  • 求依赖集的意思
  • 问关系模式存在哪些问题
    • 一般就是数据冗余，插入删除异常