Re: [infinispan-dev] range query in Infinispan !!

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. 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. [1] http://www.sciencedirect.com/science/article/pii/S0743731508000518 On 14 May 2012, at 18:06, Tristan Tarrant wrote: -- Manik Surtani manik(a)jboss.org twitter.com/maniksurtani Lead, Infinispan http://www.infinispan.org