If requests that use a red-black tree tend to come in bursts, then you can probably get speedups by deferring rebalancing for idle periods, even single-threaded. That's pretty darn cool. I would like to see some programming language runtime that watched rb-tree access patterns and decided if this would be a good idea at runtime.
http://www.imada.sdu.dk/~kslarsen/RelBal/
If requests that use a red-black tree tend to come in bursts, then you can probably get speedups by deferring rebalancing for idle periods, even single-threaded. That's pretty darn cool. I would like to see some programming language runtime that watched rb-tree access patterns and decided if this would be a good idea at runtime.