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 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.