Background: I'm working on a data structure benchmark tool to benchmark insert and search time and I am trying to improve my own implementation of a BST to support parallelism.
I have implemented a Binary Search Tree, it is a very basic (naive) tree structure:
class Node: Node? right; Node? left; long value;
Inserting into to the tree is the usual algorithm: I compare key to value and descend left/right depending on the comparison, return if that key is exact match, or insert into an empty node.
My question concerns parallelism: Is there a way to efficiently parallelize or make concurrent search and/or insertion? I would like to have multiple threads independently inserting items.
A global mutex when needing to insert could work but given my heavy write load it ends up less efficient than a single thread, because every time I search I also then insert.
It feels like there ought to be a way to coordinate mutex locking at the sub-tree level to only lock part of the tree but perhaps there's also a lock-free way to allow concurrent search and insert for a tree?
If it helps to relax the problem, I am actually not too concerned about a race condition where if one thread begins searching for key K while another thread is also searching for key K that they both end up inserting as long as it doesn't break the tree for future inserts. ( My reasoning for this relaxed constraint is that if the probability of collision is high enough that such a data race would occur then a new overall collision will be found again in due time. ).
I am not re-balancing the tree at any point, nor is removing items a requirement. I also appreciate there are much more efficient ways to store this, especially with regards to cache etc, but I'm not yet looking for the most efficient solution of storage, just whether parallel access of this structure is possible, mostly to test the parallel bench-marking code itself.