In computer science tree data structures, an X-tree (for eXtended node tree[1]) is an index tree structure based on the R-tree used for storing data in many dimensions.
It appeared in 1996,[2] and differs from R-trees (1984), R+-trees (1987) and R*-trees (1990) because it emphasizes prevention of overlap in the bounding boxes, which increasingly becomes a problem in high dimensions.
In extreme cases, the tree will linearize, which defends against worst-case behaviors observed in some other data structures.
The data nodes of the X-tree contain rectilinear minimum bounding rectangles (MBRs) together with pointers to the actual data objects, and the directory nodes contain MBRs together with pointers to sub-MBRs.
This algorithms or data structures-related article is a stub.