9 Ficheros indicados árboles-B (B-Trees)

En preparación.

Los árboles-B son árboles de búsqueda equilibrados, es decir, la profundidad, y por lo tanto el número de lecturas máximo para cualquier búsqueda, está determinada por el número de nodos que contenga el árbol.

La desventaja es que son más difíciles de manejar, son estructuras complejas, pero muy versátiles y potentes, como veremos.

Hay un artículo sobre el tema en árboles-B, aunque aplicado a arrays. En este caso lo aplicaremos a ficheros.

Los árboles-B pueden ser de cualquier 'orden'. Cada nodo del árbol puede contener un número de claves que decidiremos en función de varios parámetros, de modo que se minimicen los accesos al disco:

  • Tamaño de la clave.
  • Tamaño del cluster.

Para nuestro ejemplo consideraremos que el cluster tiene x bytes, y las claves por las que indicaremos el fichero son de 8 bytes.

Cada registro correspondiente a un nodo de un árbol-B contiene n-1 claves y n punteros a nodos. Siendo el tamaño de una clave long_clave y el tamaño de un puntero long_puntero, tenemos:

(n-1) * (long_clave + long_puntero) + n * long_puntero <= long_cluster

Comentarios de los usuarios (2)

Andrés Velosa
2012-06-20 22:51:06

Me llamo Andrés y estoy haciendo un sencillo programa en el cual calculamos la velocidad de 10 misiles, la pregunta es como hago para darle una instrucción que sólo permita datos numéricos, ya que al poner letras se descontrola.

Agradezco su valiosa colaboración y anexo el código fuente.

#include<iostream>

#include<iostream.h>

#include<conio.h>

#include<math.h>

using namespace std;

const float g=9.86;

const float PI=3.1416;

//Programa que calcula la distancia de recorrida en linea recta recorrida por un Misil

// "Estructura"Separamos un espacio de Memoria el cual se va a llamar proyectil y tiene

seis//partes que son

//espacios cada uno de tipo flotante con un respectivo nombre

struct proyectil{

float j;

float h;

float posh; //Por si acaso

float pos_j;

float VelocidadInicial;

float angulo;

float PosX;

float PosY;

float Tiempo; //se agrego 2 datos tiempo y distancia para guardar en la estructura proyectil

float Distancia;

float am;

};

float Cambio_grado_rad(proyectil m1){

float radianes;

radianes=m1.angulo*PI/180;

return(radianes);

}

float Tiempo_Aire(proyectil m1){

float Ta;

float r;

r=Cambio_grado_rad(m1);

Ta=(2*m1.VelocidadInicial*sin(r))/g;

return(Ta);

}

float Distancia(proyectil m1, float ta){

float distancia;

float r;

r=Cambio_grado_rad(m1);

distancia = (m1.VelocidadInicial*m1.VelocidadInicial)*sin(2*(r))/g;

return(distancia);

}

float PosX (proyectil m1, float ta){

float posh;

float j;

float h;

float r;

r=Cambio_grado_rad (m1);

posh=m1.j+(m1.VelocidadInicial*(cos(r))*((m1.VelocidadInicial*(sin(r))))+((sqrt

(m1.VelocidadInicial*m1.VelocidadInicial)*((sin(r)*sin(r)))+(2*g*j)))/g);

return (posh);}

float PosY(proyectil m1){

float j;

float pos_j;

float r;

r=Cambio_grado_rad (m1);

pos_j=m1.j+(((m1.VelocidadInicial*m1.VelocidadInicial)*((sin (r)) * (sin (r))))/(2*9.86));

return (pos_j);}

void Imprimir(proyectil m1[], int i); //procedimiento que imprime los datos y resultados de los 10

proyectiles

int main(int argv, char *argc[] )

{

proyectil misil[9]; //se crea un arreglo de la estructura proyectil

float d, ta, f, gh;

int x=0;

float h;

float posh;

float j; //altura máxima

float pos_j;

cout<<"*************Instrucciones del programa************"<<endl;

cout<<"1. El programa calcula la distancia, en linea recta,en la que cae un proyectil"<<endl;

cout<<"2. Para ejecutar el programa escriba la velocidad inicial para lanzar cada proyectil y el

angulo de lanzamiento"<<endl;

for(int i=1; i<11; i++){ //con el for se pide al usuario que ingrese los datos y los

guarda para cada

cout<<"Proyectil No. "<<i<<" "<<endl<<"Angulo en grados: "; // uno de los 10 misiles.

cin>>misil[i].angulo;

cout<<"Velocidad inicial en metros/segundo: ";

cin>>misil[i].VelocidadInicial;

cout<<"Digite la posición en x"<<endl; //modif

cin>>misil[i].h;

cout<<"Digite la posición en y"<<endl; //modif

cin>>misil[i].j;

ta=Tiempo_Aire(misil[i]);

misil[i].Tiempo=ta;

//misil[i].PosX=misil[i].PosY=0;

d=Distancia(misil[i], ta);

misil[i].Distancia=d;

cout<<endl;

//modificaciones

f=PosX (misil[i],ta);

misil[i].PosX =f;

gh=PosY(misil[i]);

misil[i].PosY =gh;

//misil[i].h=h;

//misil[i].j=j;

}

Imprimir (misil, x);

system("PAUSE");

return EXIT_SUCCESS;

}

void Imprimir(proyectil m1[], int i){ //imprime mediante un for los datos de los 10

proyectiles

cout<<" Estos son los datos de los 10 proyectiles: "<<endl;

cout<<"Proy.No.--Angulo--Vel.--PosX0--PosY0-- t vuelo--distancia --PosXf--H.MAX "<<endl;

for( i=1; i<11; i++){

cout<<"

*************************************************************************"<<endl;

cout<<" | "<<i<<" | "<<m1[i].angulo<<" | "<<m1[i].VelocidadInicial<<" | "<< m1[i].h<<" |

"<< m1[i].j<<" | "<<m1[i].Tiempo<<"|"<<m1[i].Distancia<<"|"<<m1[i].PosX<< "|"<<m1[i].PosY<<

"|"<<endl;

cout<<endl;

}

}

Márquez
2012-10-13 02:43:33

¡Un saludo a todos! Tengo entendido que el número de nodos recorridos en las distintas operaciones de Árboles B, es proporcional a la altura 'h' del árbol. Por lo tanto:

- La operación de búsqueda accederá a: h+1 nodos.

- La inserción en el peor caso tratará: 2h+1 nodos, si se debe hacer la partición a todos los niveles.

- El eliminado visitará: 3h+1 nodos, en el peor caso.

Permitanme ilustrarles la duda: (suponiendo un orden 5)

 
      (6)
   /        \
(4)(5)     (7)(8)

.La altura del árbol B es 2.

.Si se quiere buscar una clave, según la fórmula accederíamos a (2)+1=3 nodos, " según mi parecer deberíamos acceder a 2 nodos en elpeor caso ¿no? "

.¿Para inserción ,no debería acceder sólo a la altura h+el nodo a insertar?.

.¿Para eliminado,por qué 3h+1 ?.

Cualquier respuesta e idea que tengan me van a servir mucho!

Gracias!!