3、主要的数据存储方式：顺序存储结构（逻辑和物理相邻，存储密度大）和链式存储结构
顺序存储结构：
顺序存储计算公式 Li＝L0＋(i－1)×K 顺序结构可以进行随机存取；插人、删除运算会引起相应
节点的大量移动
链式存储结构：a、指针域可以有多个，可以指向空，比比顺序存储结构的存储密度小
b、逻辑上相邻的节点物理上不一定相邻。 c、插人、删除等不需要大量移动节点
4、顺序表：一般情况下，若长度为n的顺序表，在任何位置插入或删除的概率相等，元素移动的平均次数为n/2（插入）和（n-1）/2（删除）。 5、链表：线性链表（单链表和双向链表等等）和非线性链表
线性链表也称为单链表，其每个一节点中只包含一个指针域，双链表中，每个节点中设置有两个指针域。（注意结点的插入和删除操作）
6、栈：“后进先出”(LIFO)表。栈的应用：表达式求解、二叉树对称序周游、快速排序算法、递归过程的实现等
7、队列：“先进先出”线性表。应用：树的层次遍历 8、串：由零个或多个字符组成的有限序列。 9、多维数组的顺序存储：
10、稀疏矩阵的存储：下三角矩阵顺序存储
其他常见的存储方法还有三元组法和十字链表法
11、广义表：由零个或多个单元素或子表所组成的有限序列。广义表的元素可以是子表，而子表的元素还可以是子表
12、树型结构：非线性结构。常用的树型结构有树和二叉树。
二叉树与树的区别：二叉树不是树的特殊情况，树和二叉树之间最主要的区别是：二叉树的节点的子树要区分左子树和右子树，即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
13、树（森林）与二叉树之间的转换（要会转换） 14、二叉树和树的周游（遍历）
二叉树的周游主要有以下3种方式：前序法(NLR)、对称序法(LNR)、后序法(LRN) 周游树和树林：深度优先和按广度优先两种方式进行。深度优先方式又可分为按先根次序和按后根次序周游
树与二叉树周游之间的对应关系：按先根次序周游树正好与按前序法周游树对应的二叉树等同，后根次序周游树正好与按对称序法周游对应的二叉树等同 按广度优先方式就是层次次序周游 15、二叉树的存储和线索
二叉树的存储结构：二叉树的llink一rlink法存储表示
线索二叉树：在有n个节点的二叉树的且llink - rlink法存储表示中，必定有n+1个空指针域
16、哈夫曼树：一类带权路径长度最短的树。树的带权路径长度为树中所有叶子节点的带权路径长度之和WPL。 17、查找：
（1）顺序查找：平均查找长度为(n +1 )/2次，时间复杂度为O(n)
（2）二分法查找：线性表节点必须按关键码值排序，且线性表是以顺序存储方式存储的。查找成功比较次数log2n，查找失败比较次数log2n+1 （3）分块查找：先是块间查找，然后块内查找。
（4）散列表（哈希表Hash）的存储和查找：处理冲突的方法：开地址法（线性探测法）、拉链法等
负载因子(装填因子)=表实际存储的结点个数/表的最大能存储结点个数（即表长） 二叉排序树：每个结点左子树的所有关键码值都小于该结点关键码值，右子树所有结点关键码值都大于该结点关键码值。对称周游二叉排序树，得到一个有序序列，时间复杂度O（log2n）
B树和B+树：M阶树，每个结点至多有M-1个关键码，至少有M/2(取上界)-1个关键码。B树适合随机查找，不适合顺序查找。B+树适合顺序查找。 18、排序
直接插人排序、希尔排序、直接选择排序、堆排序、起泡排序、快速排序等排序算法要了解。
直接选择排序、希尔排序、快速排序和堆排序是不稳定排序，其他排序为稳定排序
第三章 操作系统
1、操作系统概念：一是管理系统中的各种资源；二是给用户提供一个友好的界面。 2、操作系统包括以下3个基本特征：并发性、共享性、随机性。 3、功能：进程管理、存储管理、作业管理、文件管理、设备管理 4、操作系统类型
（1）批处理操作系统：成批、多道，交互性不强。系统目标：提高资源利用率、作业吞吐量和作业流程自动化。
（2）分时操作系统：多路、交互性、独立性、及时性 （3）实时系统（实时控制、实时信息处理）：及时、可靠
（4）嵌入式操作系统：高可靠性、实时性、占资源少、智能化、易连接、低成本等。 5、操作系统与用户的接口：程序级接口：系统调用命令组成。操作级接口：提供操作命令
6、操作系统的硬件环境（CPU、存储体系、中断系统、I/O控制和时钟）
（1）CPU：CPU状态：管态（CPU执行操作系统程序）和目态（CPU执行用户程序） 目态到管态的转变的唯一途径是中断，通过修改程序状态字实现管态和目态的转换
（2）中断机制：
中断的实现需要硬件和软件结合完成。中断类型：强迫性中断和自愿性中断。
强迫性中断：不期望或不可预料的中断.如：输入输出中断、硬件故障中断、时钟
中断、程序性中断。
自愿性中断：程序有意安排的访管指令或系统调用。 中断向量：中断处理程序的入口地址及运行环境（程序状态字PSW）
中断优先级由硬件规定，中断屏蔽由程序状态字的中断屏蔽位决定。通过中断屏
蔽可以调整中断事件的响应次序
（3）定时装置：定时装置硬件时钟通常分为两类：即绝对时钟和相对时钟。 CPU对外部设备的控制方式：
1、循环测试I/O 2、中断 3、DMA（直接内存存取）：高速外设与内存批量处理数据 4、通道处理（I/O处理机）
7、进程管理
（1）进程与程序的区别与联系：a.进程是程序的执行，是动态的；而程序是指令的集合，是静态的。
b.进程有生命周期，即进程的存在是有限的，从运行到结束，是暂时的；而程序则是永久存在的。
c.进程包括程序、数据和进程控制块(PCB)。
d.一个程序可以有多个进程，一个进程也可以包含多个程序。 进程控制块PCB是一个数据结构，进程在内存中存在的唯一标志 (2)进程状态:运行态, 就绪态,等待状态（阻塞状态）
(3)线程：CPU调度和分派的基本单位。共享进程资源。 （4）进程的通信
临界资源是指一次只允许一个进程使用的资源：一个进程中访问临界资源的那段程序代码称为临界区。它们不允许两个及以上的进程同时访问或修改。 进程同步：多个进程协同完成任务。进程互斥：多个进程使用同一资源（临界资源)。 低级通信：少量信息的交换(P操作和V操作)
高级通信：大信息交换（消息机制（消息缓冲、信箱通信）、共享内存，管道） 进程（线程）调度：先来先服务、时间片轮转、最高优先级（紧迫度高的进程）、 多级队列反馈算法：综合了FCFS、时间片轮转和可抢占最高优先数算法。 （5）死锁：
产生死锁的必要条件：互斥条件、不可剥夺条件、部分分配、循环等待 死锁的预防： 破环必要条件之一：静态预分配（破坏部分分配）、资源有序分配（破坏环路等待）、 可剥夺资源（破坏不可剥夺性） 死锁的避免：银行家算法
死锁的检测：进程等待时检测、定时检测、系统利用率降低时检测 死锁的解除：资源剥夺和撤销进程 8、存储管理
（1）功能：内存的分配和回收、内存共享、存储保护（防止地址越界和操作越权）、地址映射（地址重定位）
内存扩充：让外存当作内存来使用
（2）碎片管理：解决碎片的方法是移动技术或紧凑(拼接)技术
（3）静态地址重定位：程序装入内存时，进行逻辑地址转换物理地址转换
动态地址重地位：程序运行过程中，要访问指令和数据才进行地址转换，需要硬
件地址映射机制（基址寄存器和限长寄存器）
（4）空闲分区的分配策略：最先适应算法（地址从小到大找第一个满足进程空间大小的分区）
最佳适应算法：分区表按容量从小到排序；最坏适应算法：分区按容量从大到小排序。
（5）虚拟存储管理：虚拟存储得以实现是由程序的局部性原理来决定的。程序的局部性原理包括时间局部性和空间局部
（6）页面淘汰算法包括以下几种：最佳淘汰算法(OPT)、先进先出淘汰算法(FIFO)、最近最久末使用淘汰算法(LRU)
最近使用最少淘汰算法(LFU)（访问次数少）
（7）影响缺页中断次数因素：a、分配给进程的物理页面数 b.页面大小 c.程序本身的编制方法
c、页面淘汰算法：最佳淘汰算法(OPT)能使缺页中断率最低 (8)颠簸（抖动）：缺页率高引起。工作集模型解决颠簸(抖动） 9、文件管理
（1）逻辑结构：流式文件（基本单位字符）（如：源程序文件、目标代码文件，Unix的文件）和记录文件（定长和不定长记录），记录包含一个记录键和其他属性 （2）文件的物理结构：连续结钩、链接结构、索引结构及Hash结构等，文件的存取方式与物理结构有关。
UNIX三级索引表的计算：如果一个物理块可以存放256个块号，则三级索引表表示文件的大小 2563+2562+256+10
（3）文件目录：文件系统的最大特点就是“按名”存取
（4）文件控制块FCB是文件在内存中存在的唯一标志，文件目录是文件控制块的有序集合。
（5）多级目录结构，有利于避免文件重名；当前目录：可以提高检索速度。目录项分解法，它可以提高文件检索速度
（6）记录的成组：若干个逻辑记录合成在一个物理块中，每个块中的逻辑记录个数为块因子。
10、设备管理
（1）按设备的工作特性可以分为存储设备和输人／输出设备两种
（2）按照资源分配方式可以分为独享设备、共享设备和虚拟设备3种
虚设备技术，一类设备模拟另一类设备的技术。在高速设备（如高速大容量磁盘）上模拟低速设备 ：SPOOLING是典型的虚设备技术，被模拟的设备称为虚拟设备。 （3）按设备的数据组织分类：块设备（磁盘、磁带）和字符设备（打印机）。 （4）通道可以分为以下3种类型：字节多路通道、选择通道和成组多路通道。 （5）单缓冲区，双缓冲区，多缓冲区和缓冲池：解决外设与CPU速度不匹配问题 （6）磁盘调度： 访问磁盘时间：寻道时间、旋转定位时间和数据传输时间。 磁盘调度由移臂调度和旋转调度组成。移臂调度：先来先服务FCFS（大幅度移动)、
最短寻道时间优先(饥饿，考虑了寻道优化），扫描算法（考虑方向和距离，考虑了寻道优化）
旋转调度：目的较少旋转延迟时间。
第四章 数据库系统技术基础
1、信息与数据的关系：数据是信息的符号表示，或称载体；信息是数据的内涵，是数据的语义解释
2、数据库系统：一般由数据库、操作系统、数据库管理系统(及其工具)、应用系统、数据
库管理人员和用户构成。
3、数据模型: 数据模型是数据库系统的数学形式框架，是数据库系统的核心和基础.
4、数据模型的分类：概念模型，也称信息模型；逻辑模型，主要包括网状模型、层次模型和关系模型等；物理模型 。
5、数据模型的三要素：数据结构、数据操作和完整性约束。
6、概念模型，信息世界建模，E-R模型是常用的概念模型。EER扩充E-R模型，面向对象模型、谓词模型。
E-R图提供了表示实体型、属性和联系的方法。 (1)实体型：用矩形表示，矩形框内写明实体名。
(2)属性：用椭圆形表示，并用无向边将其与相应的实体连接起来。
(3)联系：用菱形表示，菱形框内写明联系名，并用无向边分别与有关实体连接起来，同时在无向边旁标上联系的类型
7、逻辑模型，面向数据库管理系统。传统逻辑模型（层次、网状、关系）基于记录的模型。层次、网状模型用记录和链接表示数据和联系，关系模型用二维表表示数据，记录值表示表间联系。
面向对象的模型，对象-关系模型都属于逻辑模型，面向对象模型既是概念模型又是逻辑模型。
8、数据库系统的三级模式结构：由外模式、模式和内模式三级构成的。
9、模式(Schema)：一个数据库只有一个模式；外模式也称子模式或用户模式，一个数据库可以有多个外模式。外模式是保证数据库安全性的一个有力措施。内模式也称存储模式或物理模式，一个数据库只有一个内模式。
10. 数据库的二层映像与数据独立性：外模式／模式映像，包含在各自的外模式描述中。外模式／模式映像保证了数据与程序的逻辑独立性（模式变，外模式不变）；模式／内模式映像，包含在模式描述中，模式／内模式映像保证了数据与程序的物理独立性（物理模式变，模式不变，外模式不变）。
第五章 关系数据库系统
1、关系模型由关系数据结构、关系操作集合和关系完整性约束3部分组成。 2、关系模型中的关系操作的理论依据为关系代数和关系演算。 关系操作的特点是集合操作方式。
3、关系数据语言可以分为如下3类：关系代数语言、关系演算语言(包括元组关系演算语言和域关系演算语言)及具有关系代数和关系演算双重特点的SQL语言。
4、关系模型中有3类完整性约束：实体完整性、参照完整性（引用完整性）和域完整性约束（用户自定义的完整性） 5、关系数据库对关系的限定
当关系作为关系数据模型的数据结构时，关系数据库对关系有如下的限制。 (1)列是同质的．即每一列中的分量是同一类型的数据，来自同一个域。
(2)不同的列可以出自同一个域，称其中的每一列为一个属性，不同的属性要给予不同的属性名。
(3)列的顺序无关紧要，即列的次序可以任意交换。 (4)任意两个元组不能完全相同。
(5)行的顺序无关紧要，即行的次序可以任意交换。
(6)每一个属性是不可分解的这是关系数据库对关系的最基本的一条限定。分量必须取原子值，即每一个分量都必须是不可拆分的数据项。
6、关系模型的完整性约束：实体完整性关系的所有主属性都不能取空值，而不仅是主码整
三级数据库笔记（完整）
