1. Explique a seguinte sentença: "B-Trees são construídas de baixo para cima, enquanto árvores binárias são construídas de cima para baixo".
Quando se insere uma chave numa árvore B, ela é colocada sempre numa folha e por meio de split e promote, a árvore fica sempre balanceada. Numa árvore binária, pode ser que, ao inserir uma chave, a árvore não fique balanceada. Então será necessário fazer algoritmos para fazer as operações que garantam que a árvore fique sempre balanceada. Os nós podem ser inseridos em qualquer posição.
2. Por que B-Trees são consideradas geralmente superiores que as árvores binárias de busca para pesquisa externa, e árvores binárias são comumente usadas para pesquisa interna?
Através da B-Tree, faz-se a pesquisa externa das páginas para se encontrar o possível lugar da chave desejada. Esta pesquisa é muito mais rápida que a binária. Entretanto, dentro de uma página, utiliza-se a pesquisa binária por não ser possível B-Tree e por ser mais rápida que pesquisa sequencial. Pesquisa binária em disco é muito lenta.
3. Como uma folha de uma árvore B difere de um nó interno? Quais são as partes necessárias a uma folha?
Nó folha não possui filhos, seus ponteiros são nulos. Uma B-Tree de ordem n possui n-1 chaves no máximo e deve possuir n/2-1 chaves no mínimo. Os nós folhas são aqueles alocados no nível mais baixo da árvore. Todas as folhas aparecem num mesmo nível.
4. Mostre a árvore B de ordem 4 que resulta de carregar os seguintes conjuntos de chaves em ordem:
5. Dada a árvore B que contém todas as letras do alfabeto, mostre o que acontece com a árvore com a inserçåo das chaves $ (menor que A) e a seguir, da chave [ (maior que Z).
6. Dada uma árvore B de ordem 256, qual o número máximo de descendentes por página? Qual o número mínimo (desconsideradas as folhas e a raiz? E de uma folha? Quantas chaves tem uma página não-folha com 200 descendentes?
máximo de descendentes = 256
mínimo de descendentes = 128 (128=m/2) desconsiderando as folhas e a raiz
raiz tem no mínimo 2 descendentes
folha não tem descendentes
199 chaves
7. Suponha que você vai deletar uma chave em uma árvore B, a qual causa um underflow na página. Se pela página irmã do lado direito é necessária concatenação, e pela página esquerda é possível redistribuição, qual opção você escolheria? Por quê?
Redistribuição, porque se fosse utilizada a concatenação, poderia haver underflow da página pai e teria que ser feita outra concatenação. Com redistribuição isso não ocorre, pois há apenas uma troca de uma folha para outra.
8. Qual a diferença entre uma árvore B e uma B*? Quais as vantagens da árvore B*? Quais as desvantagens? Como se comparam a altura mínima dessas árvores?
Uma árvore B* utiliza two-to-three spliting, ou seja, o processo de divisão é adiado até que duas páginas irmãs estejam cheias. Realiza-se então a divisão do conteúdo das duas páginas em 3. Em árvore B, utiliza-se one-to-two spliting onde uma folha cheia é dividida em duas.
Vantagem: cada página tem no mínimo 2/3 das chaves (menos a fragmentação interna).
Desvantagem: deve-se tomar um cuidado especial com o nó raiz e para ele usar one-to-two spliting (algoritmos mais complexos).
Como B* tem no mínimo 2/3 das chaves, ela vai ter uma altura mínima menor que a árvore B.
9. O que é uma árvore B virtual? Como implementá-la? Quais as vantagens e desvantagens?
Quando se coloca parte da árvore B na memória.
Coloca-se a raiz e alguns de seus descendentes na memória, deixando algum espaço para manipular as páginas.
Vantagens: Quando se procura uma chave, pode ser que ela já esteja na memória o que diminui em um acesso ao disco.
Desvantagens: Pode-se deixar na memória páginas que não estão sendo usadas nunca. É necessário substituí-las.
B-Tree