数据结构 数据结构基本概念数据结构定义：数据元素之间的组织形式（逻辑结构、存储结构、数据运算）逻辑结构分类：线性结构（线性表、栈、队列）、非线性结构（树、图、集合）存储结构分类：顺序存储、链式存储、索引存储、散列存储线性结构{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）层次式（混合型）场景：多个小团队（每个团队内共享内存或磁盘），团队之间通过网络协作。特点：以上三种的混合体比如：小组内“共享内存”，小组间“无共享”优点：灵活，平衡扩展性和复杂度缺点：设计复杂怎么记？看“共享什么硬件”共享内存 → 内存和磁盘都共享（全共享）共享磁盘 → 只共享磁盘，内存不共享（半共享）无共享 → 什么都不共享（全独立）层次式 → 爱怎么混就怎么混（混合体）要简单便宜、数据量不大 → 共享内存要高可用、不怕磁盘瓶颈 → 共享磁盘要海量数据、疯狂扩展 → 无共享要平衡复杂度和性能 → 层次式实际中：互联网公司基本都用 无共享 架构（因为数据太大、机器太多）。事务调度核心问题你有一堆事务要执行，怎么安排顺序？两种基本调度方式串行调度场景：单车道收费站，一次只过一辆车。做法：一个事务完全执行完，再执行下一个。优点：绝对安全，不会出错。缺点：效率低，资源闲置。举例：先执行完“张三转账给李四”，再执行“查询余额”。并发调度场景：多车道收费站，多辆车同时过。做法：多个事务的操作交错执行。优点：效率高，资源利用率高。缺点：可能出错（出现脏读、丢更新等问题）。举例：“张三转账”和“查询余额”的操作可能交替进行。调度的最高标准：可串行化调度这是并发调度的“黄金标准”。什么是可串行化调度？翻译成人话：虽然事务是并发交错执行的，但最终结果和按某种顺序串行执行的结果完全一样。数据库只接受两种调度：串行调度（太慢，一般不用）可串行化调度（又快又对，理想目标）所有非可串行化的并发调度，数据库都认为是有问题的！如何实现可串行化调度？数据库有两大工具：锁机制（特别是两段锁协议）做法：事务在扩展阶段只能加锁，在收缩阶段只能解锁。效果：只要所有事务都遵守两段锁协议，调度就一定是可串行化的。冲突可串行化（更常用的判断标准）关键概念：冲突操作两个操作来自不同事务操作同一数据项至少有一个是写操作串行调度是为了确保事务的一致性，实现一致性的办法是保证隔离性

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

SQL优化规则 通常多表连接查询（JOIN）比嵌套查询（子查询）效率更高，因为数据库优化器可以对连接进行更好的执行计划优化，而子查询（尤其是相关子查询）可能导致多次执行或产生临时表。MYSQL5.7以前是这样相关子查询（子查询依赖外层查询的值）对外层每一行都会执行一次，效率很低；非相关子查询（独立子查询）只执行一次，效率更高。应尽量避免使用相关子查询。尽量使用UNION ALL操作，而不使用UNION操作，因为UNION 会去除重复行，需要排序和去重操作，开销大；UNION ALL 直接合并结果集，不去重，效率更高。如果业务允许（不需要去重），应使用 UNION ALL。经常使用COMMIT语句，以尽量释放封锁。及时提交事务（COMMIT）可以释放持有的锁，减少锁竞争，提高系统并发性能。尤其对于频繁执行的短事务，建议及时提交。