Bases de Dados (CC2005), Dep. Ciência de Computadores, FCUP
Eduardo R. B. Marques, DCC/FCUP
Objectivos: Exercícios sobre organização física de dados.
Referências: Organização física dos dados ("slides" das aulas teóricas)
Assumiremos nesta aula armazenamento de registos em ficheiro tal que o tamanho de cada registo é fixo com tamanho \(R\) e com tamanho igual ou inferior a \(B\) a dimensão de um bloco de disco em bytes.
| Notação | Significado |
|---|---|
| \(B\) | tamanho de um bloco em disco em bytes |
| \(N\) | nº de registos em um ficheiro |
| \(R\) | tamanho de um registo em bytes |
| \(bfr = \lfloor\: B \:/ \:R \: \rfloor\) | "blocking factor": nº de registos por bloco |
| \(n = \lceil\: N \:/\: bfr \:\rceil \) | nº de blocos em disco ocupados pelo ficheiro |
| \(x \in\: ]2^{k-1},2^k]\) | \(k = \lceil {\rm log}_2(x) \rceil\) |
|---|---|
| \(]1,2]\) | \(1\) |
| \(]2,4]\) | \(2\) |
| \(]4,8]\) | \(3\) |
| \(]8,16]\) | \(4\) |
| \(]16,32]\) | \(5\) |
| \(]32,64]\) | \(6\) |
| \(]64,128]\) | \(7\) |
| \(]128,256]\) | \(8\) |
| \(]256,512]\) | \(9\) |
| \(]512,1024]\) | \(10\) |
| \(]1024,2048]\) | \(11\) |
| \(]2048,4096]\) | \(12\) |
| \(]4096,8192]\) | \(13\) |
| \(]8192,16384]\) | \(14\) |
Considere o armazenamento de duas tabelas \(T_1\) e \(T_2\) com a seguinte caracterização:
\[T_1: \quad N = 10,000 \quad R = 32 \]
\[T_2: \quad N = 100,000 \quad R = 130 \]
Para cada um dos casos:
Calcule o "blocking factor" \(bfr\), nº de bytes não usados por bloco \(B - bfr \times R\), e nº de blocos \(n\) necessários a guardar os dados da tabela em disco.
Suponha que os ficheiros de \(T_1\) e \(T_2\) estão ordenados pelos valores dos atributos que constituem a chave primária de cada tabela. Quantos acessos a blocos de disco no máximo precisamos de aceder para localizar um registo a partir de um valor da chave primária nos dois casos? E no caso de a pesquisa ser baseada no valor de um outro atributo?
Considere a construção de índices primários para tabelas cujos ficheiros são ordenados pelos atributos de chave primária nos seguintes dois casos:
Assumindo também que referências para blocos em disco têm um tamanho de \(8\) bytes, calcule em cada caso:
Considere uma tabela contendo \(N = 25000\) registos armazenados em \(n = 400\) blocos de disco.
Repita a análise do exercício anterior, mas para um índice sobre uma chave secundária com tamanho de \(8\) bytes e considerando de novo que referências para blocos em disco ocupam \(8\) bytes.
Considere agora que definimos um índice de segundo nível sobre os índice de primeiro nível do exercício anterior.
Quantos blocos em disco seriam adicionalmente necessários e qual seria a melhoria de desempenho no acesso a disco? Faria sentido um índice de terceiro nível?