Árbol X - X-tree
En informática, un árbol X (para árbol de nodos extendido ) es una estructura de árbol de índice basada en el árbol R utilizado para almacenar datos en muchas dimensiones. Apareció en 1996 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 las dimensiones altas. En los casos en que los nodos no se pueden dividir sin evitar la superposición, la división de nodos se aplazará, lo que dará como resultado supernodos . En casos extremos, el árbol se linealizará, lo que defiende contra los peores comportamientos observados en algunas otras estructuras de datos.
Estructura
El árbol X consta de tres tipos diferentes de nodos: nodos de datos, nodos de directorio normal y supernodos. Los nodos de datos del árbol X contienen rectilíneos rectilíneos mínimos delimitadores (MBR) 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 grandes nodos de directorio 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 resultarían en una estructura de directorio ineficiente.
Referencias
- ↑ Selçuk Candan, K .; Luisa Sapino, Maria (31 de mayo de 2010). Cambridge University Press (ed.). Gestión de datos para recuperación multimedia . ISBN 9781139489584.
- ^ Berchtold, Stefan; Keim, Daniel A .; Kriegel, Hans-Peter (1996). "El árbol X: una estructura de índice para datos de alta dimensión" . Actas de la 22ª Conferencia VLDB . Mumbai, India: 28–39.
 |
Este artículo relacionado con algoritmos o estructuras de datos es un código auxiliar . Puedes ayudar a Wikipedia expandiéndolo . |