Arboles b

ÁRBOL B
Son árboles cuyos nodos pueden tener un número múltiple de hijos
Son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas dearchivos. Los árboles B mantienen los datos ordenados y las inserciones y eliminaciones se realizan en tiempo logarítmico amortizado.
Cada Nodo puede tener hasta m subárboles
Las claves se organizan enAVL
OBJETIVO: que la altura del árbol sea pequeña, pues las iteraciones y los accesos a disco dependerá de ellos.
Cada página contiene a lo sumo 2n elementos (llaves).
Todas las páginas de hojaaparecen al mismo nivel

PROPIEDADES:
Debe estar balanceado el árbol que se encuentra paginado.
Cada página puede tener cierto numero de nodos del árbol (el numero de nodos es definido por elusuario).
Entre mayor sea el numero de paginas, mayor es el número de movimientos que hará la cabeza lectora.
Entre mayor sea el número de nodos de cada pagina, mayor será el tiempo en transferir lainformación.

El numero de desplazamientos de un árbol paginado está determinado por:
Log base k+1 (N+1)
N= número de llaves (nodos del árbol).
K=número de llaves de cada pagina (nodos del árbol de lapagina).

CARACTERISTICAS:
Es m–arios y sin subárboles vacíos.
• Siempre está perfectamente equilibrado.
• Página: nombre de sus nodos. Se los accede en
bloque.
– Todas las Páginas están en elmismo nivel
– Como Máximo: m Ramas y m–1 Claves
– Como Mínimo: (m/2)+1 Ramas y (m/2) Claves
• La Raiz puede estar vacía o incluso tener 1 Clave,
con sus 2 ramas.

ELIMINACION EN UN ARBOL B
Lospasos de la eliminación de llaves de un árbol B son los siguientes:
Si la llave que se va a eliminar no está en una hoja, intercambiarla con su sucesor inmediato, el cual está en una hoja.
Eliminarla llave.
Si la hoja ahora contiene por lo menos el número mínimo de llaves, no se requiere ninguna acción adicional.
Si la hoja ahora contiene una menos de las llaves mínimas, examínese los...