使b+tree并发(c)

Question

我目前正在尝试创建一个并发的b+树。

到目前为止，我考虑的作为起点的方法是在插入时迭代树，锁定每个节点(每个节点都有自己的锁)，一旦获得树中下一个节点的锁，就解锁，直到一个节点的子节点具有b+树-1键的顺序可以被修改，之后运行所有必要的插入操作并解锁该节点。

这显然是一种非常幼稚的方法，在并发性方面没有提供太多，所以我想知道是否有更好的方法来做这件事？我们将非常感谢您的任何投入！

Answer 1

我刚刚完成了一个实现并发B+树的项目。你可以从CMU 15-445 (数据库系统)中找到一些直觉：

https://15445.courses.cs.cmu.edu/fall2018/slides/09-indexconcurrency.pdf (幻灯片) https://www.youtube.com/watch?v=6AiAR_giC6A&list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7&index=9 (视频)

这样做的一种方法被称为“闩锁抓取”。基本上，每个节点都需要一个RWLock。

在搜索叶节点时，可以在所访问的每个节点上添加一个读(搜索)或写(插入/删除)锁。一旦你发现一个节点是“安全的”(即它在插入时不会分裂，或者在删除时不会与邻居合并/重分布)，你就可以释放它的祖先的锁，因为你知道修改被限制在这个节点下。这样，你在前面获取锁，在后面释放锁，像一只蟹一样行走，这就是为什么它被称为“闩锁蟹”(我在这里误用了"latch“和"lock”)。

这可能很难实现，很好的锁:)