• Author / Uploaded
• Hector Pechonb

Citation preview

ESTRUCTURA DE DATOS

Árbol B

Docente: Carlos A. Ruiz De La Cruz Melo Correo: [email protected]

ARBOL B Un árbol B es un árbol de m ramas, con paginas también denominadas nodos, que almacenan un máximo de m-1 claves y que tienen las siguientes características: El número mínimo de claves por nodo es (m/2)-1, excepto la raíz que puede tener menos. En un árbol B, los nodos hojas están en un mismo nivel. El árbol siempre tiende a estar ordenado. Un árbol del cual parten m ramas, registrara un máximo de m-1 claves por nodo. Un factor básico en un árbol B es el orden (m), el cual nos dice que es el número máximo de ramas que pueden salir de un nodo.

Porque usar arboles B ? Los arboles B se usan cuando existe un volumen de información a procesar tan grande que se hace necesario almacenarla en disco, y en el cual los arboles ABB simples o arboles AVL no hacen un buen tiempo de acceso a la información registrada en memoria secundaria.

EJEMPLO DE ARBOL B Un nodo con espacio para 4 claves

Ejemplo de un árbol-B de ORDEN 5 y de profundidad 2.

16

5

10

81

45

78

85

97

99

EJEMPLO DE NO ARBOL B COMO ES DE ORDEN 5 DEBE TENER CADA NODO 2 CLAVES COMO MINIMO

16

5

10

45

ARBOL B vs ABB y AVL

ABB

AVL

Un ABB o un AVL solo puede registrar un dato en cada nodo, lo que causa que el acceso a disco se haga cada vez que se cargue un dato en el árbol.

DISCO

Arbol B

VENTAJAS DE ARBOLES B Para gran cantidad de información esencialmente cuando los nodos se alojan en almacenamiento secundario, evitando el uso reiterado de acceso al disco. La ventaja de un árbol B es que al tener un control sobre el número de nodos hijos que pueda tener un nodo interno, la altura del árbol disminuye, las tareas de tener que equilibrar el árbol también disminuyen, aumentando por consecuencia la eficiencia de la estructura. El número de consultas en un árbol B se puede predecir. El número de consultas no aumentara con el numero de registros a ordenar como si sucede con un árbol ABB simple.

DESVENTAJA DE ARBOLES B

El mantener un árbol B es mas complejo, tal es así que una operación de ingresar, borrar o modificar causa en un nodo unión o desunión obligando a una serie de operaciones para equilibrar el árbol.

Al insertar 44 las claves tienen el orden siguiente:

INSERCION DE CLAVES Las claves se van ordenando automáticamente en un árbol B

16, 44, 56, 67, 81 Se promociona clave del medio

16

56

16

56

56

67

81

67 56

44

67

56

81 56

67

81

16

44

67

81

la

INSERCION Insertamos: 72, 63 56

16

44

63

67

72

81

Luego insertamos: 95 56

16

44

72

63

67

81

95

INSERCION

Se insertan los siguientes valores: 8, 20, 26, 33, 48, 52, 84, 99 20

8

44

56

16

72

63 48 26

67

81

84

95

99

52

33 El árbol ha completado el nodo raíz,…que sucede si insertamos el valor 90

Se promociona la clave del centro y sube al nodo raiz.

INSERCION

Pero ya esta lleno!

90 20

8

16

44

56

63 48 26

33

52

72

67

81

84 95

99

INSERCION

Finalmente queda el árbol como se muestra

56

20

8

44

72

48

16 26

33

90

52 63

67

95 81

84

99

ELIMINACION DE CLAVES

Se eliminara la clave 85 43

12

38

48

43

12

38

73

63

76

85

95

63

76

95

98

73

48

98

ELIMINACION DE CLAVES

Se eliminara la clave 73 43

12

38

48 43

12

38

38

63

76

85

95

98

63

73

85

95

98

76

48

43

12

73

76

48

63

85

95

98

ELIMINACION DE CLAVES

Se eliminara la clave 48 43

12

38

48

43

12

38

73

63

76

85

95

76

63

73

85

95

98

98

ELIMINACION DE CLAVES

Se eliminara la clave12 43

12

38

73

48

63

76

85

95

98

76

85

95

98

73

38

43

48

63

ARBOL B +  El árbol B es bueno para la búsqueda de un elemento del árbol mediante su clave, limitando la cantidad de accesos al soporte drásticamente.  No obstante, si lo que se desea es encontrar un elemento y a partir de allí leer secuencialmente los siguientes elementos, nos encontramos a un problema difícil de solucionar que nos lleva al peor de los casos de tener que recorrer gran cantidad de nodos y realizando gran cantidad de accesos a soporte.  En ese caso se desearía tener una organización donde las claves se encuentren físicamente contiguas, ordenadas y una facilidad y gasto de pocos recursos para el mantenimiento (alta y bajas de claves).  El árbol B+ surge como una adecuada solución a este problema, combinando la estructura de un árbol B y permitiendo tanto el acceso por referencia como el acceso secuencial.

CARACTERISTICAS DE LOS ARBOL B + 1. Todas las paginas hojas tienen la misma altura 2. La información se encuentra ordenada. 3. Toda la información se encuentra almacenada en las paginas hoja, por lo que en las paginas internas se puede duplicar la claves. 4. En la raíz y en las paginas internas se encuentran almacenado índices o claves para llegar a un dato.

55

37

48

77

55

61

73

77

80

87

92

ARBOL B + Dada la siguiente secuencia de claves: 7,25,27,15,23,19,14,29,10, 50,18,22,46,17,70,33, 58 dibuje el árbol B+ de orden 5.

SOLUCION 7

7

15

25

27

7, 25, 27, 15

23

23

15

23

25

27

19, 14, 29

23

7

14

15

19

23

25

27

29

SOLUCION 23

7

7

14

10

15

19, 14, 29

19

23

14

23

14

25

27

10 15

19

14

7

10

14

29

15

23

23

19

25

27

29

50

27

23

25

27

29

50

SOLUCION 14

7

10

14

15

14

7

10

18 14

15

23

18

18

19

18

27

19

23

23

25

29

50

22

27

22 23

27

27

29

50

25

22,46,17,70,33, 58

SOLUCION 14

7

10

18

18

14

15

19

23

22

17

46, 17

27

27

23

29

7

10 14

15

70 27

18

18 17

19

50

25

23

14

46

46

22

46 23

25

27

29

50

70

SOLUCION 23

14

7

10

27

18

18 14

15

33, 58

17

19

46

22 23

25

27

46

50

29

33

58

70

ELIMINACION EN ARBOLES B+ La operación de borrado en árboles-B+ es mas simple que la operación de borrado en árboles-B. Esto ocurre porque las claves a eliminar siempre se encuentran en las paginas hojas. En general deben distinguirse los siguientes casos: 1. Si al eliminar una clave, queda mayor o igual al mínimo de claves, termina la operación de borrado. Las claves de las paginas raíz o internas no se modifican por mas que sean una copia de la clave eliminada en las hojas.

Eliminar la clave 25

25

10

13

25

27

29

ELIMINACION EN ARBOLES B+ Eliminar la clave 25

25

10

13

25

27

29

25

10

13

27

29

ELIMINACION EN ARBOLES B+ 2. Si al eliminar una clave, la cantidad de llaves queda menor al mínimo entonces debe realizarse una redistribución de claves, tanto en el índice como en las paginas hojas.

15

10

13

Eliminar la clave 27

25

15

17

21

25

27

ELIMINACION EN ARBOLES B+ 15

10

13

15

15

10

13

Eliminar la clave 27

25

17

21

25

27

21

25

21

15

17

ELIMINACION EN ARBOLES B+ 15

10

13

Eliminar la clave 21

21

15

17

21

15

10

13

15

17

25

25

ELIMINACION EN ARBOLES 29 B+ Eliminar clave 37 13

10

35

23

11

25 13

10

11 13

27

15

13

15

45

45 29

32

23

29

35

25

27

35

35 29

32

49

37

45

49

ELIMINACION EN ARBOLES B+ Eliminar clave 15, 51 y 48 25

15

10

13

29

20

20 15

17

19

21

48

24 25

27

29

48

51

31

45

60

66

ELIMINACION EN ARBOLES B+ Eliminar clave 60 25

15

10

13

29

20

20 17

19

21

48

24 25

27

29

60

66

31

45

ELIMINACION EN ARBOLES B+ Eliminar clave 31 25

15

10

13

29

20

20 17

19

21

45

24

45 25

27

29

31

66

ELIMINACION EN ARBOLES B+ 15

10

13

20 17

19

20

25

21

24

29

29 25

27

45

66

EJERCICIO Construya un árbol B y luego un árbol B+ a partir de la siguiente secuencia:

23, 56, 2, 14, 78, 44, 33, 38, 12, 19, 55, 67, 60, 48, 89, 74, 65, 5, 24, 28