Pesquisa em Memória Secundária

Prof. Jonas Potros

Árvores de Pesquisa

São estruturas de dados muito eficientes quando deseja-se trabalharcom tabelas que caibam inteiramente na memória principal docomputador.

Satisfazem condições e requisitos diversificados e conflitantes, taiscomo acesso direto e sequencial, facilidade de inserção e retirada deregistros e boa utilização de memória.

Árvore de Pesquisa Binária

Árvores de pesquisa binárias para recuperar informação da memóriasecundária:

• Uso do disco magnético como memória secundária;

• Armazena nós da árvore no disco;

• Apontadores para filho esquerdo e direito, se tornam endereços no disco;

• Custo: O(log2 𝑛) - acesso ao disco;

• Diminuir o número de acessos ao disco: nós agrupados em páginas;

Exemplo: Árvore Binária

Exemplo: Árvore Binária

Formato da árvore de binário para quaternário (número de acessos cai pela metade):

Problemas:Como agrupar os nós em páginas?Como manter equilibrado o crescimento da árvore?Como permitir inserções e remoções à vontade?

A proposta de Árvores B é resolver estes problemas!

Árvore B

Quando uma árvore de pesquisa possui mais de um registro por nó, ela deixa deser binária e passa a ser chamada de 𝑛 − á𝑟𝑖𝑎𝑠, pelo fato de possuírem mais dedois descendentes por nó.

Em uma árvore B de ordem 𝑚 (regras de construção):

1. Para 𝑚 chaves em página não-folha, tem 𝑚+ 1 filhos;

2. Cada página tem entre 𝑚 e 2𝑚 chaves, exceto raiz que tem entre 1 e 2𝑚chaves;

3. Dentro da página, chaves estão ordenadas em ordem crescente.

Exemplo:

Árvore B onde 𝒎 = 𝟐 com ordem 4 ( )

Exemplo: Árvore B

𝑚 = 2 com ordem 4:

Exemplo: Procedimento busca na Árvore B

𝑚 = 2 com ordem 4:

Buscar o valor 37

Exemplo: Procedimento busca na Árvore B

𝑚 = 2 com ordem 4:

Buscar o valor 37

Exemplo: Procedimento busca na Árvore B

𝑚 = 2 com ordem 4:

Buscar o valor 37

Exemplo: Procedimento busca na Árvore B

𝑚 = 2 com ordem 4:

(não foi encontrado)

Buscar o valor 37

Exemplo: Procedimento Inserir na Árvore B

1. Localizar a página apropriada aonde o registro deve ser inserido.

2. Se o registro a ser inserido encontra uma página com menos de2𝑚 registros, o processo de inserção fica limitado à página.

3. Se o registro a ser inserido encontra uma página cheia, é criadauma nova página, no caso da página pai estar cheia o processo dedivisão se propaga.

Exemplo: Procedimento Inserir na Árvore B

𝑚 = 2 com ordem 4:

Inserir os valores 21, 24 e 27

Exemplo: Procedimento Inserir na Árvore B

𝑚 = 2 com ordem 4:

Inserir os valores 21, 24 e 27

Exemplo: Procedimento Inserir na Árvore B

𝑚 = 2 com ordem 4:

Inserir os valores 21, 24 e 27

Exemplo: Procedimento Inserir na Árvore B

𝑚 = 2 com ordem 4:

Inserir os valores 21, 24 e 27

Exemplo: Procedimento Inserir na Árvore B

𝑚 = 2 com ordem 4:

Inserir os valores 21, 24 e 27

> 𝟐𝒎

Exemplo: Procedimento Inserir na Árvore B

𝑚 = 2 com ordem 4:

Inserir os valores 21, 24 e 27

> 𝟐𝒎

Exemplo: Operação de balanceamento: cisão de uma página

𝑚 = 2 com ordem 4:

Exemplo: Operação de balanceamento: cisão de uma página

𝑚 = 2 com ordem 4:

Procedimento Remover na Árvore B

Página com o registro a ser retirado é folha:Regra: na retirada a página permanecer com menos de 𝑚 registros, apropriedade da árvore B é violada. Então pega-se um registroemprestado da página vizinha. Se não existir registros suficientes napágina vizinha, as duas páginas devem ser concatenadas.

Pagina com o registro não é folha:1. o registro a ser retirado deve ser primeiramente substituído por um registro contendo uma chave adjacente.

Exemplo: Procedimento Remover na Árvore B (nó folha)

𝑚 = 2 com ordem 4:

Remover o valor 27

Exemplo: Procedimento Remover na Árvore B (nó folha)

𝑚 = 2 com ordem 4:

Remover o valor 27

Exemplo: Procedimento Remover na Árvore B (nó folha)

𝑚 = 2 com ordem 4:

< 𝒎

Concatenação:Q tem menos de 2𝑚 chaves;

𝑸

Exemplo: Procedimento Remover na Árvore B (nó folha)

𝑚 = 2 com ordem 4:

Concatenação:Irmãos adjacentes: páginas P e Q com mesmo pai e ponteiros adjacentes;

𝑷 𝑸

Exemplo: Procedimento Remover na Árvore B (nó folha)

𝑚 = 2 com ordem 4:

Concatenação:Irmãos adjacentes: páginas P e Q com mesmo pai e ponteiros adjacentes;

𝑷

Exemplo: Procedimento Remover na Árvore B (nó folha)

𝑚 = 2 com ordem 4:

Concatenação:Irmãos adjacentes: páginas P e Q com mesmo pai e ponteiros adjacentes;

Exemplo: Procedimento Remover na Árvore B (nó folha)

𝑚 = 2 com ordem 4:

Exemplo: Procedimento Remover na Árvore B (nó não folha)

𝑚 = 2 com ordem 4:

Remover o valor 50

Exemplo: Procedimento Remover na Árvore B (nó não folha)

𝑚 = 2 com ordem 4:

< 𝟐𝒎

Exemplo: Procedimento Remover na Árvore B (nó não folha)

𝑚 = 2 com ordem 4:

< 𝟐𝒎

Exemplo: Procedimento Remover na Árvore B (nó não folha)

𝑚 = 2 com ordem 4:

< 𝟐𝒎

Exemplo: Procedimento Remover na Árvore B (nó não folha)

𝑚 = 2 com ordem 4:

Atividades

1. Desenhe uma árvore B de ordem 𝑚 = 3 e ordem 6 que contenhaas seguintes chaves: 1, 3, 6, 8, 14, 32, 36, 38, 39, 41, 43.

2. Insira na árvore gerada no exercício anterior as seguintes chaves:2, 5, 7, 10, 13, 16, 18, 21.

3. Remova as chaves 13 e 21 da arvore gerada no número 2.