Índices: Árvore B e B+ - Aula 22/09 - Bancos de Dados 2021.2

Introdução à Árvore B

Teoria e Importância

• O apresentador, André, compartilha sua preferência pela árvore B, destacando sua elegância na resolução de problemas comuns em estruturas de dados.

• O vídeo faz parte de um curso sobre bancos de dados na Unicamp, com foco específico nas árvores B.

Estrutura e Função

• A árvore B é uma estrutura fundamental para a construção de índices em bancos de dados, permitindo a organização eficiente dos dados.

• A árvore B possui uma estrutura independente que utiliza ponteiros para arquivos de dados.

Características da Árvore B

Ordem da Árvore

• A ordem "m" da árvore indica que ela pode ter até "m" filhos por nó.

• Alguns autores definem que se a árvore tem ordem m, ela pode ter no máximo "m + 1" filhos; cada nó terá "k - 1" chaves se tiver "k" filhos.

Balanceamento e Estrutura

• As folhas da árvore B estão sempre no mesmo nível, o que proporciona um auto-balanceamento essencial para seu funcionamento.

Estrutura Detalhada da Árvore B

Exemplo Prático

• André apresenta um exemplo prático considerando uma árvore de ordem quatro, onde cada nó pode ter até quatro filhos e três chaves.

• Os nós intermediários têm configurações equivalentes às folhas, mas as folhas não apontam para outros nós.

Chaves e Filhos

• Cada chave em um nó representa valores menores ou iguais àquela chave à esquerda e maiores ou iguais à direita.

Construção da Árvore B

Processo Passo a Passo

Como Funciona uma Árvore B?

Estrutura Inicial da Árvore

• A árvore começa vazia e é preenchida com números, começando pelo nó raiz. O primeiro número inserido é 15.

• Os elementos são organizados dentro do nó de forma ordenada, por exemplo, ao inserir 2 e 15, a ordem se mantém.

• O tamanho do nó da árvore B deve ter correlação com o bloco físico para otimizar operações de leitura e gravação.

Crescimento e Divisão da Árvore

• Quando um novo número (30) não cabe no nó atual, ocorre um "estouro", levando à necessidade de dividir o nó (split).

• A divisão resulta em dois nós novos, onde um dos números centrais precisa ser escolhido para subir na hierarquia da árvore.

• A escolha do número que sobe é arbitrária quando há um número par; neste caso, o 15 foi escolhido.

Organização Após a Divisão

• Após a subida do 15, os números menores ficam à esquerda (2), enquanto os maiores vão para a direita (30 e 57).

• Essa estrutura permite buscas eficientes; por exemplo, ao buscar o número 30, inicia-se pela raiz e segue comparando valores.

Inserções Adicionais

• Ao inserir mais números como 40 e 22, novas divisões podem ocorrer se os nós excederem sua capacidade.

• O processo de inserção continua com verificações se cada novo número é maior ou menor que os existentes na árvore.

Reorganização Contínua

• Com novas inserções como o número 25, a árvore pode novamente estourar e exigir uma nova divisão.

• Durante essa reorganização, o menor valor entre as divisões será mantido à esquerda (22), enquanto os maiores ficarão à direita (28 e 29).

Estrutura e Balanceamento da Árvore B

Organização dos Nós

• A árvore B é organizada em nós, onde o nó 25 é menor que o nó 30, exigindo sua colocação antes do 30.

• Todas as folhas estão no mesmo nível, um aspecto crucial para o balanceamento automático da árvore B.

Inserção de Novos Elementos

• O número 45 será inserido na árvore; ele é maior que os números anteriores (15 e 30).

• Ao inserir o número 63, ocorre um estouro no nó, pois excede a capacidade permitida.

Tratamento de Estouro

• Quando um nó estoura, ele deve ser dividido. O número do meio (45) sobe para o nível superior.

• O número 25 também precisa ser ajustado ao dividir o nó, mantendo a estrutura balanceada.

Características da Árvore B

• A árvore continua balanceada após as inserções e divisões, com todos os caminhos tendo o mesmo comprimento.

• Em uma árvore de ordem M (neste caso M = 4), cada nó não folha pode ter até 6 filhos.

Propriedades dos Nós

• Cada nó deve ter pelo menos M/2 filhos (exceto a raiz), garantindo que a estrutura permaneça equilibrada.

• As folhas sempre estarão no mesmo nível, evitando desbalanceamentos significativos na árvore.

Vantagens das Árvores B em Banco de Dados

• A uniformidade nos níveis das folhas permite trajetos consistentes dentro da árvore.

• Árvores B são eficientes para bancos de dados devido à sua capacidade de manter profundidades reduzidas enquanto gerenciam grandes volumes de registros.

Capacidade e Escalabilidade

• Com uma ordem alta (ex: M = 255), a quantidade de registros acessíveis aumenta exponencialmente com cada nível adicional.

Árvore B: Estruturas e Características

Introdução às Árvores B

• A ideia central é a utilização de páginas grandes para armazenar dados, permitindo que um setor específico seja guardado em um nó da árvore B.

• As árvores B possuem características interessantes, como intermediários que servem apenas como guias, enquanto as folhas contêm ponteiros para os registros.

Estrutura das Folhas

• Ao subir uma chave na árvore B, a prática envolve copiar o elemento do nó inferior para o superior, mantendo-o também na folha.

• Cada folha possui um ponteiro para seu respectivo registro no banco de dados, facilitando a localização dos dados posteriormente.

Navegação e Acesso Ordenado

• As folhas têm um ponteiro que indica o próximo nó, permitindo acesso ordenado aos elementos da árvore.

• A estrutura dos nós intermediários é diferente da das folhas; os intermediários apontam para filhos enquanto as folhas apontam para registros.

Exemplo Prático de Divisão

• Durante uma divisão (split), ao invés de mover uma chave para cima, pode-se optar por fazer uma cópia dela. Isso mantém todos os elementos nas folhas.

• O exemplo ilustra como manter chaves nas folhas permite garantir que todas as informações estejam acessíveis sem transferências desnecessárias.

Vantagens da Estrutura Proposta

• Manter cópias nas folhas assegura que todos os elementos permaneçam disponíveis e acessíveis.

• Essa abordagem resulta em uma estrutura poderosa onde todas as chaves estão nas folhas, possibilitando percorrer os dados em ordem crescente com facilidade.

Aplicações Práticas das Árvores B

• A estrutura das árvores B é especialmente adequada para bancos de dados devido à sua capacidade de acessar rapidamente intervalos específicos de chaves.

Aplicações de Consultas em Dados

Importância do Havaí nas Consultas

• O Havaí é uma ferramenta excelente para realizar consultas que exigem um recorte específico, permitindo a seleção de dados entre um intervalo definido.

• A abordagem sequencial é destacada, onde o usuário pode começar em um ponto (neste caso, 15) e seguir até outro limite (40), facilitando a navegação pelos dados.

Ordenação e Pesquisa

• É comum realizar pesquisas que envolvem intervalos, como "entre X e Y", o que torna a ordenação dos dados crucial para obter resultados precisos.

• A dificuldade mencionada com outras abordagens se deve ao fato de que elas não mantêm uma ordem clara baseada na consulta desejada, diferentemente do método discutido.