Dancing tree

In computer science, a dancing tree is a tree data structure that is used by Namesys Reiser4 file system. As opposed to self-balancing binary search trees that attempt to keep their nodes balanced at all times, dancing trees only balance their nodes when flushing data to a disk (either because of memory constraints or because a transaction has completed).

The idea behind this is to speed up file system operations by delaying optimisation of the tree and only writing to disk (a slower operation than writing to memory) when necessary. Also because this optimisation is done less often than with other tree data structures, the optimisation can be more extensive.

External links

• Software Engineering Based Reiser4 Design Principles