En informática , un árbol danzante es una estructura de datos en forma de árbol similar a los árboles B+ . Fue inventado por Hans Reiser para su uso en el sistema de archivos Reiser4 . A diferencia de los árboles binarios de búsqueda autoequilibrados que intentan mantener sus nodos equilibrados en todo momento, los árboles danzantes solo equilibran sus nodos cuando vacían datos en un disco (ya sea por limitaciones de memoria o porque se ha completado una transacción). [1]
La idea detrás de esto es acelerar las operaciones del sistema de archivos al retrasar la optimización del árbol y escribir en el disco solo cuando sea necesario, ya que escribir en el disco es miles de veces más lento que escribir en la memoria. Además, debido a que esta optimización se realiza con menos frecuencia que con otras estructuras de datos de árbol, la optimización puede ser más extensa.
En cierto sentido, esto puede considerarse como un árbol binario de búsqueda autoequilibrado que está optimizado para el almacenamiento en un medio lento, en el que la forma en disco siempre estará equilibrada pero no tendrá escrituras a mitad de la transacción; al hacerlo, se alivia la dificultad de agregar y quitar nodos durante una transacción. En cambio, estas operaciones lentas de reequilibrio se realizan al mismo tiempo que la escritura mucho más lenta en el medio de almacenamiento.
Sin embargo, un efecto secundario negativo de este comportamiento se manifiesta en casos de apagado inesperado, escrituras de datos incompletas y otras situaciones que pueden impedir que se complete la transacción final equilibrada. En general, los árboles danzantes plantean una mayor dificultad que los árboles convencionales para la recuperación de datos de transacciones incompletas, aunque esto se puede solucionar contabilizando de forma más exhaustiva los datos de las transacciones.