3.4. Árboles B.
Al haber eliminado una entrada del padre, puede ser necesario repetir el proceso de supresión a partir de ese nivel (hacia arriba). Si la entrada eliminada está en la raíz y esta sólo tiene un elemento, entonces el árbol decrece un nivel.
Supresión de entradas en un árbol B (nodo interno).
- Sustituir la entrada del nodo interno por la siguiente en el orden (la mayor de la rama izquierda, o la menor de la rama derecha).
- Repetir el proceso anterior para la entrada eliminada en la hoja.
- Orden de complejidad. Suponemos que el elemento es un nodo hoja.
- Existirán logd N niveles, en cada uno log2 d búsquedas en promedio ? log2d*logd N= log2 N comparaciones realizadas en la búsqueda.
- En una B.D., normalmente cada nodo es un bloque de E/S. El valor que más influye en el tiempo es el número de E/S.