Introducción

Una de las tareas fundamentales del cómputo es el procesamiento de datos. A lo

largo de la historia de la Ciencia de la Computación se han propuesto diversas
estructuras como el B+-Tree, que permiten el almacenamiento y búsqueda de datos
de manera eficiente. Actualmente, el desarrollo tecnológico de los dispositivos
móviles los hace una plataforma interesante para estas tareas y el desarrollo de
aplicaciones tipo data-driven, sin embargo, a pesar de los progresos tecnológicos,
siguen existiendo restricciones en cuanto a su capacidad de memoria, poder de
procesamiento y consumo de energía. El presente trabajo describe todo lo
necesario para el estudio de los B-Tree, definición, operaciones, aplicaciones, etc.
 B-Tree
Los B-Tree o árboles-B son estructuras de datos de árbol que se encuentran
comúnmente en las implementaciones de bases de datos y sistemas de archivos.
Son árboles binarios de búsqueda en los cuales cada nodo puede poseer más de
dos hijos.

Los B-Tree surgieron en 1972 creados por R. Bayer y E. McCreight. 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.

Definición

La idea tras los B-Tree 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.

Definición Técnica
B-Tree 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.

Un árbol-B de orden M (el máximo número de hijos que puede tener cada nodo) es
un árbol que satisface las siguientes propiedades:

1. Cada nodo tiene como máximo M hijos.

2. Cada nodo (excepto raíz y hojas) tiene como mínimo M/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 ciertas
condiciones:
1. El primero tiene valor menor que r1.
 2. El segundo tiene valor mayor que r1 y menor que r2, etc.
3. El último hijo tiene valor mayor que rm.

Además de estas características, los árboles B tienen que cumplir un cierto orden:
● Los nodos dentro de una página mantienen un orden ascendente de
izquierda a derecha.
● Cada nodo es mayor que los nodos situados a su izquierda.
● Cada nodo es mayor que los nodos situados a su derecha.
Evidentemente se trata de un árbol o mejor dicho de la generalización de un árbol
que permite varias "salidas" o ligas desde sus nodos, de hecho cada nodo contiene
varios registros.

Estructura de un Nodo
Cada elemento de un nodo interno actúa como un valor separador, que lo divide en
sub árboles.
Los nodos internos de un árbol B, es decir los nodos que no son hoja, usualmente
se representan como un conjunto ordenado de elementos y punteros a los hijos.
Cada nodo interno contiene un máximo de U hijos y, con excepción del nodo raíz, un
mínimo de L hijos. Esta relación entre U y L implica que dos nodos que están a
medio llenar pueden juntarse para formar un nodo legal, y un nodo lleno puede
dividirse en dos nodos legales. Estas propiedades hacen posible que el árbol B se
ajuste para preservar sus propiedades ante la inserción y eliminación de elementos.
Los nodos hoja tienen la misma restricción sobre el número de elementos, pero no
tienen hijos, y por tanto carecen de punteros. El nodo raíz tiene límite superior de
número de hijos, pero no tiene límite inferior. Algunos árboles balanceados guardan
valores sólo en los nodos hoja, y por lo tanto sus nodos internos y nodos hoja son
de diferente tipo. Los árboles B guardan valores en cada nodo, y pueden utilizar la
misma estructura para todos los nodos. Sin embargo, como los nodos hoja no
tienen hijos, una estructura especial para éstos mejora el funcionamiento.

Operaciones básicas de los B-Tree

● Búsqueda

Localizar una clave en un B-Tree 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 clave que
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 al segundo paso.

● Inserción

La operación de inserción en un árbol B es relativamente sencilla, sólo hay un caso

en el que este procedimiento se complica ligeramente.
La primera acción a realizar en la operación de inserción es localizar el lugar
adecuado en el árbol donde se insertará el nuevo elemento. De esta forma
aseguraremos que la propiedad de orden se mantiene.
Una vez localizado el lugar adecuado, hay que tener en cuenta el número de nodos
que tiene la página destino del nuevo elemento. Si tiene menos de 2n, entonces se
inserta el nuevo nodo y se da por finalizada la operación de inserción.
La complejidad se produce cuando la página destino está al completo de su
capacidad, es decir, tiene 2n nodos. En estos casos el procedimiento a seguir es el
siguiente:
1. Insertar el nodo como si realmente tuviese sitio libre.
2. Extraer el nodo que ocupa la posición del medio e insertarlo en la página
padre. Si no hubiese página padre se crearía una nueva página con ese
nodo.
3. Dividir la página original en dos nuevas páginas, cada una de ellas con n
elementos. Estas páginas serán los hijos derechos e izquierdo del nodo que
promocionó a la página superior.
4. Si la página a la que promociona el nodo mediano también se encuentra
completa, se repetiría la misma operación de división y promoción.
Como consecuencia de que todas las hojas deben estar en el último nivel, los
árboles B crecen hacia arriba, característica que también los diferencia del resto de
árboles. Este crecimiento se produce cuando la inserción de un nodo en una página
completa provoca su división.
Vamos a ver un ejemplo de inserción en árboles B.

Sobre este árbol se inserta el elemento 18. La página que le corresponde es la que
contiene los elementos 10,15,17,19. Al estar completa se produce el ascenso del
nodo mediano (el 17) y la división en dos páginas de la página original.

● Eliminación

Es localizar y eliminar el elemento, y luego corregir, o hacer una única pasada de

arriba a abajo por el árbol, pero cada vez que se visita un nodo, reestructurar el
árbol para que cuando se encuentre el elemento a ser borrado, pueda eliminarse sin
necesidad de continuar reestructurando

Se pueden dar dos problemas al eliminar elementos: primero, el elemento puede ser
un separador de un nodo interno. Segundo, puede suceder que al borrar el
elemento, el número de elementos del nodo quede debajo de la cota mínima. Estos
problemas se tratan a continuación en orden.

Eliminación en un nodo hoja

● Se busca el valor a eliminar.
● Si el valor se encuentra en un nodo hoja, se elimina directamente la clave,
posiblemente dejándolo con muy pocos elementos; por lo que se requerirán
cambios adicionales en el árbol.

Eliminación en un nodo interno

Cada elemento de un nodo interno actúa como valor separador para dos sub
árboles, y cuando ese elemento es eliminado, pueden suceder dos casos. En el
primero, tanto el hijo izquierdo como el derecho tienen el número mínimo de
elementos, L-1. Pueden entonces fundirse en un único nodo con 2L-2 elementos.
En el segundo caso, uno de los dos nodos hijos tiene un número de elementos
mayor que el mínimo. Entonces se debe hallar un nuevo separador para estos dos
sub árboles. Nótese que el mayor elemento del árbol izquierdo es el mayor
elemento que es menor que el separador. De la misma forma, el menor elemento
del subárbol derecho es el menor elemento que es mayor que el separador. Ambos
elementos se encuentran en nodos hoja, y cualquiera de los dos puede ser el nuevo
separador.
● Si el valor se encuentra en un nodo interno, se escoge un nuevo separador
(puede ser el mayor elemento del subárbol izquierdo o el menor elemento del
subárbol derecho), se elimina del nodo hoja en que se encuentra, y se
reemplaza el elemento a eliminar por el nuevo separador.
● Como se ha eliminado un elemento de un nodo hoja, se debe tratar este caso
de manera equivalente.
Utilización de los árboles B

Los árboles B tienen un campo de aplicación similar a los árboles binarios de

búsqueda, ya que también son árboles de búsqueda. La característica que los
diferencia es la ausencia de la restricción de 2 hijos por nodo que tienen los
binarios.

Aplicación B-Tree
Las operaciones que se presentan en esta aplicación son las siguientes:
● Insertar: Acción a través de la cual se pueden insertar nuevos elementos en
la estructura de datos. Se presenta un diálogo para la introducción del nuevo
valor.
● Borrar: Si se desea borrar un nodo se debe seleccionar dicho nodo y pulsar el
botón Borrar.
● Vaciar árbol: Esta acción elimina todos los elementos presentes en la lista.
 ● Cambiar tamaño página: A través de esta opción se puede configurar el
tamaño de las páginas del árbol.
● Camino recorrido: En este lugar se muestran los diferentes nodos por los que
fue pasando (con los que se comparó), el elemento insertado o eliminado.

Utilización
Los árboles B constituyen una categoría muy importante de estructuras de datos,
que permiten una implementación eficiente de conjuntos y diccionarios, para
operaciones de consulta y acceso secuencial.
Los árboles B son ampliamente utilizados en la representación de índices en bases
de datos. De hecho, este tipo de árboles están diseñados especıficamente para
aplicaciones de bases de datos, donde la característica fundamental es la
predominancia del tiempo de las operaciones de entrada/salida de disco en el
tiempo de ejecución total. En consecuencia, se busca minimizar el número de
operaciones de lectura o escritura de bloques de datos del disco duro o soporte
físico.

Implementación en Java
import javax.swing.*;
import java.io.*;
//Arboles Btree
class Btree{
Bnodo p=new Bnodo();
Bnodo Xder = new Bnodo();
Bnodo Xizq = new Bnodo();
NodoPr X;
Bnodo Xr;
String salida="",imps="";
boolean EmpA = false,Esta=false;
//***************************************
//*****Inserta un nodo en un arbol b*****
//***************************************
void Inserta(NodoPr clave){
Insertaa(clave,p);
}
//auxiliar de inserta nodo
 public void Insertaa(NodoPr clave, Bnodo raiz){
Empujar(clave,raiz);
if(EmpA){
p=new Bnodo();
p.Cuentas= 1;
p.Claves[0]=X;
p.Ramas[0]=raiz;
p.Ramas[1]=Xr;
}
JOptionPane.showMessageDialog(null,"Insercion Completa");
}
//Empuja los elementos del arbol
public void Empujar(NodoPr clave, Bnodo raiz){
int k=0;
Esta=false;
if(Vacio(raiz)){
EmpA=true;
X=clave;
Xr=null;
}
else{
k=BuscarNodo(clave, raiz);
if(Esta){
JOptionPane.showMessageDialog(null,"No hay claves repetidas");
EmpA=false;
}
else{
Empujar(clave, raiz.Ramas[k]);
if(EmpA){
if(raiz.Cuentas < 4){
EmpA = false;
MeterHoja(X, raiz, k);
}
else{
EmpA = true;
DividirN(X, raiz, k);
}
}
}
}
 }
//Meter hoja
public void MeterHoja(NodoPr clave, Bnodo raiz, int k){
int i = raiz.Cuentas;
while (i != k){
raiz.Claves[i] = raiz.Claves[i-1];
raiz.Ramas[i+1] = raiz.Ramas[i];
--i;
}
raiz.Claves[k] = clave;
raiz.Ramas[k+1] = Xr;
raiz.Cuentas = ++raiz.Cuentas;
}
//Dividir nodo
public void DividirN(NodoPr Clave, Bnodo Raiz, int k){
int pos=0;
int Posmda=0;
if (k <= 2)
Posmda = 2;
else{
Posmda = 3;
}
Bnodo Mder = new Bnodo();
pos = Posmda+1;
while (pos != 5){
Mder.Claves [(pos - Posmda)-1] = Raiz.Claves[pos-1];
Mder.Ramas [pos - Posmda] = Raiz.Ramas[pos];
++pos;
}
Mder.Cuentas = 4 - Posmda;
Raiz.Cuentas = Posmda;
if (k <= 2)
MeterHoja(Clave, Raiz, k);
else{
MeterHoja(Clave, Mder, (k - Posmda));
}
X = Raiz.Claves[Raiz.Cuentas-1];
Mder.Ramas[0] = Raiz.Ramas[Raiz.Cuentas];
Raiz.Cuentas = --Raiz.Cuentas;
Xr=Mder;
 }
//****************************************
//*****Borrar un elemento del arbol b*****
//****************************************
void Eliminar(NodoPr clave){
if(Vacio(p)){
JOptionPane.showMessageDialog(null,"No hay elementos");
}
else
Eliminara(p,clave);
}
public void Eliminara(Bnodo Raiz, NodoPr clave){
try{
EliminarRegistro(Raiz, clave);
}
catch(Exception e){
Esta=false;
}
if (!Esta)
JOptionPane.showMessageDialog(null,"No se encontro el elemento");
else{
if (Raiz.Cuentas == 0)
Raiz = Raiz.Ramas[0];
p=Raiz;
JOptionPane.showMessageDialog(null,"Eliminacion completa");
}
}
//Elimina el registro
public void EliminarRegistro(Bnodo raiz, NodoPr c){
int pos = 0;
NodoPr sucesor;
if (Vacio(raiz))
Esta = false;
else{
pos = BuscarNodo(c, raiz);
if (Esta){
if (Vacio(raiz.Ramas[pos-1]))
Quitar(raiz, pos);
else{
Sucesor(raiz, pos);
 EliminarRegistro (raiz.Ramas[pos], raiz.Claves[pos-1]);
}
}
else{
EliminarRegistro(raiz.Ramas[pos], c);
if ((raiz.Ramas[pos] != null) && (raiz.Ramas[pos].Cuentas < 2))
Restablecer(raiz, pos);
}
}
}
//Busca el sucesor
public void Sucesor (Bnodo raiz, int k){
Bnodo q=raiz.Ramas[k];
while(!Vacio(q.Ramas[0]))
q=q.Ramas[0];
raiz.Claves[k-1]=q.Claves[0];
}
//Combina para formar un nodo
public void Combina(Bnodo raiz, int pos){
int j;
Xder = raiz.Ramas[pos];
Xizq = raiz.Ramas[pos-1];
Xizq.Cuentas++;
Xizq.Claves[Xizq.Cuentas-1] = raiz.Claves[pos-1];
Xizq.Ramas[Xizq.Cuentas] = Xder.Ramas[0];
j = 1;
while (j != Xder.Cuentas+1){
Xizq.Cuentas++;
Xizq.Claves[Xizq.Cuentas-1] = Xder.Claves[j-1];
Xizq.Ramas[Xizq.Cuentas] = Xder.Ramas[j];
j++;
}
Quitar(raiz, pos);
}
//Mueve a la derecha
public void MoverDer(Bnodo raiz, int pos){
int i = raiz.Ramas[pos].Cuentas;
while (i != 0){
raiz.Ramas[pos].Claves[i] = raiz.Ramas[pos].Claves[i-1];
raiz.Ramas[pos].Ramas[i+1] = raiz.Ramas[pos].Ramas[i];
 --i;
}
raiz.Ramas[pos].Cuentas++;
raiz.Ramas[pos].Ramas[1] = raiz.Ramas[pos].Ramas[0];
raiz.Ramas[pos].Claves[0] = raiz.Claves[pos-1];
raiz.Claves[pos-1] = raiz.Ramas[pos-1].Claves[raiz.Ramas[pos-1].Cuentas-1];
raiz.Ramas[pos].Ramas[0] = raiz.Ramas[pos-1].Ramas[raiz.Ramas[pos-1].Cuentas];
raiz.Ramas[pos-1].Cuentas--;
}
//Mover a la izquierda
public void MoverIzq(Bnodo raiz, int pos){
int i;
raiz.Ramas[pos-1].Cuentas++;
raiz.Ramas[pos-1].Claves[raiz.Ramas[pos-1].Cuentas-1] = raiz.Claves[pos-1];
raiz.Ramas[pos-1].Ramas[raiz.Ramas[pos-1].Cuentas] = raiz.Ramas[pos].Ramas[0];
raiz.Claves[pos-1] = raiz.Ramas[pos].Claves[0];
raiz.Ramas[pos].Ramas[0] = raiz.Ramas[pos].Ramas[1];
raiz.Ramas[pos].Cuentas--;
i = 1;
while (i != raiz.Ramas[pos].Cuentas+1){
raiz.Ramas[pos].Claves[i-1] = raiz.Ramas[pos].Claves[i];
raiz.Ramas[pos].Ramas[i] = raiz.Ramas[pos].Ramas[i+1];
i++;
}
}
//Quita el elemento
public void Quitar (Bnodo raiz, int pos){
int j = pos + 1;
while (j != raiz.Cuentas+1){
raiz.Claves [j-2] = raiz.Claves[j-1];
raiz.Ramas [j-1] = raiz.Ramas[j];
j++;
}
raiz.Cuentas--;
}
//Restablece el nodo
public void Restablecer(Bnodo raiz, int pos){
if (pos>0){
if (raiz.Ramas[pos-1].Cuentas > 2)
MoverDer(raiz, pos);
 else
Combina(raiz, pos);
}
else{
if (raiz.Ramas[1].Cuentas > 2)
MoverIzq(raiz, 1);
else
Combina(raiz, 1);
}
}
//Retorna true si el arbol esta vacio
public boolean Vacio(Bnodo raiz){
return (raiz==null || raiz.Cuentas==0);
}
//Buscar retorna true si lo encuentra y la posicion
public int BuscarNodo(NodoPr clave, Bnodo raiz){
int j=0;
if(clave.nump < raiz.Claves[0].nump){
Esta = false;
j=0;
}
else{
j = raiz.Cuentas;
while (clave.nump < raiz.Claves[j-1].nump && j>1)
--j;
Esta = (clave.nump == raiz.Claves[j-1].nump);
}
return j;
}
//miembro
public boolean Miembro(NodoPr clave, Bnodo raiz){
boolean si=false;
int j=0;
if(!Vacio(p)){
if(clave.nump < raiz.Claves[0].nump){
si = false;
j=0;
}
else{
j = raiz.Cuentas;
 while (clave.nump < raiz.Claves[j-1].nump && j>1)
--j;
si = (clave.nump == raiz.Claves[j-1].nump);
}
}
return si;
}
 Bibliografía

http://es.wikipedia.org/wiki/%C3%81rbol-B
http://fibonaccidavinci.wordpress.com/2010/01/10/arbol-b-en-java/
http://estructuradedatos-grupo1.blogspot.com/2009/04/arboles-b.html
http://www.virtual.unal.edu.co/cursos/ingenieria/2001412/capitulos/cap8/85.html
http://es.wikipedia.org/wiki/%C3%81rbol_B%2B