Exemplos de arquivos de Acesso DiretoExemplos de arquivos de Acesso Direto
Enunciado
• Deseja-se trabalhar no projeto de um arquivo de acesso direto
• O número de “buckets” deve ser igual a 997 e o número de “slots” por “bucket” deve ser igual a 3
• A seguir são exibidos as chaves, os “home addresses” e as assinaturas digitais para os primeiros 7 registros a incluir no arquivo.
2
Dados a incluir nos arquivos
Registro K H(K) Assinatura1 11125 158 0011111000102 23089 158 1010101001113 41035 158 0011000100014 52999 158 1011110101015 70945 158 1110101010016 44026 158 0001110101007 18669 723 1111111111118 10693 723 0001010010019 48579 723 001010010011
3
Solicita-se
• Deseja-se estudar diversas possibilidades de tratamento de transbordamento. Depois de criados os arquivos e antes da inclusão de qualquer registro as caixas de nós contém os seguintes endereços:
Tipo de tratamento de transbordamento Endereços na caixa de nós
Espalhamento baseado em tabelas 1001, 1002, ... Espalhamento dinâmico ("buckets") 1001, 1002, .... Espalhamento dinâmico (células em memória) 1001, 1002, ... Espalhamento extensível 2, 3, 4, 5, 6, ...
4
Registros a incluir
• Solicita-se exibir unicamente a configuração das porções do arquivo e as estruturas de índices envolvidas do arquivo obtido nas seguintes situações:• Após a inclusão dos registros 1 a 4• Após a inclusão dos registros 7 a 9
5
Espalhamento baseado em tabelas
Incluir 1
Bucket Slot Reg K Assinatura 158 1 1 11125 001111100010
2
3
Home addresses Célula 0 Célula 1 Célula 2 Célula 3
158 bucket 158 -1 -1 -1 assinatura 111111111111 111111111111 111111111111 111111111111
6
Espalhamento baseado em tabelas
Incluir 1 a 2
Bucket Slot Reg K Assinatura 158 1 1 11125 001111100010
2 2 23089 101010100111
3
Home addresses Célula 0 Célula 1 Célula 2 Célula 3
158 bucket 158 -1 -1 -1 assinatura 111111111111 111111111111 111111111111 111111111111
7
Espalhamento baseado em tabelas
Incluir 1 a 3
Bucket Slot Reg K Assinatura 158 1 3 41035 001111100010
2 1 11125 001111100010
3 2 23089 101010100111
Home addresses Célula 0 Célula 1 Célula 2 Célula 3
158 bucket 158 -1 -1 -1 assinatura 111111111111 111111111111 111111111111 111111111111
8
Espalhamento baseado em tabelas
Incluir 1 a 4
Bucket Slot Reg K Assinatura 158 1 3 41035 001100010001
2 1 11125 001111100010
3 4 52999 101111010101
1001 1 2 23089 101010100111
2
3
Home addresses Célula 0 Célula 1 Célula 2 Célula 3
158 bucket 158 1001 -1 -1 assinatura 1011111010101 111111111111 111111111111 111111111111
9
Espalhamento baseado em tabelas
Incluir 7
Bucket Slot Reg K Assinatura
723 1 7 18669 111111111111
2
3
Home addresses Célula 0 Célula 1 Célula 2 Célula 3
723 bucket 723 -1 -1 -1
assinatura 111111111111 111111111111 111111111111 111111111111
10
Espalhamento baseado em tabelas
Incluir 7 a 8
Bucket Slot Reg K Assinatura
723 1 8 10693 000101001001
2 7 18669 1111111111111
3
Home addresses Célula 0 Célula 1 Célula 2 Célula 3
723 bucket 723 -1 -1 -1
assinatura 111111111111 111111111111 111111111111 111111111111
11
Espalhamento baseado em tabelas
Incluir 7 a 9
Bucket Slot Reg K Assinatura
723 1 8 10693 000101001001
2 9 48579 001010010011
3 7 18669 1111111111111
Home addresses Célula 0 Célula 1 Célula 2 Célula 3
723 bucket 723 -1 -1 -1
assinatura 111111111111 111111111111 111111111111 111111111111
12
Espalhamento dinâmico
Incluir 1 a 3
Bucket Nível Slot Reg K Assinatura 158 2 1 1 11125 001111100010
2 2 23089 101010100111
3 3 41035 001100010001
13
158
158
Espalhamento dinâmico
Incluir 1 a 4
Bucket Nível Slot Reg K Assinatura 158 2 1 1 11125 001111100010
2 3 41035 001100010001
3
1001 2 1 2 23089 101010100111
2 4 52999 101111010101
3
14
Espalhamento dinâmico
Incluir 7 a 9
Bucket Nível Slot Reg K Assinatura 723 1 1 7 18669 111111111111
2 8 10693 000101001001
3 9 48579 001010010011
723
723
15
Espalhamento extensível
Incluir 1 a 3
Bucket Nível Slot Reg K Assinatura
d=0
1 1 1 1 11125 001111100010
0 1
2 2 23089 101010100111
3 3 41035 001100010001
16
Espalhamento extensível
Incluir 1 a 4
Bucket Nível Slot Reg K Assinatura
d=1
1 1 1 1 11125 001111100010
0 1
2 3 41035 001100010001 1 2
3
2 1 1 2 23089 101010100111
2 4 52999 101111010101
3
17
Espalhamento extensível
Incluir 1 a 5
Bucket Nível Slot Reg K Assinatura
d=1
1 1 1 1 11125 001111100010
0 1
2 3 41035 001100010001 1 2
3
2 1 1 2 23089 101010100111
2 4 52999 101111010101
3 5 70945 111010101001
18
Espalhamento extensível
Incluir 1 a 6
Bucket Nível Slot Reg K Assinatura
d=1
1 1 1 1 11125 001111100010
0 1
2 3 41035 001100010001 1 2
3 6 44026 000111010100
2 1 1 2 23089 101010100111
2 4 52999 101111010101
3 5 70945 111010101001
19
Espalhamento extensível
Incluir 1 a 6 e 7
Bucket Nível Slot Reg K Assinatura
d=2
1 1 1 1 11125 001111100010
00 1
2 3 41035 001100010001 01 1
3 6 44026 000111010100
10 2 11 3
2 2 1 2 23089 101010100111
2 4 52999 101111010101
3
3 2 1 5 70945 111010101001
2 7 18669 111111111111
3
20
Espalhamento extensívelIncluir 1 a 6 e 7 a 8
Bucket Nível Slot Reg K Assinatura
d=3
1 3 1 6 44026 000111010100
000 1
2 8 10693 000101001001 001 4
3
010 5 011 5
4 3 1 1 11125 001111100010 100 2
2 3 41035 001100010001
101 2
3 110 3
111 3
5 0
2 2 1 2 23089 101010100111
2 4 52999 101111010101
3
3 2 1 5 70945 111010101001
2 7 18669 111111111111
3
21
Espalhamento extensívelIncluir 1 a 6 e 7 a 9
Bucket Nível Slot Reg K Assinatura
d=3
1 3 1 6 44026 000111010100
000 1
2 8 10693 000101001001 001 4
3
010 5 011 5
4 3 1 1 11125 001111100010 100 2
2 3 41035 001100010001
101 2
3 9 48579 001010010011 110 3
111 3
5 0
2 2 1 2 23089 101010100111
2 4 52999 101111010101
3
3 2 1 5 70945 111010101001
2 7 18669 111111111111
3
22