In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, a dancing tree is a
tree data structure
In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be conn ...
similar to
B+ tree
A B+ tree is an m-ary tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more children.
A B+ tree can be viewed as a B- ...
s. It was invented by
Hans Reiser
Hans Reiser (born December 19, 1963) is an American computer programmer, entrepreneur, and convicted murderer. In April 2008, Reiser was convicted of the first-degree murder of his wife, Nina Reiser, who disappeared in September 2006. He subseq ...
, for use by the
Reiser4
Reiser4 is a computer file system, successor to the ReiserFS file system, developed from scratch by Namesys and sponsored by DARPA as well as Linspire. Reiser4 was named after its former lead developer Hans Reiser. , the Reiser4 patch set is stil ...
file system. As opposed to
self-balancing binary search tree
In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.Donald ...
s 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 optimization of the tree and only writing to disk when necessary, as writing to disk is thousands of times slower than writing to memory. Also, because this optimization is done less often than with other tree data structures, the optimization can be more extensive.
In some sense, this can be considered to be a self-balancing binary search tree that is optimized for storage on a slow medium, in that the on-disc form will always be balanced but will get no mid-transaction writes; doing so eases the difficulty of adding and removing nodes during a transaction. Instead, these slow rebalancing operations are performed at the same time as the much slower write to the storage medium.
However, a negative side effect of this behavior manifests in cases of unexpected shutdown, incomplete data writes, and other occurrences that may prevent the final balanced transaction from completing. In general, dancing trees pose greater difficulty than conventional trees for data recovery from incomplete transactions, though this can be addressed by more thoroughly accounting for transacted data.
References
External links
''Software Engineering Based Reiser4 Design Principles''
{{compu-storage-stub
Computer file systems
B-tree