Операция выполнена!
Закрыть
info@vsetut.pro
Стать автором
Вернуться

Black-White Array: новая структура данных с O(log N) аллокаций

14.01.2026 06:27:58 | Хабр
Хабы: Алгоритмы, Программирование, Go, Серверная оптимизация

Black-White Array (BWA) — это упорядоченная структура данных с амортизированным временем операций вставки/поиска/удаления O(log N) и O(log N) используемых участков памяти. Преимущества:

• Амортизированное время вставки/удаления/поиска сравнимое с реализацией BTree от Google;
• Низкое количество аллокаций памяти при операциях вставки O(log N) - меньше давления на сборщик мусора, ниже фрагментация памяти;
• Массивы под капотом: данные лежат рядом, что улучшает кэшируемость процессором и скорость обхода/доступа к данным;
• Позволяет хранить элементы с одинаковыми ключами - не нужно использовать дополнительные структуры для группировки таких элементов;
• Низкий оверхед на хранение служебной информации - экономия памяти по сравнению с другими структурами данных;
• Удобен для вставки батчами;
• Простая сериализация и десериализация;

Подробности
Подробнее
Читайте также
НОВОСТИ

ВСЕ НОВОСТИ
ПИШИТЕ

Техническая поддержка проекта ВсеТут

info@vsetut.pro

Copyright © 2026 - vsetut.pro