Arboles B

ARBOLES B
El problema original comienza con la necesidad de mantener índices en
almacenamiento externo para acceso a bases de datos, es decir, con el grave
problema de la lentitud de estos dispositivos se pretende aprovechar la gran
capacidad de almacenamiento para mantener una cantidad de información
muy alta organizada de forma que el acceso a una clave sea lo más rápido
posible.
Lo quesi es cierto es que la letra B no significa "binario", ya que:
a. Los árboles-B nunca son binarios.
b. Y tampoco es porque sean árboles de búsqueda, ya que en inglés se
denominan B-trees.
c. Tampoco es porque sean balanceados, ya que no suelen serlo.
A menudo se usan árboles binarios de búsqueda para ordenar listas de valores,
minimizando el número de lecturas, y evitando tener que ordenardichas
listas.
Pero este tipo de árboles tienen varias desventajas:
a. Es difícil construir un árbol binario de búsqueda perfectamente
equilibrado.
b. El número de consultas en el árbol no equilibrado es impredecible.
c. Y además el número de consultas aumenta rápidamente con el número
de registros a ordenar.
Para evitar estos inconvenientes se usan árboles-B, sobre todo cuando se
ordenanarchivos, donde se ha convertido en el sistema de indexación más
utilizado.

DEFINICIÓN.
Los B-árboles son árboles cuyos nodos pueden tener un número múltiple de
hijos tal como muestra el esquema de uno de ellos en la figura 1.

Como se puede observar en la figura 1, un B-árbol se dice que es de orden m
si sus nodos pueden contener hasta un máximo de m hijos. En la literatura
tambiénaparece que si un árbol es de orden m significa que el mínimo
número de hijos que puede tener es m + 1 (m claves).
El conjunto de claves que se sitúan en un nodo cumplen la condición:

De forma que los elementos que cuelgan del primer hijo tienen una clave con
valor menor que K1, los que cuelgan del segundo tienen una clave con valor
mayor que K1 y menor que K2, etc. Obviamente, los que cuelgandel último
hijo tienen una clave con valor mayor que la última clave (hay que tener en
cuenta que el nodo puede tener menos de m hijos y por consiguiente menos
de m-1 claves).
Ejemplo de un árbol-B de ORDEN 4 y de profundidad 2.

Las características que debe cumplir un árbol-B son:
•

•
•
•
•
•
•
•

Un parámetro muy importante en los árboles-B es el ORDEN (m). El orden
de unárbol-B es el número máximo de ramas que pueden partir de un
nodo.
Si n es el número de ramas que parten de un nodo de un árbol-b, el
nodo contendrá n-1 claves.
El árbol está ordenado.
Todos los nodos terminales, (nodos hoja), están en el mismo nivel.
Todos los nodos intermedios, excepto el raíz, deben tener entre m/2 y
m ramas no nulas.
El máximo número de claves por nodo es m-1.
El mínimonúmero de claves por nodo es (m/2)-1.
La profundidad (h) es el número máximo de consultas para encontrar una
clave.

BÚSQUEDA EN UN B-ÁRBOL.
Localizar una clave en un B-árbol es una operación simple pues consiste en
situarse en el nodo raíz del árbol, si la clave se encuentra ahí hemos
terminado y si no es así seleccionamos de entre los hijos el que se encuentra
entre dos valores de claveque son menor y mayor que la buscada
respectivamente y repetimos el proceso hasta que la encontremos. En caso de

que se llegue a una hoja y no podamos proseguir la búsqueda la clave no se
encuentra en el árbol. En definitiva, los pasos a seguir son los siguientes:
1. Seleccionar como nodo actual la raíz del árbol.
2. Comprobar si la clave se encuentra en el nodo actual:
1. Si la clave está,fin.
2. Si la clave no está:
Si estamos en una hoja, no se encuentra la clave. Fin.
Si no estamos en una hoja, hacer nodo actual igual al hijo
que corresponde según el valor de la clave a buscar y los
valores de las claves del nodo actual (i buscamos la clave
K en un nodo con n claves: el hijo izquierdo si K < K1, el
hijo derecho si K > Kn y el hijo i-ésimo si Ki < K < Ki+1) y
volver...