20051216現在私が知り得る最速の二分木

http://d.hatena.ne.jp/studiokingyo/20041213#p1
にて、

私の知る限り、パフォーマンスが良いと言われているのが？
Red Black TreeとAVL Treeの二つだ。
(実際速度的にどうなのかは良く分からない。ただ、聞いただけ。B-Treeとかはどうなんでしょう？)

と、無責任な事を書いていたが、とある書籍だか、記事だかにはＢ木が平均的にパフォーマンスが良いのではないかとの事が・・・。
しかし、他にもＢ木を元にした別のアルゴリズムもありそうですし、Ｎ分木とかもパフォーマンスを計測したこと無いので良く分からないですし・・・。
実際、自分でプログラムして計測していないのでなんとも言えないのですが・・・*1
http://memorandumhcr.g.hatena.ne.jp/hcr/20041221
未確認な情報が引用されちゃいましたね＾＾；（/ω＼）ハズカシーィ　スミマセンデス　m(_ _)m

*1:いずれ行いたいのですが・・・