arvore b+

4. Árvores – B

4.1 Introdução

São árvores de pesquisa balanceadas para dados armazenados em memória secundária (discos)

Objetivo: minimizar o número de acessos a disco Isto é garantido ao maximizarmos o grau
(número de filhos) de um nodo (pode chegar a milhares)

Árvores-B são uma generalização de árvores binárias de pesquisa.
Exemplo:

Se um nodo x da árvore-B possui n[x] chaves, então x tem n[x] + 1 filhos.

As chaves no nodo x são usadas como pontos de divisão para separar a faixa de chaves controladas por x em n[x] + 1 sub-faixas, cada sub-faixa controlada por um dos filhos de x.

Na pesquisa numa árvore-B, fazemos uma decisão de n[x] + 1 caminhos baseada nas comparações de n[x] chaves armazenadas no nodo x.

Antes de formalizarmos o conceito de árvores-B, vamos examinar porque estruturas de dados armazenadas em disco possuem características diferentes das armazenadas na memória principal.

4.2. Estruturas de dados em Armazenamento secundário

Tecnologia mais barata

Num disco, a informação armazenada em cada trilha é dividida em setores

O SO geralmente agrupa os setores contíguos formando blocos

Ou seja, as aplicações sempre acessam o disco em unidades de blocos (1kb a 8kb, tipicamente)

Tempo de acesso a bloco = tempo de latência + tempo de busca ( na ordem de milisegundos)

Milisegundos é muito lento quando comparado a velocidade da memória principal (microsegundos, nano segundos)

Problema: quantidade de dados manipulados não cabe na memória principal.

Solução: uso de uma estrutura de dados que acesse estes dados no disco com o mínimo de leituras a blocos.

Árvores-B são potenciais candidatas à solução pois aumentando-se o grau dos nodos pode-se armazenar os dados com poucos acessos a blocos.

Exemplo: Para grandes árvores-B armazenadas em disco, graus de 50 a 2000 são usados, dependendo do tamanho da chave relativo ao tamanho do bloco.

Uma árvore-B com grau 1001 e