使用锁插入B+树
Inserting into B+ tree using locks
我正在尝试弄清楚如何使用锁将一个项目插入到 B+ 树中，但并不真正理解其背后的理论。
所以对于查找，我的看法是在根节点上加锁，然后决定去哪个子节点上锁，这时候可以释放父节点继续这个操作，直到我到达叶节点。
但是插入要复杂得多，因为我不能让任何其他线程干扰插入。我的想法是在通往叶节点的路径上的每个节点上都加锁，但是加那么多锁是相当昂贵的，然后我的问题是当叶节点因为太大而分裂时会发生什么？
有谁知道如何使用锁将项目正确地插入到 B+ 树中？
通常有许多不同的策略来处理 B 树中的锁定；其中大部分实际上涉及 B+ 树及其变体，因为它们几十年来一直在该领域占据主导地位。总结这些策略就等于总结了四个十年的进展；这几乎是不可能的。以下是一些亮点。
在初始下降期间最小化锁定量的一种策略是不锁定从根开始的整个路径，而只锁定从最后一个 'stable' 节点（即赢得的节点）开始的子路径'作为当前计划操作的结果拆分或合并）。
另一种策略是假设不会发生拆分或合并，这在大多数情况下都是正确的。这意味着可以通过仅锁定当前节点和下一个将下降到的子节点来完成下降，然后释放先前 'current' 节点上的锁，依此类推。如果事实证明最终需要拆分或合并，则在更重的锁定机制下从根重新下降（即以最后一个稳定节点为根的路径）。
另一个主要技巧是通过预防splitting/merging确保每个节点'descended through'稳定；也就是说，当当前节点在从下方冒泡的变化下分裂或合并时，它会在继续下降之前立即获得 split/merged 。这可以简化操作（包括锁定），并且在轮子的重新发明中有些流行 - 作业分配和 'me too' 实施，而不是复杂的生产级系统。
一些策略允许在没有任何锁定的情况下执行大多数正常操作，但通常它们需要稍微修改标准 B+Tree 结构；例如，参见 B-link trees。这意味着在树上运行的不同并发线程可以 'see' 不同的 物理 这棵树的视图 - 取决于它们何时到达哪里以及跟随哪个 link - 但它们所有人都看到相同的 逻辑 视图。
开创性论文和良好的概述：
- Efficient Locking for Concurrent Operations on B-Trees (Lehman/Yao 1981)
- Concurrent Operations on B*-Trees with Overtaking (Sagiv 1986)
- A survey of B-tree locking techniques (Graefe 2010)
- B+Tree Locking (slides from Stanford U, including Blink trees)
- A Blink Tree method and latch protocol for synchronous deletion in a high concurreny environment (Malbrain 2010)
- A Lock-Free B+Tree (Braginsky/Petrank 2012)
我正在尝试弄清楚如何使用锁将一个项目插入到 B+ 树中，但并不真正理解其背后的理论。
所以对于查找，我的看法是在根节点上加锁，然后决定去哪个子节点上锁，这时候可以释放父节点继续这个操作，直到我到达叶节点。
但是插入要复杂得多，因为我不能让任何其他线程干扰插入。我的想法是在通往叶节点的路径上的每个节点上都加锁，但是加那么多锁是相当昂贵的，然后我的问题是当叶节点因为太大而分裂时会发生什么？
有谁知道如何使用锁将项目正确地插入到 B+ 树中？
通常有许多不同的策略来处理 B 树中的锁定；其中大部分实际上涉及 B+ 树及其变体，因为它们几十年来一直在该领域占据主导地位。总结这些策略就等于总结了四个十年的进展；这几乎是不可能的。以下是一些亮点。
在初始下降期间最小化锁定量的一种策略是不锁定从根开始的整个路径，而只锁定从最后一个 'stable' 节点（即赢得的节点）开始的子路径'作为当前计划操作的结果拆分或合并）。
另一种策略是假设不会发生拆分或合并，这在大多数情况下都是正确的。这意味着可以通过仅锁定当前节点和下一个将下降到的子节点来完成下降，然后释放先前 'current' 节点上的锁，依此类推。如果事实证明最终需要拆分或合并，则在更重的锁定机制下从根重新下降（即以最后一个稳定节点为根的路径）。
另一个主要技巧是通过预防splitting/merging确保每个节点'descended through'稳定；也就是说，当当前节点在从下方冒泡的变化下分裂或合并时，它会在继续下降之前立即获得 split/merged 。这可以简化操作（包括锁定），并且在轮子的重新发明中有些流行 - 作业分配和 'me too' 实施，而不是复杂的生产级系统。
一些策略允许在没有任何锁定的情况下执行大多数正常操作，但通常它们需要稍微修改标准 B+Tree 结构；例如，参见 B-link trees。这意味着在树上运行的不同并发线程可以 'see' 不同的 物理 这棵树的视图 - 取决于它们何时到达哪里以及跟随哪个 link - 但它们所有人都看到相同的 逻辑 视图。
开创性论文和良好的概述：
- Efficient Locking for Concurrent Operations on B-Trees (Lehman/Yao 1981)
- Concurrent Operations on B*-Trees with Overtaking (Sagiv 1986)
- A survey of B-tree locking techniques (Graefe 2010)
- B+Tree Locking (slides from Stanford U, including Blink trees)
- A Blink Tree method and latch protocol for synchronous deletion in a high concurreny environment (Malbrain 2010)
- A Lock-Free B+Tree (Braginsky/Petrank 2012)