一.为什么索引需要并发控制假设两个线程同时向一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.叶子结点扫描问题通常按从左到右的顺序获得闩锁但删除或合并操作可能需要以另一个方向访问兄弟节点。如果两个操作的获取顺序相反就可能发生死锁。因此范围扫描通常采用尝试获取下一片叶子的闩锁的方式如果失败不无限等待释放当前闩锁重新开始或稍后重试。十.哈希表的并发控制1.保护的内容桶内容槽位状态溢出页全局扩容状态目录结构2.闩锁的类型1整表闩锁2页面级或桶级闩锁3槽位级保护3.为什么哈希表容易并发1不同键大概率映射到不同的桶普通哈希操作只访问一个桶或者少量槽位2B树从根节点开始操作还可能沿父子关系传播分裂或者合并所以更加困难十一.物理正确性和逻辑正确性1.物理正确性:由闩锁保护1页面没有被破坏2指针关系有效3键保持有效4分裂合并处于同一个状态2.逻辑正确性由事务锁MVCC等机制保护1事务能否看到某条记录2是否允许两个事务修改同一行3查询结果是否满足隔离级别4是否出现不可重复读或幻读附.性能优化原则易错点