Логарифмически структурированное дерево слияния
-
Описание LSM-деревьев
- LSM-деревья (лог-структурированные деревья слияния) оптимизированы для индексированного доступа к файлам с большим объемом вставки.
- Поддерживают пары ключ-значение и хранят данные в двух или более структурах.
- Данные синхронизируются между структурами эффективно, пакетно.
-
Двухуровневое LSM-дерево
- Состоит из двух древовидных структур: C0 (в памяти) и C1 (на диске).
- Новые записи вставляются в C0, при превышении порога записи удаляются из C0 и объединяются с C1.
- Оптимизация сокращает время поиска на HDD и задержку на SSD.
-
Многоуровневые LSM-деревья
- Уровень 0 хранится в памяти и может быть представлен в виде дерева.
- Данные на диске организованы в виде отсортированных серий.
- Каждый запуск содержит данные, отсортированные по индексному ключу.
- Запрос по ключу требует поиска в дереве уровня 0 и при каждом запуске.
-
Ступенчатое объединение LSM-деревьев
- Поддерживает несколько уровней с несколькими древовидными структурами на каждом уровне.
- Определенный ключ может появляться при нескольких запусках, что зависит от приложения.
- Некоторые приложения требуют самую новую пару ключ-значение, другие комбинируют значения для возврата совокупного значения.
-
Расширения LSM-деревьев
- Предложены расширения для включения древовидных структур B+, такие как bLSM и Diff-Index.
- LSM-tree изначально разрабатывался для рабочих нагрузок с интенсивной записью.
- Доступ к данным для чтения может сопровождаться высокой задержкой и низкой пропускной способностью из-за частых аннулирований кэшированных данных.
-
LSbM-деревья
- Предложено и реализовано логарифмически структурированное дерево с буферизованным объединением (LSbM-tree) для эффективного буферного кэширования.