Estruturas de dados: Princípios e implementação C++/Estruturas de ordenação simples
Origem: Wikilivros, livros abertos por um mundo aberto.
Tabela de conteúdo |
[editar] Árvores binárias de busca
[editar] Árvores AVL
[editar] Árvores rubro-negra
[editar] Heap
[editar] Heap minmax
[editar] Árvore B
[editar] Introdução
O estudo das diferentes estruturas de dados vistas anteriormente foi realizado supondo um custo de acesso aos dados uniforme e da mesma ordem de grandeza que as demais operações. Porém, na prática, isso nem sempre é o caso. Em sistemas computacionais atuais, a memória é organizada hierarquicamente, sendo o custo de acesso inversamente proporcional ao custo financeiro. Por ordem decrescente de velocidade de acesso (e por ordem crescente de custo financeiro), temos: registros internos do processador, memória cache, memória principal (RAM), memória secundária (disco rígido), memória externa (mídia ótica, fitas).
Um exemplo é quando é preciso representar e manipular através de buscas, inserções e remoções, uma quantidade de dados tal que a capacidade da memória principal disponível não é suficiente. Neste caso, por razões econômicas (o custo de expansão da memória principal) ou tecnológicas (o maior tamanho de memória principal que o sistema operacional pode gerenciar), torna-se necessário recorrer a memória secundário para armazenar parte dos dados.
Historicamente, o tempo de acesso a memória secundária (discos ou fitas) sempre foi muito superior ao de acesso a memória principal. Nas tecnologias atuais, o fator relacionando esses dois tempos torna entre 104 e 105: o tempo de um acesso em memória secundária é equivalente ao tempo de execução de 10.000 a 100.000 instruções. Em geral, os sistemas gerenciadores de bancos de dados devem operar vários usuários em paralelo. Supondo uma média de 50 usuários concorrentes, e um tempo médio de acesso ao disco de 10ms, o número médio de acessos que um usuário pode fazer é de 2 por segundo.
Por exemplo, supõe que você deve elaborar um sistema de gerenciamento de um banco de dados que tem cerca de 25.000.000 (vinte-e-cinco milhões) de registros. Cada registro tem um tamanho de 1kB e uma chave de 4 bytes (supondo a existência de uma relação de ordem entre as chaves). A quantidade total de memória necessária é de 25 GB (vinte-e-cinco gigabytes). Se for usada uma árvore binária balanceada, por exemplo uma árvore rubro-negra, os números médio e máximo de acessos à memória secundária numa busca seria 48 (
)$. Os tempos médios e máximos de busca seriam portanto 12s e 24s. Em certas aplicações, esses números podem não ser aceitáveis.
As árvores B são um tipo de árvores de busca que foram projetadas para minimizar o número de acessos à memória secundária. Como o número de acessos à memória secundária depende diretamente da altura da árvore, as árvores B foram projetadas para ter uma altura inferior às árvores rubro-negras ou AVL, para um dado número de chaves. Para manter o número de registros armazenados e, ao mesmo tempo, diminuir a altura, uma solução é aumentar o grau de ramificação da árvore (o número máximo de filhos que um nó pode ter). Assim árvores B são árvores de busca que possuem um grau de ramificação geralmente muito maior que 2. Além disso, a cada nó de uma árvore B são associados mais de um registro de dados: se o grau de ramificação de um nó for g, este pode armazenar até g − 1 registros. A figura abaixo mostra um exemplo de árvore B, com grau de ramificação dos nós de até 4.
Em geral o grau de ramificação de uma árvore B é determinado pelas características físicas da memória secundária empregada, pois memórias secundárias usualmente têm uma unidade atômica de leitura/escrita. Para armazenar uma árvore B, cada nó da árvore será armazenado numa unidade de memória secundária. Por exemplo, supondo que a unidade tem uma capacidade de 4kB e que seu endereço seja codificado sobre 4 bytes. O maior grau de ramificação possível neste caso é denotado gmax e é tal que: 
, ou seja 
.
Esse grau de ramificação é muito perto do das árvores balanceadas. A altura do árvore B correspondente não será significativamente inferior a altura que teria uma árvore binária correspondente.
Uma alternativa é, no lugar de armazenar o registro inteiro no nó da árvore B, colocar a chave e uma referência a um unidade de disco que contem essa informação. Em nosso exemplo, o tamanho de uma referência é 4 bytes. Supondo que o tamanho da chave seja também de 4 bytes, o grau de ramificação é tal que: ![(g_{max} \times 4) + [(g_{max}-1) \times (4+4)] \leq 4096](http://upload.wikimedia.org/math/e/e/c/eec2711edcc65ca00e8d201dc29051cd.png)
, ou seja gmax = 342.
Neste caso, cada nó armazena 341 chaves com a referência ao registro correspondente. A raiz pode ter até 342 filhos e 116964 netos. A capacidade desta árvore B é 
referências.
Supondo que a raiz sempre fica em memória principal, são necessários, no máximo, dois acessos a memória secundária para achar uma chave, e de um terceiro acesso para ler o registro correspondente. Utilizando os parâmetros da discussão acima, o tempo de espera do usuário devido as transações com a memória secundária cai para 1,5s (a comparar com as estimativas de até 24s com uma implementação por árvores rubro-negra).
[editar] Exercício
Seja uma árvore B de altura a e grau máximo de ramificação gmax. Dar, em função de a e gmax, o número máximo de referências que essa árvore B pode armazenar.
