Exercício das aulas de 12/06 e 13/06
Considere as chaves de busca a seguir, que consistem em números inteiros positivos. Considere também que a chave de busca a ser promovida deve ser a primeira chave do novo nó resultante do particionamento (ou seja, o primeiro elemento do segundo nó é a chave promovida durante o particionamento). Considere que as seguintes chaves de busca devem ser inseridas no índice, na ordem de inserção especificada.
15 13 2 8 7 18 23 25 38 43 57 9 12 17 0 5 6 4
Para cada um dos exercícios especificados a seguir, ilustre graficamente o índice gerado. Mostre também o RRN (relative record number) para cada página da árvore (ou seja, do índice) e o endereço do nó raiz da árvore no registro de cabeçalho.
1. Considere um índice árvore-B de ordem 5. Insira as chaves de busca na árvore-B, considerando que se encontram implementadas as rotinas de split e de concatenação. Ou seja, a rotina de redistribuição durante a inserção não se encontra implementada.
2. Considere um índice árvore-B* de ordem 5. Insira as chaves de busca na árvore-B*, considerando que se encontram implementadas as rotinas de split, de concatenação e de redistribuição durante a inserção. Na redistribuição, considere que a distribuição das chaves deve ser uniforme entre os nós.