使 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。

当您搜索叶节点时，您可以在您访问的每个节点上添加读（搜索）或写（插入/删除）锁。一旦您发现一个节点是“安全的”（即它不会拆分插入，或者在删除时不会与邻居合并/重新分配），您就可以释放其祖先的锁，因为您知道修改仅限于这个节点。这样，你就在前面获取锁，在后面释放锁，像螃蟹一样行走，这就是为什么它被称为“闩锁螃蟹”（我在这里误用了“闩锁”和“锁”）

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