>>только надеятся, что для случайного ключа в среднем скорость будет вести
>>себя как в идеальном случае,
>
>Все это конечно замечательно, но для дерева то время поиска (включая и
>среднее) будет логарифмически расти с ростом числа записей в бд.А у
>хеша это время в среднем не растет.На бд с большим числом
>записей хэш должен выиграть.Как минимум при вытаскивании пар ключ-значение.При том то
>что на конкретном ключе может быть и несколько медленнее чем в
>среднем обычно мало кого волнует.

Ну, дык я и не спорю. Хэш рано или поздно на больших объемах победит деревья, но пока до этого дойдет - замотаешься пыль глотать.

Хотя практика сравнения среднего времени в смысле статистики с гарантированным worst case - кажется мне несколько порочной ...