分类： 未分类

发布于

架构师软考学习笔记【1】：渐入佳境（课程基础）

渐入佳境（课程基础）

技术类-计算机基础知识

第1章 计算机基础

1-1 计算机基础：冯·诺依曼计算机

冯·诺依曼计算机五大特征：
  1. 计算机由五大部件组成：
    • 控制器
    • 运算器
    • 存储器
    • 输入设备
    • 输出设备
      注：

      • 后期"控制器"和"运算器"被统一到CPU中
      • 存储器可分为内部存储器和外部存储器
  2. 指令和数据以同等地位存于存储器
  3. 指令和数据用二进制表示
  4. 指令由操作码和地址码组成
  5. 存储程序
  6. 以运算器为中心

    1-2 现代计算机硬件图和CPU（一）

    计算机主要硬件组成：
    • 主机：
    • 运算器ALU
    • 控制器
    • 存储器：
    • 主存
    • 辅存
    • I/O设备：
    • 输入设备
    • 输出设备
      注：CPU构成：运算器ALU、控制器、主存

      1-3 现代计算机硬件图和CPU（二）

      CPU主要构成
    • 运算器的组成：
      ① 自述逻辑单元ALU：数据的算术运算和逻辑运算；
      ② 累加寄存器AC：通用寄存器，为ALU提供一个工作区，用来缓存数据；
      ③ 数据缓冲寄存器DR：写内存时，暂存指令或数据；
      ④ 状态条件寄存器PSW：存状态标志与控制标志。
    • 控制器的组成：
      ① 程序计数器PC：存储下一条要执行指令的地址；
      ② 指令寄存器IR：存储即将执行的指令；
      ③ 指令译码器ID：对指令中的操作码字段进行分析解释；
      ④ 地址寄存大AR：用来保存当前CPU所访问的内在单元的地址；
      ⑤ 时序部件：提供时序控制信号。

      1-4 主存

    • 存储器的基本单位是存储单元，一般以8位二进制为一个存储单元。每个存储器单元都有一个地址，一般用十六进制数表示。
    • 地址总线：假如需要n位二进制数来表示所有的地址，则地址总线个数为n。
    • 数据总线：一次处理n位的数据，则数据总线的长度n。n的位数为一个字的长度。
    • 寻址空间范围算法：最大地址码-最小地址码+1。

      1-5 存储器

      存储器分类：
    • 按所处位置分：
    • 内存（主存）：CPU当前使用的指令和数据
    • 外存（辅存）：存放后备程序和数据
    • 按构成材料分：
    • 半导体存储器：
      • 静态存储器：双稳态触发器
      • 动态存储器：依靠电容上的电荷存储，主存
    • 磁存储器：利用磁性材料两种不同的状态长期保存信息，外存
    • 光存储器：利用光斑、晶像的变化表示信息，外存
    • 按工作方式分：
    • 读/写存储器：RAM
    • 只读存储器：
      • 固定只读存储器ROM：用户不能写数据
      • 可编程的只读存储器PROM：用户可写入一次
      • 可擦除可编程的只读存储器EPROM：可多次编程，紫外线擦除
      • 电可擦除可编程的只读存储器EEPROM：可多次编程，电擦除
      • 闪存：接近EEPROM，U盘
    • 按访问方式分：
    • 按地址访问的存储器
    • 按内容访问的存储器
    • 按寻址方式分：
    • 随机存储器RAM：按地址访问存储器的任一单元，主存
    • 顺序存储器SAM：访问时按顺序查找目标地趣，磁带
    • 直接存储器DAM：按照数据块所在位置访问，磁盘
    • 相联存储器：按照内容进行访问，Cache
存储器比较

寄存器\rightarrowCache\rightarrow主存\rightarrow磁盘
【容量】小\rightarrow大
【速度】快\rightarrow慢
【价格】高\rightarrow低

1-6 校验码概念

  • 信息出错：信息保存在电容中，如遇电磁环境干扰，会导致电容的充放电或触发器的翻转，存在存储器的信息可能会出错。
  • 码距与检错纠错：一个编码系统的码距就是整个编码系统中任意（所有）两个码字的最小距离。
    • 在一个码组内为了检测e个误码，要求最小dcgd距应该满足：d \geq e + 1
    • 在一个码组内为了纠正t个误码，要求最小码距应该满足：d \geq 2t + 1
    • 同时纠错检错：d \geq e + t + 1

      1-7 奇偶校验码

  • 奇偶校验方法：保证信息位上的1的个数为奇（偶）数个
  • 局限：只能发现奇数个们出错的情况

    1-8 海明码（一）

  • 海明码：基于奇偶校验、分组校验
  • 海明码的校验码的位置必须是在2^n位置（n从0开始，分别代表从右边数起分别是1、2、4、8、16……），信息码也就是在非2^n位置

    1-9 海明码（二）

  • 设数据位是n位，校验位是k位，则n和k必须满足以下关系：
    2^k \geq n + k + 1

    1-10 循环冗余校验码CRC

  • 采用CRC进行差错校验，生成多项式为G(X) = X^4 + X + 1，信息码字为10111，则计算出来的CRC校验码为（    ）。
    • 解题步骤：
      (1) 化解多项式为10011
      （X^4 + X + 1 = 2^4 + 2^1 + 2^0 \rightarrow 2^4 + 2^3 + 2^2 + 2^1 + 2^0 \rightarrow 10011）
      (2) 信息码加0做模二除运算（不进位加法/异或运算）\rightarrow补（4{多项式最高次幂}个零）；异或运算：相同为0，不同为1
      (3) 得到的余数即为校验码

      1-11 指令的流水线（一）

      指令
  • 指令周期：取出（解释）并执行一条指令所需的全部时间
  • 完成一条指令（一个指令周期）可以分为：取指周期、分析周期、执行周期
  • 指令流水技术：指令步骤的并行、提高处理器执行指令的效率
  • 指令的三种执行方式：
    (1) 顺序方式
    (2) 重叠方式
    (3) 并行方式

    1-12 指令的流水线（二）

  • 流水线周期：【并行指令中（取指、分析、执行）】执行时间最长的一段
  • 公式：(k为流水线执行阶段数，n为指令数）
    ① 理论公式：(t1 + t2 + t3 + ... + tk) + (n-1) * \Delta t
    ② 实践公式：(k + n - 1) * \Delta t
  • 流水线的吞吐率(TP)和最大吞吐率($$TP_{max}$$)：
    • TP = \frac{n}{t}
      (n=指令条数，t=流水线执行时间)
    • TP_{max}=\lim_{n\rightarrow\infty}\frac{n}{(k+n-1)\Delta t}=\frac{1}{\Delta t}
  • 流水线加速比：S = \frac{a}{b}
    (a = 不执行流水线的时间，b = 执行流水线的时间)
    注：大数比小数

    1-13 高速缓冲储存器

    局部性原理：
  • 时间局部性
  • 空间局部性
    Cacher的映射方法
  • 直接映像
    • 优点：地址变换很简单
    • 缺点：不灵活、块冲突率高。
  • 全相联映像
    • 优点：位置不受限制，十分灵活。
    • 缺点：无法从主存块号中直接获得Cache的块号，变换比较复杂，速度比较慢。
  • 组相联映像
    距离CPU较近位置可以采用直接映像或者组相联映像；距离CPU较远的可以采用全相联映像

    Cache的性能

    如果以Hc为代表对Cache的访问命中率，tc为Cache的存取时间，tm为主存的访问时间，则Cache的平均访问时间ta为：
    ta=Hc * tc + (1 - Hc ) * tm

    写策略。
    1. 写回法（write-back）
      当CPU对Cache写命中时，只修改Cache的内容不立即写入主存，只当此行被换出时才写回主存。这种策略使Cache在CPU-主存之间，不仅在读方向而且在写方向上都起到高速缓存作用。
    2. 写直达法（write-through）
      又称全写法，写透。是当Cache写命中时，Cache与主存同时发生写修改。
    3. 标记法
      数据进入Cache后，有效位置1，当CPU对该数据修改时，数据只写入主存并将该有效位置0。要从Cache中读取数据时要测试其有效位，若为1则直接从Cache中取数，否则从主存中取数。

      Cache替换策略

      (1) 随机算法。最简单。
      (2) 先进先出（First In and First Out, FIFO）算法。容易实现，系统开销小。缺点是可能会把一些需要经常使用的数据替换掉。
      (3) 近期最少使用（Least Recently Used, LRU）算法。需要对每一块设置一个“年龄计数器”的硬件或软件，用以记录其被使用的情况。
      (4) 最不经常使用页置换（Least Frequently Used, LFU）算法。计数器位数多，实现困难。

      1-14 磁盘储存器

  • 存储容量=n * t * s * b，其中：n为保存数据的总记录面数，t为每面磁道数，s为每道的扇区数，b为每个扇区存储的字节数。
  • 硬盘存取时间=寻道时间+等待时间+读/写时间，其中读/写时间可忽略不计。

    1-15 计算机系统结构的分类&指令系统

    计算机系统结构的分类
    Flynn分类

    (1) 指令流：指机器执行的指令序列；
    (2) 数据流：指由指令流调用的数据序列，包括输入数据和中间结果，但不包括输出数据。
        Flynn根据不同的指令流-数据流组织方式，把计算机系统分成以下四类：
    (1) 单指令流单数据流（Single Instruction stream and Single Data stream, SISD）
    (2) 单指令流多数据流（Single Instruction stream and Multiple Data stream, SIMD）：SIMD以并行处理机（矩阵处理机）为代表
    (3) 多指令流单数据流（Multiple Instruction stream and Single Data stream, MISD）：不常见
    (4) 多指令流多数据流（Multiple Instruction stream and Multiple Data stream, MIMD）：多核处理器。

    指令系统
  • 复杂指令系统CISC的特点
    (1) 指令数据众多
    (2) 指令使用频率相差悬殊
    (3) 支持很多种寻址方式
    (4) 变长的指令
    (5) 指令可以对主存单元中的数据直接进行处理
    (6) 以微程序控制为主
  • 精简指令系统RISC的特点
    (1) 指令数量少
    (2) 指令的寻址方式少
    (3) 指令的长度固定
    (4) 以硬布线逻辑控制为主
    (5) 单周期指令执行，采用流水线技术
    (6) 优化的编译器
    (7) CPU中的能用寄存器数量多，一般在32个以上，有的可达上千个

    1-16 总线

    总线是一组能为多个部件分时共享的公共信息传送线路

  • 按相对于CPU或其他芯片的位置可分为内部总线和外部总线。
  • 按总线功能分，可分为地址总线、数据总线、控制总线
  • 按总线中数据线的多少，可分为并行总线和串行总线
名称 数据线 特点 应用
并行总线 多条双向数据线 有传输延迟，适合近距离连接 系统总线（计算机各部件）
串行总线 一条双向数据线，或两条单身数据线 速率不高，但适合长距离连接 通信总线（计算机之间或计算机与其他系统间）

1-17 磁盘阵列

  1. RAID 0（无冗余和无校验的数据分块）代表了所有RAID级别中最高的存储性能。
  2. RAID 1（磁盘镜像阵列）磁盘空间利用率为50%。
  3. RAID 2（采用纠错海明码的磁盘阵列）：增加了海明码纠错技术，适用于大量数据传输，很少使用。
  4. RAID 3和RAID 4（采用奇偶校验码的磁盘阵列）RAID 3采用位交叉奇偶校验—适用于大型文件且I/O需求不频繁的应用，RAID 4采用块交叉奇偶校验码—适用于大型文件的读取。
  5. RAID 5（无独立校验盘的奇偶校验码的磁盘阵列）：适用于I/O需求频繁的应用。当有N块阵列盘时，用户空间为N-1块盘容量。
  6. RAID 6（独立的数据硬盘与两人独立的分布式校验方案）：RAID 5的扩展，增加了数据保护。当有N块阵列盘时，用户空间为N-2块盘容量。
  7. RAID 7（最优化的异步高I/O速率和高数据传输率）：自带操作系统和管理工具，可独立运行。
  8. RAID 10（最可靠与高性能）：将RAID 1和RAID 0标准结合.

    第2章 操作系统基础

    2-1 操作系统基础：概述

    分类
    • Windows
    • macOS
    • Unix
    • Linux
      考点分布
    • 处理机处理
    • 进程的状态
    • 前驱图
    • PV操作
    • 存储器管理
    • 逻辑地址
    • 物理地址
    • 存储方案
    • 设备管理
    • 输入输出控制方式
    • 文件管理
    • 文件的索引
    • 用户接口

      2-2 进程

    • 进程的三状态模型：
              运行
          \nearrow\swarrow \searrow
        就绪\longleftarrow阻塞
    • 进程通常由程序、数据集合、进程控制块PCB组成。PCB是一种数据结构，是进程存在的唯一标识。
    • PCB组织方式
    • 线性方式
    • 链接方式
    • 索引方式
    • 前驱图是一个有向无循环图。描述多个程序或进程之间的执行顺序关系。

      2-3 PV操作01

    • 互斥问题
    • 进入临界区之前先执行P操作（可能阻塞当前进程）
    • 离开临界区之后执行V操作（可能唤醒某个进程）
    • P操作
      ① 将信号量S的值减1，即S–；
      ① 如果S>=0，则该进程继续；否则该进程置为等待状态。
    • V操作
      ① 将信号量的值加1，即S++；
      ① 如果S>0，则该进程继续执行；否则说明有等队列中有等待进程，需要唤醒等待进程。

      2-4 PV操作02

    • 同步问题
    • 运行条件不满足时，能让进程暂停（在关键操作之前执行P操作）
    • 运行条件满足时，能让进程继续（在关键操作之后执行V操作）
    • 规则：
      • 不能向满缓冲区存产品
      • 不能向空缓冲区取产品
      • 每个时刻仅允许1个生产者或消费者存或取1个产品

        2-5 存储管理01

              _____
             \downarrow                        \downarrow
           CPU\longleftrightarrow缓存\longleftrightarrow内存\longleftrightarrow辅存

  • 当内存太小不够用时，用辅存来支援内存
  • 暂时不运行的模块换出到辅存上，必要时再换入内存
    地址重定位

    是指将程序中的虚拟地址（逻辑地址）变换成内存的真实地址（物理地址）的过程

  • 逻辑地址
    • 相对地址
    • CPU所生成的地址。内部和编程使用、并不唯一
  • 物理地址
    • 绝对地址
    • 加载到内存地址寄存器中的地址，内存单元的真正地址
      静态重定位
  • 绝对地址=相对地址+程序存放的内存地址
  • 特点：
    • 程序运行前就确定映射关系
    • 程序装入后不能移动
    • 程序战胜连续的内存空间
      动态重定位
  • 绝对地址=重定位寄存器器的值（BR）+逻辑寄存器的值（VR）
  • 特点
    • 程序占用的内存空间可动态变化
    • 程序不要求连续的内存空间
    • 便于多个进程共享代码

      2-6 存储管理02

      存储管理的主要目的是解决多个用户使用主存的问题

  • 分区存储管理
  • 分页存储管理
  • 分段存储管理
  • 段页式存储管理
  • 虚拟存储管理
    分区管理

    把主存的用户区划分成若干个区域，每个区域分配给一个用户作业使用，并限定它们只能在自己的区域运行。

  • 可重定位分区
  • 可变分区
  • 固定分区
    页式存储管理

    分页的基本思想是把程序的逻辑空间和内存空间的物理空间按照同样的大小划分成若干页面，并以页面为单位进行分配。
    常用的页面调度算法：

  • 最优（OPT）算法
  • 随机（RAND)算法
  • 先进先出（FIFO）算法
  • 最近最少使用（Least Recently Used，LRU）算法
    段式存储管理

    分段的基本思想是把用户作业按逻辑意义上有完整意义的段（主程序、子程序、数据段等）来划分，并以段为单位作为内外存交换的空间尺度。

    段页式存储管理

    根据程序模块分段，段内再分页，内存被划分成定长的页。可提高内存空间的利用率。

    2-7 设备管理

  • 外围设备和内存之间的数据控制方式
    • 程序控制方式
    • 中断方式
    • 直接存储访问（Direct Memory Access，DMA）
  • 虚设备与SPOOLING技术
    • 假脱机（Simulataneous Peripheral Operating On Line, SPOOLING）的意思是外部设备同时联机操作，又称为假脱机输入/输出操作，采用一组程序撒气一台输入/输出处理器。
    • 用于将低速独占设备改造成可共享设备。

      2-8 文件存储管理

      文件的逻辑结构
  • 无结构的字符流文件
  • 有结构的记录文件
    （1）顺序文件
    （2）索引顺序文件
    （3）索引文件
    （4）直接文件

    文件的物理结构

    常用的文件分配策略：
    （1）顺序分配（连续分配）
    （2）链接分配（串联分配）
    （3）索引分配

    • 一级索引（n个地址）
    • 二级间接索引（n^2个地址）
    • 三级间接索引（n^3个地址）

      2-9 文件存储设备管理

      有三种不同的空闲块管理方法：
      （1）索引法
      （2）链接法
      （3）位示图法在外存上建立一张位示图（Bitmap），记录文件的存储器的使用情况。每一位仅对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用。

      第3章 计算机网格基础

      3-1 计算机风格基础：网络互联模型&常见网络协议

  • 1977，国际标准化组织制定了“开放系统互联参考模型（Open System Interconnection/Reference Model, OSI/RM）”。七层以模型，分别是物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。口决：“巫术忘传会飚鹰”。
  • 常见的网络协议
    • 应用层协议：
      • FTP(File TransportProtocol，文件传输协议)
      • TFTP(Trivial FileTransfer Protocol，简单文件传输协议)
      • HTTP(Hypertext TransferProtocol，超文本传输协议)
    • 传输层协议：
      • TCP：可靠的、面向连接的、全双工的数据传输服务。用于传输数据量比较少，且对可靠性要求高的场合。
      • UDP：不可靠的、无连接的协议，可以保证应用程序进程间的通信。用于传输数据量大，对可靠性要求不是很高，但要求速度快的场合。
    • 网络层协议：
      • IP：无连接的和不可靠的，它将差错检测和流量控 制之类的服务授权给了其他的各层协议，这正是 TCP/IP 能够高效率工作的一个重要保证。
      • ICMP（Internet Control Message Protocol， 网际控制报文协议）
      • IGMP（Internet Group Management Protocol，网际 组管理协议）
      • ARP（Address Resolution Protocol，地址解析协议）
      • RARP（Reverse Address Resolution Protocol，反向地址解析协议）

        3-2 IP地址及其表示方法

        IP（IPV4）地址是一个32位的二进制数的逻辑地址，分成4个字节，每个字节间以“.”区分。IP地址由两个部分组成，网络号+主机号。
        网络号（4位）分类：

  • A类：1～126
  • B类：128～191
  • C类：192～223
  • D类：224～255+组播地址
  • E类：240～255+保留

    3-3 子网与子网掩码

    三级IP地址：网络号+子网号+主机号
    子网掩码也是32位二进制数，网络与子网标识全为1，主机标识全部为0。

  • A类地址的子网掩码:255.0.0.0
  • B类地址的子网掩码:255.255.0.0
  • C类地址的子网掩码:255.255.255.0

将IP地址和其对应的子网掩码逐位进行“与”运算，可得到对应的子网的网络地址。
131.1.123.24/27：/27代表前27位都是网络号，主机号是5位，主机号要去掉全0和全1。

3-4 IPV4数据报/IPV6

IPV4数据报
报名 含义
版本 IP协议的版本。这里版本号为4。
首部长度 可表示的最大数值是15个单位(4 字节为一个单位)，60字节。
区分服务 不同优先级服务质量不同，只有在使用区分服务(DiffServ) 时有效。
总长度 首部与数据之和的长度，最大长度为2^16-1=65535字节。
标识 唯一标识数据报的标识符。
片偏移 指明该段处于原来数据报中的位置。
生存时间 记为TTL(Time To Live)，指示数据报在网络中可通过的路 由器的最大值。
协议 数据报携带的协议(TCP、UDP、IGMP等)
首部检验和 只检验首部，不检验数据。采用16位二进制反码求和算法。
可选字段 可记录时间戳 ，通过路径，安全信息等。
填充 填充为4的倍数
IPV6
  • 1995年12月推出。
  • 共128位，以16位为一段，共为8段，每段的16位转换为 一个4位的十六进制数，每段之间用“:”分开。
  • IPV6的优势：
    • IPv6有更大的地址空间
    • IPv6使用更小的路由表
    • IPv6增加了组播支持与对流支持
    • IPv6加入了自动配置的支持
    • IPv6具有更高的安全性
  • IPv4/IPv6 过渡技术:
    (1) 双协议栈技术: 支持两种业务的共存。
    (2) 隧道技术: 实现在 IPv4 网络上对 IPv6 业务的承载。具体的隧道技术包括: 6to4 隧道;6over4 隧道;ISATAP 隧道。
    (3) NAT-PT 技术：NAT – PT 使用网关设备连接 IPv6 和 IPv4 网络。
  • IPV6数据报
报名 含义
版本 IP协议的版本。这里版本号为6。
流量分类 通信类型，相当于IPV4服务类型字段。
流标签 从源点到终点的一系列数据报，同一个流上的数据报标签相同，保证服务质量。
有效负载长度 除基本首部以外的字节数(所有扩展首部都算在有效负载内)，最大 值64KB
下一头部 相当于IPV4的协议字段或可选字段。
跳数限制 用于检测路由循环，路由器在转发数据报时对这个字段减1，变成0丢弃该数据报。
  • IPv6数据报的目的地址可以是以下三种基本类型地址之一∶ (1)单播((unicast)∶传统的点对点通信。 (2)多播/组播(multicast)∶一点对多点的通信。 (3)任播(anycast)∶这是 IPv6增加的一种类型。任播的目的站是一组 计算机，但数据报在交付时只交付其中的一个，通常是距离最近的一个。

    3-5 TCP与UDP

    TCP协议
  • 传输控制协议(Transmission Control Protocol，TCP)是一种可靠的、面向 连接的字节流服务。
  • TCP建立在无连接的IP基础之上，因此使用了3种机制实现面向连接的服务。
    1) 使用序号对数据报进行标记。
    2) TCP使用确认、校验和定时器系统提供可靠性。
    3) TCP使用窗口机制调整数据流量。
  • TCP只有一种类型的PDU，叫作TCP段
    UDP协议
  • 用户数据报协议(User Datagram Protocol，UDP)是一种不可靠的、无连接的数据报服务。
  • UDP特点：
    (1) UDP是无连接的，发送数据之前不需要建立连接，因此减少了开销和发送数据之前的时延。
    (2) UDP使用尽最大努力交付，即不保证可靠交付，因此主机不需要维持复杂
    的连接状态表。
    (3) UDP是面向报文的。UDP对应用层交下来的报文，既不合并，也不拆分，而
    是保留这些报文的边界。UDP一次交付一个完整的报文。
    (4) UDP没有拥塞控制，因此网络出现的拥塞不会使源主机的发送速率降低。
    这对某些实时应用是很重要的。很适合多媒体通信的要求。
    (5) UDP支持一对一、一对多、多对一和多对多的交互通信。
    (6) UDP的首部开销小，只有8个字节，比TCP的 20个字节的首部要短。

    3-6 网络设计&综合布线系统

    网格设计
  • 接入层：通常将网络中直接面向用户连接或访问网络的部分称为接入层，将 位于接入层和核心层之间的部分称为分布层或汇聚层。
  • 汇聚层：是核心层和接入层的分界面，完成网络访问策略控制、数据包处理、过滤、寻址，以及其他数据处理的任务。
  • 核心层：网络主干部分称为核心层，核心层的主要目的在于通过高速转发通信，提供优化、可靠的骨干传输结构，因此，核心层交换机应拥有 更高的可靠性，性能和吞吐量。
    综合布线系统

    综合布线系统是一个用于传输语音、数据、影像和其他信息的标准结 构化布线系统，是建筑物或建筑群的传输网络，它使语言和数据通信设备、 交换设备和其他信息管理系统彼此相连接。
    综合布线的热物理结构一般采用模块化设计和分层星型拓扑结构。系统结构有6个独立的子系统:

    1. 工作区子系统：它是工作区内终端设备连接到信息插座之间的设备组成，包括信息插座、连接软线、适配器、计算机、网络集散器、电话、报警探头、摄像机、监视器、音响等。
    2. 水平子系统：水平子系统是布置在同一楼层上，一端接在信息插座，另一端接在配线间的跳线架上，它的功能是将干线子系统线路延伸到用户工作区，将用户工作区引至管理子系统，并为用户提供一个符合国际标准，满足语音及高速数据传输要求的信息点出口。
    3. 管理子系统：安装有线路管理器件及各种公用设备，实现整个系统集中管理，它是干线子系统和水平子系统的桥梁，同时又可为同层组网提供条件。其中包括双绞线跳线架、跳线(有快接式跳线和简易跳线之分)。
    4. 垂直(干线)子系统：通常它是由主设备间至各层管理间，特别是在位于中央点的公共系统设备处提供多个线路设施，采用大对数的电缆馈线或光缆，两端分别端接在设备间和管理间的跳线架上，目的是实现计算机设备、程控交换机(PBX)、控制中心与各管理子系统间的连接，是建筑物干线电缆的路由。
    5. 设备间子系统：该子系统是由设备间中的电缆、连接跳线架及相关支撑件、防雷电保护装置等构成。可以说是整个配线系统的中心单元，因此它的布放、造型及环境条件的考虑适当与否，直接影响到将来信息系统的正常运行及维护和使用的灵活性。电话交换机、计算机主机设备及入口设施也可与配线设备安装在一起。
    6. 建筑群子系统:它是将多个建筑物的数据通信信号连接成一体的布线系统，它采用架空或地下电缆管道或直埋敷设的室外电缆和光缆互连起来，是结构化布线系统的一部分，支持提供楼群之间通信所需的硬件。

      3-7 地址和域名

      Internet地址

      Internet地址分为3级，可表示为“网络地址.主机地址.端口地址”的形式。其中，网络和主机地址即 IP地址;端口地址就是TCP或UDP地址，用于表示上层进程的服务访问点。TCP/IP 网络中的大多数公共应用进程都有专用的端口号，这些端口号是IANA (Internet Assigned Numbers Authority)指定的，其值小于1024，而用户进程的端口号一般大于1024。

      域名系统
  • 域名系统(Domain Name System，DNS)是把主机域名解析为IP 地址的系统，解决了IP地址难记的问题。该系统是由解析器和域名服务器组成的。
  • DNS使用UDP协议，较少情况下使用TCP协议，端口号均为53。
  • 域名系统由三部分构成:DNS名字空间、域名服务器、DNS客户机。
    1) 根域：根域处于Internet上域名空间结构树的最高端，是树的根，提供根域名服务。根域用“.”来表示。
    2) 顶级域名(To p Level Domain，TLD)：顶级域名在根域名之下，分为三大类:国家顶级域名、通用顶级域名和国际顶级域名。
    3) 主机：属于最低层域名，处于域名树的叶子端，代表各类主机提供的服务。
  • 通用顶级域名
域名 使用对象
com 商业机构等盈利性组织
edu 教育机构、学术组织和国家科研中心等
gov 美国非军事性的政府机关
mil 美国的军事组织
net 网络信息中心(NIC)和网络操作中心(BIC)等
org 非盈利性组织、例如技术支持小组、计算机用户小组等
int 国际组织
  • 顶级域下面是二级域，这是正式注册给组织和个人的唯一名称，例如
    www.microsoft.com 中的microsoft 就是微软注册的域名。
  • 在二级域之下，组织机构还可以划分子域，使其各个分支部门都获得一个专用的名称标识， 例如www.sales.microsoft.com中的sales是微软销售部门的子域名称。划分子域的工作可以一直延续下去，直到满足组织机构的管理需要为止。但是标准规定，一个域名的长度通常不超过63个字符，最多不能超过255个字符。
    域名服务器
    名称 定义 作用
    主域名服务器 维护本区所有域名信息，信息存于磁盘文件和数据库中 提供本区域名解析，区内域名信 息的权威。具有域名数据库。一个域有且只有一个主域名服务器
    辅助域名服务器 主域名服务器的备份服务器 提供域名解析服务，信息存于磁盘文件和数据库中主域名服务器备份，可进行域名 解析的负载均衡。具有域名数据库
    缓存域名服务器 向其他域名服务器进行域名查询，将查询结果保存在缓存中的域名服务器 改善网络中DNS服务器的性能，减少反复查询相同域名的时间，提高解析速度，节约出口带宽。 获取解析结果耗时最短，没有域名数据库
    转发域名服务器 负责非本地和缓存中无法查到的域名。接收域名查询请求，首先查询自身缓存，如果找不到对应的，则转发到指定的域名服务器查询 负责域名转发，由于转发域名服务器同样可以有缓存，因此可以 减少流量和查询次数。具有域名数据库
    域名查询

    DNS查询过程的两种方法:
    (1) 递归查询：当用户发出查询请求时，本地服务器要进行递归查询。这种查询方式 要求服务器彻底地进行名字解析，并返回最后的结果一一IP地址或错误信息。
    (2) 迭代查询：服务器与服务器之间的查询采用迭代的方式进行，发出查询请求的服 务器得到的响应可能不是目标的IP地址，而是其他服务器的引用(名字和地址)，那么本地服务器就要访问被引用的服务器，做进一步的查询。如此反复多次，每次都更接近目标的授权服务器，直至得到最 后的结果一一目标的IP地址或错误信息。

    网络互连与常用设备
    互联设备 工作层次 主要功能
    中继器 物理层 对接收信号进行再生和发送，对高层协议是透明的，但使用个数有限（例如，在以太网中只能使用4个
    网桥 数据链路层 根据帧物理地址进行网络之间的信息转发，可缓解网络通信繁忙度，提高效率。只能够连接相同MAC层的网络
    路由器 网络层 通过逻辑地址进行网络之间的信息转发，可完成异构网络之间的互联互通，只能连接使用相同网络层协议的子网
    网关 高层（第4～7层） 最复杂的网络互联设备。用于连接网络层以上执行不同协议的子网
    继线器 物理层 多端口中继器
    二层交换机 数据链路层 是指传统意义上的交换机，多端口网桥
    三层交换机 网络层 带路由功能的二层交换机
    多层交换机 高层（第4～7层） 带协议转换的交换机
    网络存储技术

    目前，主流的网络存储技术主要有三种，分别是直接附加存储(Direct Attached Storage， DAS)、网络附加存储(Network Attached Storage， NAS)和存储区域网络(Storage Area Network，SAN)。

    1. 直接附加存储
      DAS 是将存储设备通过 SCSI(Small Computer System Interface，小 型计算机系统接口)电缆直接连到服务器，其本身是硬件的堆叠，存储操作依赖 于服务器，不带有任何存储操作系统。因此，有些文献也把 DAS 称为 SAS (Server Attached Storage，服务器附加存储)。
    2. 网络附加存储
      采用 NAS 技术的存储设备不再通过 I/O 总线附属于某个特定的服务器，而是通过网络接口与网络直接相连，由用户通过网络访问。
      NAS 存储支持即插即用，可以在网络的任一位置建立存储。基于 Web 管理，从而使设备的安装、使用和管理更加容易。NAS 可以很经济地解决存储容量不足的问题，但难以获得满意的性能。
    3. 存储区域网络
      SAN 是通过专用交换机将磁盘阵列与服务器连接起来的高速专用子网。它没有采用文件共享存取方式，而是采用块(block)级别存储。SAN 是通过专用高速网将一个或多个网络存储设备和服务器连接起来的专用存储系统，其最大特点是将存储设备从传统的以太网中分离出来，成为独立的存储区域网络。

      网络系统建设

      网络设计的原则：

    4. 采用先进、成熟的技术。
    5. 遵循国际标准，坚持开放性原则。
    6. 网络的可管理性。
    7. 系统的安全性。
    8. 灵活性和可扩充性。
    9. 系统的稳定性和可靠性。
    10. 经济性。
    11. 实用性。

      第4章 数据库系统的结构

      4-1 数据库基础：数据库系统的结构

  • 应用开发人员的角度
    • 三级抽象
      • 用户级数据库：用户视图，可相互重叠。
      • 概念级数据库：DBA视图，所有用户视图的最小并集。
      • 物理级数据库：内部视图，对应于内模式，接近于物理存储。
    • 三级模式：
      • 概念模式：模式、逻辑模式，是数据项值的框架。一个数据库只有一个概念模式。
      • 外模式：子模式、用户模式，描述用户视图的数据结构。
      • 内模式：数据物理结构和存储方式的描述，数据库内部的数据表示方式。一个数据库只有一个内模式。
  • 最终用户角度
    • 单用户结构
    • 主从结构
    • 分布式结构
    • 客户-服务器结构
    • 浏览器-应用服务器/数据库服务器
  • 两级独立性
    • 物理独立性：物理存储改变时，应用程序不需要改变。
    • 逻辑独立性：数据的逻辑结构改变时，应用程序不需要改变。（更难实现）

      4-2 数据模型

  • 概念数据模型：按用户的观点进行数据建模，E-R模型。
  • 基本数据模型：按照计算机系统的观点进行数据建模，常用的模型有层次模型、网状模型、关系模型和面向对象模型。
  • 数据的约束条件：
    • 实体完整性—主属性不能取空值。
    • 参照完整性—外键要么为空，要么必须是其他关系的主属性。
    • 用户定义完整性—具体应用所定义的约束条件。

      4-3 关系型数据库

概念 名词解释
关系 可以理解为一张二维表，每个关系都具有一个关系名，即表名
元组 可以理解为二维表中的一行，在数据库中被称为记录
属性 可以理解为二维表中的一列，在数据库中被称为字段
域 属性的取值范围，即数据库中某一列的取值限制
关键字 一组可以唯一标识元组的属性，数据库中称为主键，由一列或多列组成
关系模式 对关系的描述。格式为：关系名（属性1，属性2，……，属性N），在数据库中成为表结构。

4-4 关系代数01

集合运算符 含义 名词解释
\cup 并 关系R与S的并是由属于R或属于S的元组构成的集合。
- 差 关系R与S的差是由属于R但不属于S的元组
\cap 交 关系R与关系S的交是由属于R同时又属于S的元组构成的集合
\times 笛卡尔积 两个元组分别为n目和m目的关系R和关系S的笛卡尔积是一个（n+m)列的元组的集合。元组的前n列是关系R的一个元组，后m列是关系S的一个元组。
专门关系的运算符 含义 名词解释
\sigma 选择 取得关系R中符合条件的行
\pi 投影 取得关系R中符合条件的列
\Join 连接 等值连接：关系R、S,取两者笛卡尔积中属性值相 等的元组。自然连接:一种特殊的等值连接，它要求比较的属性列必须是相同的属性组，并且把结果中重复属性去掉。注意与笛卡尔积的区别。

4-5 关系代数02

  • 外连接：两个关系R和S进行自然连接时，选择两个关系R和S公共属性相等的元组，去掉重复的属性列构成新关系。
    1) 左外连接：R和S进行自然连接时，只把R中舍弃的元组放到新关系中。
    2) 右外连接：R和S进行自然连接时，只把S中舍弃的元组放到新关系中。
    3) 完全外连接：R和S进行自然连接时，只把R和S中舍弃的元组都放到新关系中。

    4-6 函数依赖

    定义
  • 设R(U)是在属性U上的关系模式，X,Y是U的子集，若对于R(U)的任意的一个可能的关系r，r中的任意两个元组在X上的属性值相等，那么在Y上的属性值也相等，则称“X函数确定Y“或”Y函数依赖于X“，记作X \rightarrow Y。X称为这个函数依赖的决定属性组，也称为决定因素。
  • 若Y不函数依赖于X，则记为X \nrightarrow Y
  • 函数依赖是语义范畴内的概念。如Sname \rightarrow Sno函数依赖只有在“学生不允许有重名”的条件下成立。
  • X \rightarrow Y，Y \nsubseteq X，则称X \rightarrow Y是非平凡的函数依赖。
  • X \rightarrow Y，Y \subseteq X，则称X \rightarrow Y是平凡的函数依赖。
  • 例如：关系式Student(Sno,Sdept,Mname,Cno,Grade)
名称 定义
完全函数依赖 (Sno,Cno) \rightarrow Grade是完全函数依赖
部分函数依赖 (Sno,Cno) \rightarrow Sdept是完全函数依赖
传递依赖 Sno \rightarrow Sdept,Sdept \rightarrow Mname，则称Sno传递依赖于Mname
Armstrong公理

从已知的一些函数依赖，可以推导出另外一些函数依赖，这就需要一些推理规则，这些规则常被称作“Armstrong 公理”。

  • 设关系式R(U,F)，U是关系模式R的属性集，F是U上一组函数依赖，则有以下三条推理规则：
    • A1自反律：若Y \subseteq X \subseteq U，则X \rightarrow Y为F所蕴含；
    • A2增广律：若X \rightarrow Y为F所蕴含，且Z \subseteq U，则XZ \rightarrow YZ；
    • A3传递律：若X \rightarrow Y，Y \rightarrow Z为F所蕴含，则X \rightarrow Z为F所蕴含。
  • 根据上面三条推理规则，又可推出下面三条推理规则：
    • 合并规则：若X \rightarrow Y，Y \rightarrow Z，则X \rightarrow YZ为F所蕴含；
    • 伪传递规则：若X \rightarrow Y，WY \rightarrow Z，则XW \rightarrow YZ为F所蕴含；
    • 分解规则：若X \rightarrow Y，Z \subseteq Y，则X \rightarrow Z为F所蕴含。
      键值
  • 例如：关系式S1(Sno,Sdept,Sage)
    • 超键：(Sno,Sdept)、(Sno,Sage)、(Sno,Sdept,Sage)是超键
    • 主键：Sno \rightarrow Sdept，Sno \rightarrow Sage，Sno是主键（码）；若有关系式SC(Sno,Cno,Grade)中,（Sno,Cno)是主键
  • 例如：关系式S2(Sno,Sname,Sdept,Sage)
    • 候选键：Sno、Sname是候选键，选择Sno为主键。不含有多余属性的超键称为候选键。
  • 外键
    如果关系模式R中的某些属性集不是R的主键，而是关系模式S的主键，则这个属性集对模式R而言是外键。

    属性

    包含在任何一个主键中，称为主属性，否则为非主属性。

    全码

    例如：关系模式R(P，W，A)中，P是演奏者，W是作品，A是听众，该关系模式只有一个包含了全部属性的主键，是全码。

    4-7 规范化01

    关系数据库设计的方法之一就是设计满足适当范式的模式，通常可以通过判断分解后的模式达到几范式来评价模式的规范化程度。

  • 第一范式（1NF）
  • 第二范式（2NF）
  • 第三范式（3NF）
  • BC范式（BCNF）
  • 第四范式（4NF）
  • 第五范式（5NF）

    4-8 规范化02

  • 第一范式（1NF）：若关系模式R的每一个分量是不可再分的数据项，则关系式R属于第一范式。
    1. 冗余较大
    2. 修改异常
    3. 插入异常
    4. 删除异常
  • 第二范式（2NF）：若关系式R \in 1NF，且每一个非主属性完全依赖主健时，则关系式R是2NF（第二范式）

    4-9 规范化03

  • 第三范式（3NF）：即当2NF消除了非属性以码的传递函数依赖，则称为3NF。
  • BC范式（BCNF）：R属于BCNF当且当其F中每个依赖的决定因素必定包含R的某个候选键。

    4-10 数据库设计&需求分析

    数据库设计
  • 规划阶段：建立数据库的必要性、可行性
  • 需求分析：收集需求，理解需求，需求规格说明书、数据字典
  • 概念设计：建立概念模型，E-R图
  • 逻辑设计：建立逻辑模型，关系模式
  • 建立物理：建立物理模型，“create table”，依赖于DBMS
    需求分析
  • 需要分析的目标是通过调查研究，了解用户的数据和处理要求，并按照一定格式整理成需求规格说明书。
    • 充分了解原系统(手工或计算机)工作概况
    • 详细调查待开发系统的组织/部门/企业等
    • 明确用户的各种需求
    • 确定新系统的功能(注意今后的扩充和改变)
  • 调查的重点是“数据”和“处理”：【数据库的元数据交由数据字典来进行管理】
    1. 数据库需要哪些数据？如:数据名、属性及其类型、数据量估计等。
    2. 数据处理要求？如:更改要求、使用频率和等。
    3. 安全性与完整性要求?如:保密 要求、完整性约束条件(主键属性) 等。
  • 数据字典的内容：数据项、数据流、数据存储、数据加工(处理过程) 。

    4-11 概念设计&逻辑设计

    概念设计

    其任务是在需求分析阶段产生的需求说明书的基础上，按照特定的方法将它们抽象为一个不依赖于任何DBMS的数据模型，即概念模型。
    【需求分析】
            \downarrow
    【确定局部视图范围】
            \downarrow
    【识别实体及其标识】
            \downarrow
    【确定实体间的联系】
            \downarrow
    【分配实体及联系的属性】
            \downarrow
    【全局E-R模式设计】（消除冲突）

  • 属性冲突
    • 属性域冲突（不同学校编码方式不同）
    • 属性值冲突（重量采用千克、磅）
  • 结构冲突
    • 同一对象在不同应用中的抽象不同（一个应用是实体，另一个是属性）
    • 同一实体在不同E-R图中属性个数和排列次序不同
  • 命名冲突
    • 同名异义
    • 异名同义
      逻辑设计

      也称为逻辑结构设计，其任务是将概念模型转化为某个特定的逻辑模型（层次模型、网状模型、关系模型）

      物理设计
      1. 设计存储记录结构，包括记录的组成、数据项的类型和长度，以及逻辑记录到存储记录的映射。
      2. 确定数据存储安排。
      3. 设计访问方法，为存储在物理设备上的数据提供存储和检索的能力。
      4. 进行完整性和安全性的分析与设计。
      5. 数据库程序设计。
        反规范化

        常见的反规范化技术：

      6. 增加冗余列
      7. 增加派生列
      8. 重新组表
      9. 分割表
    • 水平分割：根据一列或多列数据的值把数据行放到两个独立的表中。使用场景：
      • 情况1：表很大，提高查询效率
      • 情况2：表中的数据有独立性
      • 情况3：需要把数据存放到多个介质上
    • 垂直分割：把主码和一些列放到一个表，然后把主码和另外的列放到另一个表中。优点是在查询时就会减少 I/O 次数，缺点是需要管理冗余列，查询所有数据需要连接操作。

      4-12 事务管理&并发控制

      事务管理

      数据库系统运行的基本工作单位是事务，事务相当于操作系统中的进程，是用户定义的一个数据库操作序列，这些操作序列要么全做要么全不做，是一个不可分割的工作单位。

事务管理的ACID原则：

  1. 原子性（Atomicity）—操作：操作序列要么全 做要么全不做。
  2. 一致性（Consistency）—数据：数据库从一个一致性状态变到另一个一致性状态。
  3. 隔离性（Isolation）—执行：不能被其他事务干扰。
  4. 持续性（永久性）（Durability）—变化：一旦提交，改变就是永久性的。
    并发控制

    处理并发控制的主要方法是采用封锁技术。它有两种类型：排他型封锁(X封 锁)和共享型封锁(S封锁)：
    1) 排他型封锁(简称 X 封锁)。如果事务 T 对数据 A(可以是数据项、 记录、数据集，乃至整个数据库)实现了 X 封锁，那么只允许事务 T 读取和 修改数据 A，其他事务要等事务 T 解除 X 封锁以后，才能对数据 A 实现任何类型的封锁。可见 X 封锁只允许一个事务独锁某个数据，具有排他性。
    2) 共享型封锁(简称 S 封锁)。如果事务 T 对数据 A 实现了 S 封锁，那么 允许事务 T 读取数据 A，但不能修改数据 A，在所有 S 封锁解除之前绝不允许任何事务对数据 A 实现 X 封锁。

封锁协议： 协议 说明 作用
一级封锁协议 事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放 可防止丢失修改
二级封锁协议 一级封锁协议加上事务T在读取数据R之前先 对其加S锁，读完后即可释放S。 可防止丢失修改，还可防止读“脏”数据
三级封锁协议 一级封锁协议加上事务T在读取数据R之前先 对其加S锁，直到事务结束才释放 可防止丢失修改，还可防止读“脏”数据与防止数据重复读
两段锁协议 分为封锁阶段(扩展)和释放阶段(收缩)。封锁阶段只能加锁、扩展阶段只能解锁 可串行化，可能发生死锁

4-13 分布式数据库&故障恢复

分布式数据库
分布式数据库系统的特点

1) 数据的分布性。布式数据库中的数据分布于网络中的各个结点。
2) 统一性。主要表现在数据在逻辑上的统一性和数据在管理上的统一性两个方面。
3) 透明性。用户无须知道数据的存放位置。

分布式数据库的优点

1) 坚固性好。多台服务器构成，容错能力强，可靠性和可用性好。
2) 可扩充性好。
3) 可改善性能。
4) 自治性好。

分布透明性

1) 分片透明性是分布透明性的最最高层次。分片透明性是指用户或应用程序只对全局关系进行操作而不必考虑数据的分片。
2) 位置透明性是分布透明性的下一层次。位置透明性是指，用户或应用程序应当了解分片情况，但不必了解片段的存储场地。
3) 局部数据模型(逻辑透明)透明性。局部数据透明性是指用户或应用程序应当了解分片及各片断存储的场地，但不必了解局部场地上使用的是何种数据模型。

故障恢复
  • 数据库的故障可用事务的故障来表示，主要分为四类：
    1) 事务故障。逻辑、数据错误导致事务未正常终止就被撤销。
    2) 系统故障。操作失误、三件错误、停电等买不到内存信息丢失。
    3) 介质故障。磁盘损坏、操作系统问题导致数据损失。
    4) 计算机病毒。
  • 故障的恢复
    1) 事务故障的恢复。由系统自动完成，步骤如下：

    • 反向扫描文件日志，查找该事务的更新操作。
    • 对该事务的更新操作执行逆操作。
    • 继续反向扫描日志文件，查找该事务的其他更新操作，并做同样处理。
    • 如此处理下去，直至读到此事务的开始标记，事务故障恢复完成。
      2) 系统故障的恢复。在重新启动时自动完成，步骤如下：
    • 正向扫描日志文件，找出在故障发生前已经提交的事务，将其事务标识记入 重做(Redo)队列。同时找出故障发生时尚未完成的事务，将其事务标识记 入撤销(Undo)队列。
    • 对撤销队列中的各个事务进行撤销处理:反向扫描日志文件，对每个 Undo 事务的更新操作执行逆操作。
    • 对重做队列中的各个事务进行重做处理:正向扫描日志文件，对每个 Redo 事务重新执行日志文件登记的操作。
      3) 介质故障与病毒破坏的的恢复。磁盘上的物理数据库被破坏，这时的恢复操作可分为三步：
    • 装入最新的数据库后备副本，使数据库恢复到最近一次转储时的一致性状态。
    • 从故障点开始反向读日志文件，找出已提交事务标识将其记入重做队列。
    • 从起始点开始正向阅读日志文件，根据重做队列中的记录，重做所有已完成 事务，将数据库恢复至故障前某一时刻的一致状态。
      4) 具有检查点的恢复技术。检查点记录的内容可包括:
    • 建立检查点时刻所有正在执行的事务清单。
    • 这些事务最近一个日志记录的地址。
    • 采用检查点的恢复步骤如下:
      • 从重新开始文件中找到最后一个检查点记录在日志文件中的地址，由该地址在日志文件中找到最后一个检查点记录。
      • 由该检查点记录得到检查点建立时所有正在执行的事务清单队列(A)。
      • 建立重做队列(R)和撤销队列(U)，把 A 队列放入 U 队列中，R 队列为空。
        备份

        数据库备份按照不同方式可分为多种，这里按照备份内容分为物理备份和逻辑备份两类。
        物理备份是在操作系统层面上对数据库的数据文件进行备份，物理备份分为冷备份和热备份两种。

        4-14 数据仓库

        数据仓库定义

        著名的数据仓库专家 W.H.Inmon 在《Building the Data Warehouse》一书中 将数据仓库定义为:数据仓库(Data Warehouse)是一个面向主题的、集成的、 相对稳定的、反映历史变化的数据集合，用于支持管理决策。

        数据仓库与传统数据库的比较
        比较项目 传统数据库 数据仓库
        数据内容 当前值 历史的、归档的、归纳的、计算机的数据(处
        理过的
        数据目标 面向业务操作程序、重复操作 面向主体域、分析应用
        数据特性 动态变化、更新 静态、不能直接更新，只能定时添加、更新
        数据结构 高度结构化、复杂、适合操作计算 简单、适合分析
        使用频率 高 低
        数据访问量 每个事务一般只访问少量记录 每个事务一般访问大量记录
        对响应时间的要求 计时单位小、如秒 计时单位相对较大，除了秒，还有分钟、小时
        数据仓库的结构
        1. 数据源。是数据仓库系统的基础，是整个系统的数据源泉。
        2. 数据的存储与管理。整个数据仓库系统的核心。数据仓库的真正关键是数据的存储和管理。
        3. OLAP服务器。对分析需要的数据进行有效集成，按多维模型予以组织，以便进行多角度、多层次的分析，并发现趋势。其具体实现可以为:ROLAP、 MOLAP 和 HOLAP。
        4. 前端工具。主要包括各种报表工具、查询工具、数据分析工具、数据挖掘工具及各种基于数据仓库或数据集市的应用开发工具。
          数据仓库的实现方法
        5. 自顶向下法
        6. 自底向上法
        7. 混合法

          4-15 数据挖掘

          数据挖掘定义

          数据挖掘(Data Mining)技术是人们长期对数据库技术进行研究和开发的结果。数据挖掘与传统的数据分析(如查询、报表、联机应用分析)的本质区 别是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信息应具有先知，有效和可实用三个特征。

          数据挖掘的流程
        8. 问题定义。在开始数据挖掘之前，最先的也是最重要的要求就是熟悉背 景知识，弄清用户的需求。
        9. 建立数据挖掘库。要进行数据挖掘必须收集要挖掘的数据资源。一般建议把要挖掘的数据都 收集到一个数据库中，而不是采用原有的数据库或数据仓库。
        10. 分析数据。分析数据就是通常所进行的对数据深入调查的过程。
        11. 调整数据。通过上述步骤的操作，对数据的状态和趋势有了进一步的了解，这时要尽 可能对问题解决的要求能进一步明确化、进一步量化。
        12. 模型化。在问题进一步明确，数据结构和内容进一步调整的基础上，就可以建立形 成知识的模型。
        13. 评价和解释。上面得到的模式模型，有可能是没有实际意义或没有实用价值的，也有可 能是其不能准确反映数据的真实意义，甚至在某些情况下是与事实相反的，因 此需要评估，确定哪些是有效的、有用的模式。
          常用的数据挖掘技术
        14. 关联分析。关联分析主要用于发现不同事件之间的关联性，即一个事件发生的同时，另一个事件也经常发生。
        15. 序列分析。序列分析技术主要用于发现一定时间间隔内接连发生的事件。
        16. 分类分析。分类分析通过分析具有类别的样本的特点，得到决定样本属于各种类别的规则或方法。其主要方法有基于统计学的贝叶斯方法、神经网络方法、决策树方法及支持向量机(support vector machines)等。
        17. 聚类分析。聚类分析是根据物以类聚的原理，将本身没有类别的样本聚集成不同的组，并且对每一个这样的组进行描述的过程。
        18. 预测。预测与分类类似，但预测是根据样本的已知特征估算某个连续类型的变量的取值的过程，而分类则只是用于判别样本所属的离散类别而已。预测常用的技术是回归分析。
        19. 时间序列。分析时间序列分析的是随时间而变化的事件序列，目的是预测未来发展趋势，或者寻找相似发展模式或者是发现周期性发展规律。

          4-16 NoSql数据库：关系型数据库的缺点

  • 不满足高并发读写需求
  • 不满足海量数据的高效率读写
  • 不满足高扩展性和可用性

    集群方式虽然可以缓解上述问题，但仍然存在下列缺陷:
    • 复杂性–集群配置、部署、管理都和复杂。
    • 延迟性–主数据库压力较大时，会产生较大延迟。主备切换时候可能
    需要人工参与。
    • 扩容性–集群中增加新机器时，对整个数据集重新分区，非常复杂。

    4-17 ACID理论、CAP理论、BASE理论

    ACID理论

    ACID，是指数据库管理系统(DBMS)在写入或更新资料的过程中，为保证事务(transaction)是正确可靠的，所必须具备的四个特性：

    • 原子性(Atomicity)
    • 一致性(Consistency)
    • 隔离性(Isolation)
    • 持续性(永久性)(Durability)
Nosql数据库

NoSQL(NoSQL = Not Only SQL )，意即 “不仅仅是SQL”。

NoSQL数据库的产生就是为了解决大规模数据集合多重数据种类带来 的挑战，尤其是大数据应用难题。
1) 灵活的可扩展性
2) 灵活的数据模型
3) 与云计算结合

CAP理论
主要概念 解释
C(Consistency)一致性 一致性是指更新操作成功并返回客户端完成后，所有节点在同一时间的数据完全一致，与ACID的 C完全不同。
A(Availability)可用性 可用性是指服务一直可用，而且是正常响应时间。
P(Partition tolerance)分区容 错性 分区容错性是指分布式系统在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务。

鱼与熊掌不可兼得。一个分布式系统不可能同时满足一致性、可用性、分区容忍性这三个需求，最多只能同时满足其中两个。

CA CP AP
优先保证一致性和可用性，放弃分区容错。缺点:不再是分布式系统 优先保证一致性和分区容错性，放弃可用性。缺点:牺牲用户体验 优先保证可用性和分区容错性，放弃一致性。缺点:全局数据的不一致性
BASE理论
基本可用(BasicallyAvailable) 软状态(Soft state) 最终一致性(Eventuallyconsistent)
指分布式系统在出现不可预知故障的时候，允许数许损失部分可用性。允许分区失败的情形出现。 硬状态：数据库状态必须一直保持数据库一致性。软状态：状态可以有一段时间不同步 系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。
Nosql数据库与sql数据库的比较
特征 SQL数据库 NoSql数据库
数据类型 结构化 非结构化
数据一致性 强一致性 弱一致性
事务 高事务性 弱事务性
扩展性 一般 好
数据容量 有限数据 海量数据
标准化 是 否
技术支持 高 低
可维护性 复杂 复杂
NoSql数据库的主要类型
  1. 键值数据库
  2. 列族数据库
  3. 文档数据库
  4. 图形数据库

    4-18 NoSQL的主要类型：键值数据库

    键可以是一个字符串对象，值可 以是任意类型的数据。如整型、 字符型、数组、列表、集合等。

相关产品 Redis、Riak、SimpleDB、Chordless、Scalaris、Memcached
数据模型 键/值对：键是一个字符串对象 值是可以任意类型的数据，比如整型、字符型、数组、列表、集合等
典型应用 涉及频繁读写、拥有简单数据模型的应用内容缓存，比如会话、配置文件、参数、购物车等存储配置和用户数据信息的移动应用
优点 扩展性好，灵活性好，大量写操作时性能高
缺点 无法存储结构化信息，条件查询效率较低
不适用情形 不是通过键而是通过值来查：键值数据库根本没有通过值查询的途径；需要存储数据之间的关系：在键值数据库中，不能通过两个获两个以上的键来关联数据；需要事务的支持：在一些键值数据库中，产生故障时，不可以回滚
使用者 百度云数据库(Redis)、GitHub(Riak)、BestBuy(Riak)、Twitter (Redis和Memcached)、StackOverFlow(Redis)、Instagram (Redis)、Youtube(Memcached)、Wikipedia(Memcached)

4-19 NoSQL的主要类型：列族数据库

相关产品 BigTable、Hbase、Cassandra、HadoopDB、GreenPlum、PNUTS
数据模型 列族
典型应用 分布式数据存储与管理；数据在地理上分布于多个数据中心的应用程序；可以容忍副本中存在短期不一致情况等的应用程序；拥有动态字段的应用程序；拥有潜在大量数据的应用程序，大到几百TB的数据
优点 查找速度快，可扩展性强，容易进行分布式扩展，复杂性低
缺点 功能较少，大都不支持强事务一致性
不适用情形 需要ACID事务支持的情形，Cassandra等产品就不适用
使用者 Ebay(Cassandra)、Instagram(Cassandra)、NASA(Cassandra) Twitter(Cassandra and HBase)、Facebook(HBase)、Yahoo! (HBase)

4-20 NoSQL的主要类型：文档数据库

相关产品 MongoDB、CouchDB、Terrastore、ThruDB、RavenDB、SisoDB、CloudKit、Perservere、Jackrabbit
数据模型 键/值 值(value)是版本化的文档
典型应用 存储、索引并管理面向文档的数据或者类似的半结构化数据比如，用于后台具有大量读写操作的网站、使用JSON数据结构的应用、 使用嵌套结构等非规范化数据的应用程序
优点 性能好(高并发)，灵活性高，复杂性低，数据结构灵活提供嵌入式文档功能，将经常查询的数据存储在同一个文档中既可以根据键来构建索引，也可以根据内容构建索引
缺点 缺乏统一的查询语法
不适用情形 在不同的文档上添加事务。文档数据库并不支持文档间的事务，如果对这方面有需求则不应该选用这个解决方案
使用者 百度云数据库(MongoDB)、SAP(MongoDB)、Codecademy(MongoDB)、Foursquare(MongoDB)、NBC News(RavenDB)

4-21 NoSQL的主要类型：图形数据库

相关产品 Neo4J、OrientDB、InfoGrid、Infinite Granph、GraphDB
数据模型 图结构
典型应用 专门用于处理具有高度相互关联关系的数据，比较适合于社交网络、模式识别、依赖分析、推荐系统以及路径寻找等问题
优点 灵活性高，支持复杂的图形算法，可用于构建复杂的关系图谱
缺点 复杂性高，只能支持一定的数据规模
使用者 Adobe(Neo4J)、Cisco(Neo4J)、T-Mobile(Neo4J)