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
