Make a B+ Tree concurrent thread safe

Question

I have implemented a B+ Tree in Java. Now I want to know what is the best way to allow concurrent inserts. My thought is to lock a node if it is maxFilled -1 (which means a split event is close). Otherwise I would just lock the array during a shift. But this way it can happen to lock a node very close to the root and therefore lock far too much child nodes too. Is there a better way or a best practice of how to make a B+ Tree thread safe?

Answer 1

You could implement a lock-free version of a B-tree.

This approach causes a node that needs to be split to be gradually marked as frozen (by marking individual entries in the node as frozen one by one with atomic compare-and-swap operations until it is entirely frozen). Readers can continue to navigate across a partially/fully frozen node on their way to other parts of the tree, ensuring high concurrency for readers. A fully frozen node is replaced and later garbage collected, which works well with Java which has garbage collection.

Details are well documented in the paper and there is no point in copying them all here. This graph (taken from the paper) shows the benefit: