Arvóres de Pesquisa

2- Árvores de Pesquisa

As árvores binárias de pesquisa são estruturas eficientes quando a memória principal consegue armazenar todos os itens, a qual proporciona acesso direto e sequencial e boa utilização de memória.

Para se pesquisar um item em grandes arquivos de dados armazenados em memória secundária, árvores binárias de pesquisa podem ser usadas de forma simplista. Ou seja, os nodos da árvore são armazenados em disco e os seus apontadores à esquerda e à direita armazenam endereços de disco ao invés de endereços de memória principal. Os nodos podem ser agrupados em páginas para diminuir o número de acessos ao disco. A forma de organizar os nodos dentro de páginas é muito importante em relação ao nº esperado de páginas lidas quando se realiza uma pesquisa.

O método de alocação de nodos em páginas, proposto por Muntz e Uzgalis (1970), considera a proximidade dos nodos dentro da árvore. Ou seja, o novo nodo é sempre colocado na mesma página do nodo pai e se a página do nodo pai estiver cheia, o novo nodo é colocado no início de uma nova página criada (ASSIS,2012).

2.1 Árvore B

Proposta por Bayer e McCreight (1972) para organização e manutenção de arquivos, e segundo Gazzola, as árvores de pesquisa balanceadas são projetadas para funcionar bem em discos magnéticos ou outros dispositivos de armazenamento secundário.  Muitos SGBD usam árvores B ou variações de árvores B para armazenar informações. É um método para armazenamento e recuperação de dados, o qual serve para arquivos volumosos, proporciona rápido acesso aos dados e custo mínimo de overhead.

Em uma árvore B de ordem m temos as seguintes propriedades:

- Cada página contém no mínimo m registros m+1 descendentes;

- Cada página contém no máximo 2m registros e 2m+1 descendentes;

- Todas as páginas folhas devem estar no mesmo nível;

- Cada página, exceto a raiz e as folhas, tem pelo menos [d/2] páginas filhas;

- A página raiz tem ao menos duas páginas filhas.

2.1.1 Árvores B: Pesquisa

Segundo Assis, a operação de pesquisa em uma árvore B é semelhante à pesquisa em uma árvore binária de pesquisa.  Para encontrar um item, é necessário:

- Comparar a chave do item com as chaves que estão na página raiz até encontrar a chave desejada ou o intervalo que ela se encaixa;

- Caso não seja possível encontrar a chave, é necessário seguir o apontador para a subárvore do intervalo encontrado;

- Repetir o processo até encontrar a chave desejada ou atingir uma página folha.

2.1.2 Árvores B: Inserção

Para inserir um item numa árvore, deve-se:

- Localizar a página apropriada aonde o item deve ser inserido ("pesquisa sem sucesso");

- Se o item a ser inserido encontra uma página com menos de 2m itens, o processo de inserção fica limitado a tal página;

- Se o item a ser inserido encontra uma página cheia, é criada uma nova página para divisão dos itens, envolvendo a nova página, a página onde o item seria inserido, e a página pai de ambas (ASSIS, 2012).

[pic 1]

Passos para a inserção da chave 80 em uma árvore B com m=2

2.1.3 Árvores B: Remoção

A remoção de um item em uma árvore B sempre implica na remoção de um item presente em uma página folha. Quando o item esteja numa página folha, a remoção é direta, caso contrário, é necessário seguir conforme abaixo: