Ing de sistemas

-------------------------------------------------
Árbol-B

Ejemplo de árbol B.
En las ciencias de la computación, los árboles-B o B-árboles son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos ysistemas de archivos. Son árboles binarios de búsqueda en los cuales cada nodo puede poseer más de dos hijos.1 Los árboles B mantienen los datosordenados y las inserciones y eliminaciones se realizan en tiempo logarítmico amortizado.
Contenido  [ocultar]  * 1 Definición * 2 Definición técnica * 3 Altura: El mejor y el peor caso * 4 Estructura de los nodos * 5 Algoritmos * 5.1 Búsqueda * 5.2 Inserción * 5.3 Eliminación * 5.3.1 Eliminación en un nodo hoja * 5.3.2 Eliminación en un nodo interno *5.4 Rebalanceo después de la eliminación * 5.5 Construcción Inicial * 6 Notas * 6.1 Multi-modo:combinar y dividir * 6.2 Relación entre U y L * 6.3 Acceso concurrente * 7 Véase también * 8 Referencias * 9 Enlaces externos |
-------------------------------------------------
[editar]Definición
La idea tras los árboles-B es que los nodos internos deben tener un númerovariable 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 rango variable de nodos hijo, los árboles-B no necesitan rebalancearse tan frecuentemente comolos árboles binarios de búsqueda auto-balanceables, pero por otro lado pueden desperdiciar memoria, porque los nodos no permanecen totalmente ocupados. Los límites superior e inferior en el número de nodos hijo son definidos para cada implementación en particular. Por ejemplo, en un árbol-B 2-3 (A menudo simplemente llamado árbol 2-3 ), cada nodo sólo puede tener 2 ó 3 nodos hijo.
Un árbol-B semantiene balanceado porque requiere que todos los nodos hoja se encuentren a la misma altura.
Los árboles B tienen ventajas sustanciales sobre otras implementaciones cuando el tiempo de acceso a los nodos excede al tiempo de acceso entre nodos. Este caso se da usualmente cuando los nodos se encuentran en dispositivos de almacenamiento secundariocomo los discos rígidos. Al maximizar el número de nodoshijo de cada nodo interno, la altura del árbol decrece, las operaciones para balancearlo se reducen, y aumenta la eficiencia. Usualmente este valor se coloca de forma tal que cada nodo ocupe un bloque de disco, o un tamaño análogo en el dispositivo. Mientras que los árboles B 2-3 pueden ser útiles en la memoria principal, y además más fáciles de explicar, si el tamaño de los nodos se ajustan paracaber en un bloque de disco, el resultado puede ser un árbol B 129-513.
Los creadores del árbol B, Rudolf Bayer y Ed McCreight, no han explicado el significado de la letra B de su nombre. Se cree que la Bes de balanceado, dado que todos los nodos hoja se mantienen al mismo nivel en el árbol. La B también puede referirse a Bayer, o aBoeing, porque sus creadores trabajaban en el Boeing ScientificResearch Labs en ese entonces.
-------------------------------------------------
[editar]Definición técnica
B-árbol es un árbol de búsqueda que puede estar vacío o aquel cuyos nodos pueden tener varios hijos, existiendo una relación de orden entre ellos, tal como muestra el dibujo.
Un árbol-B de orden M (el máximo número de hijos que puede tener cada nodo) es un árbol que satisface lassiguientes propiedades:
1. Cada nodo tiene como máximo M hijos.
2. Cada nodo (excepto raíz y hojas) tiene como mínimo (M+1)/2 hijos.
3. La raíz tiene al menos 2 hijos si no es un nodo hoja.
4. Todos los nodos hoja aparecen al mismo nivel.
5. Un nodo no hoja con k hijos contiene k-1 elementos almacenados.
6. Los hijos que cuelgan de la raíz (r1, ···, rm) tienen que cumplir...