gpt4 book ai didi

java - 使 B+ 树并发线程安全

转载 作者:塔克拉玛干 更新时间:2023-11-02 08:09:15 24 4
gpt4 key购买 nike

我已经用 Java 实现了一个 B+ 树。现在我想知道允许并发插入的最佳方法是什么。我的想法是锁定一个节点,如果它是 maxFilled -1(这意味着拆分事件已关闭)。否则我会在轮类期间锁定阵列。但是这种方式可能会碰巧锁定一个非常靠近根的节点,因此也锁定了太多的子节点。是否有更好的方法或最佳实践来确保 B+ 树线程安全?

最佳答案

你可以实现一个 lock-free version of a B-tree.

这种方法会导致需要拆分的节点逐渐标记为卡住(通过原子比较和交换操作将节点中的各个条目逐一标记为卡住,直到完全卡住)。读者可以继续在部分/完全卡住的节点上导航到树的其他部分,确保读者的高并发性。替换完全卡住的节点,然后进行垃圾收集,这与具有垃圾收集功能的 Java 配合得很好。

论文中详细记录了详细信息,没有必要将它们全部复制到此处。这张图(摘自论文)显示了好处:

enter image description here

关于java - 使 B+ 树并发线程安全,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31203880/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com