<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Sanne is right, it will be non-trivial. Attempting to sort the data set in memory for each such range operation will not scale. Actually storing it in a sorted form (a thread safe linked hash map or something) is tricky too - I've looked at several algorithms (including Sundell/Tsigas' lock-free doubly linked lists [1]) and even the best lock-free structures end up with contention on the heads/tails when performing a CAS. Arbitrary insertions get very expensive too.<div><br></div><div>Another approach would be to accept O(log n) for reads as well as writes and use a B*tree in memory, but that would require a lot of re-architecting.</div><div><br></div><div>[1] <a href="http://www.sciencedirect.com/science/article/pii/S0743731508000518">http://www.sciencedirect.com/science/article/pii/S0743731508000518</a><br><div><br><div><div>On 14 May 2012, at 18:06, Tristan Tarrant wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div>On 05/14/2012 07:01 PM, Sanne Grinovero wrote:<br><blockquote type="cite">but what's this concept of "key order" you're mentioning ?? The <br></blockquote><blockquote type="cite">complexity of such a patch would be close to "rewrite Infinispan" !? <br></blockquote><blockquote type="cite">No actually that would be simpler since we likely learned a bit from <br></blockquote><blockquote type="cite">the first time :D I had drafted some<br></blockquote>Are you sure it would be that complex ? Basically it's just comparable <br>keys, a linked list and a grouper class. I don't want to oversimplify <br>though, and there might be things I don't understand.<br><br>Tristan<br><br>_______________________________________________<br>infinispan-dev mailing list<br><a href="mailto:infinispan-dev@lists.jboss.org">infinispan-dev@lists.jboss.org</a><br>https://lists.jboss.org/mailman/listinfo/infinispan-dev<br></div></blockquote></div><br><div apple-content-edited="true">
<div><div>--</div><div>Manik Surtani</div><div><a href="mailto:manik@jboss.org">manik@jboss.org</a></div><div><a href="http://twitter.com/maniksurtani">twitter.com/maniksurtani</a></div><div><br></div><div>Lead, Infinispan</div><div><a href="http://www.infinispan.org">http://www.infinispan.org</a></div><div><br></div></div><br class="Apple-interchange-newline">
</div>
<br></div></div></body></html>