Дерево слияний с лог-структурой
 | Эта статья включает список общих ссылок , но в ней отсутствуют достаточные соответствующие встроенные цитаты . ( Апрель 2013 г. ) |
| Дерево слияний с лог-структурой | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Тип | Гибрид (два древовидных компонента) | ||||||||||||||||||||
| Изобретенный | 1996 | ||||||||||||||||||||
| Изобретён | Патрик О’Нил , Эдвард Ченг, Дитер Гаулик, Элизабет О’Нил | ||||||||||||||||||||
| |||||||||||||||||||||
В информатике ( дерево слияния с логарифмической структурой также известное как LSM-дерево или LSMT). [1] ) — это структура данных с характеристиками производительности, которые делают ее привлекательной для обеспечения индексированного доступа к файлам с большим объемом вставки, например к данным журнала транзакций . Деревья LSM, как и другие деревья поиска , поддерживают пары ключ-значение. Деревья LSM хранят данные в двух или более отдельных структурах, каждая из которых оптимизирована для соответствующего базового носителя данных; данные синхронизируются между двумя структурами эффективно, в пакетном режиме.
Одной из простых версий LSM-дерева является двухуровневое LSM-дерево. [2] Как описал Патрик О'Нил , двухуровневое LSM-дерево состоит из двух древовидных структур, называемых C 0 и C 1 . C 0 меньше по размеру и полностью находится в памяти, тогда как C 1 находится на диске. Новые записи вставляются в резидентный компонент C 0 памяти . Если вставка приводит к превышению определенного порогового размера компонента C 0 , непрерывный сегмент записей удаляется из C 0 и объединяется с C 1 на диске. Характеристики производительности LSM-деревьев обусловлены тем фактом, что каждый компонент настроен на характеристики своего базового носителя данных и что данные эффективно переносятся между носителями скользящими пакетами с использованием алгоритма, напоминающего сортировку слиянием . Такая настройка предполагает запись данных последовательным образом, а не серией отдельных запросов произвольного доступа. Эта оптимизация сокращает время поиска на жестких дисках (HDD) и задержку на твердотельных накопителях (SSD).
Большинство деревьев LSM, используемых на практике, используют несколько уровней. Уровень 0 хранится в основной памяти и может быть представлен в виде дерева. Данные на диске организованы в отсортированные наборы данных. Каждый прогон содержит данные, отсортированные по ключу индекса. Запуск может быть представлен на диске как один файл или, альтернативно, как набор файлов с непересекающимися диапазонами ключей. Чтобы выполнить запрос по определенному ключу и получить связанное с ним значение, необходимо выполнить поиск в дереве уровня 0, а также при каждом запуске. Версия дерева LSM с пошаговым слиянием [3] — это вариант дерева LSM, который поддерживает несколько уровней с несколькими древовидными структурами на каждом уровне.
Конкретный ключ может появляться при нескольких запусках, и то, что это означает для запроса, зависит от приложения. Некоторым приложениям просто нужна новейшая пара ключ-значение с заданным ключом. Некоторые приложения должны каким-то образом комбинировать значения, чтобы получить правильное совокупное значение для возврата. Например, в Apache Cassandra каждое значение представляет строку в базе данных, и разные версии строки могут иметь разные наборы столбцов. [4]
Чтобы снизить стоимость запросов, система должна избегать ситуаций, когда выполняется слишком много запросов.
Были предложены расширения «уровневого» метода для включения древовидных структур B+ , например bLSM. [5] и Дифференциальный индекс. [6] LSM-дерево изначально было разработано для рабочих нагрузок с интенсивным объемом записи. Поскольку все больше рабочих нагрузок чтения и записи сосуществуют в структуре хранения LSM-дерева, доступ к данным чтения может иметь высокую задержку и низкую пропускную способность из-за частых признаний недействительными кэшированных данных в буферных кэшах операциями уплотнения LSM-дерева. Чтобы снова включить эффективное буферное кэширование для быстрого доступа к данным, предлагается и реализуется лог-структурированное буферизованное объединенное дерево (LSbM-дерево). [7]
Ссылки [ править ]
- ^ Чжан, Вэйтао; Сюй, Иньлун; Ли, Юнкун; Ли, Динлун (декабрь 2016 г.). «Улучшение производительности записи хранилища ключей и значений на основе LSMT» . 22-я Международная конференция IEEE по параллельным и распределенным системам (ICPADS) , 2016 г. стр. 553–560. дои : 10.1109/ICPADS.2016.0079 . ISBN 978-1-5090-4457-3 . S2CID 13611447 .
- ^ О'Нил, Патрик; Ченг, Эдвард; Гавлик, Дитер; О'Нил, Элизабет (1 июня 1996 г.). «Дерево слияния с лог-структурой (LSM-дерево)» (PDF) . Акта Информатика . 33 (4): 351–385. дои : 10.1007/s002360050048 . ISSN 1432-0525 . S2CID 12627452 .
- ^ Джагадиш, Х.В.; Нараян, ППС; Сешадри, С.; Сударшан, С.; Каннеганти, Рама (1997). «Поэтапная организация записи и хранения данных» (PDF) . Материалы конференции ВЛДБ . Фонд ВЛДБ: 16–25.
- ^ «Уровневое сжатие в Apache Cassandra: DataStax» . 13 февраля 2014 г. Архивировано из оригинала 13 февраля 2014 г.
- ^ Сирс, Рассел; Рамакришнан, Рагху (20 мая 2012 г.). «БЛСМ» . Материалы Международной конференции ACM SIGMOD 2012 по управлению данными . СИГМОД '12. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 217–228. дои : 10.1145/2213836.2213862 . ISBN 978-1-4503-1247-9 . S2CID 207194816 .
- ^ Тан, Вэй; Тата, Сандип; Тан, Юже; Фонг, Лиана (2014), Diff-Index: Дифференцированный индекс в распределенных хранилищах данных с логической структурой (PDF) , OpenProceedings.org, doi : 10.5441/002/edbt.2014.76 , получено 22 мая 2022 г.
- ^ Дэджун Тенг; Лэй Го; Рубао Ли; Фэн Чен; Яньфэн Чжан; Сиюань Ма; Сяодун Чжан (2018). «Недорогое дисковое решение, позволяющее LSM-дереву достичь высокой производительности при смешанных рабочих нагрузках чтения/записи» . Транзакции ACM в хранилище. стр. 1–26. дои : 10.1145/3162615 .
- Общий
- О'Нил, Патрик Э.; Ченг, Эдвард; Гавлик, Дитер; О'Нил, Элизабет (июнь 1996 г.). «Дерево слияния с лог-структурой (LSM-дерево)». Акта Информатика . 33 (4): 351–385. CiteSeerX 10.1.1.44.2782 . дои : 10.1007/s002360050048 . S2CID 12627452 .
- Ли, Иньань; Он, Биншэн; Ло, Цюн; Йи, Ке (2009). «Индексация дерева на флэш-дисках». 2009 25-я Международная конференция IEEE по инженерии данных . стр. 1303–6. CiteSeerX 10.1.1.144.6961 . дои : 10.1109/ICDE.2009.226 . ISBN 978-1-4244-3422-0 . S2CID 2343303 .
- Ло, Чен; Кэри, Майкл Дж. (июль 2019 г.). «Методы хранения на основе LSM: обзор». Журнал ВЛДБ . 29 : 393–418. arXiv : 1812.07527 . дои : 10.1007/s00778-019-00555-y . S2CID 56178614 .