Estructura de datos - Arbol-B









Trabajo Grupal “Árboles-B”

















Integrantes: Asignatura:
-Jonathan Acuña Estructura de Datos ILI-134
-Mario Pérez
-Felipe González USM Casa Central
Primer Semestre 2014Profesor:
Hubert Hoffmann

14/07/2014

Índice
1.-Introducción…………………………………………………………………………………………………….. 3
2.- Definición………………………………………………………………………………………………………… 4
3.- Estructura………………………………………………………………………………………………………… 5
3.2- Ejemplos…………………………………………………………………………………………….. 6
4.-Algortimos………………………………………………………………………………………………………..
4.1Búsqueda……………………………………………………………………………………………. 7
4.2.- Inserción…………………………………………………………………………………………… 8
4.3.-Eliminación………………………………………………………………………………………… 9
4.3.-Ejemplos……………………………………………………………………………………………. 10
5.- Códigos...……………………………..…………………………………………………………………………. 12
6.- Resumen…………………………………………………………………………………………………………. 15
7.- Conclusión……………………………………………………………………………………………………… 16
8.- Referencias……………………………………………………………………………………………………… 17
9- Metodología de trabajo…………………………………………………………………………………… 18Introducción
A lo largo del curso de estructura de datos, hemos sido capaces de aprender que en las ciencias de la computación existen ciertas estructuras necesarias al momento de desarrollar programas y algoritmos con el fin de lograr resultados deseados  de una manera más fácil, eficiente y ordenada.
Pilas, Listas y Colas son un ejemplo claro de las mismas, lascuales nos han sido útiles a lo largo del desarrollo de las tareas, permitiéndonos descubrir de esta manera, el valor que tienen y su utilidad al facilitar el manejo de la información.
No obstante, dentro de las estructuras que han sido aprendidas durante el estudio de las estructuras, se encuentran los árboles donde el curso se enfocó en enseñarnos las herramientas necesarias para lograr elentendimiento de su funcionamiento y sus diversos tipos tales como árboles binarios y AVL.
En el presente informe se pretende introducir y realizar un profundo estudio en el concepto de árboles(a,b) o árboles-B, dando un énfasis en entregar una definición simple de que son estos árboles, su forma de funcionamiento y su estructura con el fin de que el lector pueda comprender de manera correcta elcontenido de este informe y así poder añadir satisfactoriamente un nuevo conocimiento a los antiguamente ya adquiridos durante el transcurso de este semestre.

















Definición

Los árboles-B o B-árboles creados por Rudolf Bayer y Ed McCreight, son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Aligual que los árboles binarios de búsqueda, son árboles balanceados de búsqueda, pero cada nodo puede poseer más de dos hijos, es decir, manejan árboles de búsqueda multicamino, cuyos nodos guardan más de un elemento. Los árboles B mantienen los datos ordenados lo cual repercute en búsquedas eficientes y en accesos mínimos a disco, las inserciones y eliminaciones se realizan en tiempo logarítmicoamortizado.
La idea 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, la cantidad de nodos hijo varía dentro de un nodo. Para que siga manteniéndose el número de nodos dentro del rango predefinido, los nodos internos se juntan o se parten. Dado que se permite un rangovariable de nodos hijo, los árboles-B no necesitan rebalancearse tan frecuentemente como los árboles binarios de búsqueda auto-balanceables, esto se debe a que un árbol-B requiere que todos los nodos hoja se encuentren a la misma altura. Los límites (uno superior y otro inferior) en el número de nodos hijo son definidos para...