Танцующее дерево

Танцующее дерево

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

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

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

Примечания

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

Ссылки



Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Полезное


Смотреть что такое "Танцующее дерево" в других словарях:

  • Дерево отрезков — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Содержание 1 Дерево отрезков в памяти …   Википедия

  • Дерево Фенвика — (двоичное индексированное дерево, англ. Fenwick tree, binary indexed tree, BIT) структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Впервые описано Питером Фенвиком в 1994 году …   Википедия

  • Дерево Фибоначчи — АВЛ дерево с наименьшим числом вершин при заданной высоте (глубине). Если для какой либо из вершин высота поддерева, для которого эта вершина является корнем, равна , то правое и левое поддерево этой вершины имеют высоты равные соответственно и …   Википедия

  • Дерево (структура данных) — У этого термина существуют и другие значения, см. Дерево (значения). Простой пример неупорядоченного дерева Дерево  одна из наиболее широко распространённых структу …   Википедия

  • Дерево (теория графов) — У этого термина существуют и другие значения, см. Дерево (значения). Дерево  это связный ациклический граф.[1] Связность означает наличие путей между любой парой вершин, ацикличность  отсутствие циклов и то, что между парами вершин… …   Википедия

  • Дерево квадрантов — Разбитая с помощью дерева квадрантов плоскость Дерево квадрантов (также квадродерево, 4 дерево, англ. quadtree) дере …   Википедия

  • B+ дерево — Пример B+ дерева, связывающего ключи 1 7 с данными d1 d7. Связи (выделены красным) позволяют быстро обходить дерево в порядке возрастания ключей. B+ дерево  структура данных, представляет собой сбалансированное дерево поиска. Яв …   Википедия

  • Двоичное дерево поиска — Тип Дерево Временная сложность в О символике В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(h) O(n) Вставка O(h) O(n) Удаление O(h) O(n) где h высота дерева …   Википедия

  • Красно-чёрное дерево — Тип дерево поиска Изобретено в 1972 году Изобретено Рудольф Байер Временная сложность в О символике В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(log n) O(log n) Вставка O(log n) O(log n) Удаление O(log n) O(log n) Красно чёрное… …   Википедия

  • Двоичное дерево — древовидная структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. Для практических целей обычно используют два подвида… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»