Здравствуйте, vdimas, Вы писали:

V>И проблема не только в логарифмичности — даже если элемент найден в первом же узле дерева, то даже такой случай слишком проигрывает обычному массиву.
В листе B+ дерева внутри лежит обычный массив. Для размеров до 16 элементов доступ не слишком отличается от List<T>. Если отказаться от fancy stuff типа операторов, то можно вообще наружу выставлять прямо сам узел дерева, и убрать лишний уровень косвенности. Для больших размеров начинает сказываться copy on write.

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