Árbol B
Estructura de Datos en
memoria secundaria
Introducción



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
efectuar las rotaciones. Otro problema es
que se requieren tantos accesos como
niveles se recorran en el árbol para efectuar
la búsqueda.
Árboles B
 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.
10 20
5 8
25 65 92 99
12 18
Características del Árbol B

Un Árbol B de orden n es aquel que:



Todas las hojas del árbol están en el nivel
inferior.
Cada nodo contiene entre n y 2n elementos,
excepto el nodo raíz, que puede tener entre 1
y 2n elementos.
Si un nodo tiene ‘m’ elementos, el nodo
siempre contendrá m + 1 hijos si no es un
nodo hoja.
Ejemplo....
 Para

un Árbol B de orden 3:
Cuántos elementos máximo puede guardar
cada nodo del árbol?
6

¿Cuántos elementos mínimo puede guardar
cada nodo del árbol?
1 si el la raíz, 3 cualquier otro nodo.

¿Cuántos hijos máximo puede tener un nodo?
7

¿Cuántos hijos mínimo puede tener un nodo?
0 si es hoja, 2 si es raíz, 4 cualquier otro nodo.
Más características del Árbol B

Un árbol B de orden n es aquél en que:

Los elementos de un nodo están ordenados
linealmente.

Los elementos están organizados de tal forma
que se cumple la regla de la búsqueda: a la
izquierda menores, a la derecha mayores.
10 20
5 8
25 65 92 99
12 18
Ejemplo...
 ¿De
qué orden es este árbol B?
10 20
5 8
25 65 92 99
12 18
Este árbol es de
orden 2 ya que
puede almacenar
hasta 4 elementos en
cada nodo.
Proceso
de
Inserción
 Buscar el nodo hoja en donde se debería agregar el


elemento.
Si hay espacio disponible en el nodo, agregar el
elemento y terminar.
Si el nodo hoja NO tiene capacidad de almacenar
el elemento, se deberá crear un nuevo nodo al
mismo nivel de la hoja y distribuir a los 2n+1
elementos de la siguiente forma:



El nuevo nodo recibe a los ‘n’ elementos más grandes.
El nodo existente se queda con los ‘n’ elementos más
pequeños.
El elemento medio se insertará en el nodo padre siguiendo
la misma lógica de inserción. En caso de no haber nodo
padre, se creará un nuevo nodo que pasará a ser la
nueva raíz.
Ejemplo....
10 20
5 8
25 65 92 99
12 18
Agregar el 4
10 20
Si hay espacio para el elemento,
éste se agrega en el nodo.
Los elementos están acomodados
de menor a mayor.
4 5 8
25 65 92 99
12 18
Ejemplo...
10 20
5 8
25 65 92 99
12 18
Agregar el 56
Cuando el nuevo
elemento no cabe en el
nodo, se agrega otro
nodo y se reparten los
elementos.
10 20 65
4 5 8
12 18
92 99
25 56
Ejemplo...
10 20 65
4 5 8
12 18
70 75 80 85
25 56
Agregar el 78
El árbol siempre se
resiste a crecer, ya que
trata de distribuir los
elementos en los
nodos ya existentes.
10 20 70
4 5 8
12 18
75 78 80 85
25 56 65
10206590
Ejemplo
9495
70758085
4 5 8
1218
1
4 5 8
12 18
2556 5760
Agregar el 66
El árbol crece de abajo
hacia arriba. Cuando el
árbol aumenta de altura
sólo se agrega una
nueva raíz.
2
10 20 65 90
65
75
9495
1020
80 85
25 56 57 60 66 70
4 5 8
1218
2556 5760
7590
9495
8085
6670
Proceso de Eliminación
 Buscar el elemento a borrar.
 Si el elemento a borrar está en
una nodo
hoja, se borra y termina el proceso.
 Si el elemento a borrar no se encuentra
en una hoja, al igual que en un ABB, se
buscará al sustituto más apropiado. El
sustituto será:


El último elemento de la hoja más derecha del
subárbol izquierdo del nodo actual (el mayor
de los menores).
El primer elemento de la hoja más izquierda del
subárbol derecho del nodo actual (el menor de
los mayores).
Ejemplo...
10 20 65
4 5 8
12 18
Cuando el nodo tiene
más elementos que el
mínimo, se da de baja
al elemento y termina
el proceso.
70 75 80 85
25 56
Eliminar el 8
10 20 65
4 5
12 18
70 75 80 85
25 56
Ejemplo...
10 20 65
4 5 8
12 18
70 75 80 85
25 56
Eliminar el 56
Cuando el nodo
tiene el mínimo se
toma un elemento
de los hermanos.
10 20 70
4 5 8
12 18
75 80 85
25 65
Ejemplo...
10 20 65
4 5 8
12 18
70 75
25 56
Cuando el nodo tiene el
mínimo y los hermanos
también, se une el nodo
con uno de sus hermanos
y le libera el nodo
sobrante.
Eliminar el 56
10 20
4 5 8
12 18
25 65 70 75
65
1020
7590
4 5 8
9395
1218
Ejemplo...
Eliminar el 65
Utilizar el menor de los mayores
8085
2556 5760
1
6670
2
66
1020
4 5 8
1218
2556 5760
1020 6690
90
9395
7075 8085
4 5 8
1218
9395
7075 8085
2556 5760
65
102060
9395
4 5 8
1218
61 62
2556 5758
1
4 5 8
1218
2556 5758
61 62
Eliminar el 65
Utilizar el menor de los mayores
8085
6670
2
66
1020 60
Ejemplo...
7590
60
90
1020
9395
4 5 8
7075 8085
1218
2556 5758
6690
9395
7075 8085
61 62
Descargar

Árbol B