Árvore B+
Origem: Wikipédia, a enciclopédia livre.
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 Linux, 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 dos 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.
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 é nh
- 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.
