一.为什么索引需要并发控制

假设两个线程同时向一B+树叶子节点插入数据，若没有同步机制，可能出现以下问题

一个线程的修改覆盖另一个线程；节点中的键失去顺序；页面分裂执行两次；父节点保存错误的分隔键；线程读到修改一半的数据；指针指向无效页面；B+树结构永久损坏

二.事务锁（Lock）与闩锁（Latch）的区别

事务锁：防止另一个事务违反隔离性
闩锁：防止多个线程同时破坏B+树页面

三.闩锁的两种模式

1.读闩锁

多个线程可以同时持有读闩锁；持有读闩锁时不能进行结构修改

2.写闩锁

同一时间只能有一个线程持有；与其他读闩锁、写闩锁互斥

兼容关系

四.闩锁的常见实现

1.阻塞式互斥锁：线程无法获得闩锁时进入休眠，等待操作系统唤醒。

优点：等待时不持续消耗CPU；适合临界区较长的场景

缺点：线程休眠和唤醒成本较高；涉及操作系统调度

2.自旋锁：线程无法获得锁时进行循环检查

while (无法获得锁) {
    继续尝试
}

优点：不需要线程休眠和唤醒；适合持锁时间非常短的场景

缺点：等待期间持续消耗CPU；竞争激烈时性能较差

3.读写锁：

读写锁分别支持：多个并发读者；一个独占写者

4.设计闩锁时候需要考虑的问题

（1）公平性

（2）缓存一致性

（3）闩锁粒度

粒度过大：一把闩锁保护整个B+树。实现简单，但是几乎所有操作都是串行

粒度过小：每个键一个闩锁。并发度高，但是复杂度高

因此，实际系统通常采用节点级闩锁。

五.闩锁耦合

1.核心过程

锁住父节点
    ↓
锁住子节点
    ↓
释放父节点
    ↓
继续向下

线程移动时，短暂同时持有相邻两层节点的闩锁，就像沿树向下移动。

2.优点：可以避免

线程刚读取子节点指针
另一个线程就分裂或删除了该子节点

六.安全节点

是否能够提前释放祖先节点的闩锁取决于当前节点是否安全

1.查询节点：不会修改树结构，属于安全节点

2.插入操作：如果插入节点后子节点不会分裂，就是安全节点

3.删除操作：如果删除后不会低于最低占有率，就是安全节点

七.基本的B+树插入流程

保守的插入流程：

1. 从根节点开始获得写闩锁；
2. 向下找到目标子节点；
3. 获得子节点写闩锁；
4. 如果子节点安全，释放所有祖先闩锁；
5. 到达叶子节点后插入；
6. 必要时执行分裂并向上更新；
7. 释放剩余闩锁。

注：大多数插入不会引发分裂，但保守协议一路获取写闩锁，会阻塞大量只读操作。

八.乐观闩锁协议

为了提高并发效率，可以先假设本次操作不会引起节点的分裂

执行过程：

1. 从根节点向下时只获得读闩锁；
2. 到达目标叶子节点后获得写闩锁；
3. 如果叶子节点安全，直接完成操作；
4. 如果发现需要结构修改，则释放闩锁；
5. 使用保守协议重新执行。

九.常见问题以及处理

1.根节点并发问题

如果每次操作都长时间持有根节点闩锁，即使下层访问的是不同分支，也会被串行化。

优化方向包括：尽快释放根节点闩锁；使用乐观协议；单独保护根指针；’仅在根节点分裂或树高变化时使用独占保护

2.叶子结点扫描问题

通常按从左到右的顺序获得闩锁，但删除或合并操作可能需要以另一个方向访问兄弟节点。如果两个操作的获取顺序相反，就可能发生死锁。

因此，范围扫描通常采用尝试获取下一片叶子的闩锁的方式

如果失败：不无限等待；释放当前闩锁；重新开始或稍后重试。

十.哈希表的并发控制

1.保护的内容：桶内容；槽位状态；溢出页；全局扩容状态；目录结构

2.闩锁的类型

（1）整表闩锁

（2）页面级或桶级闩锁

（3）槽位级保护

3.为什么哈希表容易并发

（1）不同键大概率映射到不同的桶，普通哈希操作只访问一个桶或者少量槽位

（2）B+树从根节点开始操作，还可能沿父子关系传播分裂或者合并，所以更加困难

十一.物理正确性和逻辑正确性

1.物理正确性:由闩锁保护

（1）页面没有被破坏

（2）指针关系有效

（3）键保持有效

（4）分裂合并处于同一个状态

2.逻辑正确性：由事务锁，MVCC等机制保护

（1）事务能否看到某条记录

（2）是否允许两个事务修改同一行

（3）查询结果是否满足隔离级别

（4）是否出现不可重复读或幻读

附.性能优化原则，易错点