Acesso Sequencial Indexado
Objetivo: Considerar de forma unificada as seguintes visões
sobre estruturas de acesso a arquivos:
• Visão indexada: o arquivo é visto como um conjunto de
registros indexados por chaves.
• Visão sequencial: o arquivo pode ser acessado sequencialmente,
gerando registros ordenados por chaves.
Exemplo:
Operações cosequenciais
+
operações indexadas
ler um arquivo “inteiro” (menos seek) ler cada chave para acessar os registros
para, por exemplo, ordená-lo
Acesso Sequencial Indexado
Conjuntos de sequência de registros
Objetivo: manter dinamicamente um conjunto de registros ordenados
por chaves no disco
Problema: ordenação do arquivo em disco é “cara”!
Solução:
• organizar os registros em blocos  operações locais
• um bloco se torna a menor unidade endereçável nas operações
de leitura e escrita no disco (é carregado todo na RAM).
Exemplo:
Chaves = nomes
4 nomes/bloco (fator de bloco)
Chaves:
Adams
Baird
Bixby
Boone
Bynum
Carson
Cole
Davis
Denver
Ellis
bloco 1
Adams
bloco 2
Baird Bixby
Boone
Bynum Carson Cole Davis
bloco 3
Denver
Ellis
Introduzir Carter :
bloco 1
bloco 2
bloco 3
bloco 4
Adams
Baird Bixby Boone
Bynum Carson Carter
Denver
Cole
Ellis
Davis
subdivisão (split)
de bloco
Eliminar Davis :
bloco 1
bloco 2
bloco 3
bloco 4
Adams
Baird Bixby
Boone
Bynum Carson Carter
Denver
Cole
Ellis
underflow
Eliminar Davis :
bloco 1
bloco 2
Adams
Baird Bixby
Bynum Carson Carter
bloco 3
bloco 4
Boone
disponível
Cole
Denver
Ellis
concatenação
Conclusão: o arquivo inteiro pode ser mantido ordenado apenas
pela ordenação de suas partes (blocos).
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?
-Deve representar um compromisso entre tempo de acesso, memória RAM
(buffer) disponível e as operações a serem executadas.
• O tamanho do bloco deve permitir o armazenamento de vários destes na
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 economizando-se em seeks).
Sequência de registros e indexação
Objetivo: definir um método eficiente que possibilite o acesso a
um bloco contendo uma chave (ou registro) procurada.
Ideia: construir um índice de chaves (a partir do último registro de
cada bloco, por exemplo), apontando para cada um destes blocos.
Sequência de blocos:
Adams-Berne Bolen-Cage Camp-Dutton Embry-Evans Faber-Folk
1
2
3
4
5
Folks-Gaddis
6
Adams-Berne Bolen-Cage Camp-Dutton Embry-Evans Faber-Folk
1
2
Chave
Berne
Cage
Dutton
Evans
Folk
Gaddis
3
4
Número do Bloco
1
2
3
4
5
6
Índices da sequência de blocos
5
Folks-Gaddis
6
Chaves delimitadoras
• Os índices servem apenas de guia na busca do bloco que contém a chave a
ser acessada  delimitadores
• Menor delimitador possível (não-único)  economia de espaço (neste caso,
teremos uma árvore B+ de prefixo simples)
Delimitadores de blocos
CAM
BO
F
E
FOLKS
Adams-Berne Bolen-Cage Camp-Dutton Embry-Evans Faber-Folk
1
2
3
4
5
Folks-Gaddis
6
Arquivo sequencial indexado e árvore B+ de prefixo simples
E
conjunto de
índices
BO
F
CAM
FOLKS
Adams-Berne Bolen-Cage Camp-Dutton Embry-Evans Faber-Folk
1
2
3
4
5
Folks-Gaddis
6
A busca
• A partir dos índices na árvore B, podemos acessar um bloco da seguinte
forma:
1.
Se chave procurada < delimitador, então vá para a esquerda na árvore
2.
se chave >= delimitador, então vá para a direita na árvore
Lembrando: Árvore B+ de prefixo simples  os delimitadores são os
menores possíveis na árvore B
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
E
conjunto de
índices
BO
CAM
F
FOLKS
Adams-Berne Bolen-Cage Camp-Dutton Embry-Evans Faber-Folk
1
2
3
4
5
Folks-Gaddis
6
Apagar Embry e Folks
E
BO
F
CAM
FOLKS
Adams-Berne Bolen-Cage Camp-Dutton Embry-Evans Faber-Folk
1
2
3
4
5
Folks-Gaddis
6
E
BO
Adams-Berne
1
F
CAM
Bolen-Cage Camp-Dutton
2
3
FOLKS
Ervin-Evans
Faber-Folk
4
5
Frost-Gaddis
6
• Inserção causando subdivisão  mudanças no número de blocos
de registros
 alteração no conjunto de índices através das regras aplicadas às
árvores B.
• Supressão com redistribuição e/ou concatenação  idem
Inserir Ayers
E
BO
Adams-Berne
CAM
F
Bolen-Cage Camp-Dutton
1
Ervin-Evans
Faber-Folk
4
5
3
2
FOLKS
Frost-Gaddis
6
Ayers (causa subdivisão do bloco 1 com criação do bloco 7)
BO
CAM
AY
Adams-Avery
1
Ayers-Berne
7
E
F
Bolen-Cage Camp-Dutton
2
3
FOLKS
Ervin-Evans
Faber-Folk
4
5
Frost-Gaddis
6
• Supressão com underflow  concatenação dos blocos de registros
BO
CAM
AY
Adams-Avery
1
Ayers-Berne
7
E
F
Bolen-Cage Camp-Dutton
2
3
FOLKS
Ervin-Evans
Faber-Folk
4
5
Frost-Gaddis
6
remoções no bloco 2 causam underflow e subsequente
concatenação com o bloco 3, o qual pode ser colocado numa
avail list
BO
CAM
AY
Adams-Avery
E
F
Ayers-Berne Bolen-Cage Camp-Dutton
7
1
2
FOLKS
Ervin-Evans
Faber-Folk
4
5
3
Frost-Gaddis
6
concatenação
E
AY
Adams-Avery
1
BO
F
Ayers-Berne Bolen-Dutton
7
2
FOLKS
Ervin-Evans
Faber-Folk
Frost-Gaddis
4
5
6
Assim:
• 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
Blocos de Conjunto de Índices (delimitadores)
• Os índices podem ser armazenados em blocos, tal como os registros
(de mesmo tamanho dos blocos dos registros)
• Os delimitadores podem ser de tamanho variável  grande número de
delimitadores em um bloco de índice  árvore menos profunda. Uma
busca binária pode ser feita sobre estes delimitadores armazenados em
RAM
Exemplo de estrutura de um bloco de índice
AsBsBroCChCraDeleEdlErrFaFle
delimitadores concatenados
00 02 04 07 08 10 13 17 20 23 25
NRR dos delimitadores
Número de delimitadores
Tamanho total dos delimitadores
11
28
AsBsBroCChCraDeleEdlErrFaFle 00 02 04 07 08 10 13 17 20 23 25 B00 B01 B02 B03 B04 B05 B06 B07 B08 B09 B10 B11
delimitadores
NRR dos delimitadores
Número relativo dos blocos
Número de delimitadores
Tamanho total dos delimitadores
11
28
AsBsBroCChCraDeleEdlErrFaFle 00 02 04 07 08 10 13 17 20 23 25 B00 B01 B02 B03 B04 B05 B06 B07 B08 B09 B10 B11
delimitadores
NRR dos delimitadores
Número relativo dos blocos
Nível conceitual:
ordem dos delimitadores
0
1
2
3
4
5
6
7
8
9
10
B00 As B01 Bs B02 Bro B03 C B04 Ch B05 Cra B06 Dele B07 Edi B08 Err B09 Fa B10 Fle
B11
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 de índices (contido na
memória até que o bloco esteja cheio)
Exemplo:
ALWASPBET 00 03 06
Access-Also
Always-Ask
Aspect-Best
Better-Cast
Catch-Check
Novo bloco
CAT
-1 -1
ALWASPBET 00 03 06
Access-Also
Always-Ask
bloco sem
delimitadores!
00 -1 -1
Aspect-Best
Better-Cast
-1
Catch-Check
Class-Copy
Novo bloco
00
CAT
ALWASPBET 00 03 06
CL
-1 -1
00 -1 -1
Access-Also Always-Ask Aspect-Best Better-Cast
Catch-Check Class-copy
Cost-Damage
Novo bloco
00
CAT
ALWASPBET 00 03 06
CL COS
-1 -1
00 02 -1
Access-Also Always-Ask Aspect-Best Better-Cast
Catch-Check Class-copy Cost-Damage
Delete-Dise
Novo bloco
CAT
ALWASPBET 00 03 06
00
CL COS DE
-1 -1
00 02 05
Access-Also Always-Ask Aspect-Best Better-Cast
Catch-Check Class-copy Cost-Damage Delete-Dise
Drum-Editor
Novo bloco
CAT DR
ALWASPBET 00 03 06
00
CL COS DE
03 -1
00 02 05
Access-Also Always-Ask Aspect-Best Better-Cast
Catch-Check Class-copy Cost-Damage Delete-Dise
Drum-Editor
-1 -1 -1
Effort-Crow
Novo bloco
CAT DR
ALWASPBET 00 03 06
00
CL COS DE
03 -1
00 02 05
EF
Access-Also Always-Ask Aspect-Best Better-Cast
Catch-Check Class-copy Cost-Damage Delete-Dise
Drum-Editor Effort-Crow
00 -1 -1
Head-Ideal
Novo bloco
CAT DR
ALWASPBET 00 03 06
00
CL COS DE
03 -1
00 02 05
EFH
00 02 -1
Access-Also Always-Ask Aspect-Best Better-Cast
Catch-Check Class-copy Cost-Damage Delete-Dise
Drum-Editor Effort-Crow Head-Ideal
Ignore-Item
Novo bloco
CAT DR
ALWASPBET 00 03 06
00
CL COS DE
03 -1
00 02 05
EFHIG
00 02 03
Access-Also Always-Ask Aspect-Best Better-Cast
Catch-Check Class-copy Cost-Damage Delete-Dise
Drum-Editor Effort-Crow Head-Ideal
Ignore-Item
Separadores Completos
ALWAYSASPECTBETTER
Access-Also
Always-Ask
00 06 12
Aspect-Best
Better-Cast
Referência:
- Michael
J. Folk e Bill Zoellick. File Structures, Second Edition,
Addison-Wesley, 1992.