En informática, un árbol T es un tipo de estructura de datos de árbol binario que utilizan las bases de datos de la 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 los casos en los que tanto el índice como los datos reales se mantienen 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 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 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 índices. En su lugar, aprovechan el hecho de que los datos reales siempre están en la memoria principal junto con el índice para que solo contengan punteros a los campos de datos reales.
La 'T' en el árbol T 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]
Estructuras de nodo
Un nodo de árbol T generalmente consta de punteros al nodo principal, al nodo secundario 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 para un valor si el valor se encuentra entre el valor mínimo y máximo actual del nodo, 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 más grande ) 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
Algoritmos
Buscar
- La búsqueda comienza en el nodo raíz
- Si el nodo actual es el nodo delimitador para el valor de búsqueda, busque 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 un 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 correcto.
Inserción
- Busque un nodo delimitador para el nuevo valor. Si tal nodo existe entonces
- 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 tiene el límite inferior más grande para el nodo en el que se insertó el nuevo valor. Si el valor mínimo eliminado aún encaja 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 encaja en él. En este caso, el nuevo valor se convertirá en el nuevo valor mínimo o máximo. Si el valor ya no encaja, 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.
Supresión
- Busque el nodo delimitador del valor que se 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 el número mínimo de elementos, mueva el mayor valor de límite inferior 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 en la matriz de datos, elimine el nodo. Reequilibre el árbol si es necesario.
- Nodo 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 hoja. Reequilibre el árbol si es necesario.
Rotación y balanceo
Un árbol T se implementa 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 de árbol o un par de rotaciones, lo que garantiza el equilibrio de todo el árbol.
Cuando la rotación da como resultado un nodo interno que tiene menos del número mínimo de elementos, los elementos de los nuevos hijos del nodo se mueven al nodo interno.
Rendimiento y almacenamiento
Aunque los árboles T se utilizaron una vez ampliamente para las 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. Con los sistemas de bases de datos NOSQL modernos que a menudo almacenan billones de registros, el costo de memoria para almacenar incluso un solo índice que incluye valores reales puede exceder decenas o incluso cientos de terabytes.
Ver también
Otros arboles
Referencias
- ^ Lehman, Tobin J .; Carey, Michael J. (25 a 28 de agosto de 1986). Un estudio de estructuras de índices para los principales sistemas de gestión de bases de datos de memoria . Duodécima Conferencia Internacional sobre Bases de Datos Muy Grandes (VLDB 1986). Kyoto. ISBN 0-934613-18-4.