Organização de Arquivos e Métodos de Acesso

Os arquivos são gerenciados pelo sistema operacional e é mediante a implementação de arquivos que o sistema operacional estrutura e organiza as informações.

A parte do sistema responsável pela gerência é denominada Sistema de Arquivo que é a parte mais visível do sistema operacional, pois é uma atividade frequentemente realizada pelos usuários.

Arquivo é um conjunto de registros definidos pelo sistema de arquivos e podem ser armazenados em diferentes dispositivos físicos. É constituído de informações logicamente relacionadas, podendo representar programas ou dados. É identificado por meio de um nome, formado por uma sequência de caracteres. Em alguns sistemas operacionais, a identificação de um arquivo é composta por duas partes separadas por um ponto, a parte após o ponto é chamada extensão do arquivo e serve para identificar o conteúdo.

A organização dos arquivos consiste no modo como os dados estão internamente armazenados, podendo, sua estrutura, variar em função do tipo de informação contida no arquivo.

Quando o arquivo é criado pode-se definir qual organização será adotada, que pode ser uma estrutura suportada pelo sistema operacional ou definida pela própria aplicação.

A forma mais simples de organização é através de uma sequência não estruturadas de bytes. A aplicação deve definir toda a organização, com vantagem da flexibilidade, porém todo o controle de dados é de inteira responsabilidade da aplicação.

Alguns Sistemas Operacionais estabelecem diferentes organizações de arquivos e cada arquivo deve seguir a um modelo suportado.

As organizações mais conhecidas e implementadas são a sequencial, relativa e indexada. Nestes tipos de organização, podemos visualizar um arquivo como um conjunto de registros. Quando não há uma organização dizemos que há uma organização não-estruturada.

Quando definidos sempre com o mesmo tamanho são chamados de registros de tamanho fixo e caso contrário são chamados de registros de tamanho variável.

Quando o arquivo tem registros de diversos tipos ele é chamado de Arquivo Misto.

Métodos de Acesso

Em função de como o arquivo está organizado o sistema de arquivos pode recuperar registros de diferentes maneiras:

Acesso Sequencial: arquivos armazenados em fitas magnéticas, o acesso era restrito à leitura na ordem em que eram gravados, sendo a gravação de arquivos possível apenas no final do arquivo. Pode-se combinar o acesso sequencial com o direto e com isso acessar diretamente um arquivo e os demais de forma sequencial.

• Um processo só pode ler os bytes de um arquivo na ordem em que eles estão armazenados;
• Primeiros sistemas operacionais;
• Arquivos sequenciais podem ser “rebobinados” para serem lidos novamente;
• Utilizado em fitas magnéticas.

Acesso Direto: Permite a leitura/gravação de um registro diretamente na sua posição. É realizado através do número de registro. Não existe restrição a ordem em que os registros são lidos ou gravados. Somente é possível quando é definido com registros de tamanho fixo.

• Surgiu com o aparecimento dos discos magnéticos;
• Possibilidade de acesso aos bytes fora de sua ordem de armazenamento;
• Fundamentais para algumas aplicações. Ex: bancos de dados que podem armazenar grande quantidade de dados em um único arquivo físico;
• Utilizado nos sistemas operacionais atuais.

Acesso Indexado ou Acesso por Chave: O arquivo deve possuir uma área de índice onde existam ponteiros para os diversos registros e a partir desta informação realiza-se um acesso direto.

• É o mais sofisticado dos métodos;
• Tem como base o acesso direto;
• O arquivo deve possuir uma área de índice onde existam ponteiros para os diversos registros.
• Quando a aplicação deseja acessar um registro, deverá ser especificada uma chave através da qual o sistema pesquisará, na área de índice, o ponteiro correspondente, a partir disso, acessando diretamente o arquivo.

Particionado: Quando um arquivo é composto de subarquivos denominados membros. Para acessar seus membros, o arquivo particionado possui um diretório, que funciona como seu índice. São utilizados para armazenar bibliotecas ou banco de dados.

O hashing proporciona acesso muito rápido a um registro arbitrário.

Alocação de Registros em Blocos

Os registros de um arquivo precisam ser alocados em blocos de discos porque um bloco é a unidade de transferência de dados entre o disco e a memória. Quando o tamanho do bloco é maior que o tamanho do registro, cada bloco conterá vários registros, embora raramente alguns arquivos possam ter registros tão extensos que não caibam em um bloco. Suponha que o tamanho do bloco é B bytes. Para um arquivo de registros de tamanho fixo de R bytes, com B > R, podemos colocar bfr = LB/RJ registros por bloco, onde. O valor de bfr é chamado fator blocagem (fator de divisão em blocos) para o arquivo. Em geral, R pode não dividir B exatamente; assim, em cada bloco, devemos ter espaço não utilizado igual a B – (bfr * R) bytes.

Para usar esse espaço sem uso, podemos armazenar parte de um registro em um bloco e o restante em outro. Ao final do primeiro bloco, um ponteiro aponta para o bloco que contém o restante do registro no caso de ele não ser um bloco consecutivo no disco. Essa organização é chamada Registros Spanned porque os registros podem se fragmentar por mais de um bloco. Sempre que um registro for maior que um bloco, devemos usar uma organização Spanned. Se os registros não puderem atravessar as fronteiras dos blocos, a organização é chamada de não-spanned. Essa organização é usada com registros de tamanho fixo, tendo B > R, porque isso faz com que cada registro comece em uma localização conhecida no bloco, simplificando o processamento dos registros. Para registros de tamanho variável, podem ser usadas tanto a organização spanned quanto a não-spanned. Se o tamanho médio dos registros é grande, é vantajoso usar a spanned para reduzir a perda de espaço em cada bloco.

Alocação de Blocos de Espaço em Disco

O Sistema Operacional possui uma estrutura de dados que armazena informações que possibilitam ao sistema de arquivos gerenciar as áreas ou blocos livres.

Nessa estrutura, geralmente uma lista ou tabela, é possível identificar blocos livres que poderão ser alocados por um novo arquivo.

Quando um arquivo é eliminado, todos os seus blocos são liberados para a estrutura de espaços livres.

Mapa de Bits: Forma mais simples de implementar uma estrutura de espaços livres. Cada entrada da tabela é associada a um bloco do disco representado por um bit que pode ser 0 (livre) ou 1 (ocupado).

Lista encadeada: Existe uma lista encadeada de todos os blocos livres do disco. Cada bloco possui uma área reservada para armazenamento do endereço do próximo bloco; A partir do primeiro bloco livre pode-se ter acesso sequencial aos demais de forma encadeada; Problema: para se achar espaço livre, o algoritmo deve sempre realizar uma pesquisa sequencial na lista.

Blocos Contíguos: são geralmente alocados ou liberados simultaneamente. Enxerga o disco como um conjunto de segmentos de blocos livres. Possível manter uma tabela com o endereço do primeiro bloco de cada segmento e o número de blocos livres contíguos que se seguem.

Alocação Contígua

A alocação contígua consiste em armazenar um arquivo em blocos sequencialmente dispostos, permitindo ao sistema localizar um arquivo através do endereço do primeiro bloco e da sua extensão em blocos. O acesso é feito de maneira simples, tanto para a forma sequencial quanto para a direta.

Um problema desse tipo de alocação é que quando um arquivo é criado com n blocos, é necessário que exista uma cadeia de n blocos livres disposto sequencialmente. Nesse tipo de alocação, o disco é visto como um grande vetor, com segmentos ocupados e livres.

A alocação em um novo segmento livre consiste técnicas para escolha, algumas das principais são:

First-fit (Algoritmo da Primeira Alocação): Seleciona o primeiro segmento livre com o tamanho suficiente para alocar o arquivo e a busca é feita sequencialmente, interrompendo ao achar um segmento livre do tamanho adequado. É o mecanismo mais rápido, consumindo menos recursos do sistema.

Ou seja, procura-se pelo primeiro espaço na lista o suficientemente grande para armazenar o processo. É um algoritmo rápido pois ele gasta o tempo mínimo em procura. Se o processo não ocupa todo o espaço o restante é disponibilizado como buraco na lista. A pesquisa por espaço sempre inicia na parte baixa de memória, independentemente dos locais escolhidos para alocar os dados.

Next-Fit (Algoritmo da Próxima Alocação – Circular Fit): A algoritmo da próxima alocação (next fit): semelhante ao first-fit, só que a próxima alocação inicia com uma busca a partir da página onde terminou a alocação anterior e não da parte baixa da memória.

Best-fit (Algoritmo da Melhor Alocação): Seleciona o menor segmento livre disponível com o tamanho suficiente para armazenar o arquivo e é necessária a busca em toda a lista, caso esta não esteja ordenada por tamanho. Este algoritmo é mais lento que o anterior pois precisa pesquisar em toda a lista para descobrir qual a melhor opção.

De acordo com o próprio livro de SO do Tanenbaum, o algorítmo best fit é um dos que apresenta pior fragmentação, por deixar pequenos fragmentos de memória inúteis (quando não encontra a alocação perfeita, ele aloca em um espaço com uma pequena sobra que acaba não sendo usada com facilidade). Tanto que o worst fit foi criado com a intenção de reduzir a fragmentação deixando espaços maiores que podem ser úteis.

Worst-fit (Algoritmo da Pior Alocação): Seleciona o maior segmento livre e a busca funciona como no caso anterior. Algoritmo da pior alocação (worst fit): procura pelo maior espaço capaz de armazenar o processo, de tal forma que o espaço restante seja grande o suficiente para armazenar outro processo.

Last Fit: Aloca no última área disponível.

Um problema na alocação contígua é a fragmentação dos espaços livres causado pela criação e eliminação constante de arquivos é que com o tempo surgem espaços vagos sem o tamanho suficiente para se alocar novos arquivos. Buscando solucionar este problema, utiliza-se a desfragmentação que tenta reorganizar os arquivos no disco de maneira que só exista um único segmento de blocos contíguo. A desfragmentação é lenta e deve ser realizada periodicamente.

Alocação Encadeada

Na alocação encadeada um arquivo pode ser organizado como um conjunto de blocos ligados logicamente no disco, independente da sua localização física, sendo que cada bloco possui um ponteiro para o bloco seguinte do arquivo e assim sucessivamente.

Neste tipo de alocação, ocorre grande fragmentação dos arquivos devido aos blocos livres dos arquivos não precisarem ser contíguos, existe a quebra do arquivo em diversos pedaços, denominados extents. Essa fragmentação aumenta o tempo de acesso aos arquivos, pois exige que o mecanismo de leitura/gravação se desloque diversas vezes sob sua superfície. Dessa forma se torna necessário a execução da operação de desfragmentação periodicamente.

Um problema na alocação encadeada é que ela só permite o acesso sequencial aos blocos dos arquivos, não possuindo acesso direto aos blocos e desperdiça espaço nos blocos com o armazenamento de ponteiros.

Alocação Indexada

A alocação indexada soluciona o problema da alocação encadeada referente ao acesso direto aos blocos dos arquivos, pois mantém os ponteiros de todos os blocos do arquivo em uma única estrutura denominada bloco de índice.

Fragmentação

A fragmentação interna é a perda de espaço dentro de uma área de tamanho fixo. Numa memória secundária, ela ocorre quando um arquivo ou fragmento de arquivo não ocupa completamente o espaço da unidade de alocação destinado a ele, causando desperdício de espaço.

Arquivos são alocados em blocos. Estes blocos têm tamanho fixo entre 512 bytes e 8 Kbytes. Um bloco não pode ser alocado parcialmente. Por exemplo: Se utilizarmos blocos de 4096 bytes, e tentarmos alocar um arquivo de 5700 bytes, terminaremos ocupando 2 blocos:

• Bloco 01: 4096 bytes;
• Bloco 02: 1604 bytes.

No Bloco 02 deixará de ser utilizado 2492 bytes, que estarão inutilizáveis. Em média, perde-se 1/2 bloco por arquivo. Este é um exemplo de Fragmentação Interna.

A escolha do tamanho dos blocos é importante para a eficiência do sistema.

Blocos Pequenos: menor perda por fragmentação interna, mais blocos por arquivo: maior custo de gerência e desempenho.

Blocos Grandes: maior perda por fragmentação interna, menos blocos por arquivo: menor custo de gerência e desempenho.

A fragmentação externa é semelhante, porém não é interna aos blocos, mas perda de espaço em um disco ou particionamento dinâmico. Este tipo de fragmentação começa a acontecer quando os programas forem terminando e deixando espaços cada vez menores na memória, não permitindo o ingresso de novos programas. Para contornar o problema, há algoritmos que movem os segmentos para próximos uns dos outros (compactação), deixando espaço de memória contíguo, não-fragmentado disponível. Há também algoritmos de escolha de espaços vazios para alocar processos como o first-fit, best-fit e o worst-fit.

No particionamento dinâmico de memória, tanto o número de partições quanto o tamanho das partições podem variar de acordo com a demanda dos processos.

Armazenamento em Banco de Dados

A coleção de dados que compõe um banco de dados computadorizado precisa ser armazenada fisicamente em alguma mídia de armazenamento de computador. Assim, os softwares SGBD podem recuperar, atualizar e processar esses dados conforme necessário. As mídias de armazenamento de computador formam uma hierarquia de armazenamento que inclui duas categorias principais:

Armazenamento primário: Esta categoria inclui mídias de armazenamento que podem ser operadas diretamente pela unidade central de processamento (CPU), tais como a memória principal do computador e as menores, porém rápidas, memórias cache. O armazenamento primário geralmente fornece acesso rápido aos dados, mas sua capacidade é limitada.

Armazenamento secundário: Os dados de um armazenamento secundário não podem ser processados diretamente pela CPU; eles devem primeiro ser copiados em um armazenamento primário. Esta categoria inclui discos magnéticos, discos ópticos e fitas. Esses dispositivos geralmente possuem maior capacidade, menor custo e proporcionam um acesso mais lento aos dados do que os dispositivos de armazenamento primário.

Hierarquias de Memórias e Dispositivos de Armazenamento

Em um sistema de computador moderno, os dados residem e são transportados por meio de uma hierarquia de mídias de armazenamento. A memória de maior velocidade é mais cara e, por isso, tem menor capacidade. A memória de menor velocidade como armazenamento em fita, que é off-line, tem capacidade de armazenamento potencialmente infinita.

No nível de armazenamento primário, a hierarquia de memória possui, na extremidade mais cara, a memória cache, que é uma RAM (Random Access Memory — Memória de Acesso Aleatório) estática. A memória cache é geralmente usada pela CPU para acelerar a execução de programas. No próximo nível de armazenamento primário está a DRAM (RAM Dinâmica), que fornece a principal área de trabalho para a CPU manter seus programas e dados — é popularmente chamada de memória principal. A vantagem da DRAM é seu baixo custo, que continua a cair; a desvantagem é sua volatilidade e sua menor velocidade se comparada à RAM estática. No nível de armazenamento secundário, a hierarquia compreende discos magnéticos, bem como armazenamento em massa na forma de dispositivos de CD-ROM (Compact Disk-Read-Only Memory — Memória Apenas para Leitura em Disco Compacto), e finalmente as fitas, na extremidade mais barata da hierarquia. A capacidade de armazenamento é medida em kilobytes (Kbyte ou 1.000 bytes), megabytes (Mbyte ou 1 milhão de bytes), gigabytes (Gbyte ou 1 bilhão de bytes) e até mesmo em terabytes (1.000 Gbytes).

Os programas residem e são executados na DRAM. Geralmente os bancos de dados de grande porte que permanecem residentes em memória usam a memória secundária, e parcelas desse banco de dados são lidas e registradas em buffers da memória principal, conforme necessário. Agora que os computadores pessoais e as estações de trabalho possuem centenas de megabytes de dados em DRAM, está se tornando possível carregar uma grande fração de um banco de dados em memória principal. RAMs de 8 a 16 gigabytes em um único servidor estão se tornando comuns. Em alguns casos, bancos de dados inteiros podem ser mantidos na memória principal (com um backup em disco magnético), levando aos bancos de dados em memória principal — estes são particularmente úteis em aplicações de tempo real que exigem tempos de resposta extremamente rápidos. Um exemplo são as aplicações de comutação telefônica, que armazenam, em memória principal, os bancos de dados de roteamento e de linhas.

Entre o armazenamento em DRAM e em discos magnéticos, outra forma de memória, a memória flash, está se tornando comum, particularmente porque é não-volátil. As memórias flash são de alta densidade e de alto desempenho, e usam a tecnologia EEPROM (Electrically Erasable Programmable Read-Only Memory — Memória Apenas de Leitura Eletricamente Programável). A vantagem da memória flash é sua alta velocidade de acesso; a desvantagem é que um bloco inteiro precisa ser apagado e escrito de cada vez. Cartões de memória flash estão aparecendo como mídia de armazenamento de dados em componentes com capacidades que variam de alguns megabytes a gigabytes. Eles vêm sendo usados em câmeras, aparelhos de MP3, acessórios de armazenamento USB etc.

Os discos CD-ROM armazenam dados opticamente, que são lidos por um laser. Os CD-roms contêm dados pré-gravados que não podem ser sobrescritos. Os discos WORM (Write’Once’Read’Memory — Memória de Leitura de Única Gravação) são uma forma de armazenamento óptico usado para arquivar dados; eles permitem que os dados sejam escritos uma vez e lidos infinitas vezes, sem a possibilidade de serem apagados. Eles mantêm aproximadamente meio gigabyte de dados por disco e duram muito mais que os discos magnéticos. As memórias ópticas juke box usam uma série de discos CD-ROM, que são carregados em unidades de leitura segundo a demanda. Embora as juke box ópticas tenham capacidade da ordem de centenas de gigabytes, seu tempo de recuperação é da ordem de centenas de milissegundos, muito mais lentos que os discos magnéticos. Esse tipo de armazenamento está em declínio em vista da rápida queda no custo e do aumento da capacidade dos discos magnéticos. O DVD (Digital Video Disk — disco de vídeo digital) é um padrão recente dos discos ópticos, permitindo de 4,5 até 15 gigabytes de armazenamento por disco. A maioria das unidades de disco dos computadores pessoais atuais lê discos CD-Rom e DVD.

Finalmente, as fitas magnéticas são usadas para arquivo e backup de dados. As fitas juke box — que contêm um conjunto de fitas catalogadas e podem ser automaticamente gravadas em unidades de fitas — estão se tornando populares como armazenamento terciário, para manter Terabytes de dados. Por exemplo, o sistema EOS (Earth Observation Satellite — Satélite de Observação da Terra) da NASA mantém bancos de dados arquivados dessa maneira.

Grandes empresas já consideram normal manter bancos de dados da ordem de Terabytes. O termo banco de dados muito grande (Very Large Database) não pode mais ser definido com precisão, pois a capacidade de armazenamento em disco está em ascensão enquanto os custos estão em queda. Muito brevemente, o termo será reservado a bancos de dados que contenham dezenas de Terabytes.

Armazenamento de Bancos de Dados

Os bancos de dados geralmente armazenam grandes quantidades de dados que devem ser mantidos por longos períodos de tempo. Os dados são acessados e processados repetidamente durante essa fase. Tal fato contrasta com a noção de estruturas de dados transitórios (Transient), que são mantidos por tempo limitado durante a execução de um programa. Muitos bancos de dados são armazenados permanentemente (ou persistentemente) em armazenamento secundário de discos magnéticos pelas seguintes razões:

• Geralmente os bancos de dados são muito grandes para caberem inteiramente na memória principal.
• As circunstâncias que causam a perda permanente de dados armazenados aparecem menos frequentemente em armazenamento secundário de disco do que em armazenamento primário. Assim, nos referimos a disco — e a outros dispositivos de armazenamento secundário — como armazenamento não-volátil, enquanto a memória principal é frequentemente chamada armazenamento volátil.
• O custo de armazenamento por unidade de dado é uma ordem de magnitude menor para discos que para armazenamento primário.

Algumas das tecnologias mais novas — tais como discos ópticos, DVDs e fitas juke box — provavelmente serão opções viáveis para o uso de discos magnéticos. Assim, no futuro, os bancos de dados poderão residir em níveis da hierarquia de memória diferentes daqueles descritos na Seção anterior. Entretanto, pode-se antecipar que os discos magnéticos continuarão a ser a mídia de escolha primária para grandes bancos de dados nos próximos anos. Por isso, é importante estudar e compreender as propriedades e as características dos discos magnéticos e a maneira como os arquivos de dados podem ser neles organizados com o objetivo de projetar bancos de dados eficientes e com desempenho aceitável.

As fitas magnéticas são frequentemente usadas como uma mídia de armazenamento para backup de bancos de dados porque o armazenamento em fita tem um custo ainda menor que o armazenamento em disco. Entretanto, o acesso a dados em fitas é mais lento. Os dados armazenados em fitas são off-line, isto é, é necessária alguma intervenção de um operador — ou de um dispositivo automático de carga — para carregar a fita antes que os dados se tornem disponíveis. Em contraste, os discos são dispositivos on-line, ou seja, podem ser acessados diretamente, a qualquer momento.

As técnicas utilizadas para armazenar grandes quantidades de dados estruturados em um disco são importantes para os projetistas de bancos de dados, bem como para o DBA e para os responsáveis pela implementação de SGBDs. Os projetistas de bancos de dados e o DBA devem conhecer as vantagens e as desvantagens de cada técnica de armazenamento quando projetam, implementam e operam um banco de dados em um SGBD específico. Geralmente o SGBD possui diversas opções disponíveis para a organização dos dados, e o processo de projeto físico do banco de dados envolve escolher, entre as opções disponíveis, as técnicas de organização que melhor se adaptem aos requisitos de uma dada aplicação. Os responsáveis pela implementação de sistemas SGBD devem estudar as técnicas de organização de dados de forma que possam implementá-las eficientemente e, assim, proporcionar opções suficientes ao DBA e aos usuários de SGBD.

Normalmente as aplicações comuns de bancos de dados necessitam de apenas uma pequena parte do banco de dados para processamento em um determinado momento. Quando certa porção dos dados for necessária, ela precisará ser localizada no disco, copiada para a memória principal para ser processada e, então, registrada, caso os dados tenham sido modificados. Os dados armazenados no disco são organizados como arquivos de registros. Cada registro é uma coleção de valores de dados que podem ser interpretados como fatos a respeito de entidades, bem como seus atributos e seus relacionamentos. Os registros devem ser armazenados no disco de maneira que seja possível localizá-los eficientemente quando necessário.

Dispositivos de armazenamento secundário

Os discos são dispositivos de armazenamento secundário de acesso aleatório porque um bloco de disco arbitrário pode ser acessado “aleatoriamente”, desde que especifiquemos seu endereço. As fitas magnéticas são dispositivos de acesso sequencial, pois para acessar o n-ésimo bloco na fita, devemos primeiro percorrer os n-1 blocos precedentes.

Organizações Primárias de Arquivo

Há diversas organizações primárias de arquivo que determinam como os registros de um arquivo são posicionados fisicamente no disco e, portanto, como eles podem ser acessados. Um arquivo heap (ou arquivo desordenado) posiciona os registros no disco sem nenhuma ordem específica, por meio do acréscimo de novos registros ao final do arquivo; já um arquivo ordenado (sorted ou arquivo seqüencial) mantém os registros ordenados segundo o valor de um campo em particular (chamado chave de ordenação). Um arquivo hashed usa uma função hash aplicada a um campo em particular (chamado chave de hash) para determinar a posição de um registro no disco. Outras organizações primárias de arquivo, tais como as árvores-B (B-trees), usam estruturas de árvores. Uma organização secundária ou uma estrutura de acesso auxiliar permite um acesso eficiente aos registros de um arquivo baseando-se em campos alternativos àqueles que tenham sido usados para a organização primária do arquivo. A maioria deles existe como índices.

Métodos para a organização dos registros de um arquivo em disco. Várias técnicas genéricas, tais como classificação, hashing e indexação, são usadas para criar métodos de acesso. Além disso, várias técnicas genéricas para a manipulação de inclusões e exclusões funcionam com muitas organizações de arquivo.

Arquivos de registros desordenados (Heap Files): No tipo de organização mais simples e básica, os registros estão posicionados no arquivo segundo a ordem pela qual foram incluídos, de forma que novos registros são acrescentados ao final do arquivo. Tal organização é chamada heap file ou pile file (arquivo pilha). Essa organização é frequentemente utilizada com caminhos de acesso adicionais, tais como os índices secundários. Ela também é usada para coletar e armazenar registros para uso futuro.

Arquivos de registros Ordenados (Sorted Files): Podemos ordenar fisicamente os registros de um arquivo em um disco a partir dos valores de um de seus campos— chamado campo de classificação. Isso leva a um arquivo ordenado ou sequencial. Se o campo de classificação também for um campo chave do arquivo — um campo do qual se garante ter um único valor em cada registro —, então o campo é chamado Chave de Classificação para o arquivo.

Técnicas de Hashing: Um outro tipo de organização primária de arquivo baseia-se em hashing, que fornece um acesso muito rápido aos registros sob certas condições de pesquisa. Essa organização é geralmente chamada arquivo hash. A condição de pesquisa precisa ser de igualdade em um único campo; neste caso, o campo é chamado campo de hash. Na maioria dos casos, o campo de hash será também o campo-chave do arquivo e, assim, será chamado Chave de Hash. A idéia do hashing é fornecer uma função H, chamada Função Hash ou Função Randomizing, que, aplicada ao valor do campo de hash de um registro, gere o endereço do bloco de disco no qual o registro está armazenado. A busca do registro dentro do bloco pode ser realizada em um buffer da memória principal. Para a maioria dos registros, necessitamos de apenas um bloco para recuperar esse registro.  A maior desvantagem do esquema de hashing estático, que acabamos de ver, é que o espaço de endereços hash é fixo. Desse modo, é difícil expandir ou diminuir o arquivo dinamicamente.

• Hashing Interno: Facilitar localização de registros em um arquivo.
• Hashing Externo: Facilitar localização de arquivos em um disco.
• Hashing extensível: Uma solução para o problema do Hashing Estático.
• Hashing Linear: Outra solução para o problema do Hashing Estático, utilizando Buckets.

Ainda existem outros tipos de organizações primárias de arquivos, como Arquivos de Registro Misto, e Árvore B.

Caminhos de Acesso Secundário

Além da Organização Primária de Arquivo como a desordenada, a ordenada ou Hash, que foram descritas acima. Descreveremos estruturas de acesso adicionais auxiliares chamadas Índices, que são usadas para aumentar a velocidade da recuperação de registros na resposta a certas condições de busca. Geralmente, as estruturas de índice fornecem caminhos de acesso secundário, que proveem caminhos de acesso alternativos aos registros sem afetar a disposição física dos registros no arquivo. Elas possibilitam um acesso eficiente aos registros a partir de campos de indexação que são usados para construir o índice.

Tipos de índices ordenados em nível único

A ideia em que se baseia a estrutura de acesso de índice ordenado é a mesma do índice de um livro-texto: listar os termos importantes ao final do livro, em ordem alfabética, com uma lista dos números de páginas onde o termo aparece. Podemos pesquisar um índice para encontrar a lista de endereços — números de página, neste caso— e usar esses endereços para localizar um termo no livro-texto, pesquisando nas páginas indicadas. A alternativa, se nenhum outro guia nos fosse fornecido, seria peneirar lentamente, palavra por palavra, todo o livro-texto para encontrar o termo no qual estivéssemos interessados; isso corresponde a fazer uma busca linear em um arquivo. É claro que a maioria dos livros possui informações adicionais, tais como títulos de capítulo e de seção, que nos ajudam a encontrar um termo sem a necessidade de pesquisar o livro inteiro. Entretanto, o índice é a única indicação exata de onde cada termo se encontra no livro.

Para um arquivo com uma dada estrutura de registros, composto de diversos campos (ou atributos), uma estrutura de acesso de índice geralmente é definida com base em um único campo do arquivo, chamado Campo de Indexação (ou Atributo de Indexação). De maneira geral, o índice armazena cada valor do campo de indexação com uma lista de ponteiros para todos os blocos de disco que contêm registros com aquele valor de campo. Os valores no índice são ordenados de forma que possamos realizar uma busca binária. O arquivo de índice é muito menor que o arquivo de dados, assim, a busca do índice por meio da busca binária é razoavelmente eficiente. Os índices multiníveis nos desobrigam da necessidade de realizar a busca binária ao custo da criação de índices para o próprio índice.

Há vários tipos de índices ordenados. Um índice primário é especificado sobre o campo-chave de classificação de um arquivo ordenado de registros. Relembre que na qual um campo-chave de classificação é usado para ordenar fisicamente os registros do arquivo no disco, e cada registro possui um único valor para o campo. Se o campo de classificação não é um campo-chave — ou seja, se vários registros no arquivo podem ter o mesmo valor para o campo de classificação —, outro tipo de índice, chamado índice clustering, pode ser utilizado. Observe que um arquivo pode ter, no máximo, um campo de classificação física, portanto, ele só terá um índice primário ou um índice clustering, mas não ambos. Um terceiro tipo de índice, chamado índice secundário, pode ser especificado sobre qualquer campo que não seja o de classificação de um arquivo. Um arquivo pode ter diversos índices secundários além de seu método de acesso primário.

Índices Multiníveis

Os esquemas de indexação que descrevemos até aqui envolvem um arquivo de índice ordenado. Uma busca binária é aplicada ao índice para localizar os ponteiros para um bloco do disco ou para um registro (ou registros) do arquivo que possua um valor específico no campo de indexação. Uma busca binária exige aproximadamente (k^b;) acessos a blocos em um índice com bj blocos, porque cada passo do algoritmo reduz à metade a parte do arquivo de índice na qual devemos prosseguir a busca. Essa é a razão pela qual usamos a função log com base 2. A ideia de um índice multinível é reduzir a parte do arquivo de índice na qual devemos prosseguir a busca dividindo-a por bfr;, fator de divisão em blocos para o índice, que é maior que 2. Por isso, o espaço de busca é reduzido muito mais rapidamente . O valor bfrj é chamado de fan-out do índice multinível, e nos referimos a ele pelo símbolo fo. A busca em índice multinível requer aproximadamente (logfobj) acessos a blocos, que é um número menor que o da busca binária se o fan-out for maior que 2.

Resolução de Questões de Concursos Anteriores

RESPOSTA: B

Algoritmo da primeira alocação (first fit): procura-se pelo primeiro espaço na lista o suficientemente grande para armazenar o processo. É um algoritmo rápido pois ele gasta o tempo mínimo em procura. Se o processo não ocupa todo o espaço o restante é disponibilizado como buraco na lista. A pesquisa por espaço sempre inicia na parte baixa de memória, independentemente dos locais escolhidos para alocar os dados.

RESPOSTA: D

A primeira está incorreta, a fragmentação externa é que é resultante do particionamento dinâmico de memória.

RESPOSTA: A

Para reduzir o excesso de fragmentação interna, a Alocação Particionada Dinâmica elimina o conceito de partição externa e passa a alocar o espaço de memória exatamente necessário para a execução do processo, mas precisa enfrentar o problema da fragmentação externa, pois à medida que os vários processos são alocados e desalocados da memória principal, espaços de memória remanescentes entre os vários processos podem ser tão pequenos a ponto de não comportarem qualquer processo que encontre-se em espera, gerando a fragmentação externa da memória.

RESPOSTA: D

Não pode ser next-fit, nem o First-fit pois trabalham de forma parecida e o First fit alocaria a memória no primeiro espaço, sobrando 1K para ser alocado no segundo espaço (14K), ocorrendo uma fragmentação interna de 13K.

Best-fit alocaria os 21k no espaço de 22k, havendo uma fragmentação interna de 1K

Worst-fit alocará no maior espaço disponível (39k), havendo uma fragmentação de 18K.

Last-Fit alocaria no ultimo espaço disponível 27k, haveria uma fragmentação de 5K.

Logo, o Best Fit é a melhor opção no exemplo. Embora seja importante relembrar que Tanenbaum disse: “o algorítmo best fit é um dos que apresenta pior fragmentação, por deixar pequenos fragmentos de memória inúteis (quando não encontra a alocação perfeita, ele aloca em um espaço com uma pequena sobra que acaba não sendo usada com facilidade). Tanto que o worst fit foi criado com a intenção de reduzir a fragmentação deixando espaços maiores que podem ser úteis.”

RESPOSTA: A e B (Questão Anulada)

Os métodos de acesso são: Sequencial, direto, Indexado e Particionado (este último citado por alguns autores).

RESPOSTA: Certo

Como na questão não foi citado nada sobre o modo de acesso, nem que seriam usados índices (quando são utilizados índices, a pesquisa pode ser de várias formas, p ex.: binária, inverso, etc..), por “default” refere-se à pesquisa sequencial, onde todos os registros são lidos desde o 1º até que o referido registro seja encontrado.

RESPOSTA: Errado

Pegadinha, o arquivo está ordenado pela matrícula, mas a pesquisa será feita pelo nome! Por esse motivo a questão está incorreta, se a pesquisa fosse feita pela matrícula (que está ordenado) poderia ser utilizada a pesquisa binária.

Como não está ordenado por nome, a pesquisa não pode ser aplicada por nome, seria necessário a criança anteriormente de um índice em nome.

RESPOSTA: C

First-Fit: aloca memória na primeira partição que couber o programa. Assim, não há gasto com processamento.

RESPOSTA: Errado

As duas podem acontecer na memória principal como na secundária.

Tanto a fragmentação interna quanto a externa são indesejáveis, porque causam desperdícios na RAM:

Fragmentação interna: ocorre na alocação estática, nos espaços livres que sobram em cada bloco, ao se encaixar um novo processo;

Fragmentação externa: ocorre na alocação dinâmica, nos espaços livres que se formam, quando um ou mais processos terminam.

A fragmentação interna é a perda de espaço dentro de uma área de tamanho fixo. A fragmentação externa ocorre no particionamento dinâmico.

No particionamento dinâmico, cada processo submetido à execução recebe o tamanho necessário para se comportar por completo na memória. Assim, a memória principal é subdividida em segmentos de tamanho variado. No particionamento fixo, a memória é subdividida em blocos de tamanho fixo (iguais ou não) chamados em páginas, blocos ou frames.

Na memória principal eu posso realizar o particionamento dinâmico ou fixo. Então a questão está errada.

RESPOSTA: D

A letra A está incorreta pois as fitas são para acesso sequencial, e não aleatório. Discos sim são para acesso aleatório.

A letra B está incorreta pois arquivos é que são uma sequencia ou não de registros.

A letra C está incorreta pois é nos Heaps que os registros estão posicionados no arquivo segundo a ordem pela qual foram incluídos, de forma que novos registros são acrescentados ao final do arquivo.

A letra E está incompleta, as organizações primárias de arquivos são a desordenada, a ordenada e a Técnica Hashing.

RESPOSTA: C

RESPOSTA: Errado

O erro da questão está no uso do termo “Em ambos os casos”, a explicação que segue é apenas para “arquivo invertido”.

“Um banco de dados textual é uma coleção de documentos, que pode também ser visto como um largo conjunto de registos, em que cada registo contém apenas uma lista de palavras de tamanho arbitrário. Os dois métodos principais de busca por frases em bancos de dados textuais de larga escala, utilizando indexação de textos, são os arquivos invertidos com contadores de posição e índices para a próxima palavra.

Um arquivo invertido possui duas partes principais: uma estrutura de busca, chamada de vocabulário, contendo todos os termos distintos existentes no texto indexados e, para cada termo, uma lista invertida que armazena os identificadores dos registros contendo o termo. Consultas são feitas tomando-se a lista invertida correspondente ao termo procurado. As consultas booleanas são feitas obtendo-se a conjunção ou disjunção entre as listas relativas ao termos presentes na consulta. Arquivos invertidos podem ser utilizados para busca de frases, através da adição de mais informações a lista invertida. Basicamente, adiciona-se os deslocamentos no texto em que ocorrem as palavras.

Para a recuperação da frase “the man who is”, inicialmente devemos determinar os pares a serem pesquisados. Uma vez que o número de palavras na frase é par, podemos agrupar em pesquisas ao índice de próxima palavra. Dessa forma, realizamos a recuperação do par `”the man”, juntamente com a recuperação do par ”who is”. Analisando, notamos que o par “the man” ocorre no documento 5, na posição 235. Fazendo o mesmo para o par “who is”, podemos constatar sua ocorrência no mesmo documento 2 posições subseqüentes. Isso significa que os pares se sucedem no texto. Pares distintos são sucessivos se ocorrem com diferença de 2 posições. Pares compostos são sucessivos se possuem diferença de 1 posição. Se a consulta desejada fosse a frase “the man who”, estaríamos impossibilitados de dividir a frase em pares distintos. Nesse caso, teríamos que procurar o par “the man” e o par “man who”. Esses pares, para serem considerado sucessivos, devem ocorrer com uma diferença de 1 posição nos índices. Existem diversas técnicas para otimizar a pesquisa por frases. Na seção 3.2 discutimos essas alternativas.

A técnica de índice para a próxima palavra pode auxiliar não apenas na pesquisa por frases. Dentre suas outras utilidades destacamos:

• Navegação em frases. Dado uma palavra w, o índice pode ser utilizado para identificar todas as palavras seguintes. Esta funcionalidade não pode ser alcançada pelos arquivos invertidos.
• O índice pode ser utilizado para a complementação de frases e complementação de palavras dentro de uma frase“

RESPOSTA: Errado

A alocação indexada permite distribuir um arquivo em diversos blocos, o que pode aumentar a fragmentação interna.