I like relaxed balanced red-black trees. In those, you're allowed to violate the balancing conditions; you can go back and fix the violations later. This is useful if you want to use them concurrently. The balancing transformations tend to cause lots of contention between threads, so deferring that rebalancing for a later, clean-up thread can really help with scalability.
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.
Comments
I like relaxed balanced red-black trees. In those, you're allowed to violate the balancing conditions; you can go back and fix the violations later. This is useful if you want to use them concurrently. The balancing transformations tend to cause lots of contention between threads, so deferring that rebalancing for a later, clean-up thread can really help with scalability.
I only learned about this fairly recently:
http://www.itl.nist.gov/div897/sqg/dads/
And I feel pretty stupid for not having realized earlier that something like that almost has to exist.
Heh; it hit me that way, too. It seems obvious in retrospect. I found that this page has a nice mini-introduction:
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.