>>4
概算なんだ。

>>5
Bツリーであることが重要であって、それを平衡させるアルゴリズムは、
ぶっちゃけなんでもいいと思うよ。
あとはソーティングしたいデータの特性にあわせてチューニングした結果、
一番良かったのが赤白だったのかもね。
別に赤白である必要はなくて、もっとチューニングすることもできるだろうけど、
いかんせんプロセスがどうメモリを使うかなんて、前もって定義できないからね。