数据库系统工程师学习笔记（慢慢进行整合）_数据库系统工程师 复习攻略

一、计算机的各种周期

时钟周期：也称为振荡周期，定义为时钟频率的倒数。是计算机中最基本、最小的时间单位。

机器周期：也称为CPU周期，指完成一个基本操作所需要的时间。通常用内存中读取一个指令字的最短时间来规定CPU周期。

指令周期：从主存取一条指令并执行指令的时间

总线时间：CPU完成一次内存访问（读写）或接口操作所需要的时间

二、流水线计算

流水线周期：工序中最长的那段执行时间

流水线计算公式：第一条指令执行时间+（指令条数-1）*流水线周期

流水线吞吐率：指单位时间内流水线完成的任务数量或输出的结果数值
TP=指令条数 / 流水线执行时间

流水线加速比：完成同一批任务，不使用流水线所用时间与使用流水线所用时间之比
S= 不使用流水线执行时间 / 使用流水线执行时间

例题：指令流水线把一条指令分为取值、分析、执行三部分。每部分所用时间分别为2t、2t、t，完成100条指令。
解：流水线周期：2t（最大）
第一条指令时间：2+2+1 = 5t
流水线计算公式：5t + （100-1）*2 t= 203t

流水线吞吐率：100 t/ 203 t

流水线加速比：500t / 203t

三、I/O接口

I/O（Input/Output）：即输入/输出，指数据在内部存储器和外部存储器或其他周边设备之间的输入和输出。

I/O接口作用：
1、数据缓冲：主机和外设工作速度匹配
2、错误或状态检测：反馈设备各种错误、状态信息
3、控制和定时：接受从控制总线发来的控制信号、时钟信号。
4、数据格式转换：串并、并串等格式转换
5、与主机和设备通信：实现主机- I/O接口- I/O设备间通信

四、系统总线

总线（BUS）：连接多个部件的信息传输线，是各部件共享的传输介质。

系统总线
分类：数据总线、地址总线、控制总线

特点：在某一时刻，只允许有一个部件向总线发送消息，但多个部件可以同时从总线接收到相同消息。总线上信息传送可以串行和并行。

计算机使用总线结构便于增减外设，同时减少信息传输线的条数。但相对于专线结构，其实际上也降低了信息传输的并行性、信息的传输速度。

五、算术表达式

（一）、后缀表达式例题：

规则：从左到右遍历表达式的每个数字和符号，遇到数字就进栈，遇到符号，就将处于栈顶的两个数字出栈，进行运算，运算结果进栈，一直到最终结果。

（二）、中缀表达式转后缀表达式的运算
a、直接转换法
b、利用表达式树
c、利用栈

六、数据结构

（一）、栈：是一种线性数据结构，数据像碗一样，一层层堆起来，数据“后进先出”

（二）、树：是一种非线性数据结构，存储的是具有“一对多”关系的数据元素的集合

二叉树：每个结点最多有两个分支（子树），子树有左右之分（次序不能颠倒）。

特殊二叉树：完全二叉树、满二叉树（特殊的完全二叉树）

注意：
（1）完全二叉树的叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部
（2）满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树

结点的度：结点拥有的子分支数
树的度： 树内各结点中最大的度

二叉树遍历

遍历：顺着一条搜索路径访问二叉树中的节点，每个节点均被访问一次，且只被访问一次。最后得到一个线性排列

先序遍历：根左右
中序遍历：左根右
后序遍历：左右根

（三）、队列

队列：是一种线性数据结构，数据排成一队，在头部删除旧数据，在尾部添加新数据，数据“先进先出”

（四）、串

串：又叫字符串，是一种特殊的线性数据结构，它的数据元素是字符。

特殊的串
空串 String s = “” ; 长度为0
空格串 String s = " " ; 长度为空格数
子串和主串
A： hellochina
B：china （A是B的主串，B是A的子串）

线性表：又称线性存储结构，是最简单的一种存储结构，专门用来存储逻辑关系为“一对一”的数据。

七、查找方法

顺序查找 < 分块查找 < 二分查找

（1）顺序查找 ： 从一端开始逐个比较

（2）二分查找（折半查找）：关键字先排序，以中间值为中心一分为二，先与中间值比较；再根据比较结果，选择在左段或者右段比较。

特点：1、元素值有序；2、顺序存储

（3）分块查找：又称索引查找，是折半查找和顺序查找的改进，适合于节点动态变化的情况。

特点：1、块内元素可以无序，块之间必须有序；2、第n块中任意元素都必须小于第n+1块中任意元素

（4）哈希表查找（散列查找）