Árvore de Pesquisa

Search tree of order p

Cada nó contém, no máximo:

• p - 1 valores e p ponteiros.

key value tem associado um ponteiro para o registo de dados.

Pi - ponteiro para um nó filho ou NULL.

Ki - valor a pesquisar

• K1 < K2 < ... < Kq-1;

Balanceada

Uma árvore diz-se balanceadas (equilibrada) se a distância de qualquer folha ao nó raiz for sempre a mesma

• i.e. os nós folha estão todos ao mesmo nível.

As operações de inserção e remoção são efectuadas segundo um algoritmo que mantém a árvore sempre equilibrada.

B-Tree são árvores balanceadas muito utilizadas pelos SGBD para implementar índices multi-level.

• permitem uniformizar os tempos de pesquisa de valores na estrutura.