Arboles-B

E structura de Datos
Sulay Manosalvas
INGRESO Y ELIMINACION EN ARBOLES B

Sulay Manosalvas-Estructura de Datos

son árboles cuyos nodos
pueden tener un número
múltiple de hijos

sonestructuras de datos
de árbol que se
encuentran
comúnmente en las
implementaciones
de bases de
datos y sistemas de
archivos

Sulay Manosalvas-Estructura de Datos

Los árboles B mantienen
losdatos ordenados y las
inserciones y
eliminaciones se realizan
en tiempo logarítmico
amortizado.

Un B-árbol se dice:

En la literatura

• que es de orden m si
sus nodos pueden
contener hastaun
máximo de m hijos

• También aparece
que si un árbol es de
orden m significa
que el mínimo
número de hijos
que puede tener
es m+1(m claves).

Sulay Manosalvas-Estructura de Datos

Laidea tras los
árboles-B
• Es que los nodos
internos deben
tener un número
variable de nodos
hijo dentro de un
rango predefinido.
Cuando se inserta o
se elimina un dato
de la estructura, lacantidad de nodos
hijo varía dentro de
un nodo.

Sulay Manosalvas-Estructura de Datos

Se cree que la B es
de balanceado, dado
que todos los nodos
hoja se mantienen al
mismo nivel en elárbol

tienen ventajas
sustanciales sobre otras
implementaciones
cuando el tiempo de
acceso a los nodos
excede al tiempo de
acceso entre nodos

se mantiene
balanceado porque
requiere quetodos
los nodos hoja se
encuentren a la
misma altura.

Ventajas de árboles-B
Sulay Manosalvas-Estructura de Datos

Todos los nodos excepto
la raíz tienen al
menos E((m-1)/2) claves.Lógicamente para los
nodos interiores eso
implica que tienen al
menos E((m+1)/2) hijos

Todas las hojas están en
el mismo nivel

En el caso de que eso
ocurra en un nodo
interior distinto a la raízse soluciona propagando
hacia arriba.

hace que la raíz se divida
en dos hay que permitir
dicha situación para que
los nuevos nodos
mantengan esa
propiedad

El hecho de que la raíz...