https://habr.com/ru/articles/984184/
Преимущества
- Амортизированное время вставки/удаления/поиска O(\log N) - сравнимое с BTree от Google;
- Количество аллокаций памяти при операциях вставки так же O(\log N) - меньше давления на сборщик мусора, ниже фрагментация памяти;
- Массивы под капотом: данные лежат рядом, что улучшает кэшируемость процессором и скорость обхода/доступа к данным;
- Позволяет хранить элементы с одинаковыми ключами - не нужно использовать дополнительные структуры для группировки таких элементов;
- Низкий оверхед на хранение служебной информации - экономия памяти по сравнению с другими структурами данных;
- Удобен для вставки батчами;
- Простая сериализация и десериализация;
Компромиссы
-
Время вставки варьируется от O(1) - каждая вторая вставка, до O(N) - один раз на N операций, но амортизированное время O(\log N). Для near-real-time систем это может быть критично. Эффект может быть нивелирован вставкой батчами, или асинхронной вставкой в фоне.
-
При редких паттернах операций массового удаления, возможна деградация производительности поиска до O(N)/4. Эффект может быть предотвращен вызовом метода Compact().
Пора делать новую ФС на новом принципе.
