Programacionarboleb

Árboles B

Los árboles B nacen en 1972 y fueron creados por R. Bayer y E. McCreight La necesidad de mantener índices en almacenamiento externo para accesar a base de datos

Se pretende accesara la información indexada en la memoria RAM, y optimizar tiempo, ya que acceder a ella mediante el disco duro, puede consumir recursos importantes. Estos árboles multinivel resuelven la inserción yborrado de registros.

Principales operaciones: -Búsqueda Inserción Borrado

Principales operaciones: Búsqueda -Inserción Borrado

Principales operaciones: Búsqueda Inserción -BorradoCARACTERÍSTICAS Todos los árboles B tienen que cumplir con las siguientes características en cuanto a estructura -Toda página tiene como máximo 2 nodos -Toda página distinta a la raíz tiene como mínimotiene n nodos, la raíz tiene como mínimo 1 nodo. -Todas las páginas hojas están en el último nivel

K

1

K

2

Página con 2 nodos

K K
1

1

K K
2

2

Página con 2 nodosRaíz con 1 nodo

K

m-1

K

2

K

3

K

4

K

5

Hojas en el último nivel

ORDENAMIENTO Todos los árboles B tienen que cumplir también con el siguiente ordenamiento -Los nodosde una hoja mantienen un orden ascendente de izquierda a derecha -Cada nodo es mayor que los que se sitúan a la izquierda - Cada hoja es mayor que la que se sitúa a su izquierda

K

1

K

2Orden ascendente de izquierda a derecha

<

K

1

K

2

El nodo de la izquierda es menor que el de la derecha.

K

m-1

K

2

K

3

K

4

K

5

< Hoja derecha esmayor que la situada en la izquierda

Insertar
a) Insertar 23 13 20 30 13 20 30

22 23 25 29 b) Insertar 21 13 20 30
PARTIR EL NODO

22 23 25 29

13 20 23 30

13 20 23 30

21 22 23 2529

21 22

25 29

21 22

25 29

c) Insertar 26, 27, 28 PARTIR 13 20 23 30

EL NODO

13 20 23 27 30

PARTIR EL NODO

23 39 27 30 28 29

13 20 25 26 27 28 29 25 26 28 29 25 26...