Algoritmo de busca na árvore B §

---

A busca em uma árvore B é um processo eficiente e organizado, onde seguimos o fluxo das páginas (nós) para localizar a chave desejada.

Funciona de forma semelhante a uma busca binária, mas em uma estrutura com múltiplas chaves por página.

Passo a Passo: §

1. Comece na raiz §

Inicie a busca na página raiz da árvore.

2. Compare a chave §

Verifique as chaves na página atual.

Se a chave desejada estiver entre as chaves da página, você encontrou! Caso contrário, prossiga.

3. Escolha o próximo caminho §

Cada chave em uma página separa os valores em intervalos.

Decida para qual filho (página) ir, com base no intervalo da chave que você está procurando:

• Se a chave desejada for menor que a menor chave, siga o ponteiro do filho à esquerda.
• Se a chave desejada estiver entre duas chaves, siga o ponteiro entre elas.
• Se a chave desejada for maior que a maior chave, siga o ponteiro do filho à direita.

4. Continue até encontrar ou esgotar: §

Repita o processo até localizar a chave ou alcançar uma página folha.

Se chegar a uma folha e não encontrar a chave, isso significa que ela não está na árvore.

Exemplo: §

Imagine uma árvore B de ordem 4, onde as páginas podem ter no máximo 3 chaves. A árvore está assim:

        [10 | 20 | 30]
       /    |     |    \
 [2 | 5] [12 | 15] [22 | 25] [32 | 35]

Buscando a chave 15: §

1. Comece na raiz: .

   • 15 está entre 10 e 20, então siga para o segundo filho.

2. Chegue à página .

   • Compare as chaves da página. 15 está presente! Busca concluída.

---

Buscando a chave 28: §

1. Comece na raiz: .

   • 28 está entre 20 e 30, então siga para o terceiro filho.

2. Chegue à página .

   • Compare as chaves. 28 não está aqui.
   • Como já estamos em uma folha, concluímos que 28 não está na árvore.

Referências §

---

Aula 6 - Árvore B