Árbol B

ARBOLES B
1.- OBJETIVO
Para almacenar muchos datos disco, es necesario una estructura de datos eficiente.
Los accesos al disco son costosos en tiempo por lo que se debe evitar realizar muchos accesos a los datos.
AVL es la mejor estructura para memoria principal, pero es ineficiente si se utiliza para almacenamiento secundario. Esto se debe a la cantidad de accesos necesarios para efectuarlas rotaciones. Otro problema es que se requieren tantos accesos como niveles se recorran en el árbol para efectuar la búsqueda.
Bayer y McCreight propusieron en 1970 esta estructura.
Manejan árboles de búsqueda multicamino, cuyos nodos guardan más de un elemento.
Son árboles 100% balanceados en su estructura, lo cual repercute en búsquedas eficientes y en accesos mínimos a disco.

2.-DEFINICIÓN
B-árbol es un árbol de búsqueda que puede estar vacío o aquel cuyos nodos pueden tener varios hijos, existiendo una relación de orden entre ellos, tal como muestra el dibujo.
Un árbol-B de orden M (el máximo número de hijos que puede tener cada nodo) es un árbol que satisface las siguientes propiedades:
1. Cada nodo tiene como máximo M hijos.
2. Cada nodo (excepto raíz) tiene como mínimo(M-1)/2 claves.
3. La raíz tiene al menos 2 hijos si no es un nodo hoja. (según M)
4. Todos los nodos hoja aparecen al mismo nivel.
5. Un nodo no hoja con k hijos contiene k-1 elementos almacenados.
6. Los hijos que cuelgan de la raíz (r1, ···, rm) tienen que cumplir ciertas condiciones:
1. El primero tiene valor menor que r1.
2. El segundo tiene valor mayor que r1 y menor que r2, etc.
3.El último hijo tiene valor mayor que rm.

3.- FUNCIONES O METODOS
Los árboles B constan de 3 funciones principales:
Búsqueda
Inserción
Borrado
Búsqueda
Localizar una clave en un B-árbol es una operación simple pues consiste en situarse en el nodo raíz del árbol, si la clave se encuentra ahí hemos terminado y si no es así seleccionamos de entre los hijos el que se encuentra entre dosvalores de clave que son menor y mayor que la buscada respectivamente y repetimos el proceso hasta que la encontremos. En caso de que se llegue a una hoja y no podamos proseguir la búsqueda la clave no se encuentra en el árbol. En definitiva, los pasos a seguir son los siguientes:
1. Seleccionar como nodo actual la raíz del árbol.
2. Comprobar si la clave se encuentra en el nodo actual:
1. Sila clave está, fin.
2. Si la clave no está:
Si estamos en una hoja, no se encuentra la clave. Fin.
Si no estamos en una hoja, hacer nodo actual igual al hijo que corresponde según el valor de la clave a buscar y los valores de las claves del nodo actual (i buscamos la clave K en un nodo con n claves: el hijo izquierdo si K < K1, el hijo derecho si K > Kn y el hijo i-ésimo si Ki < K < Ki+1) yvolver al segundo paso.

Inserción
Para realizar la inserción, lo primero que debe hacerse es un proceso de búsqueda, para localizar el nodo en el que se va a insertar. Si este proceso de búsqueda da por resultado que el elemento ya existe, no se realizará ninguna operación, pues el árbol B no permite elementos repetidos.
La búsqueda de un elemento inexistente y que, por tanto, pueda serinsertado en el árbol, terminará en el momento en que, tratando de buscar un puntero Pi que apunte al nodo donde debería estar el elemento, encontremos un puntero nulo, siendo insertado el nuevo elemento en el nodo actual. Cuando se inserta en un nodo que no está lleno, solo debemos preocuparnos por el lugar que debe ocupar la nueva llave en ese nodo y hacer un corrimiento de las restantes.
Enproblema surge cuando ya se han insertado varias llaves en un mismo nodo hasta que este queda completo. Una vez lleno un nodo con p-1 valores de la clave de búsqueda, si intentamos insertar una entrada más en él, debemos seguir el siguiente procedimiento:

1. Insertar la llave como si realmente tuviese sitio libre.
2. Extraer el nodo que ocupa la posición del medio e insertarlo en la página padre....