数据库基础知识小结
54 69 73 78 三 六 
1 基础知识
计算机采用的是 存储程序控制 原理。
计算机功能部件--运算器 存储器 控制器 输入设备 输出设备
计算机指令类型--数据传送类、算术逻辑类、判定控制类 
总线--数据总线 地址总线 控制总线
系统软件包括--程序设计语言处理程序 操作系统 数据库管理系统 通用服务程序
配置技术指标--运算速度MIPS 主频Hz 字长 存储容量 数据传输率bps
计算机应用领域--科学和工程计算 数据和信息处理 过程控制 计算机辅助系统 人工智能 网络应用
汉字代码体系--输入码 机内码 交换码（矢量 点阵)
网络分类 
传输技术--广播式网络 点一点是网络
覆盖的地理范围--广域网 局域网（以太网） 城域网（FDDI）
广域网
X.25--速率较低 误码率高
帧中继--光纤 传输速率高 误码率高
ISDN--成本高 线路利用率低
ATM--满足多媒体网络
A类IP地址 空间长度7位 主机地址长度24位 
B类IP地址 空间长度14位 主机地址长度16位 
C类IP地址 空间长度21位 主机地址长度8位（192.0.0.0-223.255.255.255） 
超文本标注语言HTML 超文本传输协议HTTP Internet服务提供者ISP
标准的URL组成--主机名 文件名与路径 协议类型 
ISDN ADSL适用于小型公司 DDN 帧中继适用于大型企业
信息认证--数字签名技术 身份识别技术 信息的完整性校验技术
计算机病毒--传染性 破坏性 隐藏性 潜伏性 可激发性
操作系统的安全--隔离 分层 内控 
网络安全主要涉及的内容--安全攻击 安全服务 安全机制




2 数据结构与算法
数据结构--数据的逻辑结构 存储结构 运算
算法的代价 if n>N T(n)<=C*f（n）
顺序表--插入一个结点和删除一个结点所需移动节点个数=n/2
栈stack   LIFO stack push(S.x) pop(S) top(S.x)   empty(S) makempty(S)
队列queue FIFO queue enq(Q.x)  deq(Q) front(Q.x) empty(Q）makempty(Q)
头变量Q。F 存放进行删除运算时应被删除的元素的下标
尾变量Q。R 存放待插入新元素的空位置的下标
定义
TYPE stack =RECORD
          A;ARRAY[1..m]OFdatatype
          t;0..m
VAR S;stack
栈的推入
PROCEDURE push(VAR s:stack;x:datatype)
   BEGIN
     IF s.t=m
        THEN print(‘overflow')
        ELSE BEGIN
             s.t;=s.t + 1;
             s.A[s.t];= x;
             END
   END
串最坏的情况下 比较次数n-m+1
二叉树 度-一个结点子树的个数 高度-叶结点的最大层数 层-父节点层数（0）加1.
完全二叉树；只有最下面两层度<2,最后一层节点都在左边。
树对应的二叉树 左结点是子女右结点是兄弟
线索二叉树；n个结点有n+1个空指针。
扩充二叉树（霍夫曼算法）的外部结点=二叉树结点+1
顺序查找优点；逻辑次序无要求，对存储结构无要求。
        缺点；平均检索长度长。平均比较次数（n+1）/2.
二分法平均检索长度小，平均比较次数log2n。
      缺点；需将线性表排序，存储方式插入删除不方便。
处理碰撞的方法 拉链法和开地址法
二叉排列树 左子树<根结点<右子树
最佳排序二叉树除了最下面一层各层都是满的。
B树--1，每个结点至多有m棵子树 2，根结点或为叶结点或至少有两棵子树 3 中间节点至少有m/2棵子树 4 k(i)<k(i+1) 5 叶结点出现在同一层
B+树--1 每个结点至多有m个子女 2 每个结点至少有m/2个子女 3 根结点至少有2个子女 4有l个子女的结点必须有l个关键码
直接插入排序平均比较i/2,总移动个数n*n/4.
二分法比较次数nlog2n,移动个数n*n。
shell排序法比较次数和移动个数为n（1.3）
直接排序比较次数为 n（n-1）/2
起泡排序法比较次数最大为n（n-1）/2 平均执行时间nlog2n
快速排序法 最坏执行时间n*n 平均执行时间nlog2n
散列表的平均检索长度不直接依赖于n
按后根次序周游树或树林等同于按对称次序周游树对应的二叉树




3 操作系统
操作系统的特征--并发性 共享性 随机性
操作系统的功能--进程管理 存储管理 文件管理 设备管理 用户接口
操作系统结构 整体结构 层次结构 客户机/服务器结构
操作系统的硬件环境--中央处理器 存储体系 I/O控制方式 时钟
管态(R0)-特权态 系统态 核心态 目态(R3)-普通态 用户态
多到程序设计--允许多个程序同时进入内存并运行--提高整个系统的效率
系统吞吐量--单位时间内系统所处理作业的道数
进程--运行 等待 就绪
死锁--每个进程要求的资源都已被另一进程占用，于是也就没有一个进程能继续运行
进程由程序、数据和进程控制块组成，进程控制块--调度信息 现场信息
线程--轻量级进程--调度和分配的基本单位
解决进程之间的信息通信的方案--共享内存 消息机制 管道通信（传输量大，速度较慢）
死锁的必要条件--互斥条件 不剥夺条件 部分分配 循环等待
文件目录是文件控制块的有序集合
存储共享的目的--节省内存空间 实现进程通信




4 数据库基础
人工管理阶段 文件系统阶段 数据库系统阶段
数据库管理技术是指对数据的分类，组织，编码，存储，检索和维护的技术
数据库的三件大事--1968，IBM推出IMS 1969 CODASYL'发表DBTG报告 1970 E.F.Codd奠定关系数据库基础
数据库管理软件研究的目标是提高系统的性能和提高用户的生产率
数据模型由数据结构（基础） 数据操作 数据约束组成
数据模型分类 概念层模型（ER） 逻辑层模型 物理层模型
逻辑模型有层次模型IMS 网状模型DBTG 关系模型RDBME 面向对象模型ODBMS 对象关系模型（Oracle DB2）
模式--逻辑模式，概念模式 内模式--物理模式，存储模式 外模式--子模式，用户模式
外模式/模式映像-逻辑独立性 模式/内模式-物理独立性


5 关系数据库系统
关系数据模型由关系数据结构、关系操作集合、关系完整性约束组成
关系完整性--域完整性 实体完整性 参照完整性
插入操作--首先检查实体完整性 在检查参照完整性 最后检查域完整性
删除操作--只需考虑参照完整性
基本操作--并 差 笛卡尔积 投影 选择
更多:http://www.52mvc.com



6 SQL结构化查询语言
SQL --数据查询(SELECT) 数据定义(CREATE DROP ALTER) 数据操作(INSERT UPDATE DELETE) 数据控制（GRANT REVOKE）
SQL特点--综合统一 高度非过程化 面向集合的操作方式 灵活的使用方式 语言简洁
SQL语言 数据定义语言DDL 数据操作语言DML 数据控制语言DCL 嵌入式和动态SQL规则 SQL调用和会话规则
模式SCH