Usuário:Aexpedito/B+tree

Exemplo simples de árvore B+ referenciando chaves de 1 até 7 aos dados d1 até d7. Os apontadores em vermelho permitem o acesso sequencial ordenado das chaves inseridas na árvore

Na ciência da computação uma árvore B+ é uma estrutura de dados do tipo árvore derivada das árvores B, mas com uma forma diferente de armazenamento de suas chaves. Tal organização confere propriedades, algoritmos de inserção, busca e remoção de chaves diferentes dos utilizados em árvores B, mas com uma gama de aplicações muito semelhantes em banco de dados e sistemas de arquivos.

Estruturas de dados como essa são muito empregadas em banco de dados e sistemas de arquivos como o NTFS para o Microsoft Windows, o sistema de ficheiros ReiserFS para Unix, o XFS para IRIX e Linux, e o JFS2 para AIX, OS/2 e Linux, usam este tipo de árvore.

Assim como as árvores B, as árvores B+ visam reduzir as operações de leitura e escrita em memória secundária, uma vez que, essas operações são demoradas para um sistema computacional e devem ser minimizadas sempre que possível.

Visão Geral

Organização de uma árvore B+ em *index set* e *sequence set*. Os nós folha são os amarelos e os azuis são os nós internos

A árvore B+ aparentemente foi proposta por Knuth e grande parte da literatura sobre essa estrutura é encontrada em forma de artigos ao invés de livros.^[1] Com ela foi possível organizar um arquivo de maneira que o processamento sequencial (característica até então pouco eficiente para árvores B) e aleatório de chaves fossem eficientes

A idéia inicial desta variação da árvore B é manter todas as chaves de busca em seus nós folha de maneira que o acesso sequencial ordenado das chaves de busca seja um processo mais eficiente do que em árvores B. Obviamente tal acesso sequencial também é possivel nestas, mas, para isso seria necessário algum algoritmo semelhante ao percurso em ordem realizado numa árvore binária.

Para manter o acesso sequencial, cada nó folha contém apontadores para quais nós são seus predecessores ou sucessores na sequência de chaves e como nas árvores B, as chaves estão ordenadas tanto em suas páginas internas quanto em páginas folha. Dessa forma, quando realizamos uma busca por uma chave k e para encontrarmos a chave k+1, ou seja sua sucessora na ordem, basta verificar a chave ao lado de k caso k+1 esteja na mesma página de k ou carregar a próxima página contida na lista de páginas para verificar qual chave sucede k. Tal procedimento em árvores B seria mais custoso, pois, deveríamos buscar por k+1 iniciando pela raiz da árvore caso k+1 não estivesse na mesma página de k. Em comparação com as árvores B, este tipo de acesso sequencial às chaves é um dos principais benefícios proporcionados pelas árvores B+.

Além desta característica, também devemos analisar suas semelhanças com as árvores B. A organização das páginas internas ou no inglês index set é semelhante a de uma árvore B, este, por sua vez, armazena cópias de chaves para referênciar as buscas, mas não contém as chaves em si. Já no sequence set estão as páginas folha que contém as chaves inseridas na árvore e funciona como uma lista encadeada permitindo o acesso sequencial ordenado às chaves independente do index set.

Definição

Para definir uma árvore B+ devemos levar em consideração alguns aspectos relativos ao disco de memória secundária utilizado e a quantidade de memória primária disponível. Assim, para escolher o tamanho de uma página de sequence set e, portanto, quantas chaves esta pode armazenar é uma tarefa dependente do disco utilizado: suponhamos que cada página folha armazene d chaves.

O index set, como dito anteriormente, apenas carrega cópias de chaves para referênciar a busca e sua construção é semelhante ao de uma árvore B. Suponhamos que estes nós internos possam apontar para n nós filhos, ou seja, uma árvore B com no máximo n-1 chaves por página.

Com tais suposições, diferentemente das árvores B, os números d e n-1 não são necessariamente iguais, mas, manter o tamanho físico em arquivo dessas páginas iguais facilita a implementação da estrutura e geralmente o melhor a se fazer é manter o tamanho físico em arquivo de ambas as páginas iguais.^[2]

Páginas internas

As páginas internas apresentam apenas referências para a localização das chaves de busca contidas nas páginas folha. Estas páginas incluem a página raiz da árvore e todos os nodos internos (exceto as páginas folha). Ou seja, as páginas internas funcionam como um índice que apenas apontam para a localização exata de uma chave e sua construção é semelhante ao de uma árvore B com número mínimo de chaves igual a ⌈n/2⌉-1 e máximo de n-1.

Páginas folha

Nas páginas folha estão abrigadas todas as chaves inseridas e durante o processo de inserção e remoção de chaves estas podem sofrer overflows ou underflows conforme estas violem o número máximo igual a d ou mínimo igual a ⌊d/2⌋ permitido de chaves.

Operações básicas

Figura 1: Antes e depois da inserção da chave 3 na árvore B+

Figura 2: Antes e depois da inserção da chave 25 na árvore B+. Aqui a chave intermediária do processo de *split* é a chave 22

Busca

A operação de busca sobre uma árvore B+ pode ser realizada de duas maneiras: iniciando a busca (linear ou binária) pelo apontador para o sequence set ou pelo apontador para a raíz da árvore. O método mais eficiente é pelo apontador para a raíz na qual é semelhante ao realizado numa árvore B. Dessa forma quando buscamos uma chave k, percorremos a árvore de cima para baixo carregando as páginas internas e selecionando a página apontada pelo ponteiro correspondente ao intervalo no qual pertence k e caso uma cópia de k esteja numa página interna devemos carregar a página à direita de k. Encontrado uma página folha o algoritmo deve buscar k nesta e responder se ela se encontra ou não.

Inserção

Durante a inserção de chaves numa árvore B+ as páginas folha podem sofrer overflow caso já estejam cheias. Assim, após buscar a página folha que uma chave deve ser inserida, devemos analisar dois casos:

Página folha incompleta: Apenas inserimos a chave de maneira a manter a ordenação das chaves. Caso da figura 1.
Página folha completa: A página folha em questão deve sofrer uma operação de split. Tal operação cria uma nova página em arquivo dividindo as chaves entre a nova página e a anterior. Assim devemos escolher uma chave intermediária da sequência formada por todas as chaves da página folha inclusive a chave a ser inserida e distribuir essas chaves de maneira que a nova página contenha a chave intermediária e as chaves maiores do que ela e a página anterior contenha as chaves menores do que a chave intermediária. Após isso a chave intermediária deve ser inserida no index set semelhante ao processo de inserção em árvores B. Caso da figura 2.

Remoção

A operação de remoção de chaves em árvores B+ pode parecer algo complicado, mas as mesmas técnicas empregadas em árvores B também aplicam-se aqui. A redistribuição de chaves e concatenação de páginas são operações mais simples de compreender nessa estrutura contanto que saibamos qual é a chave separadora de duas páginas adjacentes. Assumindo que essa chave separadora entre duas páginas adjacentes é a menor chave da página à direita, o index set deve conter uma cópia dessa chave supondo que nenhuma operação de remoção foi realizada sobre a árvore.

Por exemplo, na figura 3 a chave separadora do index set das páginas folha que contém as chaves 20 e 30 é o valor 30 que está na raíz do index set. Para as páginas folha que contém as chaves 50 e 60, a chave separadora no index set é o valor 60 e assim por diante para as demais páginas folha.

Portanto, conhecido a chave que separa duas páginas adjacentes, sabemos que após uma operação de remoção pode-se ocorrer underflow em suas páginas folha e se isso ocorrer devemos aplicar a redistribuição de chaves entre o sequence set ou concatenar o conteúdo de páginas adjacentes.

Para cada método deste temos uma alternativa para reconstruir o index set de maneira a mante-lo organizado adequadamente, lembrando que quando uma chave é removida e o underflow não é constatado na página, não precisamos fazer nada como na figura 3.

Figura 5: Antes e depois da remoção da chave 30

Figura 6: Antes e depois da remoção da chave 20

Figura 7: Antes e depois da remoção da chave 61. Nesta figura ocorre *underflow* na página folha do 61 e na página do *index set* que contém a chave separadora 60

A seguir são demonstrados dois exemplos de redistribuição de chaves nas figuras 4 e 5. Quando ocorrido o underflow na página e a possibilidade de redistribuir as chaves entre páginas irmãs é constatada, devemos alterar o valor da chave separadora dessas páginas adjacentes para o menor valor da página à direita resultante. Isso somente é possível porque a página em que foi removida a chave tem uma página irmã com um número maior de chaves do que o mínimo permitido.

Na figura 6, apesar da remoção da chave 20, não ocorre o underflow na página e ainda assim o separador 20 no index set é um bom separador para futuras buscas na árvore.

A figura 7 demonstra um caso em que temos a necessidade de concatenar duas páginas folha adjacentes. Após a remoção da chave 61 é constatado o underflow da página folha e a não possibilidade de redistribuição de chaves entre as páginas irmãs desta. Sendo assim, a operação de concatenação deve ser a opção para manter as propriedades da árvore e, por esse motivo, a chave separadora das páginas que contém as chaves 50 e 60 deve ser removida do index set, semelhante à remoção em árvores B.

Propriedades

O número de chaves que poderá ser indexado ao usar a árvore B+ é uma função da ordem da árvore e da sua altura. Para uma árvore B+ de ordem n com uma altura h:

O número máximo de nodos é $n^{h}$
O número mínimo de chaves é $2(n/2)^{h-1}.$

Ver também

Referências

↑ Folk, Michael; Zoellick, Bill (1992). File Structures (em inglês) 2 ed. [S.l.]: Addison-Wesley. p. 443
↑ Folk, Michael; Zoellick, Bill (1992). File Structures (em inglês) 2 ed. [S.l.]: Addison-Wesley. p. 421

Bibliografia

Folk, Michael; Zoellick, Bill (1992). File Structures (em inglês) 2 ed. [S.l.]: Addison-Wesley. 590 páginas. ISBN 0-201-55713-4

Ligações externas

[[:Categoria:Estruturas de dados]] [[cs:B+ strom]] [[de:B+-Baum]] [[en:B+ tree]] [[es:Árbol-B+]] [[fa:درخت بی‌پلاس]] [[he:עץ B Plus]] [[ja:B+木]] [[ko:B+ 트리]] [[ru:B+ дерево]] [[sr:Б+ стабло]] [[uk:B+ дерево]] [[zh:B+树]]

[folk443-1] Folk, Michael; Zoellick, Bill (1992). File Structures (em inglês) 2 ed. [S.l.]: Addison-Wesley. p. 443

[folk421-2] Folk, Michael; Zoellick, Bill (1992). File Structures (em inglês) 2 ed. [S.l.]: Addison-Wesley. p. 421

[1]

[2]