1. 节点（Node）结构体 关键思想：跳表由多层链表组成。每个节点在第 i 层有一个 forward[i] 指针，指向该层的下一个节点；为了支持排名（rank）/区间计数，我们在每层维护一个 span[i] —— 从当前节点走 forward[i] 到下一个节点时跨越的底层节点数量（用来累加数量）。 C++ 的典型定义： struct Node { int val; ...

问题1: 主存（由DRAM构成）存储容量受限，但我不想让计算机收到物理内存大小的制约 问题2: 现代操作系统都支持多道程序运行，如何让多个程序有效而安全地共享主存 操作系统的出现 第一台计算机诞生时，采用手工操作的方式，一个用户独占全机 批处理系统：加载在计算机上的一个系统软件，在它的控制下，计算机能够自动地、成批地处理一个或多个用户的作业（包括程序、数据和命令） ...

并发 并发控制概述 事务是并发控制的基本单位 事务的ACID特性可能遭到破坏的原因之一：多个事务进行并发操作互相干扰 为了保证事务的隔离性和一致性，需要对并发操作进行正确调度 并发操作带来数据不一致性：丢失修改、脏读、不可重复读、幻读 丢失修改：两个事务T1和T2读入同一数据并修改， T2的提交结果破坏了T1提交的结果，导致T1的修改被丢失。 脏读： ...

机器永远是对的，未测代码永远是错的 理论基础：程序是个状态机 调试理论：如果我们能判定任意程序状态的正确性，那么给定一个failure，我们可以通过二分查找定位到第一个error的状态，即fault(error) 单步调试的局限性在于，假设某一个状态是对的，以此来调试下一个状态是否正确 工具：printf，GDB //TODO

会话层（The Session Layer） 1. 核心功能：管理对话 会话层的主要目标是建立、维护和同步两个通信应用之间的“会话”或“对话”。它确保通信是有组织、可管理和可靠的。 2. 具体职责： 会话控制：负责会话的建立、维护和有序终止。 对话管理：确定通信模式，如全双工或半双工。 同步与恢复：在长时间的通信中插入检查点。如果传输中断，可以从最近的检查点恢复，而不是...

哈希就是一种索引 核心思想：哈希是一种通过一个函数（哈希函数），将任意长度的输入（如字符串、对象等），映射到一个固定长度的输出（哈希值）的技术。这个输出通常是一个整数，可以作为数组的索引。 目标：理想情况下，通过这个索引可以直接访问到目标数据，从而实现近乎 O(1) 时间复杂度的查找、插入和删除操作。 1. 哈希的总体思想 哈希（Hashing）是一种用 O(1) 常数时间存取...

前面已经讨论了数据库系统的一般概念，介绍了关系数据库的基本概念、关系模型的三个部分以及关系数据库的标准语言 SQL 。但是还有一个很基本的问题尚未涉及：针对一个具体问题，应该如何构造一个适合于它的数据库模式，即应该构造几个关系模式，每个关系由哪些属性组成等。这是数据库设计的问题，确切地讲是关系数据库逻辑设计问题。 规范化、关系模式及范式 关系模式 [R(U, D, DOM, F)] ...

如果无法显示PDF，请 点击这里下载。 或者可以直接看图片版：

存储器概述 现代计算机的结构 存储器的层次化结构 主存储器逻辑上可以分为存储体、MAR、MDR SRAM、DRAM DRAM：利用栅极电容存储信息 SRAM：利用双稳态触发器存储信息 核心区别：存储元不一样 刷新是存储器独自完成的，不需要CPU的控制 ROM 很多ROM也具有随机存取的特性 断电后，RAM内数据全部丢失 ...

外部存储设备 特性 用于存储不经常使用的、数据量较大的信息 非易失 类型 磁盘存储器（magnetic disk） 光存储器（optical memory） 磁带（magnetic tape） U盘（USB flash disk），固态硬盘（solid state disk...