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.
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 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.
Si este era el único elemento de la matriz de datos, elimine el nodo. Reequilibre 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 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.