Acesso Sequencial Indexado

1
Acesso Sequencial Indexado
25 de outubro de 2011
2
Acesso Sequencial Indexado
•
Objetivo: Considerar de forma unificada duas
visões sobre estruturas de acesso a arquivos
•
Sequencial: arquivo pode ser acessado
sequencialmente (sem seeks), gerando registros
ordenados por chave
•
Indexada: arquivo é visto como um conjunto de
registros indexados por chave
2
Acesso Sequencial Indexado
•
l
b
o
Pr
1
a
em
l
b
o
Pr
2
a
em
Objetivo: Considerar de forma unificada duas
visões sobre estruturas de acesso a arquivos
•
Sequencial: arquivo pode ser acessado
sequencialmente (sem seeks), gerando registros
ordenados por chave
•
Indexada: arquivo é visto como um conjunto de
registros indexados por chave
3
Exemplo
Operações cosequenciais
Operações indexadas
Ler dois arquivos para
unir os registros
Acessar um registro
dado uma chave
3
Exemplo
Operações cosequenciais
Ler dois arquivos para
unir os registros
+
Operações indexadas
Acessar um registro
dado uma chave
Acesso Sequencial Indexado
l
b
o
Pr
1
a
em
4
Conjunto de Sequência de Registros
•
Objetivo: manter dinamicamente, em disco, um
conjunto de registros ordenados por chave
•
Problema: ordenação do arquivo em disco é “cara”
l
b
o
Pr
1
a
em
4
Conjunto de Sequência de Registros
•
Objetivo: manter dinamicamente, em disco, um
conjunto de registros ordenados por chave
•
•
Problema: ordenação do arquivo em disco é “cara”
Solução:
•
•
Organizar os registros em blocos
Um bloco se torna a menor unidade endereçável
nas operações de leitura e escrita no disco
5
Exemplo de organização em blocos
Chave: nome
Fator de bloco: 4 nomes/bloco
Chaves:
Adams, Baird, Bixby, Boone,
Bynum, Carson, Cole, Davis,
Denver, Ellis
6
Exemplo de organização em blocos
Chave: nome
Fator de bloco: 4 nomes/bloco
bloco 1
bloco 2
bloco 3
Adams, Baird, Bixby, Boone,
Bynum, Carson, Cole, Davis,
Denver, Ellis
6
Exemplo de organização em blocos
Chave: nome
Fator de bloco: 4 nomes/bloco
bloco 1
bloco 2
bloco 3
Adams, Baird, Bixby, Boone,
Bynum, Carson, Cole, Davis,
Denver, Ellis
Inserir Carter
6
Exemplo de organização em blocos
Chave: nome
Fator de bloco: 4 nomes/bloco
bloco 1
bloco 2
bloco 3
Adams, Baird, Bixby, Boone,
Bynum, Carson, Cole, Davis,
Denver, Ellis
Inserir Carter
7
Exemplo de organização em blocos
Chave: nome
Fator de bloco: 4 nomes/bloco
bloco 1
bloco 2
bloco 3
bloco 4
Adams, Baird, Bixby, Boone,
Bynum, Carson, Carter,
Denver, Ellis
Cole, Davis,
subdivisão (split)
de bloco
8
Exemplo de organização em blocos
Chave: nome
Fator de bloco: 4 nomes/bloco
bloco 1
bloco 2
bloco 3
bloco 4
Adams, Baird, Bixby, Boone,
Bynum, Carson, Carter,
Denver, Ellis
Cole, Davis,
Remover Davis
9
Exemplo de organização em blocos
Chave: nome
Fator de bloco: 4 nomes/bloco
bloco 1
bloco 2
bloco 3
bloco 4
Adams, Baird, Bixby, Boone,
Bynum, Carson, Carter,
Denver, Ellis
Cole,
Remover Davis
underflow
10
Exemplo de organização em blocos
Chave: nome
Fator de bloco: 4 nomes/bloco
bloco 1
bloco 2
bloco 3
bloco 4
Adams, Baird, Bixby, Boone,
Bynum, Carson, Carter,
Cole, Denver, Ellis
Remover Davis
disponível
concatenação
11
Exemplo de organização em blocos
Chave: nome
Fator de bloco: 4 nomes/bloco
bloco 1
bloco 2
bloco 3
bloco 4
Adams, Baird, Bixby, Boone,
Bynum, Carson, Carter,
Cole, Denver, Ellis
Conclusão: o arquivo inteiro pode ser mantido ordenado
apenas pela ordenação de suas partes (blocos)
12
Conjunto de Sequência de Registros
•
Problemas:
•
A ordenação do arquivo pode exigir mais
espaço em disco por conta de fragmentações
internas. Neste caso, pode-se adotar estratégias
que privilegiem a redistribuição de chaves
•
A ordem física dos registros só é garantida ao
longo de um bloco e não entre-blocos
•
Qual deve ser o tamanho de um bloco ?
13
Conjunto de Sequência de Registros
•
Qual deve ser o tamanho de um bloco ?
•
Deve representar um compromisso entre
tempo de acesso, memória RAM disponível e as
operações a serem executadas
•
O tamanho do bloco deve permitir o
armazenamento de vários destes em memória
•
O tempo de leitura e escrita de um bloco não
deve ser muito longo (para não perder o que se
ganhou por economia de seeks)
l
b
o
Pr
2
a
em
14
Sequência de Registros e Indexação
•
Objetivo: definir um método eficiente que
possibilite o acesso a um bloco dado uma chave
•
•
Ideia: construir um índice de chaves apontando
para cada um dos blocos
Sequência de blocos:
Adams-Berne
Bolen-Cage
Camp-Dutton
Embry-Evans
Faber-Folk
Folks-Gaddis
1
2
3
4
5
6
l
b
o
Pr
2
a
em
14
Sequência de Registros e Indexação
•
Objetivo: definir um método eficiente que
possibilite o acesso a um bloco dado uma chave
•
•
Ideia: construir um índice de chaves apontando
para cada um dos blocos
Sequência de blocos:
Adams-Berne
Bolen-Cage
Camp-Dutton
Embry-Evans
Faber-Folk
Folks-Gaddis
1
2
3
4
5
6
15
Sequência de Registros e Indexação
•
Sequência de blocos:
Adams-Berne
Bolen-Cage
Camp-Dutton
Embry-Evans
Faber-Folk
Folks-Gaddis
1
2
3
4
5
6
chave
número do bloco
Berne
1
2
3
4
5
6
Cage
Dutton
Evans
Folk
Gaddis
Índices para a
sequência de blocos
16
Chaves Delimitadoras
•
Os índices servem apenas de guia na busca do
bloco que contém a chave a ser acessada
•
Menor delimitador possível (não-único): economia
de espaço
•
Neste caso, teremos uma Árvore B+ de prefixo
simples
17
Chaves Delimitadoras
•
Os índices servem apenas de guia na busca do
bloco que contém a chave a ser acessada
•
Menor delimitador possível (não-único): economia
de espaço
•
Delimitador de blocos:
Adams-Berne
Bolen-Cage
Camp-Dutton
Embry-Evans
Faber-Folk
Folks-Gaddis
1
2
3
4
5
6
17
Chaves Delimitadoras
•
Os índices servem apenas de guia na busca do
bloco que contém a chave a ser acessada
•
Menor delimitador possível (não-único): economia
de espaço
•
Delimitador de blocos:
Bo
Cam
E
F
Folks
Adams-Berne
Bolen-Cage
Camp-Dutton
Embry-Evans
Faber-Folk
Folks-Gaddis
1
2
3
4
5
6
18
Arquivo Sequencial Indexado e
+
Árvore B de Prefixo Simples
E
conjunto
de índices
Bo
Cam
F
Folks
Adams-Berne
Bolen-Cage
Camp-Dutton
Embry-Evans
Faber-Folk
Folks-Gaddis
1
2
3
4
5
6
19
Busca por Blocos
•
•
A partir dos índices na Árvore B, podemos acessar
um bloco da seguinte forma:
•
Se chave procurada < delimitador, então vá para
a esquerda na árvore
•
Se chave procurada ≥ delimitador, então vá para
a direita na árvore
Lembre que: Árvore B+ de prefixo simples possui
os menores delimitadores possíveis
20
Operações sobre Árvores
+
B
•
Supressão de registros sem originar concatenação
e redistribuição: alterações apenas nos blocos de
registros; o conjunto de índices não é alterado
•
Inserção sem subdivisão: idem
21
Operações sobre Árvores
+
B
Remover Embry e Folks
E
Bo
Cam
F
Folks
Adams-Berne
Bolen-Cage
Camp-Dutton
Embry-Evans
Faber-Folk
Folks-Gaddis
1
2
3
4
5
6
21
Operações sobre Árvores
+
B
Remover Embry e Folks
E
Bo
Cam
F
Folks
Adams-Berne
Bolen-Cage
Camp-Dutton
Embry-Evans
Faber-Folk
Folks-Gaddis
1
2
3
4
5
6
22
Operações sobre Árvores
+
B
Remover Embry e Folks
E
Bo
Cam
F
Folks
Adams-Berne
Bolen-Cage
Camp-Dutton
Ervin-Evans
Faber-Folk
Folks-Gaddis
1
2
3
4
5
6
22
Operações sobre Árvores
+
B
Remover Embry e Folks
E
Bo
Cam
F
Folks
Adams-Berne
Bolen-Cage
Camp-Dutton
Ervin-Evans
Faber-Folk
Folks-Gaddis
1
2
3
4
5
6
23
Operações sobre Árvores
+
B
Remover Embry e Folks
E
Bo
Cam
F
Folks
Adams-Berne
Bolen-Cage
Camp-Dutton
Ervin-Evans
Faber-Folk
Frost-Gaddis
1
2
3
4
5
6
24
Operações sobre Árvores
•
Inserção com subdivisão: mudanças no número de
blocos de registros
•
•
+
B
Alteração no conjunto de índices através das
regras aplicadas às Árvores B
Supressão com redistribuição e/ou concatenação:
idem
25
Operações sobre Árvores
+
B
Inserir Ayers
E
Bo
Cam
F
Folks
Adams-Berne
Bolen-Cage
Camp-Dutton
Ervin-Evans
Faber-Folk
Frost-Gaddis
1
2
3
4
5
6
25
Operações sobre Árvores
+
B
Inserir Ayers
E
Bo
Cam
F
Folks
split
Adams-Berne
Bolen-Cage
Camp-Dutton
Ervin-Evans
Faber-Folk
Frost-Gaddis
1
2
3
4
5
6
26
Operações sobre Árvores
+
B
Inserir Ayers
E
Bo
Cam
F
Folks
split
Adams-Avery Ayers-Berne
1
Ay
7
Bolen-Cage
Camp-Dutton
Ervin-Evans
Faber-Folk
Frost-Gaddis
2
3
4
5
6
27
Operações sobre Árvores
+
B
Inserir Ayers
Bo
Cam
Ay
Adams-Avery Ayers-Berne
1
7
E
F
Folks
Bolen-Cage
Camp-Dutton
Ervin-Evans
Faber-Folk
Frost-Gaddis
2
3
4
5
6
28
Operações sobre Árvores
•
Supressão com underflow: concatenação dos blocos
de registros
Bo
Adams-Avery Ayers-Berne
7
E
Cam
Ay
1
+
B
F
Folks
Bolen-Cage
Camp-Dutton
Ervin-Evans
Faber-Folk
Frost-Gaddis
2
3
4
5
6
28
Operações sobre Árvores
•
Supressão com underflow: concatenação dos blocos
de registros
Remover Cage
Bo
Adams-Avery Ayers-Berne
7
E
Cam
Ay
1
+
B
F
Folks
Bolen-Cage
Camp-Dutton
Ervin-Evans
Faber-Folk
Frost-Gaddis
2
3
4
5
6
29
Operações sobre Árvores
•
Supressão com underflow: concatenação dos blocos
de registros
Remover Cage
Bo
Adams-Avery Ayers-Berne
7
E
Cam
Ay
1
+
B
Bolen
Camp-Dutton
2
3
concatenação
F
Folks
Ervin-Evans
Faber-Folk
Frost-Gaddis
4
5
6
30
Operações sobre Árvores
•
Supressão com underflow: concatenação dos blocos
de registros
Remover Cage
Bo
Adams-Avery Ayers-Berne Bolen-Dutton
7
E
Cam
Ay
1
+
B
2
F
Folks
Ervin-Evans
Faber-Folk
Frost-Gaddis
4
5
6
31
Operações sobre Árvores
•
Supressão com underflow: concatenação dos blocos
de registros
Remover Cage
Bo
Adams-Avery Ayers-Berne Bolen-Dutton
7
E
F
Ay
1
+
B
2
Folks
Ervin-Evans
Faber-Folk
Frost-Gaddis
4
5
6
32
Operações sobre Árvores
•
Supressão com underflow: concatenação dos blocos
de registros
Remover Cage
E
Ay
Bo
Adams-Avery Ayers-Berne Bolen-Dutton
1
+
B
7
2
F
Folks
Ervin-Evans
Faber-Folk
Frost-Gaddis
4
5
6
33
Operações sobre Árvores
•
+
B
Supressão com underflow: concatenação dos blocos
de registros
Remover Cage
E
Ay
F
Bo
Folks
Adams-Avery Ayers-Berne Bolen-Dutton Ervin-Evans
1
7
2
4
Faber-Folk
Frost-Gaddis
5
6
34
Operações sobre Árvores
•
+
B
Portanto:
•
Se blocos de registros são subdivididos, um
novo delimitador é necessário no conjunto de
índices
•
Se blocos são concatenados, um separador deve
ser removido do conjunto de índices
•
Se registros são redistribuídos entre blocos da
sequência de registros, o delimitador no
conjunto de índices deve ser atualizado
35
Blocos de Conjunto de Índices
•
Os índices (delimitadores) podem ser armaenados
em blocos, tal como os registros
•
Os delimitadores podem ser de tamanho variável
•
•
Grande número de delimitadores em um bloco
de índice
•
Árvore menos profunda
Busca binária pode ser feita sobre estes
delimitadores armazenados em RAM
36
Exemplo de Estrutura de um
Bloco de Índice
Delimitadores concatenados
AsBaBroCChCraDeleEdiErrFaFle
00 02 04 07 08 10 13 17 20 23 25
Índices dos delimitadores
36
Exemplo de Estrutura de um
Bloco de Índice
Delimitadores concatenados
AsBaBroCChCraDeleEdiErrFaFle
00 02 04 07 08 10 13 17 20 23 25
Índices dos delimitadores
No de delimitadores
Tamanho total dos delimitadores
índices
delimitadores
no relativo dos blocos
11 28 AsBaBroCChCraDeleEdiErrFaFle 00 02 04 07 08 10 13 17 20 23 25 B00 B01 B02 B03 B04 B05 B06 B07 B08 B09 B10 B11
37
Exemplo de Estrutura de um
Bloco de Índice
No de delimitadores
Tamanho total dos delimitadores
índices
delimitadores
no relativo dos blocos
11 28 AsBaBroCChCraDeleEdiErrFaFle 00 02 04 07 08 10 13 17 20 23 25 B00 B01 B02 B03 B04 B05 B06 B07 B08 B09 B10 B11
Nível conceitual:
ordem dos delimitadores:
0
1
2
3
4
5
6
7
8
9
10
B00 As B01 Ba B02 Bro B03 C B04 Ch B05 Cra B06 Dele B07 Edi B08 Err B09 Fa B10 Fle B11
38
Criação Sequencial da Árvore
•
+
B
Problema: A criação aleatória da árvore (com registros
introduzidos não-ordenadamente à medida que chegam)
envolve operações de subdivisão e redistribuição que
são “caras”
38
Criação Sequencial da Árvore
+
B
•
Problema: A criação aleatória da árvore (com registros
introduzidos não-ordenadamente à medida que chegam)
envolve operações de subdivisão e redistribuição que
são “caras”
•
Ideia: Ordenar o conjunto dos registros que comporão
a árvore, armazenando-os sucessivamente nos blocos
•
Os registros são armazenados na ordem correta.
Para cada bloco é definido o seu delimitador que, em
seguida, é armazenado no bloco índices (contido em
memória até que o bloco fique cheio)
39
Exemplo
ALWASPBET 00 03 06
ACCESS-ALSO
ALWAYS-ASK
ASPECT-BEST
BETTER-CAST
39
Exemplo
Novo bloco: CATCH-CHECK
ALWASPBET 00 03 06
ACCESS-ALSO
ALWAYS-ASK
ASPECT-BEST
BETTER-CAST
40
Exemplo
Novo bloco: CATCH-CHECK
CAT
00 -1 -1
bloco sem
delimitadores
ALWASPBET 00 03 06
ACCESS-ALSO
ALWAYS-ASK
ASPECT-BEST
-1 -1 -1
BETTER-CAST
CATCH-CHECK
41
Exemplo
Novo bloco: CLASS-COPY
CAT
00 -1 -1
ALWASPBET 00 03 06
ACCESS-ALSO
ALWAYS-ASK
ASPECT-BEST
-1 -1 -1
BETTER-CAST
CATCH-CHECK
42
Exemplo
Novo bloco: CLASS-COPY
CAT
ALWASPBET 00 03 06
ACCESS-ALSO
ALWAYS-ASK
ASPECT-BEST
00 -1 -1
CL
BETTER-CAST
00 -1 -1
CATCH-CHECK
CLASS-COPY
43
Exemplo
Novo bloco: COST-DAMAGE
CAT
ALWASPBET 00 03 06
ACCESS-ALSO
ALWAYS-ASK
ASPECT-BEST
00 -1 -1
CLCOS
BETTER-CAST
00 02 -1
CATCH-CHECK
CLASS-COPY
COST-DAMAGE
44
Exemplo
Novo bloco: DELETE-DISE
CAT
00 -1 -1
ALWASPBET 00 03 06
ACCESS-ALSO
ALWAYS-ASK
ASPECT-BEST
...
CLCOSDE
BETTER-CAST
CATCH-CHECK
00 02 05
...
CLASS-COPY
COST-DAMAGE
DELETE-DISE
45
Exemplo
Novo bloco: DRUM-EDITOR
CATDR
ALWASPBET 00 03 06
ACCESS-ALSO
ALWAYS-ASK
00 03 -1
CLCOSDE
ASPECT-BEST
...
CATCH-CHECK
...
00 02 05
BETTER-CAST
CLASS-COPY
DRUM-EDITOR
-1 -1 -1
...
COST-DAMAGE
DELETE-DISE
...
46
Exemplo
Novo bloco: EFFORT-GROW
CATDR
ALWASPBET 00 03 06
ACCESS-ALSO
ALWAYS-ASK
00 03 -1
CLCOSDE
ASPECT-BEST
...
CATCH-CHECK
...
00 02 05
BETTER-CAST
CLASS-COPY
DRUM-EDITOR
EF
00 -1 -1
...
COST-DAMAGE
EFFORT-GROW
DELETE-DISE
...
47
Exemplo
Novo bloco: HEAD-IDEAL
CATDR
ALWASPBET 00 03 06
ACCESS-ALSO
ALWAYS-ASK
00 03 -1
CLCOSDE
ASPECT-BEST
...
CATCH-CHECK
...
00 02 05
BETTER-CAST
CLASS-COPY
DRUM-EDITOR
EFH
00 02 -1
...
COST-DAMAGE
EFFORT-GROW
DELETE-DISE
HEAD-IDEAL
...
48
Exemplo
Novo bloco: IGNORE-ITEM
CATDR
ALWASPBET 00 03 06
ACCESS-ALSO
ALWAYS-ASK
00 03 -1
CLCOSDE
ASPECT-BEST
...
CATCH-CHECK
...
00 02 05
BETTER-CAST
CLASS-COPY
DRUM-EDITOR
EFHIG
00 02 03
...
COST-DAMAGE
EFFORT-GROW
DELETE-DISE
HEAD-IDEAL
...
IGNORE-ITEM
49
Separadores Completos
ALWAYSASPECTBETTER
ACCESS-ALSO
00 06 12
ALWAYS-ASK
ASPECT-BEST
BETTER-CAST
50
Referência
•
Michael Folk, Bill Zoellick. File Structures 2nd ed.,
Addison-Wesley, 1992.