Árvore B+: diferenças entre revisões
Linha 4: | Linha 4: | ||
Em [[ciência da computação]], uma '''Árvore B+''' é um tipo de [[árvore (estrutura de dados)|á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. |
Em [[ciência da computação]], uma '''Árvore B+''' é um tipo de [[árvore (estrutura de dados)|á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 |
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 ligada|lista ligada]] para efectuar consultas facilmente. |
||
O número máximo de apontadores num registo é chamado de [[ordem de magnitude|ordem]] da árvore B+. |
O número máximo de apontadores num registo é chamado de [[ordem de magnitude|ordem]] da árvore B+. |
Revisão das 18h23min de 3 de março de 2011
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a8/Btree.png/400px-Btree.png)
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 ligada 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 é
- O número mínimo de chaves é
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.