程序知识 了解程序是如何被计算机理解和执行的，对于理解数据库内核、存储过程、触发器以及SQL查询的处理过程至关重要。程序设计语言是用来定义计算机程序的符号系统，它允许程序员以人类可读的方式向计算机发出指令{card-default label="基本成分" width=""}字符集：构成语言的基本符号，通常包括字母、数字、下划线以及运算符等。关键字：又称保留字，是语言中具有特殊含义的单词，例如if、else、while、int、class等，不能用作标识符。标识符：由程序员定义的名称，用于代表变量、常量、函数、数据类型等程序对象。常量与变量：常量是在程序运行过程中其值不能被改变的量；变量是其值可以在程序运行中被改变的量，是内存中数据存储空间的抽象。数据类型：定义了数据的取值范围和可进行的操作。运算符：用于对数据进行操作的符号。表达式：由操作数和运算符组成的式子，可以计算出一个值。语句：程序中最基本的执行单位，用于完成一定的操作任务。{/card-default}{card-default label="类型和特征" width=""}命令式语言 (Imperative Languages)：也称为过程式语言，其核心思想是通过赋值语句改变变量的状态。典型代表有C、Pascal和Fortran。面向对象的程序设计语言 (Object-Oriented Programming, OOP)：其核心概念是类和对象。它将数据和对数据的操作封装在一起，支持继承、多态等特性，极大地提高了代码的可重用性和可维护性。典型代表有C++、Java和C#。函数式语言 (Functional Languages)：将计算看作是数学函数的求值过程，避免使用程序状态和可变数据。逻辑语言 (Logic Languages)：基于形式逻辑，通过推理来解决问题。Prolog是主要代表。脚本语言 (Scripting Languages)：通常用于控制软件应用程序，将应用程序联系起来，或用于快速编程。它们通常是解释执行的，如Perl、Python、Ruby、JavaScript、Shell等。一个重要的区别是：HTML不是编程语言。它是超文本标记语言（Hyper Text Markup Language），用于定义网页的结构和内容，而不是用于逻辑控制和计算的编程指令{/card-default}语言处理程序是介于用户程序与计算机硬件之间的重要系统软件，其任务是将程序员用高级语言编写的源代码翻译成计算机能够执行的机器码。{card-default label="语言处理程序分类" width=""}主要有三类：汇编程序、编译程序和解释程序。汇编程序 (Assembler)：将汇编语言（介于机器语言和高级语言之间的符号化语言）翻译成机器语言。汇编指令与机器指令之间基本上是一一对应的关系。编译程序 (Compiler)：将高级语言源程序一次性整体翻译成目标程序（通常是机器代码）。编译过程分为前端和后端，前端是机器无关部分，后端是机器相关部分。C、C++、Java等语言采用这种编译方式。编译方式下，用户程序运行速度更快。解释程序 (Interpreter)：不事先将源程序编译成目标代码，而是逐行读取源程序，边分析边执行。脚本语言如JavaScript、Shell通常采用解释执行方式。{/card-default}编译过程{card-default label="编译过程" width=""}编译过程是一个复杂的多阶段信息加工过程，通常包括：词法分析：从左到右逐个字符扫描源程序，识别出一个个“单词”（Token），如关键字、标识符、常数、运算符等。语法分析：根据语言的语法规则，将词法分析得到的单词序列进行解析，检查其结构是否符合语法要求，并构造出语法分析树。语义分析：判断源程序的语义是否正确，例如类型是否匹配、变量是否先声明后使用等。中间代码生成：将语法分析树或经过语义分析的源程序转换为一种内部表示形式（中间代码）。常用的中间码形式有后缀式（逆波兰式）、三地址码和抽象语法树等。代码优化：对中间代码进行等价变换，以期生成更高效的目标代码。目标代码生成：将优化后的中间代码翻译成最终的目标机器代码。符号表：是编译器用来记录源程序中各种标识符（如变量名、函数名）的属性和特征信息的数据结构，比如它的类型、作用域、存储地址等。在词法分析、语法分析和语义分析阶段，编译器会不断地查找、填入或更新符号表。函数调用和返回控制是用栈实现的，在程序运行期间，函数的调用和返回遵循“后进先出”（LIFO）的规则。因此，操作系统和运行时环境使用栈结构来管理函数调用，每个函数调用在栈上分配一个“栈帧”，用于存放其局部变量、参数和返回地址。函数返回时，其对应的栈帧被弹出。编译方式是将源代码一次性转换成目标代码（机器码），后续运行时直接执行目标代码，因此速度更快。解释方式则是逐条翻译并立即执行，不生成独立的目标程序，因此运行速度相对较慢。“编译程序不参与用户程序的运行控制”意味着执行的是编译后的目标代码，编译器本身已经退出了；“解释程序参与”意味着解释器本身一直在内存中运行，控制着整个执行流程。{/card-default}程序运行时的存储组织程序在运行的时候，其内存空间的组织方式对于理解数据库内部的内存管理非常重要。通常分为以下几个部分：程序代码区：存放程序的机器指令。静态数据区：存放已初始化的全局变量和静态变量。这些变量的生命周期是整个程序运行期。栈 (Stack)：又称动态数据区，用于存放函数调用过程中的局部变量、函数参数和返回值。栈的特点是“后进先出”，函数调用时分配，返回时释放。堆 (Heap)：又称动态数据区，用于存放程序运行过程中动态申请和释放的内存（如C语言中的malloc/free，C++中的new/delete）。堆的分配和释放由程序员控制，比栈更灵活，但管理也更复杂。在高级语言源程序中，为变量分配的存储单元地址通常属于逻辑地址，在运行时才转换为物理地址{card-default label="传值调用和引用调用的区别" width=""}传值调用传递实参的副本，形参在函数内的修改不影响原实参；引用调用传递实参的地址，形参与实参共享内存，函数内的修改直接影响原实参。传值调用方式下，数据是实参向形参的单向流动。引用调用方式下，可以实现形参和实参间双向传递数据的效果。传值调用的实参要求可以是变量，常量，表达式（有确定的值）。引用调用的实参必须是变量（内存地址中的左值）C语言基本类型传参、默认的简单类型传递。C++引用(&)、Java/C#中的对象传参。{/card-default}

数据结构 数据结构基本概念数据结构定义：数据元素之间的组织形式（逻辑结构、存储结构、数据运算）逻辑结构分类：线性结构（线性表、栈、队列）、非线性结构（树、图、集合）存储结构分类：顺序存储、链式存储、索引存储、散列存储线性结构{card-default label="线性结构" width=""}线性表顺序存储（顺序表）：特点：物理位置邻接表示逻辑关系，可随机存取优点：查找快，存储密度高缺点：插入删除需移动大量元素链式存储（链表）：特点：用任意存储单元存放，逻辑次序与物理次序不一定相同类型：单链表、循环链表、双向链表优点：插入删除方便缺点：查找需遍历，存储密度低栈（Stack）定义：限定只在表尾（栈顶）进行插入和删除的线性表特点：后进先出（LIFO）基本操作：入栈（Push）、出栈（Pop）、读栈顶应用场景：表达式求值、括号匹配、函数调用、递归实现队列（Queue）定义：只允许在表一端插入（队尾）、另一端删除（队头）的线性表特点：先进先出（FIFO）循环队列：解决假溢出问题，队空队满判断条件应用场景：任务调度、缓冲区、广度优先搜索串（String）定义：由零个或多个字符组成的有限序列子串：主串中任意连续字符组成的子序列，位置从第一个字符首次出现位置算起模式匹配：KMP算法（重点：next数组计算）数组和广义表数组：多维数组的存储：行优先、列优先二维数组地址计算（按行存储）特殊矩阵压缩存储：对称矩阵：存储下三角三对角矩阵：k = 2i + j - 3稀疏矩阵：三元组表、十字链表广义表：线性表的推广，元素可以是单元素或子表长度：最外层元素个数；深度：括号嵌套的最大层数表头、表尾操作{/card-default}树与图{card-default label="树与图" width=""}树的基本概念结点的度：子树个数树的度：结点度的最大值叶子结点：度为0的结点树的深度：最大层次二叉树定义：每个结点最多有两棵子树的树结构重要性质：第i层最多有 2^(i-1) 个结点（i≥1）深度为k的二叉树最多有 2^k - 1 个结点（k≥1）终端结点数n0与度为2的结点数n2关系：n0 = n2 + 1具有n个结点的完全二叉树深度为 ⌊log₂n⌋ + 1满二叉树：每层都满完全二叉树：除最后一层外都满，且最后一层结点靠左排列二叉树的遍历先序遍历：根 → 左 → 右中序遍历：左 → 根 → 右后序遍历：左 → 右 → 根层次遍历：从上到下，从左到右树与二叉树的转换转换规则：左孩子不变，兄弟结点变为左孩子的右孩子遍历对应关系：树的前序 = 二叉树的先序；树的后序 = 二叉树的中序图基本概念：顶点、边（弧）、有向图、无向图、完全图、度重要结论：有向图中，所有顶点出度数之和 = 入度数之和图中边数 = 所有顶点度数之和的一半存储结构：邻接矩阵、邻接表遍历：深度优先搜索（DFS）、广度优先搜索（BFS）应用：最小生成树（Prim、Kruskal）、最短路径（Dijkstra、Floyd）、拓扑排序{/card-default}{card-default label="查找算法" width=""}静态查找表顺序查找：O(n)折半查找（二分查找）：要求：顺序存储且关键字有序排列时间复杂度：O(log₂n)分块查找：块间有序，块内无序动态查找表二叉排序树（查找二叉树）：定义：左子树所有结点值 < 根结点值 < 右子树所有结点值中序遍历结果有序查找效率与树的高度相关平衡二叉树（AVL树）：定义：任一结点左右子树深度差不超过1平衡因子：右子树深度 - 左子树深度（取值-1,0,1）B树：多路平衡查找树，用于文件系统和数据库索引散列查找散列表：根据关键码值直接访问的数据结构散列函数：构造方法（直接定址法、除留余数法、数字分析法等）冲突处理：开放定址法（线性探测、二次探测、伪随机探测）链地址法再散列法装填因子：α = 表中记录数 / 散列表长度排序算法{/card-default}设计方法递归算法：函数调用自身（如阶乘、斐波那契、汉诺塔）分治法：分解 → 解决 → 合并（如归并排序、快速排序）回溯法：试探性搜索（如八皇后、图的着色）贪心法：局部最优（如最小生成树、最短路径）动态规划：记录子问题解避免重复计算（如斐波那契优化、背包问题）数据结构部分的重点集中在：二叉树的性质与遍历（每年必考，尤其是性质计算）查找算法比较（二分查找、二叉排序树、哈希冲突处理）排序算法对比（时间复杂度、稳定性、适用场景）图的基本结论（度与边数的关系）

此内容被密码保护 加密文章，请前往内页查看详情

数据库并发控制 并发控制要解决什么问题？当多个事务同时操作数据库时，如果不加控制，会出现以下四种问题：{callout color="#f0ad4e"}丢更新：你改的被我覆盖了。脏读：我读到你没提交的草稿，结果你反悔了。不可重复读：我查两次同一条数据，中间被你改了，两次结果不一样。幻读：我查两次同一类数据，中间被你插了新数据，第二次多出几行“幽灵”。{/callout}怎么解决？两大门派门派一：锁机制（悲观锁派）理念：“先锁门，再办事”，怕冲突。怎么锁：读锁（共享锁）：我读时，别人能读不能改。写锁（排他锁）：我改时，谁也别动。锁的规矩（协议）：一级：改前加写锁 → 防丢更新。二级：改前加写锁，读前加读锁（读完就放） → 防丢更新+脏读。三级：改前加写锁，读前加读锁（直到事完才放） → 防丢更新+脏读+不可重复读。门派二：MVCC（乐观锁派）理念：“各写各的版本，最后看谁的对”，不怕冲突。怎么玩：每条数据存多个版本，你读你的旧版本，我写我的新版本，互不阻塞。好处：读特快，读写不打架。代价：可能白写（提交时发现冲突，得回滚）。你该用哪个？（怎么选）选锁（悲观）：当 写很多、抢很凶 的时候（如秒杀、库存扣减）。选MVCC（乐观）：当 读很多、写很少 的时候（如新闻网站、查询系统）。现代数据库（如MySQL）：两个混着用，MVCC为主，锁为辅。终极心法：默认就用数据库的默认设置（通常是“读已提交”或“可重复读”），它已经平衡得很好了。真的遇到具体乱子（比如库存超卖），再对症下药：防覆盖 → 用写锁（SELECT ... FOR UPDATE）或乐观锁（加版本号）。要绝对一致 → 升隔离级别到串行化（性能会降）。记住：并发控制就是在 “不打架” 和 “快点干” 之间找平衡。没有完美方案，只有适合场景的方案。并行数据库体系结构把数据库任务分给多个处理器一起干，看这些处理器怎么共享硬件。四种架构：从“亲密”到“独立”想象一个办公室，看工位、文件柜怎么分配：共享内存（最亲密）场景：一个开放办公室，所有人用同一个大桌子（内存）和同一个文件柜（磁盘），靠喊话交流。特点：所有CPU共享同一块内存和同一套磁盘像一台电脑插了多个CPU优点：简单，协调容易（数据都在眼皮底下）缺点：大桌子（内存总线）太挤，人多了就堵文件柜（磁盘）排队严重扩展性差：加人（CPU）效果越来越差实际应用：小型服务器、老式数据库机共享磁盘（部分独立）场景：每人有自己的小办公桌（私有内存），但共享同一个公共文件柜（磁盘），需要时去柜子取文件。特点：每个CPU有私有内存，但共享同一套磁盘系统像多台电脑连同一个网络存储（SAN）优点：避免内存争抢（各自有桌子）方便扩展CPU磁盘坏了影响所有人缺点：抢文件柜：磁盘和网络易成瓶颈缓存同步麻烦：各自内存里的数据可能不一致实际应用：Oracle RAC（集群数据库）无共享（最独立）场景：每人有独立办公室，里面有自己的桌子、文件柜和电话，只通过网络沟通。特点：每个CPU有私有内存+私有磁盘完全不共享硬件，只通过网络通信像分布式系统优点：扩展性极好：加人加办公室就行没有硬件瓶颈缺点：协调复杂：数据分散，需要精心分配网络通信开销大一个办公室坏了，部分数据访问不了实际应用：大数据系统（Hadoop）、现代分布式数据库（Google Spanner、CockroachDB）层次式（混合型）场景：多个小团队（每个团队内共享内存或磁盘），团队之间通过网络协作。特点：以上三种的混合体比如：小组内“共享内存”，小组间“无共享”优点：灵活，平衡扩展性和复杂度缺点：设计复杂怎么记？看“共享什么硬件”共享内存 → 内存和磁盘都共享（全共享）共享磁盘 → 只共享磁盘，内存不共享（半共享）无共享 → 什么都不共享（全独立）层次式 → 爱怎么混就怎么混（混合体）要简单便宜、数据量不大 → 共享内存要高可用、不怕磁盘瓶颈 → 共享磁盘要海量数据、疯狂扩展 → 无共享要平衡复杂度和性能 → 层次式实际中：互联网公司基本都用 无共享 架构（因为数据太大、机器太多）。事务调度核心问题你有一堆事务要执行，怎么安排顺序？两种基本调度方式串行调度场景：单车道收费站，一次只过一辆车。做法：一个事务完全执行完，再执行下一个。优点：绝对安全，不会出错。缺点：效率低，资源闲置。举例：先执行完“张三转账给李四”，再执行“查询余额”。并发调度场景：多车道收费站，多辆车同时过。做法：多个事务的操作交错执行。优点：效率高，资源利用率高。缺点：可能出错（出现脏读、丢更新等问题）。举例：“张三转账”和“查询余额”的操作可能交替进行。调度的最高标准：可串行化调度这是并发调度的“黄金标准”。什么是可串行化调度？翻译成人话：虽然事务是并发交错执行的，但最终结果和按某种顺序串行执行的结果完全一样。数据库只接受两种调度：串行调度（太慢，一般不用）可串行化调度（又快又对，理想目标）所有非可串行化的并发调度，数据库都认为是有问题的！如何实现可串行化调度？数据库有两大工具：锁机制（特别是两段锁协议）做法：事务在扩展阶段只能加锁，在收缩阶段只能解锁。效果：只要所有事务都遵守两段锁协议，调度就一定是可串行化的。冲突可串行化（更常用的判断标准）关键概念：冲突操作两个操作来自不同事务操作同一数据项至少有一个是写操作串行调度是为了确保事务的一致性，实现一致性的办法是保证隔离性

此内容被密码保护 加密文章，请前往内页查看详情