La operación de inserción en un árbol B es relativamente sencilla, sólo hay un caso en el que este procedimiento se complica ligeramente.
La primera acción a realizar en la operación de inserción es localizar el lugar adecuado en el árbol donde se insertará el nuevo elemento. De esta forma aseguraremos que la propiedad de orden se mantiene.
Una vez localizado el lugar adecuado, hay que tener en cuenta el número de nodos que tiene la página destino del nuevo elemento. Si tiene menos de 2n, entonces se inserta el nuevo nodo y se da por finalizada la operación de inserción.
La complejidad se produce cuando la página destino está al cmopleto de su capacidad, es decir, tiene 2n nodos. En estos casos el procedimiento a seguir es el siguiente:
Como consecuencia de que todas las hojas deben estar en el último nivel, los árboles B crecen hacia arriba, característica que también los diferencia del resto de árboles estudiados hasta ahora. Este crecimiento se produce cuando la inserción de un nodo en una página completa provoca su división.
Vamos a ver un ejemplo de inserción en árboles B.
Sobre este árbol se inserta el elemento 18. La página que le corresponde es la que contiene los elementos 10,15,17,19. Al estar completa se produce el ascenso del nodo mediano (el 17) y la división en dos páginas de la página original.
El proceso de borrado puede llegar a ser algo más complejo que la inserción.
La eliminación de elementos siempre se hace en una hoja, si el nodo a borrar no estuviese en un nodo hoja, se sustituiría el nodo a borrar por el inmediatamente inferior o superior, que sí que debe estar en undo hoja.
El caso más sencillo se produce cuando al eliminar un nodo de una página hoja, bien porque sea el nodo a eliminar, bien porque sea un elemento que sustituyó al nodo a eliminar, el tamaño de la página sigue siendo al menos n. De esta forma, la estructura del árbol se sigue cumpliendo y no hay que realizar ninguna reestructuración.
El problema surge cuando al eliminar un nodo de la hoja, la página se queda con menos del mínimo número de nodos permitidos. En este caso se agrupa esta página con una de sus páginas vecinas y con su nodo padre, el nodo mediano del conjunto resultante sería el nuevo padre, y el resto de nodos se repartiría equitativamente entre las dos páginas.
Aún resta un caso más. Este caso es idéntico al anterior, pero ahora la página vecina tiene el número mínimo de nodos. En esta situación se produce el efecto inverso a la división, las dos páginas se agrupan en una sola, formando una nueva página de 2n-1 nodos. A esta página se le añade el nodo central que estaba situado en la página padre.
Vamos a ver gráficamente los efectos de una eliminación.
Si sobre el árbol representado arriba se elimina el elemento 18, el árbol resultante sería el siguiente:
Para llegar a esta situación se fusionaron la primera y la segunda hoja con su nodo mediano situado en la página padre.
Como en el caso de los árboles binarios las operaciones secundarias más usuales son las búsquedas y los recorridos. Estos algoritmos son semejantes a los utilizados para los árboles binarios.
