Loa raboles b

Unidad 8  Árboles B 

•Bibliografía: “Algoritmos y Estructuras de datos” de Aguilar y Martinez. Unidad 16  •Autor: Ing Rolando Simon Titiosky.

Problemas de los AVL 
•  Los AVL tienen una Eficiencia F(n)= log n. 
– Su altura depende de la cantidad de nodos.  k+1  – A Nivel k, tendrá 2  –1 nodos. 

•  Cuando se tienen un conjunto masivo de datos (ej 1millon de Registros de Clientes  de un banco equivalen k @ 19 niveles), los  datos estarán ubicados en Discos. 
– El Tiempo de Acceso a disco es notablemente  superior que el de RAM.  – Es necesario minimizar estos accesos al disco 

y maximizar el uso de RAM

Definición de Árbol B 
•  •  •  •  Solución: Árboles de Búsqueda m–arios.  Cada Nodo puede tener hasta m subárboles.  Las claves se organizan en AVL. Objetivo: Que la altura del árbol sea pequeña,  pues las iteraciones y los acceso a disco  dependerá de ello. 
–  El Árbol B es una solución particular de esta tecnología 
39 39  20  30  20  30  4  13  15  16  4  13  15  16  22  25  29  22  25  29  33  34  33  34  41  42  41  42  45  62  45  62  47  52  47  52  63  73  63  73 

Características del Árbol B 
•  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 el mismo 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. 
39 39  20  30  20  30  4  13  15  16  4  13  15  16  22  25  29  22  25  29  33  34  33  34  41 42  41  42  45  62  45  62  47  52  47  52  63  73  63  73 

Características del Árbol B 
•  Las claves dividen el espacio de claves como en el AVL  •  Los Árboles que estudiaremos serán de orden m=5 
–  Un orden mayor aumenta la complejidad de la Inserción y Borrado.  –  Un Orden menor disminuye la eficiencia de Búsqueda  –  Numero Máximo Por Nodo: 4 Claves y 5 Ramas  – Numero Mínimo Por Nodo: 2 Claves y 3 Ramas 

•  Se rastrea el camino de búsqueda al igual que en el Árbol  de Búsqueda. 

a  b  c  d 
 a   b   c  d

Variantes: B+
•Los árboles B+ permiten un recorrido secuencial mas rápido que el B pues
–Las claves se encuentran en el Indice Y en las hojas –Existe un puntero ProximaPagina.

Variante: B*
•Propone nuevas reglas para el mantenimiento.–Los nodos deben estar 2/3 llenos siempre.  –La nueva construcción logra una búsqueda más rápida que el B+ pero una  inserción más costosa.

•Si cada nodo tiene un máximo de m descendientes.
–C/ nodo menos la raíz tiene al menos (2m­1)/ hijos. 3 –Si es de orden m=5 
•Numero Máximo Por Nodo: 4 Claves y 5 Ramas  •Numero Mínimo Por Nodo: 3 Claves y 4 Ramas 

•Recuerden: En Arbol B
–C/nodo menos la raíz tiene almenos (m/2)+1 hijos.
•Numero Máximo Por Nodo: 4 Claves y 5 Ramas  •Numero Mínimo Por Nodo: 2 Claves y 3 Ramas

TAD arbolB: ArbolB.h 
/*Definición de los Datos del TAD*/  #define m 5  /*Orden del Árbol B:  Como Máximo: m Ramas y m–1 Claves*/  typedef int tipoClave;  typedef struct pagina  {  tipoClave claves[m];  /* m{0..4}Numero de claves será for (k=1; k ≤m; k++) */ struct pagina* ramas[m];  int cuenta;  /*Numero de claves de la pagina*/  } Pagina;  /*Definición de las Operaciones del TAD*/  void escribeNodo(Pagina* actual);  int nodoLLeno(Pagina* actual); /*Devuelve verdadero si el numero de claves es m–1*/  int nodoSemiVacio(Pagina* actual); /*Devuelve .V. si el numero de claves es menor a m/2*/  void crearArbolB(Pagina **raiz); Pagina *buscar (Pagina *actual, tipoClave cl, int * indice);  Pagina *buscarNodo(Pagina *actual, tipoClave cl, int * k);  void insertar (Pagina **raiz, tipoClave cl);  ….

TAD arbolB: ArbolB.c 
int nodoLLeno(Pagina* actual)  0 {return (actual­>cuenta == m ­1);  }  int nodoSemiVacio(Pagina* actual)  {  return (actual­>cuenta claves[k]);  printf("\n");  } 

1  2  3  4  C1  C2  C3  C4 

R0  R1  R2  R3  R4 ...