Arquitetura

Árvore B+

Árvore B+
♦ Variante da árvore B. ♦ Os nós não folha armazenam as chaves dos registros e não os registros inteiros. Em nó interno de uma árvore B+ cabe mais registro do que o de uma árvore B. Consequentemente a altura da árvore B+ é menor do que a da árvore B. ♦ Os registros são armazenados em nós folha. ♦ Nó não folha agem como se fossem uma estrutura de índice para nós que contém os dados. ♦ Diferentemente da árvore B, a árvore B+ tem a estrutura de índices separada da estrutura de dados. ♦ Para acessar qualquer registro é necessário o mesmo número de acessos, já que todos ficam no mesmo nível. ♦ Vantagens: Na maioria das vezes a árvore B+ tem altura menor do que a árvore B para os mesmos registros, o que significa que menos operações de E/S são necessárias durante a busca. Não é necessário subir e descer na árvore para acessar sequencialmente os registros. Tanto o acesso direto como o acesso sequencial são melhores que na árvore B. ♦ Definição: Uma árvore B+ é uma árvore B na qual os registros dados são armazenados em nós folha e os nós não folha armazenam apenas os valores das chaves, formando um índice para os nós de dados. ♦ Melhoria no acesso sequencial é obtida interligando os nós de dados. Como resultado não é necessário mover através da árvore mas apenas processar uma lista encadeada formada pelos nós não folha. ♦ Pela própria definição da árvore B, os registros dos nós folha estão automaticamente ordenados na lista encadeada.

Índice

.... .
Representa um nó de dados na sequência de nós encadeados.

♦ Dado que os registros não mais armazenados nos nós não folha, o procedimento de busca é modificado a fim de que, numa comparação igual, a busca prossiga à esquerda ou à direita para localizar o nó folha apropriado. Arbitrariamente, escolheremos ir à esquerda – o que é importante ser definido a priori. ♦ As principais diferenças entre a árvore B e a árvore B+ está na inserção em um nó folha e no que acontece quando ocorre overflow. ♦