RE: b-arvore+

[Francisco Reverbel <reverbel at ime.usp.br>]

Alexandre Freire da Silva writes:
 > 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:

Faça como o Breno sugeriu nesta mensagem:

    http://www.ime.usp.br/~reverbel/mac211/maillist/msg00353.html

 > para a pagina que tem os valores menores que o menor desta página atual e

Guarde este ponteiro no campo previous da HFPage.

 > para a pagina que contem os valores maiores que o maior desta página?????

Este ponteiro é o pid contido no ultimo registro da 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?????

Sim, precisam. Crie na classe HFPage um método que faça inserção
ordenada de registros de índice. Note que basta ordenar as entradas do
diretório de slots da HFPage, de modo que a entrada 0 aponte para o
"menor registro", a entrada 1 para o registro seguinte, etc. Este método
(não testado!) deve funcionar: 

    // na classe HFPage
    static long insertIndexEntry(Buffer b, IndexEntry e) 
            throws java.io.UTFDataFormatException {
        long recId = insertRecord(b, e);
        if (recId !=FAIL) {
            int slotCnt = b.readShort(slotCount(b));
            int j = slotNumberFrom(recId);
            if (j != slotCnt - 1) {
                throw new Error("Isto não podia estar acontecendo...");
            }
            for (int i = 0; i < slotCnt; i++) {
                if (e.compareTo(b, recPos(b, i)) < 0) {
                    short rPos = b.readShort(recPos(b, j));
                    short rLen = b.readShort(recPos(b, j));
                    System.arraycopy(b.data(), recPos(b, j - 1), 
                                     b.data(), recPos(b, j),
                                     (j - i) * DIR_ENTRY_SIZE);
                    b.writeShort(recPos(b, i), rPos);
                    b.writeShort(recLen(b, i), rLen);
                    return recordId(b.readLong(thisPage(b)), i);
                }
            }
        }
        return recId;
    }

Esse método assume que um IndexEntry sabe "se comparar" com outro
IndexEntry que está armazenado num Buffer. Ele chama o segundo 
método compareTo() da interface abaixo.

interface IndexEntry extends DBObject {
    public abstract int compareTo(IndexEntry other);
    public abstract int compareTo(Buffer buf, int bufPos)
            throws java.io.UTFDataFormatException;
}

 > 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...

Não precisa ser às 6 da manhã... Pegarei os EPs do panda quando eu
chegar aqui na manhã de sexta-feira, por volta de 9 horas.

Reverbel