ＳＴＬのmapの中味って、二分木ですか？
登録時にバランス化されますか？
登録コストはlog nですか？

mapエントリ削除、編集のコストはどうですか？
このときも逐一再バランスされますか？