数据密集型应用系统设计

1. 红黑树、跳表介绍 & 同类有序结构
   1. 红黑树
      1. 一种自平衡二叉查找树，通过颜色规则（红 / 黑）+ 旋转保证树高始终为 O (log n)
      2. 核心约束：根节点黑、红节点子节点必黑、任意节点到叶子路径黑节点数相同
      3. 特点：查询 / 插入 / 删除均为 O(log n)，内存结构，适合频繁读写、随机查找
      4. 典型使用：C++ STL map/set、Java TreeMap
   2. 跳表（Skip List）
      1. 基于有序链表 + 多层索引实现的有序结构，用 “跳步” 加速查找
      2. 每层都是原链表的子集，高层索引跨度更大，查找时从高层往下逼近
      3. 特点：实现简单、并发友好，查询 / 插入 / 删除 O (log n)
      4. 典型使用：Redis SortedSet、LevelDB 内部索引
2. 类似的有序数据结构
   1. 平衡二叉树类：AVL 树、2-3 树、2-3-4 树
   2. 哈希 + 有序类：LinkedHashMap（Java）、OrderedDict（Python）
   3. 多路平衡查找树：B 树、B+ 树、B* 树
   4. 其他：treap（树堆）、splay tree（伸展树）、笛卡尔树

该算法最初于 1996 年以 日志结构合并树 （ Log-Structured Merge-Tree ）或 LSM 树 （ LSM-Tree ） 的名称发布，建立在早期日志结构文件系统工作的基础上。因此，基于合并和压实排序文件原理的存储引擎通常被称为 LSM 存储引擎 。

1. LSM = Log-Structured Merge Tree，日志结构合并树，这是一个算法，就是上面提到的日志结构存储，不是具体的某种树结构。核心思想：
   1. 写入不直接修改磁盘，先写内存 + 日志
   2. 内存满了再批量刷到磁盘形成有序文件
   3. 后台异步合并多个磁盘文件，减少小文件
   4. 适合极高写入吞吐，查询略慢（需多层查找）
   5. 典型使用：LevelDB、RocksDB、HBase、Cassandra、TiKV 等。
2. B 树 / B+ 树
   1. 经典磁盘友好的多路平衡查找树
   2. B 树：键值存在所有节点，叶子非链表
   3. B+ 树：键只在叶子节点，叶子形成有序链表
   4. 适合读多写少、强事务、随机查询
   5. 典型使用：MySQL InnoDB 索引、PostgreSQL、SQL Server
   6. B + 树适合 “读多、稳定、强事务”，LSM 树适合 “写爆、高吞吐、可接受略慢查询” 的场景。

1. MySQL 默认存储引擎 InnoDB 的默认事务隔离级别为：REPEATABLE READ（可重复读），简称 RR。注：MyISAM 等不支持事务的存储引擎，没有隔离级别概念。
2. MySQL 四大隔离级别（从低到高）：SQL 标准定义了4种隔离级别，InnoDB 全部支持。
   1. READ UNCOMMITTED（读未提交）：最低级别，能读到未提交的脏数据（脏读），几乎不用。
   2. READ COMMITTED（读已提交，RC）：只能读到已提交的数据，解决脏读，允许不可重复读。
   3. REPEATABLE READ（可重复读，RR）：✅ MySQL 默认，解决脏读+不可重复读；MySQL 还通过 MVCC+临键锁 额外解决了幻读（优于标准 SQL）。
   4. SERIALIZABLE（串行化）：最高级别，事务串行执行，无并发问题，但性能极差，极少使用。
3. 实用补充：
   1. 生产环境优化：互联网公司通常会把默认级别改为 READ COMMITTED（RC），锁粒度更小、并发性能更高。
   2. 修改临时隔离级别（当前会话生效）：SET SESSION transaction_isolation = 'READ-COMMITTED';

1. 临键锁(Next-Key Lock) 是 MySQL InnoDB 引擎在 REPEATABLE READ（RR） 隔离级别下默认使用的行级锁算法，本质是 记录锁(Record Lock)+间隙锁(Gap Lock) 的组合体。它不仅锁定具体的索引记录，还会锁定该记录之前的间隙，防止新记录插入，从而彻底解决幻读问题。

   锁类型	作用	锁定范围	触发场景	作用
   记录锁(Record Lock)	防止同一行被并发修改/删除：只锁这一行，不锁间隙	仅锁定具体索引记录本身	唯一索引等值查询（值存在）	防行并发修改
   间隙锁(Gap Lock)	防止在间隙中插入新记录：只锁 “空白区间”，不锁任何真实行	锁定两个索引值之间的空白区域，不包含记录本身	唯一索引等值查询（值不存在）	防插入
   临键锁(Next-Key)	组合防护，解决幻读：既锁行，又锁前面的间隙	左开右闭区间：(prev_value, current_record]，既锁记录又锁间隙	非唯一索引 / 范围查询	防幻读

2. 锁定范围与规则
   1. 临键锁遵循左开右闭原则，锁定区间为 (a, b]，例如：
      1. 当索引值存在 10、13、17 时，查询 WHERE age = 13 会锁定 age 索引上 (10, 13] 区间
      2. 范围查询 WHERE age BETWEEN 10 AND 20 会锁定锁定 age 索引上 (10,13]、(13,17]、(17,20] 多个区间（范围查询会把所有匹配区间全部上临键锁。）
3. 在 RR 隔离级别下，InnoDB 的加锁原则如下：
   1. 默认单位：加锁的基本单位是临键锁（Next-Key Lock）。
   2. 锁退化（优化）：
      1. 如果是唯一索引等值查询且记录存在，锁退化为记录锁（Record Lock）。
      2. 如果是唯一索引等值查询但记录不存在，锁退化为间隙锁（Gap Lock）。
   3. 非唯一索引/范围查询：始终使用完整临键锁
      1. 等值查询：对匹配的记录加记录锁，并加间隙锁（防止幻读）。
      2. 范围查询：使用临键锁。
      3. 适用范围：上述规则适用于 SELECT ... FOR UPDATE、UPDATE、DELETE 等当前读操作。
         1. FOR UPDATE 只是 “加锁指令”，具体加什么锁，看查询条件
         2. 能乐观锁（版本号）解决的，尽量不用悲观锁 FOR UPDATE。
         3. 一定要走索引，没索引会锁全表，直接把业务堵死。

1. 隔离级别是“目标”，而加锁是实现这个目标的“手段”之一。隔离级别定义了一个事务能看到其他事务操作的程度（即数据可见性规则），而数据库为了实现这些规则，会根据不同的隔离级别，采取不同的加锁策略。
2. MySQL 的 InnoDB 引擎主要通过两种技术来实现隔离级别：锁（Locking） 和 多版本并发控制（MVCC）。
   1. MVCC：一种“无锁”的并发控制机制。它通过保存数据的历史版本，让读操作可以去读一个“快照”，而不需要加锁。这极大地提升了读写并发的性能。
   2. 锁：传统的并发控制机制，通过锁定资源来阻止其他事务的访问。

      隔离级别	普通 SELECT (快照读)	SELECT ... FOR UPDATE/SHARE / UPDATE / DELETE (当前读)	核心实现机制
      读未提交 (RU)	不加锁	加行级排他锁 (X锁)	读不加锁，写加锁
      读已提交 (RC)	不加锁 (使用MVCC)	加行级排他锁 (X锁)，不加间隙锁	MVCC + 行锁
      可重复读 (RR)	不加锁 (使用MVCC)	加行级排他锁 (X锁) + 间隙锁 (Gap Lock)	MVCC + 临键锁
      串行化 (Serializable)	自动加共享锁 (S锁)	加行级排他锁 (X锁)	锁机制

   3. 在 RC 和 RR（MySQL默认）这两个最常用的隔离级别下，普通的 SELECT 查询都不会加锁，而是利用 MVCC 来实现高并发读取。
   4. 只有在最高的 Serializable 隔离级别下，普通的 SELECT 才会自动加锁（共享锁），因为它要求事务完全串行执行。
3. 什么情况下会加锁？
   1. 加锁主要发生在“当前读”的场景中，即需要读取数据的最新版本，或者要修改/删除数据时。
   2. 显式加锁查询：
      1. SELECT ... FOR UPDATE：给读取的行加上排他锁 (X锁)。其他事务不能读写这些行。
      2. SELECT ... LOCK IN SHARE MODE 或者 SELECT ... FOR SHARE：给读取的行加上共享锁 (S锁)。其他事务可以读，但不能修改。
   3. 写操作 (DML)：这是最常见的“默认加锁”情况。任何对数据的修改操作，在执行时都会自动对涉及的数据行加上排他锁 (X锁)。
      1. UPDATE …
      2. DELETE …
      3. INSERT …
   4. 特殊情况：
      1. 外键约束检查：在删除或更新父表记录时，InnoDB 会对子表的相关记录加共享锁进行检查。
      2. 唯一性约束检查：在插入数据时，为了检查唯一索引是否冲突，可能会对相关的索引记录加锁。
4. 加锁的粒度
   1. 记录锁 (Record Lock)：只锁住具体的某一行记录。这是最理想的锁。
   2. 间隙锁 (Gap Lock)：锁住一个索引范围（间隙），但不包括记录本身。主要用于防止“幻读”。
   3. 临键锁 (Next-Key Lock)：记录锁 + 间隙锁的组合。在 RR 隔离级别下，范围查询（如 WHERE id > 10）会使用临键锁，锁住扫描到的所有索引区间。
   4. 退化为表锁：这是一个性能陷阱！如果 UPDATE、DELETE 或 SELECT ... FOR UPDATE 的 WHERE 条件没有用到索引，InnoDB 无法精确定位到行，就会进行全表扫描，并锁住整张表的所有行。这会严重阻塞其他所有事务，导致系统性能急剧下降。

MVCC (多版本并发控制) 是现代数据库（如 MySQL 的 InnoDB、PostgreSQL、Oracle）中用于实现高并发访问的核心机制。简单来说，它的核心思想是：通过保存数据的历史版本，让“读”操作不需要加锁，从而实现“读写不冲突”。

1. 为什么要用 MVCC？（解决什么问题）
   1. 在传统的数据库锁机制中：
      1. 读操作需要加共享锁（S锁）。
      2. 写操作需要加排他锁（X锁）。
      3. 冲突：只要有人在写数据，其他人就不能读；只要有人在读数据，其他人就不能写。这会导致并发性能很差。
   2. MVCC 的出现就是为了解决这个问题：
      1. 读不阻塞写：你在读数据时，我可以修改它。
      2. 写不阻塞读：我在修改数据时，你依然可以读到修改前的旧版本（快照）。
2. MVCC 的核心原理（它是如何工作的）
   1. MVCC 的实现依赖于三个核心组件（以 MySQL InnoDB 为例）：
      1. 隐藏字段
         1. InnoDB 会在每一行数据后面自动添加几个隐藏列：
            1. DB_TRX_ID：记录最近修改这行数据的事务 ID。
            2. DB_ROLL_PTR：回滚指针，指向这行数据的旧版本（在 Undo Log 中）。
      2. Undo Log（回滚日志）
         1. 当你更新一行数据时，InnoDB 不会直接覆盖原数据，而是：
            1. 把旧数据写入 Undo Log。
            2. 生成新数据。
            3. 通过 DB_ROLL_PTR 把新旧数据串联起来，形成一个版本链。
      3. ReadView（读视图）
         1. 这是 MVCC 的“灵魂”。当一个事务进行查询时，它会生成一个 ReadView。ReadView 里记录了当前系统中所有活跃（未提交）的事务 ID 列表。
            1. 查询时的逻辑（可见性算法）：
               1. 当事务 A 查询数据时，拿着自己的 ReadView 去对比数据行上的 DB_TRX_ID：
                  1. 如果数据行的 DB_TRX_ID 在 ReadView 的活跃列表中（说明修改者还没提交），那就顺着 DB_ROLL_PTR 去找旧版本。
                  2. 一直找到第一个“已提交”的版本，返回给你。
               2. 就像你在看一本书（数据库），虽然作者（写事务）正在涂改书页，但你手里拿的是作者刚涂改前拍的一张“照片”（ReadView/快照）。你依然可以安心读你的照片，而作者可以在原书上随意修改，互不干扰。
3. 两种读取模式，在 MySQL 中，查询分为两种，决定了是否使用 MVCC：

   模式	说明	是否加锁	典型 SQL
   快照读	读取数据的历史版本（快照），不加锁，速度最快。	否	SELECT * FROM table ...
   当前读	读取数据的最新版本，并加锁，防止并发修改。	是	SELECT ... FOR UPDATE UPDATE DELETE INSERT

4. 隔离级别与 MVCC 的关系：MVCC 主要应用在 READ COMMITTED (RC) 和 REPEATABLE READ (RR) 这两个隔离级别中。它们的区别在于 ReadView 生成的时机不同：
   1. READ COMMITTED (读已提交)：
      1. 策略：每次执行 SELECT 时都生成一个新的 ReadView。
      2. 效果：你能看到其他事务已经提交的最新数据。
      3. 问题：同一个事务内，两次 SELECT 可能读到不一样的数据（不可重复读）。
   2. REPEATABLE READ (可重复读，MySQL 默认)：
      1. 策略：第一次执行 SELECT 时生成 ReadView，后续复用这个 ReadView。
      2. 效果：不管别人怎么修改并提交数据，你在整个事务期间看到的都是事务开始时的数据快照。
      3. 优势：解决了“不可重复读”问题。
5. MVCC 的优缺点
   1. 优点：
      1. 极高的并发性能：读写互不阻塞，特别适合“读多写少”的场景（如电商浏览商品详情）。
      2. 避免死锁：因为普通的 SELECT 不加锁，减少了死锁发生的概率。
   2. 缺点：
      1. 占用存储空间：需要维护 Undo Log 和历史版本数据。
      2. 维护成本：如果历史版本太多，查询时需要沿着版本链回溯，会影响性能。数据库需要后台线程（Purge）来清理过期的旧版本。

MVCC 就是用“空间换时间”的策略——通过保存数据的历史版本（Undo Log），让读操作可以去读旧版本，从而避免了加锁，极大地提升了数据库的并发处理能力。

1. 悲观锁：我觉得一定会有人跟我抢，所以我先锁住，再操作
   1. 事务里 FOR UPDATE 锁住行 → 逻辑计算 → UPDATE
   2. 绝对安全，不会并发错误，但锁持有时间长，并发差，容易死锁、阻塞
      SQL

      已复制！

      BEGIN;
      -- 先锁 A 账户（FOR UPDATE 排他锁）
      SELECT balance FROM user_account WHERE uid = 'A' FOR UPDATE;
      
      -- 逻辑校验余额足够
      -- 扣 A 钱
      UPDATE user_account SET balance = balance - 100 WHERE uid = 'A';
      
      -- 锁 B 账户
      SELECT balance FROM user_account WHERE uid = 'B' FOR UPDATE;
      -- 加 B 钱
      UPDATE user_account SET balance = balance + 100 WHERE uid = 'B';
      COMMIT;

2. 乐观锁：我觉得没人跟我抢，所以先不加锁，直接改，改的时候再校验
   1. 核心实现：加一个 version 版本号字段（也可以用 update_time 这种字段）
      1. 每次修改，版本号 + 1
      2. 修改时校验：版本号没变，说明没人动过，修改成功；变了就失败重试
      SQL

      已复制！

      -- 1. 先查数据和版本号（无锁）
      SELECT stock, version FROM goods WHERE id=1;
      
      -- 2. 直接更新，同时校验版本号
      UPDATE goods 
      SET stock=stock-1, version=version+1 
      WHERE id=1 AND version=刚才查到的版本号;
      
      -- 3. 业务上检查
      -- 如果更新行数 = 1 → 成功
      -- 如果 = 0 → 说明别人改了，重试即可

   2. 不加锁，无阻塞，并发性能极高，只有写冲突时才重试，大部分场景效率远高于悲观锁；乐观锁是业务层实现的逻辑，数据库本身不提供这个功能，完全靠你自己加字段、写 SQL 来控制。
   3. 读多写少、冲突少 → 用乐观锁
   4. 写冲突极高、必须强一致 → 用悲观锁 FOR UPDATE
3. 在互联网、电商、后端主流业务里：乐观锁用得远远更多（占 90% 以上），悲观锁（FOR UPDATE）只在少数强一致、低并发场景才用。