directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Emmanuel L├ęcharny <>
Subject Re: AVL cursor problem?
Date Fri, 25 Nov 2011 08:09:24 GMT
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(
> ) 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).

Emmanuel L├ęcharny

View raw message