arboles b

 ARBOLES 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 y sistemas dearchivos. Son árboles balanceados de búsqueda en los cuales cada nodo puede poseer más de dos hijos.1 Los árboles B mantienen los datos ordenados y las inserciones y eliminaciones se realizan en tiempologarítmico amortizado.
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 laestructura, 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 permiteun rango variable de nodos hijo, los árboles-B no necesitan re balancearse tan frecuentemente como los árboles binarios de búsqueda auto-balanceables, pero por otro lado pueden desperdiciar memoria,porque los nodos no permanecen totalmente ocupados. Los límites una 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 (Amenudo simplemente llamado árbol 2-3 ), cada nodo sólo puede tener 2 ó 3 nodos hijo.
Un árbol-B se mantiene 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 seencuentran en dispositivos de almacenamiento secundario como los discos rígidos. Al maximizar el número de nodos hijo de cada nodo interno, la altura del árbol decrece, las operaciones para balancearlo sereducen, 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...