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

Если хеш автоматически не меняет свой размер, то с ростом количества записей скорость доступа будет уменьшаться как O(количества ключей / количество ячеек в хеш-таблице), что по сути есть O(n).

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

Как устроена таблица (в частности, есть ли в ней автоматическое изменение размера) в BDB, не известно.