árbol de navidad

En las estructuras de datos de árbol de la informática , un árbol X (de eXtended node tree ^[1] ) es una estructura de árbol de índice basada en el árbol R que se utiliza para almacenar datos en muchas dimensiones. Apareció en 1996, ^[2] y se diferencia de los árboles R (1984), los árboles R+ (1987) y los árboles R* (1990) porque enfatiza la prevención de la superposición en los cuadros delimitadores, que se convierte cada vez más en un problema en grandes dimensiones. En los casos en los que los nodos no se pueden dividir sin evitar la superposición, la división del nodo se aplazará, lo que dará como resultado supernodos . En casos extremos, el árbol se linealizará, lo que protege contra los comportamientos del peor caso observados en algunas otras estructuras de datos.

El árbol X consta de tres tipos diferentes de nodos: nodos de datos, nodos de directorio normales y supernodos. Los nodos de datos del árbol X contienen rectángulos delimitadores mínimos (MBR) rectilíneos junto con punteros a los objetos de datos reales, y los nodos de directorio contienen MBR junto con punteros a sub-MBR. Los supernodos son nodos de directorio grandes de tamaño variable (un múltiplo del tamaño de bloque habitual). El objetivo básico de los supernodos es evitar divisiones en el directorio que darían como resultado una estructura de directorio ineficiente.