Create parallel stream B + Tree
I have implemented B + Tree in Java. Now I want to know what is the best way to allow parallel inserts. My thought is to block node if it's maxFilled -1 (which means the split event is close). Otherwise, I would just lock the array during the change. But it can happen to block a node very close to the root and therefore block too many child nodes. Is there a better way or best practice on how to make the B + Tree stream safe?
source to share
You can implement a non-blocking version of the B-tree.
This approach causes a split node to be progressively marked as frozen (by marking individual records in a node as frozen one by one with atomic compare and swap operations until it is completely frozen) .Readers can continue to navigate the partially / completely frozen node along the way to other parts of the tree, providing high concurrency for readers. Replaced completely frozen node and later garbage collected, which works well with Java, which has garbage collection.
The details are well documented in the doc and there is no point in copying them all here. This graph (taken from the article) shows the advantage:
source to share