Las estructuras de Árbol-B toman muchas de las ideas de las estructuras de Árboles binario de búsqueda (BST) pero busca mejorar la eficiencia de acceso a la memoria al utilizar arreglos en cada nodo en lugar de un solo elemento con dos hijos como se hace en los BST.
Específicamente, para alguna constante B fija, cada nodo contiene entre B-1 y 2B-1 elementos en ordenados. La raíz puede tener apenas un elemento, mientras que un nodo interno (uno que tiene hijos) con $k$ elementos tiene k + 1 hijos. De esta manera, se preserva la noción de hijos a la "izquierda" y "derecha" de los BST, pero, por ejemplo, el segundo elemento secundario contiene elementos estrictamente entre el primer y el segundo elemento. Para entender esto es mejor visualizarlo:
En este simple ejemplo es fácil entender el paralelismo entre los Àrboles-B y los BST. Vemos que la raíz consta de dos elementos el 7 y el 16. Si asumimos que los número son positivos, estos 7 elementos particionan el conjunto de los enteros en tres secciones: [0,7), [7,16), [16,\infty), todas estas a la izquierda o derecha del elemento original. A partir de esto podemos entonces crear tres nuevos nodos, con la capacidad de almacenar todos los elementos dentro de cada subconjunto, y repetimos el proceso a medida que vayamos insertando nuevos elementos.
Los Árboles-B han sido históricamente populares como una estructura de datos almacenable en el disco. Esto se debe a que acceder al disco es una operación súper lenta, pero en general se obtienen grandes fragmentos a la vez. Entonces, si se elige, por ejemplo, B = 1000 , puedes tomar mil entradas en el árbol de una vez y procesarlas en RAM de manera relativamente instantánea. Ademas, su árbol también será muy superficial, lo que significa que cada búsqueda puede llegar al disco siguiendo un puntero solo un par de veces. Este comportamiento en el contexto de las memorias RAMs permite mitigar uno de los problemas más grandes de los BST, el acceso eficiente a data contínua.
Si analizamos su estructura, es fácil ver que una vez construido, buscar una clave es un proceso con la misma idea básica que en un BST, pero en lugar de compararla con un solo elemento por nodo, se busca en un nodo el menor elementos más grande que la clave. Luego se busca recursivamente el elemento secundario izquierdo de ese elemento o el último elemento secundario si no existe tal elemento. La forma en que elige buscar es un detalle de implementación: puede ir lineal, binario o cualquier otro elemento intermedio.
Insertar en un B-Tree implica buscar dónde estaría el elemento que se insertaría si estuviera contenido (que siempre termina en una hoja si no está allí), haciendo una inserción ordenada en las matrices de ese nodo (cambiando así sobre los elementos B en un matriz), y luego potencialmente realizar una operación de manejo de overflow, el cual ocurre cuando el nodo para insertar ya está lleno. La solución es bastante simple: crea un nuevo nodo, copia la mitad de los elementos en él e insertalo en el padre usando un elemento del nodo dividido. Esto esencialmente "traslada" el problema de inserción en el nodo padre. Si el desbordamiento llega a la raíz, simplemente hacemos una nueva raíz e insertamos las dos mitades de la raíz anterior en la nueva.
La operación de eliminar en un B-Tree es la operación "difícil". Al igual que la inserción, primero busca el elemento normalmente. Si no está en un nodo hoja, debe intercambiarlo con el elemento más pequeño en su subárbol derecho, para que esté en una hoja. Luego, realiza una eliminación ordenada de la matriz (nuevamente, desplazando los elementos B en una matriz), y potencialmente maneja el flujo inferior. El overflow ocurre cuando un nodo tiene menos elementos que el mínimo permitido. El manejo del flujo inferior es un proceso de dos fases. Primero, intentas robar un elemento de un vecino. Si tienen elementos de sobra, esto funciona bien. Sin embargo si ambos están en su cantidad mínima se fusionan los dos nodos en un nodo, robando el elemento de separación del padre en el camino. Al igual que el desbordamiento, esto soluciona el problema de eliminación al padre. Si el subflujo llega a la raíz, reemplazamos la raíz con su hijo secundario restante.
Si eso fue mucho para asimilar, no te preocupes, el lugar ideal para buscar mas información si manejas el ingles es: Open Data Structures (http://opendatastructures.org/).
Para finalizar es importante comentar que los BST generalmente requieren tiempo O (log 2 n) para todas las operaciones. Para B-Trees, la búsqueda lleva tiempo O (log 2 n) (si la búsqueda binaria de los nodos), y la mutación lleva tiempo amortizado O (B + log B n). Entonces, si realmente aumenta B, está buscando hacer más "trabajo" para realizar mutaciones, pero mejor eficiencia de caché mientras lo hace . En un extremo $( B = 1000 )$, su árbol tendrá quizás dos o tres capas de profundidad, con su búsqueda binaria e inserción en matrices ordenadas masivas. En otro extremo ( B = 2 ), básicamente obtienes un BST. La forma de buscar en los nodos también es una compensación de trabajo en caché. La búsqueda lineal es, por supuesto, la cosa más amigable con el caché que puede hacer, pero toma tiempo O (B). La búsqueda binaria es un poco menos amigable con la caché, pero toma tiempo $O (log B)$.
Esta respuesta es una interpretación del contenido en: Rust Collections Case Study: BTreeMap (http://cglab.ca/~abeinges/blah/rust-btree-case/).
Si tienen interés en ver como implementar este tipo de estructuras en RUST, es un buen lugar para aprender.