Not sure if anyone will find this interesting, but I'm posting it here anyway :)<br><br>I believe I finally managed to create the structure I wanted to. The main problem that I was having is that I was still thinking in C (or sequential languages), so what I wanted to do was build a single binary search tree (bst) that scales well. What I realized though, is that rather than doing that, I should create N bsts where N is proportional to the number of processors available in the system.<br>


<br>So what I'm doing now is spawn a number of threads (servers), each thread is responsible for a bst that covers a range of keys, and whenever an operation is performed, the client sends it to the particular server that's responsible for the tree in that range. If this doesn't make sense, then maybe my code will make it clearer:-<br>

<br><a href="http://www.cs.auckland.ac.nz/%7Efuad/dbst.erl" target="_blank">http://www.cs.auckland.ac.nz/~fuad/dbst.erl</a> (code needs better error handling, general tidying up)<br><br><br>The main problem with this implementation though is that if the distribution of the keys isn't uniform within the expected range, it won't perform well. But I guess that is a problem with non-balanced bsts in general.<br>

<br>That said, this solution turned out to be simpler than other solutions I've attempted, performs better in the single-threaded case, and scales pretty well.<br><br>Here's a link to a graph that shows how well this scales on an 8 core machine:-<br>

<a href="http://www.cs.auckland.ac.nz/%7Efuad/bst-scale2.png" target="_blank">http://www.cs.auckland.ac.nz/~fuad/bst-scale2.png</a><br><br>Compare with my previous attempt:-<br><a href="http://www.cs.auckland.ac.nz/%7Efuad/bst-scale.png" target="_blank">http://www.cs.auckland.ac.nz/~fuad/bst-scale.png</a><br>

<br>Can't really ask for better than that.<br><br>What I need to do now is figure out a way to balance the load somehow when it's not uniform.<br><br>Thanks to all of you who've given me feedback. This is definitely an interesting learning experience, a different way of thinking.<br>

<br clear="all">Cheers,<br>/Fuad