Download INTRODUCCIÓN Los B-trees son estructuras de

INTRODUCCIÓN
Los B-trees son estructuras de datos especialmente diseñadas para trabajar con datos
almacenados en memoria externa.
Debido a sus características especiales, los B-trees nos proporcionan una indexación de archivos
de manera eficiente, donde las operaciones realizadas por estas estructuras se realizan en tiempo
logarítmico.
Habiendo varios tipos árboles, a menudo se usan árboles binarios de búsqueda para ordenar listas
de valores, minimizando el número de lecturas, y evitando tener que ordenar dichas listas.
Pero este tipo de árboles tienen varias desventajas:
Es difícil construir un árbol binario de búsqueda perfectamente equilibrado.
El número de consultas en el árbol no equilibrado es impredecible.
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 ordenan ficheros, el
cual se ha convertido en el sistema de indexación más utilizado. Los B-Trees se implementan
usualmente en bases de datos y filesystems.
Los B-TREES
El concepto de B-Tree surge en 1972 (después del viaje a la luna) y fue creado por Bayer y
McCreight en los Laboratorios de Investigación Boeing.
Los autores nunca han mencionado el significado de la "B", algunas personas dicen que es por
"balanced", "broad" o inclusive por "Bayer" o "Boeing".
Lo que si es cierto es que la letra B no significa "binario", ya que:
Los árboles-B nunca son binarios.
Y tampoco es porque sean árboles de búsqueda, ya que en inglés se denominan B-trees.
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 ordenar dichas listas.
Pero este tipo de árboles tienen varias desventajas:

Es difícil construir un árbol binario de búsqueda perfectamente equilibrado.

El número de consultas en el árbol no equilibrado es impredecible.

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 ordenan ficheros, donde
se ha convertido en el sistema de indexación más utilizado.
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
(llaves). Los árboles-B son árboles de búsqueda de “m” ramas, y cada nodo puede almacenar un
máximo de “m-1” claves.
La figura de abajo muestra un árbol binario señalando la ruta que se seguiría para insertar un
nodo nuevo con valor de "15".
Este árbol es el más popular cuando se habla de estructuras de datos. Pero este árbol no
necesariamente tiene que tener únicamente un registro (o una clave), la figura que sigue muestra
un árbol donde cada nodo posee dos claves y 3 ligas o salidas hacia los siguientes niveles. Se
puede observar que para el caso de la raíz el camino de la izquierda representará la ruta hacia
aquellas claves menores que 42, mientras que el de la derecha representará aquellas que sean
mayores que 81 y la del centro aquellas que sean mayores a 42 pero menores a 81.
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 de un nodo de un árbol-b parten n ramas, ese 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ínimo número de claves por nodo es (m/2)-1.

La profundidad (h) es el número máximo de consultas para encontrar una clave.
Las operaciones que se pueden realizar en un árbol-B son básicamente tres:

Insertar una clave

Eliminar una clave

Buscar una clave
GRADO MAXIMO Y MINIMO
Cada vértice salvo que la raíz debe contener por lo menos t − 1 claves (En los B-Tree, se exige
que estén por lo menos 2/3 llenos).
Cada vértice puede contener al máximo 2t − 1 claves. En consecuencia, cada vértice que no es
hoja tiene por lo menos t hijos y al máximo 2t hijos. Un vértice es lleno si
contiene el número máximo permitido de claves.
ALTURA DE UN B-TREE
En los árboles B aplica para la altura a del árbol que (se omite la demostración) para
t ≥ 2,
La búsqueda de una clave en un árbol B no diferencia mucho de la operación de búsqueda en
árboles binarios, el único cambio es que habrá que elegir entre varias alternativas en cada vértice
intermedio.
En el mejor de los casos,la altura de un árbol-B es:
logMn
En el peor de los casos,la altura de un árbol-B es:
Donde M es el número máximo de hijos que puede tener un nodo.
BALANCEO
Una de las grandes ventajas de los B-Trees son sus métodos de inserción y eliminación ya que
mantienen balanceado el árbol a diferencia de los tradicionales donde se podría tener un caso
donde se tenga un acceso secuencial (Figura a) donde no se aprovecha en nada la estructura de
árbol, mientras que el B-Tree siempre mantiene una forma piramidal (Figura b) gracias a su
balanceo.
Gracias a dicho balanceo el "camino" más largo en un B-Tree de "n" llaves contiene a lo
más logd n nodos, donde d es el orden el B-Tree.
INSERCIÓN
Buscamos la posición en dónde insertar la clave. Si el vértice donde deberíamos realizar la
inserción todavía no está lleno, insertamos la clave.
Si el vértice es lleno, habrá que identificar su clave mediana y dividir el vértice en dos partes.
La mediana moverá al vértice padre para marcar la división.
Esto puede causar que el padre también tendrá que dividirse.
Análisis de la operación inserción.
Abajo (Figura a) se presenta un B-Tree de orden 2, cada nodo en el árbol tendrá por consiguiente
entre 2 y 4 llaves (debe existir un contador por cada nodo para saber rápidamente el número
actual de llaves). La inserción es un proceso de 2 pasos, primero se debe realizar una búsqueda
desde la raíz para localizar la "hoja" apropiada para insertar; a continuación la inserción se
realiza y el balanceo se realiza por un procedimiento que mueve desde la hoja hasta la raíz.
Se desea insertar la llave "57" al B-Tree, lo primero que se hace es buscar la posición que
ocuparía, de manera que notamos que su lugar sería en el nodo donde están (53,54,63), de
manera que la llave se agrega y no se hace ningún otro movimiento adicional. (Figura b).
Si se quiere insertar la llave "72" veríamos que su lugar sería en el nodo donde están
(68,69,71,76) el cual como se puede observar ya se encuentra "lleno" de manera que debemos
dividirlo (Split). De manera que las llaves más pequeñas pertenecerán a uno de los nodos
(68,69), las llaves más grandes al otro nodo (72,76) y finalmente la llave intermedia (71) se
promocionará como separador en el nivel superior (acompañando al 66 y 78). Algo muy
importante a considerar es qué sucede cuando esta "promoción" se hace hacia un nodo superior
que ya se encuentra lleno, entonces ese nodo se deberá dividir y en caso de ser necesario se hará
sucesivamente hasta llegar a la raíz en cuyo caso estaremos hablando de que el árbol habrá
crecido en un nivel.
Ejemplo de inserción en un 2-4-Tree.
Asumiremos un nodo con 4 claves máximo y 2 claves mínimo. Insertaremos las claves en forma
ascendente a partir del número 1, lo cual es el peor caso para un árbol binario de búsqueda. Esta
estructura es una variación del B-Tree de grado t; en el caso del ejemplo se denomina 2-4-Tree.
Luego de crear el nodo raíz, se pueden agregar 4 claves. Cuando se agrega el número 5, se
produce un rebalse del nodo raíz; y es preciso dividir las claves del nodo raíz en dos nodos
descendientes, de esta manera el B-Tree crece un nivel. La altura crece por rebalse de las hojas.
Se activan dos punteros en el nodo raíz, como se muestra al centro de la siguiente figura.
Como tenemos 5 claves, podemos dejar los nodos descendientes con dos claves cada una, y de
este modo quedan con el mínimo posible; y además mover la clave 3, del nodo que rebalsó, a la
raíz. Quedando ésta con una sola clave, cumpliendo las propiedades de un B-tree. Luego se
procede al ingreso de las claves 6 y 7, completando las claves de ese nodo, lo cual se muestra en
la figura a la derecha.
Las claves siempre se insertan en las hojas, para cumplir la propiedad de que un B-Tree tiene
hojas de igual profundidad.
Luego, al introducir la clave 8, se rebalsa el nodo, y se lo divide en dos, pasando una clave a la
raíz, ahora ésta tiene tres punteros activos. Luego de ingresadas las claves 9 y 10, se completan
las claves de ese nodo, lo cual se ilustra en siguiente figura, a la derecha.
Luego de ingresar la clave 11, se activa un nuevo puntero en la raíz, debido a la división de un
nodo en dos, el ascenso del 9 y la redistribución de claves. La figura de abajo, a la derecha
muestra el nodo con todas sus claves, luego de ingresadas las claves 12 y 13.
Al insertar la clave 14, se activa el último puntero de la raíz, y además ésta queda con todas sus
claves ocupadas.
Se pueden ingresar las claves 15 y 16, completando las claves del nodo ubicado más a la
derecha.
Al introducir la clave 17, se divide el nodo ascendiendo la clave 15, pero ésta no puede ser
almacenada en la raíz, y se procede a la división del nodo raíz, ascendiendo la clave 9, que se
deposita en una nueva raíz; de este modo se vuelve a incrementar la altura del B-Tree.
Abajo se muestra que después de ingresada la clave 25, se han agregado dos nodos al subárbol
izquierdo, quedando completos los nodos de más a la derecha del segundo y tercer nivel.
Después de ingresar la clave 26, asciende la clave 24, y posteriormente la clave 18.
Cada vez que asciende una clave, se activan nuevos puntero, y se dividen los nodos.
ELIMINACIÓN
Esta operación de manera similar a la inserción requiere localizar la llave a borrar;
posteriormente existen 2 posibilidades:
a) La llave se encuentra en un nodo "hoja"
b) La llave se encuentra en un nodo que no es una hoja.
Para el segundo caso se necesita que una llave adyacente sea encontrada para intercambiar
posiciones y que la operación de búsqueda siga funcionando correctamente. Para ello
simplemente se busca por la "leftmost leaf" o la hoja ubicada más a la izquierda del árbol
derecho de la llave que deseamos eliminar.
Luego eliminamos la llave 17 y para ello debemos colocar en su lugar a la 21, pero algo
importante que no se debe olvidar es que los nodos no pueden tener menos de "d" llaves, de
manera que si en este caso el nodo que contenía a 21 queda con menos de "d" elementos
entonces se produce un "underflow" y debemos hacer una redistribución de llaves.
Para este último caso lo único que se necesita es una llave prestada desde una hoja vecina, pero
como de todas formas se necesitan 2 lecturas a disco una mejor distribución se puede hacer,
dividiendo las llaves que restan entre los dos nodos vecinos de modo que se reducen los accesos
de las próximas eliminaciones en ese nodo.
Obviamente esta distribución de llaves entre los 2 nodos funciona si al menos existen 2d llaves
(sumando ambos nodos) de otra manera lo que se debe hacer es una "concatenación".
La concatenación consiste simplemente en unir las llaves de ambos nodos en uno solo y se "baja"
la llave que servía de separador de manera que sea parte de este nuevo nodo.
Nota: en este caso el nodo que pierde el separador puede caer también en un underflow y el
proceso se repetiría sucesivamente posiblemente hasta llegar a la raíz en cuyo caso el árbol se
reducirá en un nivel.
ESTRUCTURA DE DATOS Y FUNCIONES BASICAS
Estructura de datos.
#define N 5 //2t-1 . t es el grado del B-tree
#define eshoja 1
#define esnodointerno 0
typedef struct nn
{
int clave[N]; //con N claves en el Nodo
struct nn *pn[N+1];
int act; //número de claves activas en el nodo
int hoja; // 1 es hoja; 0 en nodo interno
} nodo, *pnodo;
Creación de un nodo.
pnodo CreaNodo() {
int i;
pnodo p=malloc(sizeof(nodo));
if (p!=NULL)
{
p->act=0;p->hoja=esnodointerno;
for(i=0;i<N+1;i++) p->pn[i]=NULL;
for(i=0;i<N;i++) p->clave[i]=0;
}
return(p);
}
Mostrar nodo y el B-Tree en niveles.
void PrtNodo(pnodo p)
{ int i;
if(p->act==0) printf("Nodo vacío\n");
else for(i=0; i<p->act;i++) printf("%d ", p->clave[i]);
//putchar('\n');
}
void PrtBtree(pnodo p, int level)
{ int i;
if (p!=NULL)
{ for(i=1;i<level;i++) printf(" ");
PrtNodo(p); putchar('\n');
PrtBtree(p->pn[0],level+1);
for(i=1;i<p->act+1;i++) PrtBtree(p->pn[i],level+1);
}
}
Búsqueda de un valor.
En casos prácticos el número de claves en un nodo es elevado, por lo que suele emplearse búsqueda
binaria.
int search(pnodo p, int valor)
{ int i,l,r;
while (p!=NULL)
{
l=0; r=p->act-1;
while (r>=l) //búsqueda binaria
{ i=(l+r)/2;
if (valor<=p->clave[i]) r=i-1;
if (valor>= p->clave[i]) l=i+1;
}
/* Si (valor < p->clave[0]) r=-1, l=0, (l-r)=1
Si (valor > p->clave[p->act-1]) r=p->act-1, l=p->act, (l-r)=1
Si Si (valor == p->clave[i]) r=i-1, l=i+1, (l-r)=2
*/
r++;
/* Lo encontró en posición r. ( l-r=1 => l+1=r => l>r )
Si no lo encontró: r=0 si (valor < p->clave[0])
r=p->act si (valor > p->clave[p->act-1])
*/
if(l>r) return(1); //lo encontró en posición r del arreglo.
else p=p->pn[r]; //busca en descendiente
}
return(0);//no lo encontró
}
Partir un nodo.
//en la posición i-esima de x ingresa la clave central de y.
//Pega el nuevo nodo z, en la posición (i+1) de x.
void split(pnodo x, int i, pnodo y)
{ int j;
pnodo z = CreaNodo();
if (z==NULL){printf("Error creación de nodo. Split"); exit(1);}
z->hoja=y->hoja; z->act=N/2; //z es hermana de y. Y se le copian los (t-1) superiores de y.
for(j=0;j<N/2;j++) z->clave[j]=y->clave[j+N/2+1];//copia claves en z
if(y->hoja ==esnodointerno) //si no es hoja
for(j=0;j<(N/2)+1;j++) z->pn[j]=y->pn[j+(N/2)+1];//copia punteros en z
y->act=N/2; //se desactivan las claves de la mitad superior de y
for(j=x->act+1;j>i ;j--) x->pn[j]=x->pn[j-1];//desplaza punteros en x
x->pn[i+1]=z;
for(j=x->act;j>i ;j--) x->clave[j]=x->clave[j-1];//desplaza claves en x
x->clave[i]=y->clave[N/2]; //asciende clave central del lleno
x->act++;
}
Inserción en nodo que no está lleno.
void insertenolleno(pnodo x,int valor)
{ int i;
if (x->hoja==eshoja)
{ for(i=x->act-1;i>=0 && valor < x->clave[i];i--)
x->clave[i+1]=x->clave[i];//crea un espacio
//i apunta a clave menor que el valor
x->clave[i+1]=valor;x->act++; //solo se inserta en hojas
}
else
{ for(i=x->act-1;i>=0 && valor<x->clave[i];i--); //búsqueda secuencial
i++; //pn[i] apunta a la hoja donde debe insertarse. Ahora i es mayor o igual que cero
if(x->pn[i]->act==N)
{
split(x,i,x->pn[i]);
if(valor> x->clave[i])i++; //fija puntero en el descenso.
}
insertenolleno(x->pn[i],valor); //recursiva por el fondo
}
}
Inserción.
//Debe buscarse antes de insertar. Si la clave ya estaba, cambia B-Tree.
void inserte(pnodo *pbt, int valor)
{ pnodo p=*pbt,s;
if (p ==NULL)
{ p=CreaNodo();//si árbol vacío, crea la raíz
if (p==NULL) {printf("Error creación de nodo raíz"); exit(1);}
else {p->act=1;p->hoja=eshoja;p->clave[0]=valor;*pbt=p;}
}
else if(p->act==N)//nodo raíz lleno
{ s=CreaNodo();if (s==NULL) {printf("Error creación de nueva raíz"); exit(1);}
*pbt=s; s->hoja=esnodointerno; s->pn[0]=p;
split(s,0,p);
insertenolleno(s,valor);
}
else insertenolleno(p,valor);
}
Descartar.
La función descartar puede descomponerse en funciones primitivas como desplazar a la derecha o
izquierda y mezclar dos nodos. Se muestran expandidas, para evitar el llamado a funciones.
int descartar(pnodo *pbt, int valor)
{ int i,j,kp;
pnodo y,z,c,x=*pbt;
if(x==NULL) {printf("Error en descartar: Arbol vacío\n"); return(1);}
if(x->hoja==eshoja)
{//borrar valor;
for(i=x->act-1;i>=0 && valor< x->clave[i];i--);
//i es la clave mayor o igual al valor
if( valor==x->clave[i] )
{
for(j=i;j<x->act-1;j++) x->clave[j]=x->clave[j+1]; //mover claves en x;
x->act--;
if (debug) printf("Borrando %d en hoja\n", valor);
if(x->act==0) //B-Tree queda vacío
{ if (debug) printf("B-Tree queda vacío\n");
*pbt=NULL;
}
return(0);
}
else {printf("Error en descartar: clave %d no existe\n",valor); return(1);}
}
else //no es hoja
{
for(i=x->act-1;i>=0 && valor<x->clave[i];i--);
//v está en x ssi:
if( i>=0 && valor==x->clave[i] ) //valor está en x->clave[i]. i está entre 0 y x->cnt-1
{ y=x->pn[i]; // y apunta al hermano izquierdo
z=x->pn[i+1]; // z apunta al hermano derecho.
if (y->act>N/2)
{ kp=y->clave[(y->act)-1]; //mayor descendiente hijo izquierdo
x->clave[i] =kp;
if (debug) printf("Borrando con préstamo izquierdo en nodo %d\n",kp);
descartar(&y,kp);
}
else if (z->act>N/2)
{kp=z->clave[0]; //menor descendiente hijo derecho
x->clave[i]=kp;
if (debug) printf("Borrando con préstamo derecho en nodo %d\n",kp);
descartar(&z,kp);
}
else //merge y con z
{y->clave[y->act]=x->clave[i]; y->act++;
//copiar los de z a continuación en y;
for(j=0;j<z->act;j++) {y->clave[y->act+j]=z->clave[j];}
if (y->hoja==esnodointerno)
for(j=0;j<z->act+1;j++) {y->pn[y->act+j]=z->pn[j];}//copia punteros
y->act+=z->act;
for(j=i;j<x->act-1;j++) x->clave[j]=x->clave[j+1]; //mover claves en x;
for(j=i;j<x->act;j++) x->pn[j]=x->pn[j+1];//desplaza punteros en x
x->act--;free(z);
if(x->act==0) //B-Tree disminuye altura
{free(x);
if (debug) printf("Disminuye altura B-Tree\n");
*pbt=y;
}
if (debug) printf("Borrando con fusión de derecho en nodo izquierdo %d\n",valor);
descartar(&y,valor);
}
}
else //valor está en un descendiente de x
//pn[i] apunta a la página en la que está el valor, o cuyos descendientes contienen el valor.
{i++; // ahora i es mayor o igual que cero
c=x->pn[i];
if(c->act==N/2) //nodo descendiente con claves mínimas
{
if(i==0) y=NULL; else y=x->pn[i-1]; //si c no tiene hermano izquierdo: y=NULL
if(i==x->act) z=NULL; else z=x->pn[i+1]; //si c no tiene hermano derecho: z=NULL
if(y!=NULL && y->act>N/2)
{ for(j=c->act; j>0;j--) c->clave[j]=c->clave[j-1]; //mueve c a la derecha
if(c->hoja==esnodointerno)
for(j=c->act+1;j>0;j--) c->pn[j]=c->pn[j-1]; //mueve punteros de c a la derecha
c->clave[0]=x->clave[i-1];//baja uno de x a c
c->act++; //c queda con mas de N/2.
x->clave[i-1]=y->clave[y->act-1]; //mayor de y lo sube a x
c->pn[0]=y->pn[y->act]; //hijo de y se cuelga como hijo de c
y->act--;
if (debug)
{ printf("Deja descendiente con más del mínimo\n");
PrtBtree(btree,1);
printf("Borrando %d en nodo descendiente con prestamo de izquierdo \n",valor);
}
descartar(&c,valor);
}//y es nulo o y no tiene (t-1)
else if (z!=NULL && z->act>N/2)
{ c->clave[c->act]=x->clave[i];//baja central de x a c.
c->act++; //c queda con mas de N/2.
c->pn[c->act]=z->pn[0]; //pega menores de z a mayores del mayor de c
x->clave[i]=z->clave[0]; //el menor de z lo sube a x.
for(j=0;j<z->act-1;j++) z->clave[j]=z->clave[j+1]; //mueve claves de z a la izquierda
if (z->hoja==esnodointerno)
for(j=0;j<z->act;j++) z->pn[j]=z->pn[j+1];//mueve punteros de z a la izquierda
z->act--;
if (debug)
{ printf("Deja descendiente con más del mínimo\n");
PrtBtree(btree,1);
printf("Borrando %d en nodo descendiente con préstamo de derecho \n",valor);
}
descartar(&c,valor);
}
else //merge
{ if(y==NULL) //merge c con z;
{ c->clave[c->act]=x->clave[i]; c->act++;
for(j=0;j<z->act;j++) {c->clave[c->act+j]=z->clave[j]; }
if(c->hoja==esnodointerno)
for(j=0;j<z->act+1;j++) {c->pn[c->act+j]=z->pn[j]; }
c->act+=z->act;
//correr x (que no es hoja, tiene descendientes)
for(j=i;j<x->act-1;j++) x->clave[j]=x->clave[j+1]; //mover claves a la izquierda en x;
for(j=i+1;j<x->act;j++) x->pn[j]=x->pn[j+1];//desplaza punteros a la izquierda en x
x->pn[i]=c;
x->act--;
if(x->act==0) //B-Tree disminuye altura
{ free(x);
*pbt=c;
if (debug) printf("Disminuye altura\n");
}
free(z);
if (debug)
{ printf("mezcla c con z. Deja descendiente con más del mínimo por fusión\n");
PrtBtree(btree,1);
printf("Borrando %d en nodo descendiente con fusión de derecho \n",valor);
}
descartar(&c,valor);
}
else // merge c con y; Código es similar al del if.
{
y->clave[y->act]=x->clave[i-1]; y->act++;
for(j=0;j<c->act;j++) {y->clave[y->act+j]=c->clave[j]; }
if (y->hoja==esnodointerno)
for(j=0;j<c->act+1;j++) {y->pn[y->act+j]=c->pn[j]; }
y->act+=c->act;
//correr x
for(j=i-1;j<x->act-1;j++) x->clave[j]=x->clave[j+1]; //mover claves en x;
for(j=i;j<x->act;j++) x->pn[j]=x->pn[j+1];//desplaza punteros en x
x->pn[i-1]=y;
x->act--;
if(x->act==0) //B-Tree disminuye altura
{ free(x);
*pbt=y;
if (debug) printf("Disminuye altura\n");
}
free(c);
if (debug)
{ printf("mezcla c con y\n");
PrtBtree(btree,1);
printf("Borrando %d en nodo descendiente con fusión en izquierdo \n",valor);
}
descartar(&y,valor);
}
}
}
else //nodo descendiente con claves mayores que el número mínimo. ( >= t)
{
if (debug) printf("Borrando %d en nodo descendiente con más claves que el mínimo\n",valor);
descartar(&c,valor);
}
}
return(0); //finalizan recursiones por el fondo.
}
}
Test de las funciones.
pnodo btree=NULL;
int main(void)
{ int i;
/* Test básico
PrtNodo(btree);
descartar(&btree,1);
inserte(&btree,1);
PrtNodo(btree);
descartar(&btree,1);
PrtNodo(btree);
*/
for(i=1;i<=Nclaves;i++) inserte(&btree,i);
if (debug) PrtBtree(btree,1);
for(i=Nclaves;i>0;i--) descartar(&btree,i);
for(i=1;i<Nclaves;i++) inserte(&btree,i);
for(i=1;i<Nclaves;i++) descartar(&btree,i);
for(i=Nclaves;i>0;i--) inserte(&btree,i);
if (debug) PrtBtree(btree,1);
for(i=1;i<=Nclaves;i++) descartar(&btree,i);
for(i=Nclaves;i>0;i--) inserte(&btree,i);
for(i=Nclaves;i>0;i--) descartar(&btree,i);
//test de búsquedas
for(i=1;i<=Nclaves;i++) inserte(&btree,i);
for(i=1;i<=Nclaves;i++)
if (search(btree,i)==0) printf("Error no encuentra clave %d que está en B-tree\n",i);
for(i=Nclaves+1;i<=Nclaves+10;i++)
if (search(btree,i)) printf("Encuentra clave %d que no está en B-tree\n",i);
for(i=1;i<=Nclaves;i++) descartar(&btree,i);
printf("Ok\n");
return (0);
}