温故而知新-基础课程篇【面试】
前言
2023-7-13 17:46:03
以下内容源自《【面试】》
仅供学习交流使用
推荐
数据结构
线性表
顺序表：数组
链表：单链表、双向链表、循环链表、静态链表
操作受限的线性表：栈 队列
串
模式匹配：BF KMP
多维线性表
树
二叉树
遍历：前序，中序，后序
线索二叉树
树和森林
双亲表示法
孩子表示法
孩子兄弟表示法
哈夫曼树
给一个字符串生成对应的哈夫曼编码
图
遍历：深搜、广搜
查询
基于线性表的查找
顺序查询
折半查询
索引查找
基于树的查找
二叉排序树（BST）
平衡二叉树（AVL）
B树和B+树
红黑树
结点分为红色和黑色
根是黑色
所有扩充外部叶子NIL结点是黑色的
红色结点的子节点是黑色
从任何一个结点到叶子结点的路径，黑色结点数量是相同的
散列
处理哈希冲突的两个办法
开放定址法
链地址法
排序
插入类排序（直接插入、折半插入、希尔排序）
交换类排序（冒泡、快排）
选择类排序（简单选择、树形选择、堆）
归并类排序（二路归并、自然归并）
分配类排序（多关键字排序、链式基数排序）
外部排序（置换选择排序、多路归并外排序）
稳定的算法：
直接插入排序
冒泡排序
归并排序
基数排序
算法题
来源于算法
左程云
class034 链表高频题目和必备技巧【算法】
class035 数据结构设计高频题【算法】
code1 设计有setAll功能的哈希表
https://www.nowcoder.com/practice/7c4559f138e74ceb9ba57d76fd169967
code2 146. LRU 缓存
https://leetcode.cn/problems/lru-cache/
code3 380. O(1) 时间插入、删除和获取随机元素
https://leetcode.cn/problems/insert-delete-getrandom-o1/
code4 381. O(1) 时间插入、删除和获取随机元素 - 允许重复
https://leetcode.cn/problems/insert-delete-getrandom-o1-duplicates-allowed/
code5 295. 数据流的中位数
https://leetcode.cn/problems/find-median-from-data-stream/
code6 895. 最大频率栈
https://leetcode.cn/problems/maximum-frequency-stack/
code7 432. 全 O(1) 的数据结构
https://leetcode.cn/problems/all-oone-data-structure/
class036 二叉树高频题目-上-不含树型dp【算法】
code1 102. 二叉树的层序遍历
https://leetcode.cn/problems/binary-tree-level-order-traversal/
code2 103. 二叉树的锯齿形层序遍历
https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
code3 662. 二叉树最大宽度
https://leetcode.cn/problems/maximum-width-of-binary-tree/
code4 104. 二叉树的最大深度 111. 二叉树的最小深度
https://leetcode.cn/problems/maximum-depth-of-binary-tree/
https://leetcode.cn/problems/minimum-depth-of-binary-tree/
code5 297. 二叉树的序列化与反序列化
https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
code6 105. 从前序与中序遍历序列构造二叉树
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
code7 958. 二叉树的完全性检验
https://leetcode.cn/problems/check-completeness-of-a-binary-tree/
code8 222. 完全二叉树的节点个数
https://leetcode.cn/problems/count-complete-tree-nodes/
class037 二叉树高频题目-下-不含树型dp【算法】
code1 236. 二叉树的最近公共祖先
// 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
code2 235. 二叉搜索树的最近公共祖先
// 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
code3 113. 路径总和 II
// 测试链接 : https://leetcode.cn/problems/path-sum-ii/
code4 110. 平衡二叉树
// 测试链接 : https://leetcode.cn/problems/balanced-binary-tree/
code5 98. 验证二叉搜索树
// 测试链接 : https://leetcode.cn/problems/validate-binary-search-tree/
code6 669. 修剪二叉搜索树
// 测试链接 : https://leetcode.cn/problems/trim-a-binary-search-tree/
code7 337. 打家劫舍 III
// 测试链接 : https://leetcode.cn/problems/house-robber-iii/
class038 经典递归解析【算法】
code1 字符串的全部子序列
https://www.nowcoder.com/practice/92e6247998294f2c933906fdedbc6e6a
code2 90. 子集 II
https://leetcode.cn/problems/subsets-ii/
code3 46. 全排列
https://leetcode.cn/problems/permutations/
code4 47. 全排列 II
https://leetcode.cn/problems/permutations-ii/
code5
// 用递归函数排序栈
// 栈只提供push、pop、isEmpty三个方法
// 请完成无序栈的排序，要求排完序之后，从栈顶到栈底从小到大
// 只能使用栈提供的push、pop、isEmpty三个方法、以及递归函数
// 除此之外不能使用任何的容器，数组也不行
// 就是排序过程中只能用：
// 1) 栈提供的push、pop、isEmpty三个方法
// 2) 递归函数，并且返回值最多为单个整数
code6
// 用递归函数排序栈
// 栈只提供push、pop、isEmpty三个方法
// 请完成无序栈的排序，要求排完序之后，从栈顶到栈底从小到大
// 只能使用栈提供的push、pop、isEmpty三个方法、以及递归函数
// 除此之外不能使用任何的容器，数组也不行
// 就是排序过程中只能用：
// 1) 栈提供的push、pop、isEmpty三个方法
// 2) 递归函数，并且返回值最多为单个整数
code7
// 打印n层汉诺塔问题的最优移动轨迹
class039 嵌套类问题的递归解题套路【算法】
Code1 772. 基本计算器 III
https://leetcode.cn/problems/basic-calculator-iii/
code2 394. 字符串解码
https://leetcode.cn/problems/decode-string/
code3 726. 原子的数量
https://leetcode.cn/problems/number-of-atoms/
class049 滑动窗口技巧与相关题目【算法】
code1 209. 长度最小的子数组
https://leetcode.cn/problems/minimum-size-subarray-sum/
code2 3. 无重复字符的最长子串
https://leetcode.cn/problems/longest-substring-without-repeating-characters/
code3 76. 最小覆盖子串
https://leetcode.cn/problems/minimum-window-substring/
code4 134. 加油站
https://leetcode.cn/problems/gas-station/
code5 1234. 替换子串得到平衡字符串
https://leetcode.cn/problems/replace-the-substring-for-balanced-string/
code6 992. K 个不同整数的子数组
https://leetcode.cn/problems/subarrays-with-k-different-integers/
code7 395. 至少有 K 个重复字符的最长子串
https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/
class050 双指针技巧与相关题目【算法】
class066 一维动态规划【算法】
code1 509斐波那契数列
// 测试链接 : https://leetcode.cn/problems/fibonacci-number/
code2 983最低票价
// 测试链接 : https://leetcode.cn/problems/minimum-cost-for-tickets/
code3 91解码方法
// 测试链接 : https://leetcode.cn/problems/decode-ways/
code4 639解码方法 II
// 测试链接 : https://leetcode.cn/problems/decode-ways-ii/
code5 264. 丑数 II
// 测试链接 : https://leetcode.cn/problems/ugly-number-ii/
code6 32. 最长有效括号
// 测试链接 : https://leetcode.cn/problems/longest-valid-parentheses/
code7 67. 环绕字符串中唯一的子字符串
// 测试链接 : https://leetcode.cn/problems/unique-substrings-in-wraparound-string/
code8 940. 不同的子序列 II
// 测试链接 : https://leetcode.cn/problems/distinct-subsequences-ii/
class067 二维动态规划【算法】
code1 64. 最小路径和
// 测试链接 : https://leetcode.cn/problems/minimum-path-sum/
code2 79. 单词搜索
// 测试链接 : https://leetcode.cn/problems/word-search/
code3 1143. 最长公共子序列
// 测试链接 : https://leetcode.cn/problems/longest-common-subsequence/
code4 516. 最长回文子序列
// 测试链接 : https://leetcode.cn/problems/longest-palindromic-subsequence/
code5 节点数为n高度不大于m的二叉树个数
// 测试链接 : https://www.nowcoder.com/practice/aaefe5896cce4204b276e213e725f3ea
code6 329. 矩阵中的最长递增路径
// 测试链接 : https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/
class068 更多的动态规划【算法】
code1 115. 不同的子序列
// 测试链接 : https://leetcode.cn/problems/distinct-subsequences/
code2 72. 编辑距离
// 测试链接 : https://leetcode.cn/problems/edit-distance/
code3 97. 交错字符串
// 测试链接 : https://leetcode.cn/problems/interleaving-string/
code4 有效涂色问题
// 有效涂色问题
// 给定n、m两个参数
// 一共有n个格子，每个格子可以涂上一种颜色，颜色在m种里选
// 当涂满n个格子，并且m种颜色都使用了，叫一种有效方法
// 求一共有多少种有效的涂色方法
// 1 <= n, m <= 5000
// 结果比较大请 % 1000000007 之后返回
// 对数器验证
code5 最少删除多少字符可以变成子串
// 最少删除多少字符可以变成子串
// 给定两个字符串s1和s2
// 返回s1至少删除多少字符可以成为s2的子串
// 对数器验证
其余DP
操作系统
并行和并发
并发：单核CPU宏观上同时执行多个任务，微观上是分时交替执行多个任务；类似于时间片轮转算法
并行：多核CPU同时执行多个任务
并行：指两个或多个事件在同一时刻发生
并发：指两个或多个事件在同一时间间隔内发生
宏观上，有多个程序在同时运行
微观上，分时交替运行
什么是进程？进程和程序的区别？
引入进程：
并发执行 —— 间断性 + 失去封闭性 + 不可再现性 ——决定了通常的程序是不能参与并发执行的
为了能使程序并发执行，并且可以对并发执行的程序加以控制和描述 —— 进程
为了使参与并发执行的每个程序（含数据）都能独立地运行，在操作系统中必须为之配置一个专门的数据结构，称为进程控制块（PCB，Process Control Block）。
系统利用PCB来描述进程的基本情况和活动过程，进而控制和管理进程。
进程实体（进程映像） = 程序段 + 相关的数据段 + PCB
进程定义：
进程是程序的一次执行
进程是动态的，程序是静态的
进程创建需要CPU的资源，分配内存，进程控制块
引入进程
在一个未引入进程的系统中，在属于同一个应用程序的计算程序和I/O程序之间只能是顺序执行，即只有在计算程序执行告一段落后，才允许I/O程序执行；反之，在程序执行I/O操作时，计算程序也不能执行。
但在为计算程序和I/O程序分别建立一个进程后，这两个程序便可并发执行。若对内存中的多个程序都分别建立一个进程，它们就可以并发执行，能极大地提高系统资源的利用率，增加系统的吞吐量。
进程： 是指在系统中能独立运行并作为资源分配的基本单位，由一组机器指令、数据和堆栈等组成，是一个能独立运行的活动单位。
多个进程之间可以并发执行和交换信息。
进程的基本状态
就绪，执行，阻塞
创建，终止
进程的同步
硬件同步机制
1. 关中断
进入锁测试之前关闭中断，直到完成锁测试并上锁之后才能打开中断 —— 计算机系统不响应中断，保证锁测试和关锁操作的连续性和完整性
2. 利用 Test-and-Set指令实现互斥
3. 利用Swap指令实现进程互斥
信号量机制
1.整型信号量
2.记录型信号量
3.AND型信号量
4.信号量集
管程机制
虽然信号量机制是一种既方便、又有效的进程同步机制，但每个要访问临界资源的进程都必须具备同步操作wait(S)和signal(S)。这就使大量的同步操作分散在各个进程中。这样不仅给系统的管理带来了麻烦，而且还会因同步操作的使用不当而导致系统死锁。这样，在解决上述问题的过程中，便产生了一种新的进程同步工具——管程（Monitors）
进程通信
共享内存机制和消息传递机制两种
- 共享存储器系统
基于共享数据结构的通信方式 基于共享存储区的通信方式 - 消息传递系统
直接通信方式 间接通信方式
消息 邮箱 - 管道通信系统
连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件。 - 客户机—服务器系统
套接字、远程过程调用和远程方法调用
什么是线程？线程和进程的区别？
线程的引入
引入进程，是为了使多个程序能并发执行，以提高资源利用率和系统吞吐量。引入线程，则是为了减少程序在并发执行时所付出的时空开销，使 OS 具有更好的并发性。
时空开销：
创建进程、撤销进程、进程切换
线程与进程的比较
进程是操场系统资源拥有的最小单位
线程是操作系统调度的最小单位
进程控制块：PCB
线程控制块：TCB
TCB比PCB小
有程序计数器…等等线程私有的东西
1.调度的基本单位
在传统的 OS 中，作为拥有资源的基本单位和独立调度、分派的基本单位都是进程。而在引入线程的操作系统中，则把线程作为调度和分派的基本单位，而进程作为资源拥有的基本单位。
在同一进程中，线程的切换不会引起进程的切换，但从一个进程中的线程切换到另一个进程中的线程时，将会引起进程的切换。
2.并发性
在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行。
3.拥有资源
不论是传统的 OS，还是引入了线程的 OS，进程都可以拥有资源，并作为系统中拥有资源的一个基本单位。线程本身并不拥有系统资源，而是仅有一点必不可少的、能保证独立运行的资源，例如线程控制块等。
允许一个进程中的多个线程贡献该进程所拥有的资源，这主要表现在：属于同一进程的所有线程都具有相同的地址空间。
4.独立性
在同一进程中的不同线程之间的独立性要比不同进程之间的独立性低得多。因为进程之间是为了防止彼此干扰和破坏；而同一进程中的不同线程往往是为了提高并发性以及进行相互之间的合作而创建的。
5.系统开销
进程的创建、撤销和切换所付出的开销都明显大于线程的创建、撤销和切换的开销。
6.支持多处理机系统
对于单线程进程，不管多少处理机，同一时刻该进程只能运行在一个处理机上。对于多线程进程，就可以将一个进程中的多个线程分配到多个处理机上并行执行。
操作系统中线程的状态
三个基本状态：执行、就绪、阻塞
创建，终止
Java中线程的状态
-
新建状态(New): 线程对象被创建后，就进入了新建状态。例如，Thread thread = new Thread()。
-
就绪状态(Runnable): 也被称为“可执行状态”。线程对象被创建后，其它线程调用了该对象的start()方法，从而来启动该线程。例如，thread.start()。处于就绪状态的线程，随时可能被CPU调度执行。
-
运行状态(Running): 线程获取CPU权限进行执行。需要注意的是，线程只能从就绪状态进入到运行状态。
-
阻塞状态(Blocked): 阻塞状态是线程因为某种原因放弃CPU使用权，暂时停止运行。直到线程进入就绪状态，才有机会转到运行状态。阻塞的情况分三种：
- (01) 等待阻塞 – 通过调用线程的wait()方法，让线程等待某工作的完成。
- (02) 同步阻塞 – 线程在获取synchronized同步锁失败(因为锁被其它线程所占用)，它会进入同步阻塞状态。
- (03) 其他阻塞 – 通过调用线程的sleep()或join()或发出了I/O请求时，线程会进入到阻塞状态。当sleep()状态超时、join()等待线程终止或者超时、或者I/O处理完毕时，线程重新转入就绪状态。
-
死亡状态(Dead): 线程执行完了或者因异常退出了run()方法，该线程结束生命周期。
处理机调度的层次
1. 高级调度
作业调度
2. 低级调度
进程调度
3. 中级调度
内存调度
处理机（进程）调度算法
- 先来先服务调度算法
- 最短作业优先调度算法
- 高响应比优先调度算法
优先权=(等待时间+要求服务时间)/要求服务时间=响应时间/要求服务时间 - 时间片轮转调度算法
- 最高优先级调度算法
- 多级反馈队列调度算法
什么是死锁
如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程就是死锁的(Deadlock)。
死锁的必要条件
(1) 互斥条件
(2) 请求和保持条件
(3) 不可抢占条件
(4) 循环等待条件
怎么处理死锁
4种处理死锁的方法
(1) 预防死锁
破坏“请求和保持”条件
1.一次性申请全部资源 2.释放已用资源，请求所需资源
破幻“不可抢占”条件
请求得不到满足时释放所有资源
破坏“循环等待”条件
线性排序，按序号递增的顺序请求
(2) 避免死锁
银行家算法（Available Max Allocation Need） Request
安全性算法（Work Finish）
(3) 检测死锁
1.资源分配图
2.死锁定理
(4) 解除死锁
死锁解除算法
动态分区分配算法
基于顺序搜索的动态分区分配算法
1.首次适应（first fit，FF）算法
2.循环首次适应（next fit，NF）算法
3.最佳适应（best fit，BF）算法
4.最坏适应（worst fit，WF）算法
顺序搜索，是指依次搜索空闲分区链上的空闲分区，去寻找一个其大小能满足要求的分区。
碎片：内存空间不断被划分，会留下许多难以利用的、很小的空闲分区。
1.首次适应（first fit，FF）算法
要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止，缺点是低址部分会不断被划分，形成碎片。
2.循环首次适应（next fit，NF）算法
在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找。实现可通过设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式。缺点缺乏大的空闲分区。
3.最佳适应（best fit，BF）算法
总是把能满足要求、又是最小的空闲分区分配给作业，为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。缺点产生许多碎片。
4.最坏适应（worst fit，WF）算法
在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，分割一部分空间给作业使用。要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求即可。缺点缺乏大的空闲分区。
基于索引搜索的动态分区分配算法
1.快速适应算法
2.伙伴系统
3.哈希算法
虚拟存储
物理上扩容很简单，加内存条
逻辑上扩容，采用虚拟存储
实现方式：页面的调入调出
目的是：用磁盘来代替内存，降低成本
请求分页存储管理方式
请求分段存储管理方式
页面置换算法
-
最佳页面置换算法（OPT）
-
先进先出置换算法（FIFO）
-
最近最久未使用的置换算法（LRU）
-
最不常用置换算法（LFU）
-
时钟页面置换算法（Lock）
1.简单的 Clock 置换算法。
只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置 1。置换算法在选择一页淘汰时，只需检查页的访问位。如果是 0，就选择该页换出；若为 1，则重新将它置 0，暂不换出，而给该页第二次驻留内存的机会，再按照 FIFO 算法检查下一个页面。该算法是循环地检查各页面的使用情况的。又把该算法称为最近未用算法 NRU。
2.改进型 Clock 置换算法
在改进型 Clock 算法中，除须考虑页面的使用情况外，还须再增加一个因素，即置换代价，这样，选择页面换出时，既要是未使用过的页面，又要是未被修改过的页面。把同时满足这两个条件的页面作为首选淘汰的页面。由访问位 A 和修改位 M 可以组合成下面四种类型的页面：
1 类(A=0，M=0)：表示该页最近既未被访问，又未被修改，是最佳淘汰页。
2 类(A=0，M=1)：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。
3 类(A=1，M=0)：表示该页最近已被访问，但未被修改，该页有可能再被访问。
4 类(A=1，M=1)：表示该页最近已被访问且被修改，该页可能再被访问。
在内存中的每个页必定是这四类页面之一，在进行页面置换时，与简单 Clock 算法差别在于该算法须同时检查访问位与修改位，以确定该页是四类页面中的哪一种。其执行过程可分成以下三步：
1）从指针所指示的当前位置开始，扫描循环队列，寻找 A=0 且 M=0 的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位 A。
2）如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找 A=0 且 M=1 的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置 0。
3）如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并已将所有的访问位复 0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。
该算法与简单 Clock 算法比较，可减少磁盘的 I/O 操作次数。但为了找到一个可置换的页，可能须经过几轮扫描。换言之，实现该算法本身的开销将有所增加。
对I/O设备的控制方式
-
使用轮询的可编程I/O方式
-
使用中断的可编程I/O方式
-
直接存储器(DMA)访问方式
-
I/O通道控制方式
第六章 输入输出系统【操作系统】：6.4.3 对I/O设备的控制方式
磁盘调度算法
- 先来先服务算法
- 最短寻道时间优先算法
- 扫描算法
- 循环扫描算法
- NStepSCAN 和 FSCAN 调度算法
NStepSCAN 和 FSCAN 调度算法
1）NStepSCAN算法。
在 SSTF、 SCAN 及 CSCAN 几种调度算法中，都可能会出现磁臂停留在某处不动的情况。例如，有一个或几个进程对某一磁道有较高的访问频率，即这个(些)进程反复请求对某一磁道的 I/O 操作，从而垄断了整个磁盘设备。我们把这一现象称为“磁臂粘着”。
NStepSCAN 算法是将磁盘请求队列分成若干个长度为 N 的子队列，磁盘调度将按 FCFS 算法依次处理这些子队列。而每处理一个队列时又是按 SCAN 算法，对一个队列处理完后，再处理其他队列。当正在处理某子队列时，如果又出现新的磁盘 I/O 请求，便将新请求进程放入其他队列，这样就可避免出现粘着现象。当 N 值取得很大时，会使 N 步扫描法的性能接近于 SCAN 算法的性能；当 N=1 时，N 步 SCAN 算法便蜕化为 FCFS 算法。
2）FSCAN 算法。
FSCAN 算法实质上是 N 步 SCAN 算法的简化，即 FSCAN 只将磁盘请求队列分成两个子队列。一个是由当前所有请求磁盘 I/O 的进程形成的队列，由磁盘调度按 SCAN 算法进行处理。在扫描期间，将新出现的所有请求磁盘 I/O 的进程，放入另一个等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理。
计算机组成原理
CPU缓存：L1 L2 L3
主从与cache的地址映射
1.全相连映射方式
这种方法可使主存的一个块直接拷贝到cache中的任意一行上，非常灵活。
它的主要缺点是比较器电路难于设计和实现，因此只适合于小容量cache采用。
2.直接映射方式
直接相连映射方式的优点是硬件简单，成本低。缺点是每个主存块只有一个固定的行位置可存放,容易产生冲突。因此适合大容量cache采用。
3.组相连映射方式
组相联映射方式中的每组行数v一般取值较小，这种规模的v路比较器容易设计和实现。而块在组中的排放又有一定的灵活性,冲突减少。
I型 R型 J型指令设计
计算机系统结构
系统加速比
Amdahl定律
加速比=1/[(1-可改进比例)+可改进比例/部件加速比]
Cache
映像规则
-
全相联映像
主存中的任一块可以被放置到Cache中的任意一个位置。
特点：空间利用率最高，冲突概率最低，实现最复杂 -
直接映像
主存中的每一个块只能被放到Cache中唯一一个位置。
特点：空间利用率最低，冲突概率最高，实现最简单 -
组相联映像
Cache被等分成若干组，每组由若干个块构成。主存中的每一块可被放到Cache中唯一一个组的任何一个位置。组的选择常采用位选择算法：
Cache性能分析
平均访存时间＝命中时间＋不命中率×不命中开销
所以可以从三个方面来改进Cache的性能：降低不命中率、减少不命中开销、减少命中时间
降低Cache不命中率
三种不命中：强制性不命中 容量不命中 冲突不命中
增加Cache块的大小
增加Cache块的容量
提高相联度
伪相联Cache
硬件预取
编译器控制的预取
编译优化
牺牲Cache
减少Cache不命中开销
采用两级Cache
让读不命中优先于写
写缓冲合并
请求字处理技术
非阻塞Cache技术
减少命中时间
容量小、结构简单的Cache
虚拟Cache
Cache访问流水化
踪迹Cache
Cache优化技术总结
计算机网络
计算机网络的层次划分
各层次及其功能
OSI七层网络：物理层、数据链路层、网络层、运输层、会话层、表示层、应用层
TCP\IP四层网络：网络接口层、网际层IP、运输层、应用层
教学原理五层网络：物理层、数据链路层、网络层、运输层、应用层
物理层
透明的传输比特流
码分复用
数据链路层
其功能：封装成帧、透明传输、差错检测
CSMA/CD协议
发前先听、边发边听、冲突即停、延迟重发
MAC的帧结构
交换机自学习功能
学习源地址、转发异网帧、广播未知帧、过滤本网帧
网络层
IP协议
IP地址：分类、CIDR
IP数据报
地址解析协议ARP
根据IP地址出MAC地址
ARP请求，广播发送
ARP响应，单播发送
网际控制报文协议ICMP
ping：ICMP询问报文
tracerouter：ICMP差错报告报文
IPv6
路由选择协议
静态：人工
内部网关协议RIP：距离向量
内部网关协议OSPF：最短路径
外部网关协议BGP：路径向量
网络地址转换 NET
三个IPv4专业地址块
10.0.0.0/8：10.0.0.0至10.255.255.255
172.16.0.0/12：172.16.0.0至172.31.255.255
192.168.0.0/16：192.168.0.0至192.168.255.255
传输层
UDP
UPD是用户数据报协议
报文格式：UDP首部+数据
UDP首部（8）：目的端口（2）、源端口（2）、长度（2）、校验和（2），单位是字节
特点：
无连接 尽最大努力交付 面向报文 没有拥塞控制 支持一对多，多对一，多对多 首部开销小
应用场景：
对实时要求高的，不允许丢失要求不高的
语音、视频通话 游戏
DHCP DNS都是基于UDP的
TCP
TCP 是面向连接的、可靠的、基于字节流的传输层通信协议。
报文格式：TCP首部+数据
TCP首部格式目的端口、源端口、序号、确认号、标志位（SYN ACK FIN）、选项（窗口扩大 时间戳 选择确认）、填充、等等
固定20字节，最大60字节
特点：
面向连接的运输层协议 一对一（端到端） 可靠交付 全双工 面向字节流
应用场景：
对实时要求不高的，不允许丢失要求高的
文件传输
HTTP FTP就是基于TCP的
TCP的流量控制
用滑动窗口来实现流量控制的
发送窗口，不能大于接受方的接受窗口
防止上一次发送方接受到0窗口通知，但是后续的窗口扩大了，因为网络问题，接收不到
造成死锁，发送方发送不了数据，接收方有在等待发送数据
设置持续计时器，当收到零窗口通知时，启动计时
发送零窗口探测报文（仅携带1字节数据），如果后续还接收到0窗口通知就不发送，否则就开始发送，不超过其接受窗口
问题：如何控制发送报文段的时机：
不是收到一个确认，就发送下一个报文段
Nagle（纳格尔）算法：
先发送一个数据字节，然后把后续到来的数据字节缓存起来，收到确认，就把缓存中的全部发送出去，继续缓存后续字节
问题：糊涂窗口综合征
应用进程每次在接受缓存中处理一个字节，导致每一次发送的接受窗口大小都是1字节
解决：可以让接收方等待一段时间，使得或者接收缓存已有足够空间容纳一个最长的报文段，或者等到接收缓存已有一半空闲的空间。只要出现这两种情况之一，接收方就发送确认报文，和通知接受窗口的大小
上述两种方法可配合使用。使得在发送方不发送很小的报文段的同时，接收方也不要在缓存刚刚有了一点小的空间扰急忙把这个很小的窗口大小信息通知给发送方。
TCP的拥塞控制
慢开始：从1开始，每收到一个确认，拥塞窗口（cwnd）就加一（每一个RTT就加倍），直到门限值
拥塞避免：门限值之后，每一个传输轮次（RTT）加一，到超时0，就把新门限值设置为当前的拥塞窗口的一办，重新慢开始
快重传：当收到三个ack相同的报文，发送方就会快速发送这个序号的数据包
快回复：当收到三个ack相同的报文，引起的网络阻塞，不是进行慢开始，而是直接开始拥塞避免，从新门限开始
加法增大、乘法减小（AIMD）
TCP的连接管理
三次握手
客户端A主动打开连接，服务端B被动打开连接
开始时，服务端开启端口，接受请求，进入接听（Listen）状态
A：发送[SYN]包，SYN=1，seq=x，进入 SYN-SEND（同步已发送）状态
B：发送[SYN，ACK]包，SYN=1，ACK=1，seq=y，ack=x+1，进入SYN-RCVD（同步收到）状态
A：发送[ACK]包，ACK=1，sqq=x+1，ack=y+1，进入已建立连接（ESTABLISHED）状态；B收到后也进入已建立连接（ESTABLISHED）状态
为什么是三次握手，而不是两次或四次
四次的话，就是原先第二次握手，SYN ACK分开发送，但是有点浪费资源，能一次发送的
两次的话，就是删掉第三次握手。可能会已失效的连接请求报文段，重新建立连接
比如：A第一次发送SYN包，但是被网络拥塞了；之后又发送了SYN包，建立了链接，然后又释放了。
但是这是A第一次发送SYN包，又到了B，B接受了，处于连接状态了，但是A是不会给其发送数据的，使得B在苦等
四次挥手
客户端，服务器都可以先发送
A：发送[FIN]包，FIN=1，seq=u，主动关闭，进入FIN-WAIT-1（终止等待1）状态
B：发送[ACK]包，ACK=1，ack=u+1，被动关闭，进入CLOSE-WAIT（关闭等待）状态；A收到了进入FIN-WAIT-2（终止等待2）状态
此时，已关闭A->B的数据连接，TCP连接处于半关闭状态。
B->A，B仍可以发送数据，A依然接受
TCP是全双工的
B：发送[FIN]包，FIN=1，seq=v，进入LAST-ACK（最后确认）状态
A：发送[ACK]包，ACK=1,seq=v+1，进入TIME-WAIT（时间等待）状态，等待2MSL之后，如果没有再次接受，就CLOSE状态；B收到就进入CLOSE状态
MSL：最长报文寿命，2分种
问题：为什么，要等待2MSL？
为了保证A最后一次ACK达到B，使得B正确关闭；如果B没有收到此报文，将快速重传，让A发送。
问题：为什么是四次挥手，而不是三次
三次挥手，就是把第四次挥手删掉；
放在已失效的连接再次建立
保活计时器：没收到一个数据，就重新计时；当客户端意外故障关闭了，在2小时之后发送10个探测报文，没有响应就关闭连接
补充
tcp三次握手为什么不是两次
TCP三次握手是为了建立可靠的通信连接，确保双方都能够正常收发数据。三次握手的过程如下：
- 客户端向服务器发送一个连接请求报文段（SYN）。
- 服务器收到请求后，如果同意连接，则会发送一个确认报文段（SYN+ACK）作为回应。
- 客户端收到服务器的确认后，再次向服务器发送一个确认报文段（ACK）。
为什么不是两次握手呢？主要有以下两个原因：
-
可靠性：通过三次握手，可以确保客户端和服务器都确认了对方的存在和能力，避免了因为网络延迟或其他原因引起的错误连接。
- 在两次握手的情况下，如果客户端的连接请求报文段丢失，服务器将无法确认客户端的请求，从而无法建立连接。
- 在三次握手的情况下，即使客户端的连接请求报文段丢失，服务器能够发送自己的确认报文段，客户端收到后也能够确认服务器的存在。
-
防止已失效的连接请求报文段重复发送导致的问题：考虑这样一种情况，客户端发送了一个连接请求报文段，但是由于网络问题或其他原因导致客户端没有收到服务器的回应。如果客户端再次发送一个连接请求报文段，但是第一个连接请求报文段在网络中延迟到达，这时服务器就会误认为客户端新发送的连接请求，从而建立了两个连接。为了避免这种情况，引入了第三次握手，确保服务器收到客户端的确认报文段后，才正式建立连接。
综上所述，通过三次握手可以更好地保证通信连接的可靠性和防止错误连接的发生。
如果TCP是两次握手应该怎么发送两次握手包
如果TCP只进行两次握手，发送两次握手包的过程可以这样描述：
- 客户端发送一个连接请求报文段（SYN）给服务器。
- 服务器收到请求后，如果同意连接，则立即发送一个确认报文段（SYN+ACK）给客户端。
- 客户端收到服务器的确认后，建立连接，此时连接已建立。
在这种情况下，没有第三次握手，建立连接的过程相对简单。然而，这样的连接建立方式存在一些问题：
- 不可靠性：在两次握手的情况下，如果客户端的连接请求报文段丢失，服务器将无法确认客户端的请求，从而无法建立连接。
- 安全性问题：由于没有第三次握手，可能会有恶意主机发送大量的伪造连接请求，导致服务器资源被耗尽，也称为SYN洪泛攻击。
因此，为了确保连接的可靠性和安全性，TCP采用三次握手来建立连接。第三次握手是为了确保服务器收到客户端的确认报文段，从而避免了错误连接和资源浪费的问题。
TCP三次握手，怎么解决历史重复连接的
TCP三次握手可以解决历史重复连接的问题。具体过程如下：
- 客户端发送连接请求报文段（SYN）给服务器。
- 服务器收到请求后，如果同意连接，则发送确认报文段（SYN+ACK）给客户端，并为该连接分配资源。
- 客户端收到服务器的确认后，发送确认报文段（ACK）给服务器，建立连接。
- 连接建立后，双方可以开始进行数据传输。
在三次握手的过程中，服务器会为每个连接分配一个唯一的标识符，称为序列号（Sequence Number）。客户端发送的连接请求报文段中会包含一个初始的序列号，服务器在确认报文段中会回复一个确认序列号。
历史重复连接指的是客户端发送的连接请求报文段在网络中滞留，导致服务器延迟收到该请求，而客户端认为连接已建立，重新发送了连接请求。这样就会出现服务器收到重复的连接请求。
TCP通过使用序列号来解决历史重复连接的问题。服务器在收到重复的连接请求后，会检查该连接请求的序列号和已分配的序列号进行比较。如果两者一致，则说明该连接请求是历史重复连接，服务器会忽略该请求。如果不一致，则说明该连接请求是新的请求，服务器会重新处理并建立连接。
通过使用序列号来识别和处理历史重复连接，TCP确保了连接的可靠性和可用性。
TCP如何保证可靠性
可靠传输的工作原理 停止等待协议 连续ARQ协议
可靠传输是指在数据传输过程中，通过一定的机制保证数据能够可靠地传输到目的地。常见的可靠传输协议有停止等待协议和连续ARQ协议。
停止等待协议（Stop-and-Wait）是一种最简单的可靠传输协议，其工作原理如下：
- 发送方将数据分为固定大小的数据包，并逐个发送给接收方。
- 发送方发送一个数据包后，等待接收方确认收到的确认帧。
- 接收方收到数据包后，发送确认帧给发送方，确认该数据包已经接收。
- 发送方在接收到确认帧后，才发送下一个数据包。
- 如果发送方在一定时间内没有收到确认帧，会认为数据包丢失，并重新发送。
停止等待协议的优点是简单易实现，但由于发送方发送完一个数据包后需要等待确认帧才能发送下一个数据包，因此效率较低。
连续ARQ协议（Continuous Automatic Repeat reQuest）是一种高效的可靠传输协议，其工作原理如下：
- 发送方将数据分为固定大小的数据包，并逐个发送给接收方。
- 发送方连续发送数据包，不需要等待接收方的确认帧。
- 接收方收到数据包后，发送确认帧给发送方，确认该数据包已经接收。
- 发送方收到确认帧后，不断发送下一个数据包。
- 如果发送方在一定时间内没有收到确认帧，会认为数据包丢失，并重新发送。
连续ARQ协议通过允许发送方连续发送数据包，可以提高传输效率。同时，通过接收方的确认帧，可以保证数据传输的可靠性。常见的连续ARQ协议有选择重传ARQ（Selective Repeat ARQ）和回退N帧ARQ（Go-Back-N ARQ）。
TCP可靠传输的实现 以字节为单位的滑动窗口 超时重传时间的选择 选择确认SACK
TCP（传输控制协议）是一种可靠传输协议，它通过以下机制来实现可靠传输：
-
字节为单位的滑动窗口：TCP使用滑动窗口来管理发送方和接收方之间的数据流。发送方将数据分割成多个字节，并按顺序发送。接收方使用滑动窗口来指示可以接收的字节范围，发送方根据接收方的窗口大小来发送数据。发送方只发送接收方窗口范围内的数据，确保接收方有足够的缓冲区来接收数据。
-
超时重传时间的选择：TCP使用超时重传来处理丢失的数据包。发送方在发送数据包后，会启动一个定时器。如果在超时时间内没有收到接收方的确认，发送方会重传相应的数据包。TCP的重传时间选择是基于往返时间的估计值，通过动态调整来适应网络状况的变化。
-
选择确认（Selective Acknowledgment，SACK）：TCP的选择确认机制允许接收方在确认中指示已成功接收的数据范围，而不仅仅是下一个期望的字节。这样可以减少不必要的重传，提高传输效率。
通过上述机制，TCP实现了可靠传输。它保证了数据的顺序、完整性和可靠性，确保数据按照正确的顺序到达目的地，并能够正确处理丢失、重复、损坏和延迟等问题。
TCP粘包拆包
解决方法
- 发送端给每个数据包添加包首部，首部中至少包含数据包的长度，这样接收端接收数据后，通过读取每个数据包的长度，就可以知道每一个数据包的实际长度了，就可以区分粘包中数据包的界限。
- 发送端将每个数据包封装为固定长度（不够的通过补0填充），这样接收端每次从接收缓冲区中读取固定长度的数据，自然就会把每个数据包拆分开。
- 可以在数据包之间添加边界，如特殊符号。这样接收端就可以将不同的数据包拆分开。
TCP中的计时器
重传计时器
在一个TCP连接中，TCP每发送一个报文段就对此报文段设置一个超时重传计时器。若此计时器截止时还没有收到此报文段的确认报文，则重传此报文段，并将计时器复位。
持续计时器
为了解决0窗口大小造成的死锁。
当接收端宣布窗口大小为0时，发送TCP就会停止发送报文，直到接收端确认并宣布了一个非0大小的窗口。但是这个确认可能丢失，如果这个确认丢失，双方的TCP将会永远等待对方，称为了死锁。
要打开这个死锁，就启动了持续计时器，当持续计时器时间到了之后，发送端就发送一个特殊报文段，叫做探测报文段。探测报文段会告诉对端，确认已经丢失，必须重传。
保活计时器
保活计时器用来防止两个TCP之间的连接出现长时期的空闲。
如果客户打开了到服务器的连接，传送了一些数据，然后就保持静默。在这种情况下，这种连接将永远的处于打开状态。保活计时器每隔一段时间超时之后，会检查连接是否空闲太久了，如果空闲的时间超过了设置时间就会发送探测报文。然后通过对端是否响应、响应是否符合预期，来判断对端是否正常，如果不正常就主动关闭连接，而不用等待HTTP层的关闭。
时间等待计时器
时间等待计时器时在连接终止时使用的。（TIME_WAIT）
当TCP关闭一个连接时，他并不认为连接马上就真正关闭。在等待期间，连接处于一种中间过渡阶段，这就可以是重复的FIN报文段可以到达目的地。这个计时器的值通常设置为一个报文段的寿命期期待值的两倍。
应用层
超文本传输协议Http
端口号：80
Http1.0 1.1 2.0 3.0的优化
报文结构
超文本传输安全协议Https
端口号：443
见计算机网络安全
域名解析协议DNS
端口号：53
域名解析协议
域名换成IP地址
递归查询：
主机->本地域名服务器->根域名服务器->顶级域名服务器->权限域名服务器；
权限域名服务器->顶级域名服务器->根域名服务器->本地域名服务器；
本地域名服务器->主机
迭代查询：（指路不带路）
主机->本地域名服务器；
本地域名服务器->根域名服务器；
本地域名服务器->顶级域名服务器；
本地域名服务器->权限域名服务器
本地域名服务器->主机；
文件传送协议FTP
数据连接：20
控制连接：21
简单邮件传送协议SMTP
端口号：25
用户代理
邮件服务器
应用协议：邮件发送协议（如SMTP）和邮件读取协议（如POP3）
动态主机配置协议DHCP
客户端68 服务器67
动态获取IP地址，有租期的
dhcp release，主动解约
dhcp renew，主动申请
计算机网络安全
安全攻击
被动攻击：
消息内容泄露攻击和流量分析攻击
主动攻击：
假冒、重放、改写消息和拒绝服务。
被动攻击：窃听
主动攻击：篡改、恶意程序、拒绝服务
对称加密
明文:这是原始消息或数据，作为算法的输入。
加密算法:加密算法对明文进行各种替换和转换。
秘密密钥:秘密密钥也是算法的输入。算法进行的具体替换和转换取决于这个密钥。
密文:这是产生的已被打乱的消息输出。它取决于明文和秘密密钥。对于一个给定的消息,两个不同的密钥会产生两个不同的密文。
解密算法:本质上是加密算法的反向执行。它使用密文和同一密钥产生原始明文。
DES、3DES、AES
安全散列函数
散列函数的目的是为文件、消息或其他数据块产生“指纹”。为满足在消息认证中的应用,散列函数H必须具有下列性质:
(1)H可适用于任意长度的数据块。
(2)H能生成固定长度的输出。
(3)对于任意给定的x，计算H(x)相对容易，并且可以用软/硬件方式实现。
(4)对于任意给定值h，找到满足H(x)=h的x在计算上不可行。满足这一特性的散列函数称为具有单向性,或具有抗原像攻击性。
(5)对于任意给定的数据块x，找到满足H(y)=H(x)的y≠x在计算上是不可行的。满足这一特性的散列函数被称为具有抗第二原像攻击性，有时也称为具有抗弱碰撞攻击性。
(6)找到满足Hx)= H(y)的任意一对(x，y)在计算上是不可行的。满足这一特性的散列函数被称为抗碰撞性,有时也被称为抗强碰撞性。
前三个性质是使用散列函数进行消息认证的实际可行要求。第四个属性，抗原像攻击性，是单向性:给定消息容易产生它的散列码，但是给定散列码几乎不可能恢复出消息。如果认证技术中使用了秘密值（见图3.2（c))，则单向性很重要。秘密值本身并不会传输;然而，假如散列函数不是单向的，而攻击者能够分析或截获消息M和散列码C=H(SABlIM)，则攻击者很容易发现秘密值。攻击者对散列函数取逆得到SAB||M=H1( C)。因为这时攻击者拥有M和SABllM，所以他们可以轻而易举地恢复SAB。
抗第二原像攻击性质保证了对于给定的消息，不可能找到具有相同散列值的可替换消息。利用加密的散列码可防止消息被伪造(见图3.2（a）和图3.2(b))。如果该性质非真，则攻击者可以进行如下操作:第一，分析或截获消息及其加密的散列码;第二，根据消息产生没有加密的散列码;第三，生成具有相同散列码的可替换消息。
满足上面前5个性质的散列函数称为弱散列函数。如果还能满足第6个性质则称其为强散列函数。第6个性质可以防止像生日攻击这种类型的复杂攻击。生日攻击的细节超出了本书的范围。这种攻击把m比特的散列函数的强度从2m简化到2m/2。详细内容可参考[STAL11]。
除提供认证之外,消息摘要还能验证数据的完整性。它与帧检测序列具有相同的功能:如果在传输过程中,意外地篡改任意比特,消息摘要则会出错。
SHA
非对称加密
公钥密码方案由6个部分组成（见图3.9(a)）:
- 明文:算法的输入,它是可读的消息或数据。
- 加密算法:加密算法对明文进行各种形式的变换。
- 公钥和私钥:算法的输入，这对密钥如果一个密钥用于加密，则另一个密钥就用于解密。加密算法所执行的具体变换取决于输入端提供的公钥或私钥。
- 密文:算法的输出，取决于明文和密钥。对于给定的消息，两个不同的密钥将产生两个不同的密文。
- 解密算法:该算法接收密文和匹配的密钥，生成原始的明文。
公钥密码系统的应用
在广义上可以把公钥密码系统分为如下三类。
- 加密/解密:发送方用接收方的公钥加密消息。
- 数字签名:发送方用自己的私钥“签名”消息。签名可以通过对整条消息加密或者对消息的一个小的数据块加密来产生，其中该小数据块是整条消息的函数。
- 密钥交换:通信双方交换会话密钥。这可以使用几种不同的方法，且需要用到通信一方或双方的私钥。
RSA算法
基本的RSA加解密 对于某明文块M和密文块C加密和解密有如下的形式:
C=Memod n
M=Cd mod n=(Me)d mod n = Med mod n
发送方和按牧方那必须知道和e的值，并且只有接收方知道d的值。RSA公钥密码算法的公钥KU={e,u}私钥KR={d,n}。为使该算法能够用于公钥加密，它必须满足下列要求:
(1)可以找到e、d、n的值， 使得对所有的M<n，Medmod n=M成立。
(2)对所有满足M<n的值， 计算Me和Cd相对容易。
(3)给定e和n,不可能推出d。
前两个要求很容易得到满足。当e和n取很大的值时，第三个要求也能够得到满足。
要计算n的欧拉函数值Φ(n)。Φ(n)表示小于n且与n互素的正整数的个数。然后选择与Φ(n)互素的整数e(即e和Φ(n)的最大公约数为1)。最后，计算e关于模d(n)的乘法逆元d，d和e具有所期望的属性。
TLS 传输层安全
TLS体系结构
TLS记录协议
TLS握手协议
- 第一阶段:客户端发起建立连接请求.建立安全连接请求.包括协议版本、会话ID、密码套件、压缩方法和初始随机数
- 第二阶段:服务器认证和密钥交换。服务器发送证书、密钥交换数据和证书请求．最后发送hello消息阶段的结束信号
- 第三阶段:客户端认证和密钥交换。如果有证书请求，客户端发送证书。之后客户端发送密钥交换数据，也可以发送证书验证消息
- 第四阶段:完成。变更密码套件和结束握手协议
HTTPS RSA 握手解析
TLS 握手过程
HTTP 由于是明文传输，所谓的明文，就是说客户端与服务端通信的信息都是肉眼可见的，随意使用一个抓包工具都可以截获通信的内容。
所以安全上存在以下三个风险：
窃听风险，比如通信链路上可以获取通信内容，用户号容易没。
篡改风险，比如强制植入垃圾广告，视觉污染，用户眼容易瞎。
冒充风险，比如冒充淘宝网站，用户钱容易没。
HTTPS 在 HTTP 与 TCP 层之间加入了 TLS 协议，来解决上述的风险。
TLS 协议是如何解决 HTTP 的风险的呢？
信息加密： HTTP 交互信息是被加密的，第三方就无法被窃取；
校验机制：校验信息传输过程中是否有被第三方篡改过，如果被篡改过，则会有警告提示；
身份证书：证明淘宝是真的淘宝网；
可见，有了 TLS 协议，能保证 HTTP 通信是安全的了，那么在进行 HTTP 通信前，需要先进行 TLS 握手。TLS 的握手过程，如下图：
上图简要概述了 TLS 的握手过程，其中每一个「框」都是一个记录（record），记录是 TLS 收发数据的基本单位，类似于 TCP 里的 segment。多个记录可以组合成一个 TCP 包发送，所以通常经过「四个消息」就可以完成 TLS 握手，也就是需要 2个 RTT 的时延，然后就可以在安全的通信环境里发送 HTTP 报文，实现 HTTPS 协议。
所以可以发现，HTTPS 是应用层协议，需要先完成 TCP 连接建立，然后走 TLS 握手过程后，才能建立通信安全的连接。
事实上，不同的密钥交换算法，TLS 的握手过程可能会有一些区别。
这里先简单介绍下密钥交换算法，因为考虑到性能的问题，所以双方在加密应用信息时使用的是对称加密密钥，而对称加密密钥是不能被泄漏的，为了保证对称加密密钥的安全性，所以使用非对称加密的方式来保护对称加密密钥的协商，这个工作就是密钥交换算法负责的。
接下来，我们就以最简单的 RSA 密钥交换算法，来看看它的 TLS 握手过程。
RSA 握手过程
请看RSA 握手过程
数据库
以下都是基础学科的问题
一般面试笔试包括但不限于此
2023-10-14 15:53:04
关系数据库的定义
关系数据库是基于关系模型的数据库管理系统（DBMS），它使用表（也称为关系）来组织和存储数据。在关系数据库中，数据被存储在一个或多个表中，每个表由一组行和列组成。每个表都有一个唯一的标识符（主键），用于唯一地标识每一行。
简单理解就是一个二维表
数据库的查询
left join和right join的区别
数据库的范式
第一范式：列不可再分
第二范式：非主属性完全依赖主键
第三范式：非主属性之间不能有传递依赖
反范式化：范式化是为了减少数据冗余和消除数据更新异常，
而反范式化则是为了提高查询性能和简化复杂的查询操作。反范式化的过程可以包括合并表、增加冗余字段、创建索引等。
数据库事务
事务的特性
隔离级别
数据库的并发控制
并发操作的问题
丢失修改，不可重复读，读脏数据
封锁协议
(1) 一级封锁协议是：事务 T 在修改数据 R 之前必须先对其加 X 锁，直到事务结束才释放。
一级封锁协议能够解决"丢失修改"问题,不能保证可重复读和不读脏数据。
(2）二级封锁协议是：一级封锁协议加上事务在读取数据 R 之前必须先对其加 S 锁，读完后即可释放 S 锁。
二级封锁不仅可以解决"丢失修改"问题，而且可以解决读"脏"数据问题,不能保证可重复读。
(3）三级封锁协议是：一级封锁协议加上事务在读取数据 R 之前必须先对其加 S 锁，直到事务结束才释放。
三级封锁协议不仅解决了"丢失修改"、读"脏"数据问题，而且进一步解决了"不可重复读"问题
活锁死锁
活锁就是得不到请求的资源一直等待，饥饿现象
采用先来先服务可以解决
死锁就是互相持有对方所请求的资源，又请求另一个对方持有的资源
预防死锁：一次封锁法，顺序封锁法
诊断死锁：超时法，等待图发
解除死锁：撤销代价最小的事务
其他
可串行化
两段锁协议
多粒度封锁和意向锁
多版本并发控制
最后
2023-8-16 20:48:44
2023-10-14 17:08:41
我们都有光明的未来
祝大家考研上岸
祝大家工作顺利
祝大家心想事成
祝大家如愿以偿
点赞收藏关注哦