Dancing tree

This article relies largely or entirely on a single source. Please help improve this article by introducing citations to additional sources.
Find sources: "Dancing tree" – news · newspapers · books · scholar · JSTOR (March 2021)

|

"Dancing trees" redirects here. For the 2009 Canadian movie, see Dancing Trees.

In computer science, a dancing tree is a tree data structure similar to B+ trees. It was invented by Hans Reiser, for use by the 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).[1]

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

1. ↑ Hans Reiser. "Reiser4 release notes - Dancing Tree". http://www.namesys.com/v4/v4.html#dancing_tree.

## External links

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

* v
* t
* e

Tree data structures

Search trees
(dynamic sets/associative arrays)|

* 2–3
* 2–3–4
* AA
* (a,b)
* AVL
* B
* B+
* B*
* Bx
* (Optimal) Binary search
* Dancing
* HTree
* Interval
* Order statistic
* (Left-leaning) Red-black
* Scapegoat
* Splay
* T
* Treap
* UB
* Weight-balanced

Heaps|

* Binary
* Binomial
* Brodal
* Fibonacci
* Leftist
* Pairing
* Skew
* van Emde Boas
* Weak

Tries|

* Ctrie
* C-trie (compressed ADT)
* Hash
* Radix
* Suffix
* Ternary search
* X-fast
* Y-fast

Spatial data partitioning trees|

* Ball
* BK
* BSP
* Cartesian
* Hilbert R
* k-d (implicit k-d)
* M
* Metric
* MVP
* Octree
* Priority R
* Quad
* R
* R+
* R*
* Segment
* VP
* X

Other trees|

* Cover
* Exponential
* Fenwick
* Finger
* Fractal tree index
* Fusion
* Hash calendar
* iDistance
* K-ary
* Left-child right-sibling
* Link/cut
* Log-structured merge
* Merkle
* PQ
* Range
* SPQR
* Top

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Dancing tree. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Dancing_tree&oldid=3988596"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template