Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
X-tree
open-in-new
<p>In computer science <a href="/facts/Tree_(data_structure)/RcXz9noF">tree data structures</a>, an X-tree (for <i>eXtended node tree</i>) is an index tree structure based on the <a href="/facts/R-tree/9X5AQWln">R-tree</a> used for storing data in many dimensions. It appeared in 1996, and differs from <a href="/facts/R-tree/9X5AQWln">R-trees</a> (1984), <a href="/facts/R%252B-tree/ENl7HBuW">R+-trees</a> (1987) and <a href="/facts/R*-tree/zbEjvt5q">R*-trees</a> (1990) because it emphasizes prevention of overlap in the bounding boxes, which increasingly becomes a problem in high dimensions. In cases where nodes cannot be split without preventing overlap, the node split will be deferred, resulting in super-nodes. In extreme cases, the tree will linearize, which defends against worst-case behaviors observed in some other data structures. </p>