Дерево слияния с лог-структурой - Log-structured merge-tree

Дерево слияния с лог-структурой
ТипГибрид (два древовидных компонента)
Изобрел1996
ИзобретенныйПатрик О'Нил, Эдвард Ченг, Дитер Гоулик, Элизабет О'Нил
Сложность времени в нотация большой O
АлгоритмСреднийХудший случай
ВставлятьО (1)О (1)
Find-minНА)НА)
Удалить мин.НА)НА)

В Информатика, то лог-структурированное дерево слияния (или LSM-дерево) - это структура данных с эксплуатационными характеристиками, которые делают его привлекательным для предоставления индексированный доступ к файлам с большим объемом вставки, например данные журнала транзакций. LSM-деревья, как и другие деревья поиска, поддерживайте пары "ключ-значение". Деревья LSM хранят данные в двух или более отдельных структурах, каждая из которых оптимизирована для соответствующего базового носителя данных; данные синхронизируются между двумя структурами эффективно, в пакетном режиме.

Одна простая версия LSM-дерева - двухуровневое LSM-дерево.[1]Как описано Патрик О'Нил, двухуровневое LSM-дерево состоит из двух древовидный структуры, называемые C0 и C1. C0 меньше по размеру и полностью находится в памяти, тогда как C1 находится на диске. Новые записи вставляются в резидентную память C0 компонент. Если вставка вызывает C0 компонент для превышения определенного порога размера, непрерывный сегмент записей удаляется из C0 и слился с C1 на диске. Характеристики производительности LSM-деревьев проистекают из того факта, что каждый компонент настроен на характеристики своего базового носителя данных, и что данные эффективно переносятся между носителями в скользящих пакетах с использованием алгоритма, напоминающего Сортировка слиянием.

Диаграмма, иллюстрирующая сжатие данных в дереве слияния с лог-структурой
Диаграмма, иллюстрирующая сжатие данных в дереве слияния с лог-структурой

Большинство используемых на практике деревьев LSM используют несколько уровней. Уровень 0 хранится в основной памяти и может быть представлен в виде дерева. Данные на диске организованы в отсортированные серии данных. Каждый прогон содержит данные, отсортированные по ключу индекса. Прогон может быть представлен на диске в виде одного файла или, альтернативно, в виде набора файлов с неперекрывающимися диапазонами ключей. Чтобы выполнить запрос по определенному ключу для получения связанного с ним значения, необходимо выполнить поиск в дереве уровня 0 и при каждом запуске.

Конкретный ключ может появляться в нескольких запусках, и то, что это означает для запроса, зависит от приложения. Некоторым приложениям просто нужна новейшая пара "ключ-значение" с заданным ключом. Некоторые приложения должны каким-либо образом комбинировать значения, чтобы получить правильное агрегированное значение для возврата. Например, в Apache Cassandra, каждое значение представляет строку в базе данных, и разные версии строки могут иметь разные наборы столбцов.[2]

Чтобы снизить стоимость запросов, система должна избегать ситуаций, когда выполняется слишком много запусков.

Расширения к «выровненному» методу для включения B + дерево были предложены структуры, например bLSM[3] и Diff-Index.[4]

Деревья LSM используются в таких хранилищах данных, как Большой стол, HBase, LevelDB, SQLite4[5], Тарантоол [6],RocksDB, WiredTiger[7], Apache Cassandra, InfluxDB[8] и ScyllaDB.

Рекомендации

  1. ^ О'Нил 1996, стр. 4
  2. ^ «Выровненное уплотнение в Apache Cassandra: DataStax». 13 февраля 2014 г. Архивировано с оригинал 13 февраля 2014 г.
  3. ^ http://www.eecs.harvard.edu/~margo/cs165/papers/gp-lsm.pdf
  4. ^ http://researcher.ibm.com/researcher/files/us-wtan/DiffIndex-EDBT14-CR.pdf
  5. ^ "SQLite4 с LSM Wiki". SQLite.
  6. ^ «Сервер приложений вместе с менеджером баз данных». Получено 3 апреля, 2018. Дисковый механизм хранения в Tarantool представляет собой сплав идей современных файловых систем, лог-структурированных деревьев слияния и классических B-деревьев.
  7. ^ "GitHub - wiredtiger / wiredtiger: исходное дерево WiredTiger". 4 декабря 2019 г. - через GitHub.
  8. ^ Дикс, Пол (7 октября 2015 г.). "[Новое] Механизм хранения InfluxDB | Дерево слияния с временной структурой".
Общий

внешняя ссылка