Acesso Sequencial Indexado Objetivo: Considerar de forma unificada as seguintes visões sobre estruturas de acesso a arquivos: Visão indexada: o arquivo

Acesso Sequencial Indexado

Objetivo: Considerar de forma unificada as seguintes visõessobre 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.

Operações cosequenciais + operações indexadas

ler um arquivo “inteiro” (menos seek) para, por exemplo, ordená-lo

ler cada chave para acessar os registros

Exemplo:

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 = nomes4 nomes/bloco (fator de bloco)

Chaves:AdamsBairdBixbyBooneBynumCarsonColeDavisDenverEllis

Adams Baird Bixby Boonebloco 1

Bynum Carson Cole Davisbloco 2

Denver Ellisbloco 3

Introduzir Carter :

Cole Davis


Bynum Carson Carterbloco 2

Denver Ellisbloco 3

bloco 4

bloco 1

bloco 2

bloco 3

bloco 2 subdivisão (split)de bloco

Eliminar Davis :

Cole



Denver Ellisbloco 3

bloco 4

bloco 1

bloco 2

bloco 3

bloco 2

underflow

Eliminar Davis :

Cole Denver



Ellis

bloco 3

bloco 4

bloco 1

bloco 2

bloco 3

bloco 2

disponível

concatenação

Conclusão: o arquivo inteiro pode ser mantido ordenado apenaspela 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 deum 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 aum bloco contendo uma chave (ou registro) procurada.

Ideia: construir um índice de chaves (a partir do último registro decada bloco, por exemplo), apontando para cada um destes blocos.

Adams-Berne Bolen-Cage Camp-Dutton Embry-Evans Faber-Folk Folks-Gaddis

Sequência de blocos:

1 2 3 4 5 6


1 2 3 4 5 6

Chave Número do BlocoBerne 1Cage 2Dutton 3Evans 4Folk 5Gaddis 6

Índices da sequência de blocos

Chaves delimitadoras

• Os índices servem apenas de guia na busca do bloco que contém a chave aser acessada delimitadores

• Menor delimitador possível (não-único) economia de espaço (neste caso, teremos uma árvore B+ de prefixo simples)


1 2 3 4 5 6

BO CAM E F FOLKS

Delimitadores de blocos

Arquivo sequencial indexado e árvore B+ de prefixo simples

E

BO CAM F FOLKS


1 2 3 4 5 6

conjunto deíndices

• A partir dos índices na árvore B, podemos acessar um bloco da seguinteforma:

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

A busca

Operações sobre árvores B+

• Supressão de registros sem originar concatenação e redistribuição alteraçõesapenas nos blocos de registros; o conjunto de índices não é alterado

E

BO CAM F FOLKS

Adams-Berne Bolen-Cage Camp-Dutton Embry-Evans Faber-Folk Folks-Gaddis1 2 3 4 5 6

conjunto deíndices

• Inserção sem subdivisão idem

6

Apagar Embry e Folks

E

BO CAM F FOLKS

Adams-Berne Bolen-Cage Camp-Dutton Embry-Evans Faber-Folk Folks-Gaddis1 2 3 4 5

E

BO CAM F FOLKS

Adams-Berne Bolen-Cage Camp-Dutton Ervin-Evans Faber-Folk Frost-Gaddis1 2 3 4 5 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

E

BO CAM F FOLKS

Adams-Berne Bolen-Cage Camp-Dutton Ervin-Evans Faber-Folk Frost-Gaddis

1 2 3 4 5 6

Inserir Ayers

Ayers (causa subdivisão do bloco 1 com criação do bloco 7)

CAMAY F FOLKS

Adams-Avery Bolen-Cage Camp-Dutton Ervin-Evans Faber-Folk Frost-Gaddis

1 2 3 4 5 6

BO E

Ayers-Berne

7

• Supressão com underflow concatenação dos blocos de registros

CAMAY F FOLKS


1 2 3 4 5 6

BO E

Ayers-Berne

7

remoções no bloco 2 causam underflow e subsequenteconcatenação com o bloco 3, o qual pode ser colocado numaavail list

CAMAY F FOLKS


1 2 3 4 5 6

BO E

Ayers-Berne

7

concatenação

AY F FOLKS

Adams-Avery Ervin-Evans Faber-Folk Frost-Gaddis

1 4 5 6

BO

E

Ayers-Berne

7

Bolen-Dutton

2

Assim:

• Se blocos de registros são subdivididos um novo delimitador é necessáriono conjunto de índices

• Se blocos são concatenados um separador deve ser removido do conjuntode í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 dedelimitadores em um bloco de índice árvore menos profunda. Umabusca binária pode ser feita sobre estes delimitadores armazenados emRAM

AsBsBroCChCraDeleEdlErrFaFle

00 02 04 07 08 10 13 17 20 23 25

delimitadores concatenados

NRR dos delimitadores

AsBsBroCChCraDeleEdlErrFaFle 00 02 04 07 08 10 13 17 20 23 25 B00 B01 B02 B03 B04 B05 B06 B07 B08 B09 B10 B1111 28

Número de delimitadores

Tamanho total dos delimitadores

delimitadores NRR dos delimitadores Número relativo dos blocos

Exemplo de estrutura de um bloco de índice

AsBsBroCChCraDeleEdlErrFaFle 00 02 04 07 08 10 13 17 20 23 25 B00 B01 B02 B03 B04 B05 B06 B07 B08 B09 B10 B1111 28

Número de delimitadores

Tamanho total dos delimitadores

delimitadores NRR dos delimitadores Número relativo dos blocos

B00 As B01 Bs B02 Bro B03 C B04 Ch B05 Cra B06 Dele B07 Edi B08 Err B09 Fa B10 Fle B11

0 1 2 3 4 5 6 7 8 9 10

ordem dos delimitadores

Nível conceitual:

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 oseu delimitador que, em seguida, é armazenado no bloco de índices (contido namemória até que o bloco esteja cheio)

ALWASPBET 00 03 06

Access-Also Always-Ask Aspect-Best Better-Cast

Exemplo:

Catch-CheckNovo bloco

ALWASPBET 00 03 06


-1 -1 -1

00 -1 -1CAT

Catch-Check

bloco semdelimitadores!

ALWASPBET 00 03 06


00 -1 -1CAT

Catch-Check

Class-CopyNovo bloco

CL 00 -1 -1

Class-copy

ALWASPBET 00 03 06


00 -1 -1CAT

Catch-Check

CL 00 02 -1

Class-copy

Cost-DamageNovo bloco

Cost-Damage

COS

DEALWASPBET 00 03 06


00 -1 -1CAT

Catch-Check

CL 00 02 05

Class-copy Cost-Damage

Delete-DiseNovo bloco

COS

Delete-Dise



00 03 -1CAT

Catch-Check

CL 00 02 05


COS

Delete-Dise

Drum-EditorNovo bloco

Drum-Editor

DR

-1 -1 -1

Effort-Crow



00 03 -1CAT

Catch-Check

CL 00 02 05


COS

Delete-Dise

Effort-CrowNovo bloco

Drum-Editor

DR

00 -1 -1EF

Effort-Crow



00 03 -1CAT

Catch-Check

CL 00 02 05


COS

Delete-Dise

Drum-Editor

DR

00 02 -1EFH

Head-IdealNovo bloco

Head-Ideal

Effort-Crow



00 03 -1CAT

Catch-Check

CL 00 02 05


COS

Delete-Dise

Drum-Editor

DR

00 02 03EFHIG

Ignore-ItemNovo bloco

Head-Ideal Ignore-Item

ALWAYSASPECTBETTER 00 06 12


Separadores Completos

Referência:

- Michael J. Folk e Bill Zoellick. File Structures, Second Edition, Addison-Wesley, 1992.

Documents

Acesso Sequencial Indexado Objetivo: Considerar de forma unificada as seguintes visões sobre estruturas de acesso a arquivos: Visão indexada: o arquivo