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 equilibrada optimizada para casos en los que tanto el índice como los datos reales se mantienen completamente en la memoria, del mismo modo que un árbol B es una estructura de índice optimizada para el almacenamiento en dispositivos de almacenamiento secundarios 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 , evitando al mismo tiempo el gran espacio de almacenamiento que les es común.
Los árboles T no guardan copias de los campos de datos indexados dentro de los propios nodos del árbol de índice. En cambio, aprovechan el hecho de que los datos reales siempre están en la memoria principal junto con el índice, por lo 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 principal, los nodos secundarios 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 actual del nodo, ambos inclusive.
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 mayor ) y uno que contiene el sucesor de su valor de datos más grande (llamado límite superior mínimo ). Los nodos de 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 un número mínimo y máximo predefinido de elementos
Si se agregó un nuevo nodo, es posible que sea necesario reequilibrar el árbol, como se describe a continuación.
Ahora tenemos que distinguir por tipo de nodo:
Si la matriz de datos del nodo ahora tiene menos del número mínimo de elementos, mueva el valor del 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 de hoja del que se eliminó el valor.
Si este era el único elemento en la matriz de datos, elimine el nodo. Vuelva a equilibrar el árbol si es necesario.
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 hoja. Vuelva a equilibrar el árbol si es necesario.
Se implementa un árbol T sobre un árbol de búsqueda binario 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 la 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 el equilibrio de todo el árbol.
Cuando la rotación da como resultado que un nodo interno tenga menos elementos que el mínimo, los elementos de los nuevos hijos del nodo se mueven al nodo interno.
Aunque los árboles T alguna vez se usaron ampliamente para bases de datos de memoria principal debido a los beneficios de rendimiento, las tendencias recientes para bases de datos de memoria principal muy grandes 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 coste de memoria para almacenar incluso un único índice que incluya valores reales puede superar las decenas o incluso los cientos de terabytes.