Árboles Multicamino

   Esta estructura de datos simplemente lo que hace es incrementar el grado del árbol. A diferencia de los árboles binarios que sólo tienen un máximo de 2 hijos; en un árbol multicamino de grado "g", un nodo puede tener hasta "g" hijos.

   Las condiciones para clasificar una estructura de datos como árbol multicamino son:

En un árbol de grado "g":

• Cada nodo tiene hasta "g" hijos.
• Los valores guardados en un nodo están en orden ascendente.
• Los valores de los nodos de los hijos de un nodo padre se encuentran en los rangos de manera correspondiente a su su valor con respecto al valor de los elementos del nodo padre que definen el rango.

   De los árboles multicamino las estructuras de datos más representativas e implementadas son los Árboles Tipo-B y sus variantes.

Historia 

   La cronología del desarrollo de las estructuras de datos Árbol-B se puede dividir en períodos:

Primer Período

   En la década de 1960, Rudolf Bayer and Ed McCreight publican un documento de investigación: "Organization and maintenance of large ordered indexes" - (Organización y mantenimiento de índices de alto orden de volumen). Mientras trabajaban en Boeing's Mathematical and Information Sciences Laboratory. Precisamente en el desarrollo de algoritmos de almacenamiento y recuperación de datos en las computadoras de ese momento.

   Aún cuando las computadoras han evolucionado considerablemente desde entonces. El motivo principal de dicha investigación se mantiene invariable.

Segundo Período

   En la década de 1980, el enfoque se centra en la aplicación de estas estructuras de datos en los Sistemas de Administración de Bases de Datos - (Siglas en inglés DBMS). Principalmente se marca la exploración de los problemas que surgieron a partir del control y recuperación en la ejecución concurrente de estos sistemas.

Tercer Período

   En la época de 1990, conforme la utilización de dichas estructuras incrementó considerablemente, el enfoque nuevamente cambió a los siguientes aspectos:

• Problemas de rendimiento en el comportamiento de E/S de los árboles tipo-B. Esto causado por el gran número de operaciones de E/S generadas por el mantenimiento de índices. Estas investigaciones derivan en la combinación de técnicas encontradas en estructuras como los Árboles Combinados con Estructura de Log en los algoritmos de los árboles tipo-B. Lo que incrementa el rendimiento de rendimiento de alta-gama.

• Otros trabajaron en la noción de árboles tipo-B con manejo de versiones. Que no cambian las entradas cuando las actualizan, sino que construyen nuevos índices que puede incluir muchas versiones de un índice conforme avanza el tiempo. A estos árboles se les llega a conocer como "COW" - Copy on Write (Copia sobre Escritura).

Estos enfoques expandieron el área de utilización para ser incluidos en Sistemas de Archivos como btrfs, ZFS y WAFL. Además de permitir la introducción de nuevas características, más sofisticadas como: shadowing, snapshotting y clonación.

Cuarto Período

Con todo el progreso actual en la escala del Internet, sistemas distribuidos, virtualización y centros de datos definidos o integrados en la nube, los límites de las implementaciones de árboles tipo-B centralizadas se están modificando nuevamente. Parece que la atención ahora ha cambiado a:

• Implementaciones de árboles tipo-B distribuidos.
• La compañía Acunu ha estado adquiriendo bastante atención por parte de la comunidad tecnológica por su trabajo en árboles tipo-B estratificados. Cuyo propósito es resolver los problemas de redundancia y duplicación en los árboles COW tipo-B.

Árbol-B

   Es una estructura de árbol multicamino que mantiene la información ordenada y permite las operaciones de búsquedas, inserciones y eliminación de nodos en tiempo logarítmico amortizado.

   Estás estructuras buscan como objetivo leer y escribir largos bloques de datos de manera optimizada, para poder mejorar el rendimiento al trabajar con conjuntos de datos más grandes que la memoria principal; y por lo tanto que se encuentran en memoria secundaria donde existe una alta penalización de tiempo de ejecución en las tareas de lectura y escritura.

Ilustración de árbol Tipo-B.

   Cada árbol tipo-B depende de una constante MÍNIMO, que determina que tantos elementos se almacenan en único un nodo. A partir de este límite surgen las siguientes reglas:

1. La raíz puede tener un sólo elemento (incluso 0 en un árbol vacío); cualquier otro nodo tiene al menos MÍNIMO elementos.
2. El máximo número de elementos en un nodo es el doble de MÍNIMO.
3. Los elementos de un nodo se almacenan en un arreglo parcialmente lleno, ordenados de menor a mayor.
4. El número de subárboles bajo un nodo interno siempre es 1 más que el número de elementos en el nodo.
5. Para todo nodo interno:
• Un elemento en el índice i es mayor que todos los elementos en el subárbol número i del nodo.
• Un elemento en el índice i es menor que todos los elementos en el subárbol número i+1 del nodo
6. Cada hoja en el árbol tiene la misma altura, esto mantiene el árbol balanceado.

Operaciones

•  Inserción
1. Se "suaviza" la regla de elementos de un nodo para permitir que la raíz tenga MÁXIMO + 1 elementos. Luego se hace un agregado simple al árbol.
2. Luego de esto se evalúan 2 casos para reparar el árbol si es necesario.
•  Arreglar un nodo realizando una operación de división del nodo.
• Arreglar el elemento raíz, agregando una nueva raíz y realizando una operación de división del nodo.

Abajo se muestra en un único ejemplo ambos casos:

Se agrega el elemento 18 y se arregla el nodo con exceso posteriormente.

Posteriormente se arregla la raíz con exceso.

•  Borrado
1.  Se "suaviza" la regla de elementos mínimos de un nodo para permitir que el mismo pueda tener 1 menos del MÍNIMO. 
2. Conforme se recorre el árbol se evalúan las siguientes 4 posibilidades:
• Si el nodo no tiene hijos y el valor a remover no se ha encontrado, no se realiza ninguna operación.
• Si el nodo no tiene hijos y el elemento fue encontrado, se remueve el elemento del nodo.
• Si el nodo tiene hijos pero el elemento aún no ha sido encontrado, se llama a la función de remover de manera recursiva, pero con el el siguiente nodo a evaluar.
• Si el nodo tiene hijos y el elemento se encuentra en el mismo. Se remueve el elemento y se corrige si el nodo tiene menos elementos de lo permitido.

Árbol-B+

 Los árboles B+ son una variante de los árboles B, se diferencian en que los arboles B+ toda la información se encuentra almacenada en las hojas. En la raíz y en las hojas internas se encuentran almacenado índices o claves para llegar a un dato.

Principales características de los árboles B+ de orden m son:

• La raíz almacena como mínimo un dato y como máximo m-1 datos.
• La raíz tiene como mínimo dos descendientes.
• Las hojas intermedias tienen como mínimo (m-1)/2(Parte entera) datos.
• Las hojas intermedias tienen como máximo m-1 datos.
• Todas las hojas tienen la misma altura
• La información se encuentra ordenada.
• Toda la información se encuentra almacenada en las hojas, por lo que en las hojas internas se puede duplicar las claves.

Árbol-B*
 

   Los árboles B* son otra variante de los árboles B. Los aspectos diferenciadores son los siguientes:

• Mantiene los nodos llenos de manera más denas, al forzar que todos los nodos excepto la raíz estén al menos 2/3 llenos.
• Pospone tanto como sea posible la operación de división durante una inserción. Esto lo hace al mantener referencias con los nodos vecinos para compartir llaves en caso que el nodo esté lleno.

Referencias

• Perforce.com. (2019). A Short History of the BTree | Perforce. [online] Available at: https://www.perforce.com/blog/vcs/short-history-btree [Accessed 30 Apr. 2019].
• Cburch.com. (2019). CSci 340: B+-trees. [online] Available at: http://www.cburch.com/cs/340/reading/btree/index.html [Accessed 30 Apr. 2019].
• Exposito López, D., García Soto, A. and Martin Gomez, A. (2019). ARBOLES-B. [online] Decsai.ugr.es. Available at: http://decsai.ugr.es/~jfv/ed1/tedi/cdrom/docs/arb_B.htm [Accessed 30 Apr. 2019].
• Tang, D. (2019). CS241: Data Structures & Algorithms II. [online] Cpp.edu. Available at: https://www.cpp.edu/~ftang/courses/CS241/notes/b-tree.htm [Accessed 30 Apr. 2019].
• Es.wikipedia.org. (2019). Árbol-B. [online] Available at: https://es.wikipedia.org/wiki/%C3%81rbol-B [Accessed 30 Apr. 2019].    

Autores

• Erick Blanco Fonseca
• Luis Ortíz Rúa
• Fabián Sánchez Molina