árbol T

Este artículo se basa en gran parte o en su totalidad en una sola fuente . Se puede encontrar información relevante en la página de discusión . Por favor, ayude a mejorar este artículo introduciendo citas de fuentes adicionales . Buscar fuentes:  "T-tree" – noticias  · periódicos  · libros  · académico  · JSTOR ( junio de 2013 )

En informática, un árbol T es un tipo de estructura de datos de árbol binario que utilizan las bases de datos de memoria principal , como Datablitz , eXtremeDB , MySQL Cluster , Oracle TimesTen y MobileLite.

Un árbol T es una estructura de datos de árbol de índice equilibrado optimizada para casos en los que tanto el índice como los datos reales se guardan completamente en la memoria, al igual que un árbol B es una estructura de índice optimizada para el almacenamiento en dispositivos de almacenamiento secundario orientados a bloques, como los discos duros. Los árboles T buscan obtener los beneficios de rendimiento de las estructuras de árbol en memoria, como los árboles AVL, al tiempo que evitan la sobrecarga de gran espacio de almacenamiento que es común en ellos.

Los árboles T no conservan copias de los campos de datos indexados dentro de los nodos del árbol de índices. En cambio, aprovechan el hecho de que los datos reales siempre están en la memoria principal junto con el índice, de modo que solo contienen punteros a los campos de datos reales.

La "T" en T-tree se refiere a la forma de las estructuras de datos de los nodos en el artículo original que describió por primera vez este tipo de índice. ^[1]

Un nodo de árbol T generalmente consta de punteros al nodo padre, el nodo hijo izquierdo y derecho, una matriz ordenada de punteros de datos y algunos datos de control adicionales. Los nodos con dos subárboles se denominan nodos internos , los nodos sin subárboles se denominan nodos hoja y los nodos con un solo subárbol se denominan nodos de media hoja . Un nodo se denomina nodo delimitador de un valor si el valor está entre el valor mínimo y máximo actuales del nodo, ambos incluidos.

Para cada nodo interno, existen nodos hoja o media hoja que contienen el predecesor de su valor de datos más pequeño (llamado límite inferior máximo ) y uno que contiene el sucesor de su valor de datos más grande (llamado límite superior mínimo ). Los nodos hoja y media hoja pueden contener cualquier número de elementos de datos desde uno hasta el tamaño máximo de la matriz de datos. Los nodos internos mantienen su ocupación entre números mínimos y máximos predefinidos de elementos.

• La búsqueda comienza en el nodo raíz
• Si el nodo actual es el nodo delimitador del valor de búsqueda, se busca en su matriz de datos. La búsqueda falla si el valor no se encuentra en la matriz de datos.
• Si el valor de búsqueda es menor que el valor mínimo del nodo actual, continúe la búsqueda en su subárbol izquierdo. La búsqueda falla si no hay subárbol izquierdo.
• Si el valor de búsqueda es mayor que el valor máximo del nodo actual, continúe la búsqueda en su subárbol derecho. La búsqueda falla si no hay un subárbol derecho.

• Busque un nodo delimitador para el nuevo valor. Si existe dicho nodo, haga lo siguiente:
  • Verifique si todavía hay espacio en su matriz de datos, si es así, inserte el nuevo valor y finalice
  • Si no hay espacio disponible, elimine el valor mínimo de la matriz de datos del nodo e inserte el nuevo valor. Ahora proceda al nodo que contiene el límite inferior más grande para el nodo en el que se insertó el nuevo valor. Si el valor mínimo eliminado todavía cabe allí, agréguelo como el nuevo valor máximo del nodo; de lo contrario, cree un nuevo subnodo derecho para este nodo.
• Si no se encontró ningún nodo delimitador, inserte el valor en el último nodo buscado si aún cabe en él. En este caso, el nuevo valor se convertirá en el nuevo valor mínimo o máximo. Si el valor ya no cabe, cree un nuevo subárbol izquierdo o derecho.

Si se agregó un nuevo nodo, es posible que sea necesario reequilibrar el árbol, como se describe a continuación.

• Busque el nodo delimitador del valor que se va a eliminar. Si no se encuentra ningún nodo delimitador, finalice.
• Si el nodo delimitador no contiene el valor, finalice.
• eliminar el valor de la matriz de datos del nodo

Ahora tenemos que distinguir por tipo de nodo:

• Nodo interno:

Si la matriz de datos del nodo ahora tiene menos que la cantidad mínima de elementos, mueva el valor límite inferior más grande de este nodo a su valor de datos. Continúe con uno de los dos pasos siguientes para la media hoja o el nodo hoja del que se eliminó el valor.

• Nodo hoja:

Si este era el único elemento de la matriz de datos, elimine el nodo. Reequilibre el árbol si es necesario.

• Nudo de media hoja:

Si la matriz de datos del nodo se puede fusionar con la matriz de datos de su hoja sin desbordamiento, hágalo y elimine el nodo de hoja. Reequilibre el árbol si es necesario.

Un árbol T se implementa sobre un árbol binario de búsqueda autoequilibrado subyacente . Específicamente, el artículo de Lehman y Carey describe un árbol T equilibrado como un árbol AVL : se desequilibra cuando los árboles secundarios de un nodo difieren en altura en al menos dos niveles. Esto puede suceder después de una inserción o eliminación de un nodo. Después de una inserción o eliminación, el árbol se escanea desde la hoja hasta la raíz. Si se encuentra un desequilibrio, se realiza una rotación del árbol o un par de rotaciones, lo que garantiza que todo el árbol se equilibre.

Cuando la rotación da como resultado que un nodo interno tenga menos que el número mínimo de elementos, los elementos de los nuevos hijos del nodo se mueven al nodo interno.

Aunque los árboles T se usaban mucho en bases de datos de memoria principal debido a sus ventajas en términos de rendimiento, las tendencias recientes para bases de datos de memoria principal de gran tamaño ponen más énfasis en el costo de aprovisionamiento. Dado que los sistemas de bases de datos NOSQL modernos suelen almacenar billones de registros, el costo de memoria para almacenar incluso un solo índice que incluya valores reales puede superar las decenas o incluso los cientos de terabytes.

• Árbol (teoría de grafos)
• Árbol (teoría de conjuntos)
• Estructura de árbol
• Árbol exponencial

• Árbol B ( árbol 2–3 , árbol 2–3–4 , árbol B+ , árbol B* , árbol UB )
• Árbol danzante
• Árbol de fusión
• árbol k -d
• Octárbol
• Árbol cuaternario
• Árbol R
• Árbol de base
• Árbol superior

• Entrada de preguntas frecuentes de Oracle TimesTen sobre el índice que menciona árboles T
• Documento técnico de Oracle: Productos y tecnologías de Oracle TimesTen
• Presentación de DataBlitz que menciona los árboles T
• Una biblioteca de árboles T* de código abierto