使 B+ 树并发线程安全
Make a B+ Tree concurrent thread safe
我在Java中实现了一个B+树。现在我想知道允许并发插入的最佳方法是什么。我的想法是锁定一个节点，如果它是 maxFilled -1（这意味着拆分事件已关闭）。否则我会在轮班期间锁定阵列。但是这种方式可能会碰巧锁定一个非常靠近根的节点，因此也锁定了太多的子节点。是否有更好的方法或最佳实践来使 B+ 树线程安全？
您可以实施 lock-free version of a B-tree.
这种方法会导致需要拆分的节点逐渐标记为冻结（通过原子比较和交换操作将节点中的各个条目逐个标记为冻结，直到完全冻结）。
读者可以继续在 partially/fully 冻结节点导航到树的其他部分，确保读者的高并发性。
一个完全冻结的节点被替换，然后进行垃圾收集，这与具有垃圾收集功能的 Java 配合得很好。
论文中详细记录了详细信息，没有必要将它们全部复制到此处。这张图（摘自论文）显示了好处：
我在Java中实现了一个B+树。现在我想知道允许并发插入的最佳方法是什么。我的想法是锁定一个节点，如果它是 maxFilled -1（这意味着拆分事件已关闭）。否则我会在轮班期间锁定阵列。但是这种方式可能会碰巧锁定一个非常靠近根的节点，因此也锁定了太多的子节点。是否有更好的方法或最佳实践来使 B+ 树线程安全？
您可以实施 lock-free version of a B-tree.
这种方法会导致需要拆分的节点逐渐标记为冻结（通过原子比较和交换操作将节点中的各个条目逐个标记为冻结，直到完全冻结）。 读者可以继续在 partially/fully 冻结节点导航到树的其他部分，确保读者的高并发性。 一个完全冻结的节点被替换，然后进行垃圾收集，这与具有垃圾收集功能的 Java 配合得很好。
论文中详细记录了详细信息，没有必要将它们全部复制到此处。这张图（摘自论文）显示了好处：