For most applications where you want these, I've found that skip lists give you most of the performance advantages you want at a far lower complexity to implement and debug. Yeah, it's a probabilistic algorithm, but if you know the distribution well enough to tune correctly (and I usually do for things like time series and high scores) the performance is much better than LLRBT while also being rather cache-friendly, which is overlooked in a lot of implementations of RBTs.