WikiDer > Дерево слияния с лог-структурой

Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (апрель 2013) (Узнайте, как и когда удалить этот шаблон сообщения)

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

Одна простая версия LSM-дерева - двухуровневое LSM-дерево.^[1]Как описано Патрик О'Нил, двухуровневое LSM-дерево состоит из двух древовидный структуры, называемые C₀ и C₁. C₀ меньше по размеру и полностью находится в памяти, тогда как C₁ находится на диске. Новые записи вставляются в резидентную память C₀ компонент. Если вставка вызывает C₀ компонент для превышения определенного порога размера, непрерывный сегмент записей удаляется из C₀ и слился с C₁ на диске. Характеристики производительности 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.

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

Общий

• О'Нил, Патрик Э .; Ченг, Эдвард; Гоулик, Дитер; О'Нил, Элизабет (Июнь 1996 г.). «Лог-структурированное дерево слияния (LSM-дерево)». Acta Informatica. 33 (4): 351–385. CiteSeerX 10.1.1.44.2782. Дои:10.1007 / s002360050048.
• Ли, Инань; Он, Биншэн; Ло, Цюн; Йи, Кэ (2009). «Индексирование дерева на флеш-дисках». 2009 25-я Международная конференция по инженерии данных IEEE. С. 1303–6. CiteSeerX 10.1.1.144.6961. Дои:10.1109 / ICDE.2009.226. ISBN 978-1-4244-3422-0.
• Ло, Чен; Кэри, Майкл Дж. (Июль 2019). «Методы хранения на основе LSM: обзор». Журнал VLDB. arXiv:1812.07527. Дои:10.1007 / s00778-019-00555-у.

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

• Обзор деревьев слияния с логической структурой