WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

В информатике танцующее дерево (англ. Dancing tree) — древовидная структура хранения данных, которая похожа на B+trees. Она придумана Хансом Рейзером для использования в файловой системе Reiser4. По сравнению со сбалансированными бинарными деревьями, которые пытаются сохранить свои узлы сбалансированными постоянно, танцующие деревья сохраняют баланс между узлами только при записи данных на диск: либо из-за ограничений памяти, или потому, что транзакция завершена.[1]

Идея заключается в том, чтобы ускорить операции с файловой системой, отказавшись от оптимизации дерева, а писать на диск только когда это необходимо, так как запись на диск в тысячи раз медленнее, чем запись в память. Кроме того, поскольку такая оптимизация проводится реже, чем у других древовидных структур данных, выигрыш может быть ещё больше.

Тем не менее, побочный эффект такого поведения появляется в случае неожиданной остановки системы, записи неполных данных, и других явлений, которые могут помешать завершению окончательной (сбалансированной) транзакции. В целом, танцующие деревья создают бо́льшие трудности для восстановления данных из незавершённых операций, чем нормальные деревья, хотя эту проблему можно решить путём добавления дополнительных журналов транзакций или разработке алгоритма для поиска ранее не существовавших данных на диске с последующим выполнением оптимизаций и возобновлением операций.

Примечания

  1. Hans Reiser. Reiser4 release notes - Dancing Tree. Archive.org, as Namesys.com is no longer accessible. Проверено 22 июля 2009. Архивировано 24 октября 2007 года.

Ссылки


Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии