Кратко — вывод в конце, дальше — сравнение по ключевым свойствам. Все числовые выражения в KaTeX.
Контекст: «миллионы временных отметок», операции: insert, range query (по времени), delete-old (удалить всё старее порога). Важный дополнительный фактор: идут ли метки строго возрастающе (append-only) или произвольно вставляются во время? От этого многое зависит.
1) B-дерево / B+-дерево
- Вставка: $O(\log n)$ (несколько дисковых/страничных операций).
- Range query: очень эффективно — последовательный обход листьев, стоимость $O(\log n+k)$ для возвращения $k$ элементов. Отличная локальность и малое число I/O.
- Delete-old: если данные лежат отсортированы по времени (включая append-only), можно эффективно освобождать целые листовые страницы; в общем — удаление $k$ элементов требует $O(k\log n)$ в Naive-реализации, но реализационно можно оптимизировать до быстрого удаления страниц/сегментов.
- Плюсы: хорош для хранения на диске/SSD, быстрые последовательные сканы, стабильные гарантии.
- Минусы: конкуренция при массовых вставках (особенно случайных) может приводить к частым split/merge, сложнее горизонтальное масштабирование.
2) Балансированное двоичное дерево поиска (RB/AVL)
- Вставка/удаление: $O(\log n)$ (в памяти).
- Range query: $O(\log n+k)$ с обходом; но плохая кеш-локальность из-за указателей, высокий накладной памятью на миллионы узлов.
- Delete-old: удалять $k$ старых узлов — $O(k\log n)$ либо последовательный обход с удалениями; нет простого способа «сбросить» большой префикс.
- Плюсы: детерминированные гарантии, простая реализация в памяти.
- Минусы: память и указатели при больших объёмах, слабая производительность на внешней памяти и при массовых вставках/удалениях.
3) Skip list
- Вставка/удаление: ожидаемо $O(\log n)$.
- Range query: очень удобно — последовательное сканирование по уровням, $O(\log n+k)$. Хорошая реализация для in-memory Sorted Set (пример: Redis).
- Delete-old: можно идти от начала и «сдвинуть» голову/удалить префикс; удаление большого количества старых элементов может быть выполнено линейно по числу удаляемых $k$ и часто проще, чем в BST.
- Плюсы: простота реализации, хорошая настраиваемая память/производительность в памяти, конкурентные реализации возможны.
- Минусы: случайная структура (вероятностные гарантии), всё в памяти — масштаб на диск хуже.
4) Time-indexed LSM-tree (LSM с партиционированием по времени)
- Вставка: очень высокая пропускная способность, запись — append в memtable и последующая запись SSTable; амортизированно очень дешево (практически $O(1)$ на запись с точки зрения I/O).
- Range query: для сканирования одного времени-регионa нужно объединять несколько SSTable + memtable; стоимость примерно $O(\log n+k)$ с накладными на чтение/мердж, но при правильной организации (time-partitioned SSTables) диапазоны часто лежат в небольшом числе файлов => очень быстрые сканы. Bloom-фильтры и партиционирование улучшают чтение.
- Delete-old: самая сильная сторона — если SSTable/файлы организованы по времени, старые файлы можно просто удалить (drop) или при компактации выбрасывать устаревшие записи (tombstones) и компактировать; удаление большого временного префикса — $O(1)$ на уровне файлов/партиций или амортизированно дешево.
- Плюсы: оптимизирован для высокого throughput вставок, простое и быстрое удаление старых данных, хорошо масштабируется горизонтально, хорош на диске/SSD/HDD.
- Минусы: чтения могут быть дороже в худшем случае (особенно точечные) и нужно управлять компактацией; реализация сложнее.
Рекомендации (кратко и обоснование)
- Если данные преимущественно на диске/SSD, требуется массовая запись (миллионы событий в секунду/минуту) и регулярная массовая очистка старых данных — лучше выбрать time-indexed LSM-tree. Обоснование: максимально высокая пропускная способность вставок, простое/быстрое удаление старых данных (drop файлов или эффективная компактация по времени), хорошая масштабируемость.
- Если основной сценарий — частые range query (особенно большие сканы), dataset хранится на диске и требуется малые задержки для сканов — B+-дерево тоже сильный кандидат: отличная локальность для последовательных сканов и детерминированные задержки. Но удаление большого префикса старых данных потребует реализации удаления страниц/реорганизации или будет дороже, чем у LSM.
- Если всё помещается в оперативную память и важна простота/низкая латентность для точечных операций и диапазонов — skip list (или RB-tree) подходит; skip list проще и в реальности быстрее для диапазонных сканов, но удаление большого числа старых элементов всё равно линейно по $k$.
- Если timestamps строго возрастают (append-only): LSM-tree или B+-tree с оптимизацией вставок в конец — оба хороши, но LSM лучше при очень высоких write-throughput и когда хочется простого TTL/expiry (drop SSTables). B+-tree хорош при критичных случайных чтениях с минимальными merge-накладными.
Короткий итог (если нужно одно решение)
- Для «миллионов отметок», высокой скорости вставок и частой очистки старых данных: рекомендую time-indexed LSM-tree (лучшее соотношение throughput, простоты удаления старых данных и масштабируемости).
- Если приоритет — низкая латентность range-scan и детерминированные I/O — выбирайте B+-дерево.
Если нужно, могу дать более детальную схему реализации для выбранного варианта (структура файлов/партиций, параметры компактации, пример API).