Árvore B e Hashing

Prévia do material em texto

Prova de ED2 - Integral - 08-11-12
(3 pontos) Fazer uma função que receba como parametros MIN e MAX, a função percorre uma árvore B e imprime os valores que estiverem entre o intervalo MIN MAX.
algoritmo que o david fez, da pra colocar mais 2 condições pra melhorar a perfomace, porém assim já ta no pêlo e vale 3 pontos;
VALEU DAVIDAO!!!
typedef struct arvore_b
{
   int keycount;//Numero de chaves no bloco
   int key[n];//onde N eh ordem-1
   int pointer[m];//onde m eh ordem. ponteiro nulo = -1
   int RRN[n];
}arvore_b
void buscar(int min, int max, int pointer)
{
   //considere o arquivo de arvore jah aberto e com nome arq_arvore;
   arvore_b bloco;
   int i;
   if(pointer != -1){ 
       fseek(arq_arvire, pointer, 0);
       fread(&bloco, sizeof(arvore_b), 1, arq_arvore);
       for(i=0; i<bloco.keycount; i++)
       {
           if(bloco.key[i] >= min && bloco.key[i] <= max)
           {            
               buscar(min,max,bloco.pointer[i]);
               printf("%d ", bloco.key[i]);
               if((i+1) == keycount) buscar(min,max,bloco.pointer[i+1]);
           }
       }
   }
}
Grego says: quem mandou esse algoritmo abaixo?
Não sei quem mandou mas Tá na Wikipedia! Só foram adicionados os parâmetros.
Pois é...ta errado, no faz sentido!
Não mesmo.. Falta uma estrutura de repetição para buscar em todas as páginas..
É o que tá escrito parece não é? Só falta os códigos heuhuehe
R: Decora isso e garante 0,5 uahiuahhiaaia
ED2 201x?????? sad. Ad Eternum
Achei a solução: http://www.anhanguera.com/graduacao/cursos/ciencia_computacao.php
Não é pra fazer busca. É pra percorrer toda(ta, nem toda) a árvore! Dai quando o valor que você ta lendo ta entre o intervalo MIN e MAX você imprime. A função não retorna nada.
Ta certo?
sim, ate um bixo saberia
a galera ai não tava parecendo q sabia uHAUHAU
void intervalo(bTree raiz, int min, int max){
	int i=0;
	for(i=0; i< raiz.n;i++){
		intervalo(raiz->ponteiro[i],min,max);
		if(raiz->chave[i]>=min && raiz->chave[i]<=max)
			printf(“%d”,raiz->chave[i]);
}
intervalo(raiz->ponteiro[raiz.n],min,max);
}
(1 ponto) Como funciona o Merge Sort? Qual o seu gargalo? Como diminuir o gargalo?
Resposta:
Como funciona?
Utiliza a idéia do heapsort, mas organizando o arquivo em corridas (subarquivos ordenados).
- Fase 1: Geração das corridas
Segmentos do arquivo são ordenados em memória RAM usando algum método de ordenação interna (heapsort) e gravados em disco (subarquivo).
- Fase 2: Intercalação
As corridas geradas são intercaladas, formando o arquivo ordenado.
Qual o gargalo?
O gargalo ocorre durante a leitura das corridas armazenadas na memória (secundária) para realizar o merge. 
o gargalo acontece pq para montar o arquivo final eh preciso acessar todos os subarquivos gerados nas corridas do passo1, ou seja, sao varios seeks, o que torna essa parte um gargalo (onde há mais processamento).
Como diminuir o gargalo?
Alocar mais Hardware, realizar o merge em mais de um passo, aumentar no algoritmo o tamanho de cada corrida, encontrar maneiras de sobrepor as operações de entrada e saída.
(1 ponto) Porque a árvore B é balanceada de acordo com a sua altura? Qual a complexidade do melhor e do pior caso?
Resposta:  Para ter uma quantidade máxima de acessos ao disco constante.
Melhor caso O(1) (a chave procurada se encontra na raiz.)
Pior caso O(log n na base M (M é o numero de chaves)) (a chave procurada está em uma folha.)
fonte: http://www.ic.unicamp.br/~zanoni/mo637/aulas/arvoresB.pdf
(2 pontos) Inserir passo a passo valores em uma árvore B e depois removê-los (ordem 4).
Grego says: ela da os valores a serem inseridos ou ela quer um algoritmo??? Ela dá os valores.
Resposta:       http://www.youtube.com/watch?v=ANZBJw3a944&feature=relmfu -> inserção e remoção.
http://www.youtube.com/watch?v=XxFzd8s2u60
app mostrando inserção e remoção:
http://slady.net/java/bt/view.php (essa animação não está errada com relação a ordem da árvore?) ta certo ou nao? :S
Inserção(imagem): http://upload.wikimedia.org/wikipedia/commons/3/33/B_tree_insertion_example.png
(3 pontos) Hash dinâmico e estático, fazer um desenho passo a passo de cada um (com inserção, remoção, etc). (ela dá valores)
vídeo que demonstra inserção com hasing-> http://jocafe.net63.net/anim6.html
Resposta: Ambas usam o bucket, não entendi a diferença de um pro outro
Grego: estático e dinamico usam bucket, mas estaticos o numero de buckets são definidos, ja os dinamicos, os buckets são encadeados e criados conforme a necessidade
No estatico, seria o caso dela falar que o tamanho do bucket é 2? Ai quando ultrapassa vai quebrando?
Sim, mas não é necessariamente 2...o programador q define o tamanho
Ah sim.
Mas como eu faria esse desenho no dinâmico? nunca vai ter quebras? eu vou acrescentando sempre que for entrando chaves?
no dinamico nunca a quebras...e sempre o ultimo elemento aponta para NULL
www.facom.ufu.br/~ilmerio/gbd2/gbd2_s4_hash.pdf (acho que ajuda um pouco)
A questão do hashing dinâmico é igual aquela que ela deu no fim da penúltima aula, que você tinha números binários 0001, 0010,... e tinha que colocar nos buckets.
Então, por exemplo, você tem que adicionar 0010, 0011, 1000.
Fica assim:
0/1 ->  0010
	0011
00 -> 0010
01-> 0011
10-> 1000
Não sei se deu pra lembrar...
DEu sim!!!!
e estatico? kkkk
Então, o estático pelo que eu lembro, você tem um vetor e vai armazenando os valores, se eles forem duplicados, vai pra uma lista encadeada de sinônimos.
e essa lista é infinita? posso ir adicionando quanto quiser nela?
Acho que sim, só que aí o tamanho do arquivo aumenta...Na verdade essa lista só trata colisões...Ah, respondendo a questão do tamanho, é ruim ter longas cadeias de overflow, por isso se usa o hashing dinâmico. Tem o desenho no link passado acima.
Muita cadeia de overflow = menos espaço verdadeiro do campo, acho que li algo sobre isso
a questão da penúltima aula não era pra fazer com hash extensível?
hash extensivel = hash dinamico (ou nao?)
Isso!