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

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

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

• Software Engineering Based Reiser4 Design Principles
• Description of the Reiser4 internal tree

Дерево (структура данных)
Двоичное дерево поиска Дерево (теория графов) Древовидная структура
Двоичные деревья	Двоичное дерево T-дерево
Самобалансирующиеся двоичные деревья	АА-дерево АВЛ-дерево Красно-чёрное дерево Splay-дерево Дерево со штрафами Декартово дерево Дерево Фибоначчи B-дерево T-дерево
B-деревья	2-3-дерево B⁺-дерево B*-дерево Bx-дерево UB-дерево 2-3-4 дерево (a,b)-дерево Танцующее дерево
Префиксные деревья	Суффиксное дерево Сжатое префиксное дерево Ternary search tree
Двоичное разбиение пространства	k-мерное дерево VP-дерево
Недвоичные деревья	Дерево квадрантов Октодерево Sparse Voxel Octree Экспоненциальное дерево PQ-дерево
Разбиение пространства	R-дерево R-дерево Гильберта R+-дерево R*-дерево X-дерево M-дерево Дерево Фенвика Дерево отрезков
Другие деревья	Куча Дерево хешей Finger tree Metric tree Дерево покрытий BK-tree Doubly-chained tree iDistance Link-cut tree LSM-дерево
Алгоритмы	Поиск в ширину Поиск в глубину DSW-алгоритм Протокол остовного дерева