Is there a natural parallel analog to red-black trees with similar or even not-terribly-worse properties for updates while being reasonably work-efficient ?
More generally, what's the best we can do for parallel search with updates ?
Is there a natural parallel analog to red-black trees with similar or even not-terribly-worse properties for updates while being reasonably work-efficient ?
More generally, what's the best we can do for parallel search with updates ?
From what I can tell, strategies involve relaxing balance conditions, then performing rebalancing updates in bursts. Here is a paper from Hanke et al., 1997 [PDF], which I think focuses on their technique of aggregating and resolving update operations so that they can be performed concurrently.
I think you may find interesting answer in Okasaki's book Purely Functional Data Structures. In this book, many data structures are shown, such that every updates are not expensive (usually only take a constant or logarithm time).
Let say that "d" is a structure just before the time you must rebalance. In a purely functional data structure you have got persistant data structures, hence you can add $n$ things to "d" and need to rebalance $n$ times. This is why amortized complexity does not work in this setting, and he created other way to obtains good algorithm where every step with updates are non-expensive.