Arquivos Extensíveis
Sumário
•
•
•
•
•
2
Aplicação
Tipos de espalhamento em arquivos extensíveis
Mecanismo de acesso
Espalhamento dinâmico
Espalhamento extensível
Aplicação
• Arquivos de acesso direto que possam expandir-se
sem programação
• Embora com menor frequencia este tipo de arquivos
também pode contrair-se diminuindo sem
programação
3
Tipos de espalhamento em arquivos extensíveis
• Espalhamento dinâmico
• Espalhamento extensível
4
Mecanismo de acesso
• O espalhamento em arquivos extensíveis utiliza um
mecanismo de acesso, em memória, para obter o
endereço de bucket da memória secundária
• No espalhamento dinâmico o mecanismo é uma
floresta de árvores binárias
• No espalhamento extensível o mecanismo de acesso
é um diretório (array uni dimensional) contendo o
endereço de bucket da memória secundária
• Tal como no espalhamento baseado em tabelas os
mecanismos de acesso precisam ser arquivados em
arquivos auxiliares, carregados na abertura dos
arquivos e salvos no fechamento dos arquivos
5
Espalhamento dinâmico
Mecanismo de acesso
• Em memória existem
• Células
• Seu número é igual ao número de home buckets
• Caixa de nós de células
• Cada célula possui três atributos
• Filho da esquerda
• Filho da direita
• Pai
• Os atributos filho da direita e pai iniciam aterrados
• Os atributos filho da esquerda apontam os home
buckets
7
Conceito
• Usa-se uma função hash original
• O home address retornado por esta função seleciona uma
célula em memória
• Inicialmente existem tantas células quantos são os home
addresses
• Ao se ter acesso a uma célula, se o filho da direita estiver
aterrado, o filho da esquerda aponta para o bucket onde
deve estar o registro buscado
• O acesso a esse bucket em memória secundária completa a
operação de busca
• A operação de busca retorna o registro buscado ou um slot
para a gravação de registro novo caso não exista ainda essa
chave no arquivo
8
Memória secundária
• Em memória secundária existem
• Buckets em quantidade determinada pela função hash
• Caixa de nós de buckets para transbordamento
9
Células em memória – situação inicial
Células em memória – início da floresta
Transbordamento (1)
• Quando um home bucket, considerado de primeiro
nível, transbordar:
• A caixa de nós de buckets aloca um bucket de
transbordamento
• Os registros do home bucket e o registro que causou o
transbordamento são divididos entre o home bucket e o
bucket de transbordamento
• Estes dois buckets passam a ser considerados de nível i + 1,
no caso de segundo nível
• A caixa de nós de células aloca duas novas células
12
Transbordamento (2)
• Atributos das células alocadas
• Primeira
• Pai – célula que apontava o home bucket
• Filho da esquerda – Home bucket
• Filho da direita – null
• Segunda
• Pai – célula que apontava o home bucket
• Filho da esquerda – Bucket de transbordamento
• Filho da direita – null
• Célula que apontava o home bucket
• Filho da esquerda – Primeira nova célula alocada
• Filho da direita – Segunda nova célula alocada
• A célula que apontava o home bucket passa a ser a raiz de uma árvore
binária de acesso a buckets
• O mecanismo de acesso passa a ser uma floresta de árvores binárias
13
Transbordamento (3)
• Para a divisão de registros entre buckets calcula-se a
assinatura digital de cada chave de registro
• São direcionados para o bucket da esquerda os
registros que possuam primeiro bit da assinatura
digital igual a 0
• São direcionados para o bucket da direita os registros
que possuam primeiro bit da assinatura digital igual a
0
• Quando um bucket de nível i transbordar repete-se o
processo utilizando como seletor o bit de ordem i
das assinaturas digitais e assim por diante
14
Buckets companheiros
• Definem-se como "buckets" companheiros no "hash"
dinâmico aqueles apontados por nós externos (folhas
da árvore de índices) com pai comum
• Teste de bucket meu companheiro
• Se o filho da esquerda de meu pai sou eu
• Então o candidato a bucket companheiro é o apontado pelo filho
da direita de meu pai
• Senão o candidato a bucket companheiro é o apontado pelo filho
da esquerda de meu pai
• Se o filho da direita da célula que aponta o bucket
candidato a companheiro está aterrado
• Então este é meu bucket companheiro
• Senão não tenho bucket companheiro
15
Exclusão de registros
Nas exclusões de registros:
• Se a somas das populações do bucket aonde vai
ocorrer a exclusão e de seu bucket companheiro são
comportadas por um único bucket
• Então
•
•
•
•
16
Todos os registros são concentrados em um dos dois buckets
Desaloca-se o outro bucket
Desalocam-se duas células da árvore de índices correspondentes
A célula mãe das células desalocadas aponta o bucket que restou
alocado e com registros
Espalhamento Extensível
Mecanismo de acesso
• Em memória existe
• Um diretório (array uni dimensional) contendo o endereço
de bucket da memória secundária
• Uma variável inteira (d) contendo a profundidade do
diretório (2d)
• Identificadores das posições do diretório que são os
números binários entre 0 e 2d – 1
• Estes identificadores não são armazenados
18
Conceito
• Semelhante ao espalhamento dinâmico com o mecanismo de
acesso simplificando a floresta de árvores binárias por um
diretório
• Não são empregadas funções hash
• O endereçamento é feito exclusivamente por meio de
assinaturas digitais
• Consideram-se d bits da assinatura digital como home address
• A posição do diretório correspondente a este home address
contém o endereço de bucket para a busca
• A operação de busca retorna o registro buscado ou um slot
para a gravação de registro novo caso não exista ainda essa
chave no arquivo
19
Memória secundária
• Em memória secundária existem
• Buckets inicialmente alocados (um ou dois)
• Caixa de nós de buckets para transbordamento
• Cada bucket contém além dos slots um atributo nível (t)
que é igual ao número de bits iniciais iguais das assinaturas
de todos os registros contidos no bucket
• Os valores d e t são também chamados de headers,
do diretório e dos buckets, respectivamente
20
Diretório em memória (1)
•Havia dois buckets com d = 1
•O número de registros com assinatura começando por 0 não
coube em um bucket
•Houve necessidade de dobrar o diretório d = 2
•Foi alocado mais um bucket ficando um bucket com
registros de assinaturas começando por 00 e outro bucket
com registros de assinaturas começando por 01
•O bucket com registros de assinaturas começando por 1
não transbordou aceitando 10 e 11
21
Diretório em memória (2)
A imagem abaixo mostra:
•Diretório com d = 3
•Bucket com T= 3 e registros com assinaturas começando por 000
•Bucket com T= 3 e registros com assinaturas começando por 001
•Bucket com T= 2 e registros com assinaturas começando por 010 ou 011
•Bucket com T= 2 e registros com assinaturas começando por 010 ou 011
•Bucket com T= 2 e registros com assinaturas começando por 100 ou 101
•Bucket com T= 2 e registros com assinaturas começando por 110 ou 111
22
Inicialização do Diretório
Alternativas para inicialização do diretório
•Bucket único (d = 0)
•Dois buckets (d = 1)
•Um bucket para assinaturas começando com 0
•Um bucket com assinaturas começando com 1
d=0
0
1
Bucket Nível Slot Reg K
Assinatura
1
1
1
1 11125 001111100010
2
2 41035 101010100111
3
Bucket
d=1
0
1
1
2
Nível Slot Reg K
1
1
1
1 11125
2
3
Assinatura
001111100010
2
101010100111
1
1
2
3
2
4
41035
Transbordamento (1)
• Quando um "bucket" com "header" de T bits
transborda ocorre uma partição e os C+1 (C é a
capacidade do "bucket", medida em "slots") registros
são dispersados entre a folha do "bucket" existente e
a recém-alocada, de acordo com o bit de ordem T+1
da assinatura de suas chaves.
24
Transbordamento (2)
• Os "headers" dos "buckets" passam a ter T+1 bits.
• Se d  T +1 a partição é trivial sem necessidade de
alterar a tabela de índices.
Se d < T+1 há necessidade de incrementar d, o que
dobra a tabela.
• Os "buckets" não partidos passam a receber o dobro
do número de ponteiros.
25
Buckets companheiros
• São "buckets" companheiros no "Hash" extensível
"buckets" que tem a mesma cabeça T e, além disso,
as assinaturas ou pseudo-chaves dos registros
contidos em ambos tem T-1 bits iniciais iguais
• Para achar o bucket companheirro de um dado
bucket faz-se o seguinte:
• Seja y um binários com os T bits inicias da assinatura de
qualquer dos registros do bucket
• Seja z = y XOR 1
• O bucket de endereço z, no diretório é o bucket
companheiro
26
Exclusão de registros (1)
Nas exclusões de registros:
• Se a somas das populações do bucket aonde vai
ocorrer a exclusão e de seu bucket companheiro são
comportadas por um único bucket
• Então
• Todos os registros são concentrados em um dos dois buckets
• Desaloca-se o outro bucket
• Decrementa-se o valor do header T do bucket que permanece
27
Exclusão de registros (2)
• Para o "Hashing" Extensível, após a exclusão, o
"header" do "bucket" remanescente é decrementado
de 1 unidade
• Se todos os "headers" T forem menores do que d
• Então d deve ser decrementado reduzindo a tabela
diretório à metade
28