数据库系统核心讲义：索引与并发控制#

1. 核心概念解释#

• 定义：B+树是一种自平衡的 M 路树（M-way Tree），是数据库系统中最常用的索引数据结构。
• 结构特点：
  • 内部节点 (Inner Nodes)：仅存储键（Key）作为路标（Guideposts），用于导航，不存储实际数据。
  • 叶子节点 (Leaf Nodes)：存储所有键值对（Key-Value Pairs），并且通过兄弟指针 (Sibling Pointers) 相互连接，形成有序链表。
  • 高度平衡：从根节点到任何叶子节点的距离是相同的。

2. 关键结论 / 公式 / 方法#

• 查找 (Search)：从根节点开始，根据 Key 的大小比较决定向左或向右（或中间）遍历，直到抵达叶子节点。
• 插入 (Insert)：
  • 找到目标叶子节点。如果空间足够，直接插入。
  • 如果溢出 (Overflow)，将叶子节点分裂 (Split) 成两个，并将中间键（Middle Key）向上提升到父节点。此过程可能递归向上直到根节点。
• 删除 (Delete)：
  • 删除后若节点半满（Half-full）以上，直接结束。
  • 若下溢 (Underflow)（少于半满），尝试从兄弟节点借键 (Steal/Redistribute)。
  • 若兄弟节点无法借出，则与兄弟节点合并 (Merge)，并删除父节点中的对应键。
• 节点设计：通常节点大小对应磁盘页面大小（如 8KB），M 值（扇出）很大，树的高度通常较矮（4-5层）。

3. 易混点或易错点提示#

• B树 vs B+树：
  • B树 (B-Tree)：数据（Values）可以存储在内部节点。删除时可能很复杂，因为键可能在非叶子节点被移除。
  • B+树：数据只存在于叶子节点。内部节点只是路标。即使在叶子节点删除了键，该键仍可能保留在内部节点作为导航使用，这在 B+树中是允许的。
• 聚簇索引 (Clustered Index)：指表的数据文件按照主键索引的顺序物理排序（或数据直接存储在叶子节点中，如 MySQL InnoDB）。
• 重复键处理：通常通过在该键后追加 Record ID (RID) 来保证唯一性，而不是使用溢出页（Overflow pages）。

4. 简短复习小结#

B+树是为磁盘 I/O 优化的数据结构，支持高效的点查询（Point Query）和范围扫描（Range Scan）。通过将所有数据下沉到叶子节点并横向链接，它能将随机 I/O 转换为顺序 I/O。

1. 核心概念解释#

• 布隆过滤器 (Bloom Filter)：一种概率型数据结构，用于快速判断“某样东西一定不存在”或“可能存在”。它不存储实际数据，只占用极小的内存。
• 跳表 (Skip List)：一种基于概率的链表结构，通过多层索引指针实现近似 $O(\log N)$ 的查找。常用于内存数据库（如 MemTable）。
• 基数树 (Radix Tree / Compact Trie)：Trie 的压缩变体。通过路径上的字符/位来确定位置，具有确定性结构。适合字符串键。

2. 关键结论 / 公式 / 方法#

• Bloom Filter 运作机制：
  • 使用 $k$ 个哈希函数将键映射到位数组的 $k$ 个位置并置为 1。
  • 查询时，若所有 $k$ 个位置都为 1，则返回“可能存在”；若任一位置为 0，返回“绝不存在”。
  • 注意：标准 Bloom Filter 不支持删除（需使用 Counting Bloom Filter）。
• Skip List 运作机制：
  • 插入时通过“抛硬币”决定该节点的高度（层数）。
  • 无需像 B+树那样进行全局重新平衡（Splits/Merges），更适合高并发写入。
• Trie/Radix Tree 优势：
  • 查找复杂度仅与键长 $K$ 有关 $O(K)$，与数据量 $N$ 无关。
  • 若查找路径中断，可立即停止，对于查找“不存在”的键效率极高。

3. 易混点或易错点提示#

• Bloom Filter 的误报 (False Positive)：可能会提示键存在但实际上不存在（位碰撞导致）。但绝不会出现漏报 (False Negative)。
• Trie vs B+树：Trie 对变长字符串处理更好，且不需要重新平衡；B+树对范围查询（Range Scan）更友好。

4. 简短复习小结#

数据库不仅仅使用 B+树。Bloom Filter 用于减少不必要的磁盘读写（作为一种过滤器）；Skip List 是内存引擎（如 RocksDB/LSM）的常见选择；Radix Tree 在现代系统（如 DuckDB, Hyper）中因对 CPU 缓存友好而复兴。

1. 核心概念解释#

• 倒排索引 (Inverted Index)：用于全文搜索。将文档中的“词项 (Term)”映射到包含该词的“记录 ID 列表 (Posting List)”。
• 向量索引 (Vector Index)：用于语义搜索（Semantic Search）。将数据（如文本、图片）通过模型（Transformer）转换为浮点数向量（Embeddings），并在高维空间中查找“最近邻”。

2. 关键结论 / 公式 / 方法#

• 倒排索引查询：支持关键词查询（Contains ‘Word’），这是 B+树做不到的。常用算法如 TF-IDF 或 BM25 进行相关性排序。
• 向量搜索算法 (ANN)：
  • IVF (Inverted File)：聚类方法。先找到最近的聚类中心 (Centroid)，再在聚类内搜索。
  • HNSW (Hierarchical Navigable Small Worlds)：一种分层图结构。类似于图版本的 Skip List。从上层稀疏图开始导航，逐层向下缩小搜索范围，直至找到最近邻。

3. 易混点或易错点提示#

• 语义 vs 关键词：倒排索引做的是精确或模糊的关键词匹配；向量索引做的是语义含义匹配（例如搜 “running from police” 可能匹配到含义相近但词汇不同的歌词）。
• HNSW 与 Skip List 的联系：HNSW 借用了 Skip List 的分层思想，只是它是在图上进行而非链表。

4. 简短复习小结#

随着 AI 的发展，数据库开始原生支持向量搜索（如 PostgreSQL 的 PGVector）。HNSW 是目前最主流的向量索引算法，兼顾了效率和准确性。

1. 核心概念解释#

• 逻辑正确性 vs 物理正确性：
  • Latch（闩锁）用于保证物理正确性（防止指针指向无效内存，防止内部数据结构损坏）。
  • Lock（事务锁）用于保证逻辑正确性（事务隔离级别）。
• Latch 模式：
  • Read Mode (Shared)：允许多个读取者。
  • Write Mode (Exclusive)：独占，仅允许一个写入者。

2. 关键结论 / 公式 / 方法#

• Latch 实现方式：
  • Test-and-Set Spinlock (自旋锁)：用户态循环检查，效率高但不适合长时间持有（浪费 CPU）。
  • Blocking OS Mutex：获取失败则挂起线程，由 OS 调度。开销大（系统调用），但适合长等待。
  • Reader-Writer Latch：基于计数器实现读写分离。
• 哈希表 Latching：
  • Page Latches：锁整个页，并发度中等。
  • Slot Latches：锁单个槽位，并发度高但元数据开销大。
• B+树 Latching：螃蟹步协议 (Latch Crabbing/Coupling)：
  • 基本规则：获取子节点的 Latch 后，如果确认该子节点是“安全”的（不会发生 Split/Merge），则释放父节点的 Latch。
  • 搜索 (Search)：从上往下获取 Read Latch，获取子节点后立即释放父节点。
  • 插入/删除 (Insert/Delete)：从上往下获取 Write Latch。只有当子节点确认“安全”（不会溢出或下溢）时，才释放父节点及其祖先的 Write Latch。
• B+树 乐观锁优化 (Optimistic Latching)：
  • 假设大概率不会发生 Split/Merge。
  • 先全程使用 Read Latch 到达叶子节点。
  • 到达叶子后，获取叶子节点的 Write Latch。如果不需分裂/合并，操作完成。
  • 如果发现需要分裂/合并，释放所有锁，重启操作并使用悲观模式（全程 Write Latch）。

3. 易混点或易错点提示#

• Latch 不需要回滚 (Rollback)：Latch 保护的是极短的临界区。如果操作失败，通常是由线程自己清理，而不是像事务那样由系统回滚。
• 死锁处理 (Deadlock)：
  • Latch 不进行死锁检测。必须通过编码规范（Coding Discipline）避免死锁。
  • 叶子节点扫描死锁：当 B+树叶子节点横向扫描（Range Scan）时，可能遇到反向持锁的线程。此时只能立刻放弃并重试 (Kill yourself/Retry)，不能等待，因为没有死锁检测机制。
• Linus Torvalds 的观点 vs 数据库现状：Linus 反对用户态自旋锁，但数据库为了性能（避免系统调用和上下文切换）通常还是会在用户态实现自己的 Latch。

4. 简短复习小结#

并发控制是多线程数据库的难点。对于 B+树，Latch Crabbing 是标准解法。为了性能，通常优先尝试乐观锁策略。在叶子节点横向扫描遇到锁冲突时，遵循“不等待（No Wait）”原则以避免死锁。

寄语： 同学，Project 2 将会非常具有挑战性，尤其是并发部分。建议先实现单线程版本的 B+树，确保逻辑正确，然后再按照上述的 Latch Crabbing 协议添加并发保护。祝你编码愉快！