On 11/25/11 8:51 AM, Selcuk AYA wrote:
> I looked at the code some more and think that using read-write locks
> might not be a good idea. There are cases where a cursor is held for a
> partition and the same partition is changed. This makes it hard.
>
> My suggestion is to use a ConcurrentSkipListMap implementation of
> java( http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentSkipListMap.html
> ) rather than our own implementation of avl as the backing sorted map
> for our avl partition. We can build cursors over this map using the
> iterator provided by this map ( I did something similar to provide a
> cursor for the index changes of a txn). This iterator is weakly
> consistent, that is, it might show future changes but will show a view
> of the map at least as of the time of its creation. This works for us.
> Even if cursor shows future changes, our txn layer above should  take
> care of this and provide a transactionally consistent view.
>
> The cost of the common operations would be amortized o(logn)  with
> this map. So, this is similar to AVL tree cost. Note that, we would
> need to use ConcurrentSkipListMaps to store dup values.
>
> Let me know if you think this sounds OK with you.
Sounds good to me.

What is important is that we guarantee a o(logn) for search in this 
tree, and of course consistency, everything else is not really important 
(ie insertion can be slow).


-- 
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com