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

V>Тогда на верхнем уровне в любом случае виртуальность.
Нет конечно, не в любом. Все эти типы — struct, так что в коде нет ни одного виртуального вызова.

V>Что странно.


V>Попробую найти время, посмотреть на балансировку.
Да она там совершенно обычная, как в учебнике.
V>Точная балансировка тем дороже, чем больше арность, потому что приходится создавать более дорогие копии при каждом изменении дерева.
Да, одиночные вставки могут подтормаживать; зато на AddRange можно немножко наиграть за счёт повторного использования.

V>Ну вот как раз ради случая хеш-таблицы в хеш-таблицах всё и затевалось.
V>Capacity каждой хеш-таблицы относительно невелик (23, 19, 17, 13, 11), пересоздавать при изменении достаточно одну таблицу, а не всю цепочку их до корневого узла, как оно есть в иммутабельных деревьях при балансировке.
Да, мысль хорошая. У меня задачи делать IDictionary<,> не стояло, а для IList<> B-дерево выглядит самой эффективной реализацией.

V>Самый простой вариант — складывать конфликты в упорядоченный список (массив конфликтующих значений).
Да, именно этот вариант первым приведён у Кнута, емнип.