Árvore B+: diferenças entre revisões

← Ver a alteração anterior Ver a alteração posterior →

Conteúdo apagado Conteúdo adicionado

Em linha

Revisão das 17h37min de 2 de maio de 2012

Um exemplo simples de uma árvore B+ a ligar as chaves 1-7 aos valores de dados d₁-d₇. De notar a lista ligada (a vermelho) a permitir uma actualização ordenada rápida.

Em ciência da computação, uma Árvore B+ é um tipo de árvore. Representa a ordenação de dados de uma maneira que permita uma inserção e remoção eficiente de elementos. É um índice dinâmico de multi-níveis com ligações máximas e mínimas no número de chaves em cada nodo. Os sistemas de ficheiros 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.

Uma árvore B+ é uma variação da árvore B. Numa árvore-B+, contrastando com uma árvore-B, todos os dados são gravados nas folhas. Os nodos internos contêm apenas chaves e apontadores da árvore. Todas as folhas estão no mesmo nível mais baixo. Os nodos das folhas também estão ligados entre si como uma lista de ligações para efectuar consultas facilmente.

O número máximo de apontadores num registo é chamado de ordem da árvore B+.

O número mínimo de chaves por registo é metade do número máximo de chaves. Por exemplo, se a ordem de uma árvore B+ for n+1, cada nodo (excepto o da raiz) terá de ter entre (n+1)/2 e n chaves. Se n for um número primo, o número mínimo de chaves pode ser quer (n+1)/2 ou (n-1)/2, mas terá de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore.

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}.$

A árvore B+ foi descrita pela primeira vez em "Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Informatica 1: 173-189 (1972)".

Uma extensão de uma árvore B+ é chamada de Árvore B# que usa a estrutura da árvore B+ e adiciona mais restrições.

Ver também

Ligações externas

@@ Linha 7: / Linha 7: @@
 O número máximo de apontadores num registo é chamado de [[ordem de magnitude|ordem]] da árvore B+.
-O número mínimo de chaves por registo é metade do número máximo de chaves. Por exemplo, se a ordem de uma árvore B+ for n+1, cada nodo (excepto o da raiz) terá de ter entre (n+1)/2 e n chaves. Se ''n'' for um [[número primo]], o número mínimo de chaves pode ser quer (n+1)/2 ou (n-1)/2, mas terá de ser o mesmo em toda a árvore.
+O número mínimo de chaves por registo é metade do número máximo de chaves. Por exemplo, se a ordem de uma árvore B+ for n+1, cada nodo (excepto o da raiz) terá de ter entre (n+1)/2 e n chaves. Se ''n'' for um [[número primo]], o número mínimo de chaves pode ser quer (n+1)/2 ou (n-1)/2, mas terá de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore, de ser o mesmo em toda a árvore.
 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.