Re: b-arvore+

[Breno Pompeu Roberto <brenopr@linux.ime.usp.br>]

	A estrutura que eu fiz do no' do Barovere+ foi a seguinte:
	
	Cada record possui o par <key, ptr>, onde ptr aponta para a
sub-arvore que possui elementos maiores ou iguais a key. E estou usando o
HFPage.getPrevious() para indicar a sub-arvore que contem todos os
elementos menores que o primeiro registro do no'.

	EX:	
	
	celula = { key, ptr }
	no' = {PagePtr->ptr0}{key1, ptr1}...{keyn, ptrn}
	onde key1<key2<...<keyn

	PagePtr = Ponteiro previous da HFPage.
	
	Exemplo de arvore b+ com altura 1:	


	
        ROOT = {PagePtr->leaf1}{ 6, leaf2}{12, ptr2}
	
leaf1={reg1,2}{reg2,4} leaf2={reg2,6}{reg3,10} leaf3={reg4,13}{reg4,14}




	O exemplo esta' meio complicado, mas acho que com um pouco de
esforco...
	Portanto, nao e' preciso que toda celula contenha um ponteiro pro
menor e o maior, pois o ponteiro para os menores a celula anterior possui,
e se for a primeira celula do no, a pagina no formato HFPage contem um
campo que armazena um long (HFPage.setPrevious()). Tambem e' importante
que todos os elementos do no estejam ordenados para facilitar a busca.
	
	
	Espero que tenha ajudado.


                      --------------------------------	
                            Breno Pompeu Roberto
                           brenopr@linux.ime.usp.br
                          http://www.breno.ceara.net



On Tue, 29 Jun 1999, Alexandre Freire da Silva wrote:

> Estou com dificuldades em implementar a b-arvore+ com o hfpage, se os meus
> pares <indice, pid ou ird> s�o os records como eu fa�o para colocar
> aqueles dois ponteiros:
> para a pagina que tem os valores menores que o menor desta p�gina atual e
> para a pagina que contem os valores maiores que o maior desta p�gina?????
> outra:
> como fa�o para inserir records antes de outros records? ou n�o preciso
> fazer isso? os records na p�gina n�o precisam estar na ordem menor
> indice<indice do meio<maior indice?????
> E mais uma coisa, vc tamb�m vai deixar a entrega ate as 6 da manha na
> sexta feira professor?o carlinhos adiou pra esta data e horario...
> Valeu pessoal!
> @lex
> 
> ______________________________________________
> -"I am looking for a great warrior."
> -"Wars do no make one great."
>        -Dialog between Yoda and Luke Skywalker
> ----------------------------------------------
>  Alexandre Freire      <alex@linux.ime.usp.br>
> 
>