Ordenação de arquivos, Busca binária e árvore B

...

programação. Estes incluem os tipos de dados numéricos (inteiro, inteiro longo ou ponto

flutuante), cadeia de caracteres (tamanho fixo ou variável), booleanos (tendo valores apenas 0

ou 1, ou TRUE ou FALSE) e, às vezes, tipo de data e tempo especialmente codificados.

Em algumas aplicações de bancos de dados, pode haver necessidade de armazenar

itens de dados que consistem em grandes objetos não estruturados, que representam imagens,

vídeo digitalizado ou streams de áudio, ou então texto livre. Estes são conhecidos como

BLOBs (objetos binários grandes). Um item de dados BLOBs costuma ser armazenado

separadamente de seu registro, em um conjunto de blocos de disco, e um ponteiro para o

BLOB é incluído no registro.

Um arquivo é uma sequência de registros. Em muitos casos, todos os registros em um

arquivo são do mesmo tipo de registro. Se cada registro no arquivo tem exatamente o mesmo

tamanho (em bytes), o arquivo é considerado composto de registros de tamanho fixo. Se

diferentes registros no arquivo possuem diversos tamanhos, o arquivo é considerado

composto de registros de tamanho variável.

2.1 - Arquivos de registros desordenados (arquivos de heap)

Neste tipo de organização mais simples e mais básico, os registros são arquivados na

ordem em que são inseridos, de modo que novos registros são inseridos ao final do arquivo.

Essa organização é chamada arquivo de heap ou pilha. Normalmente, ela é usada com

caminhos de acesso adicionais, como os índices secundários. Ela também é usada para coletar

e armazenar registros de dados para o uso futuro.

A inserção de um novo registro é muito eficiente. O último bloco de disco do arquivo

é copiado para um buffer, o novo registro é acrescentado e o bloco é então regravado de volta

4

---------------------------------------------------------------

ao disco. O endereço do último bloco de arquivo é mantido no cabeçalho do arquivo. No

entanto, procurar um registro usando qualquer condição de pesquisa envolve uma pesquisa

linear pelo bloco de arquivo por bloco – um procedimento dispendioso. Se apenas um registro

satisfazer a condição de pesquisa, então, na média, um programa lerá a memória e pesquisará

a metade dos blocos de arquivo antes de encontrar o registro. Para um bloco de arquivo de b

blocos, isso exige pesquisar (b/2) blocos, na média. Se nenhum registro ou vários registros

satisfizerem a condição de pesquisa, o programa deve ler e pesquisar todos os b blocos no

arquivo.

Para excluir um registro, um programa deve primeiro encontrar seus bloco, copiá-lo

para um buffer, excluir o registro do buffer e, finalmente, regravar o bloco de volta ao disco.

Isso deixa um espaço livre no bloco de disco. A exclusão de um grande número de registros

dessa maneira resulta em espaço de armazenamento desperdiçado. Outra técnica usada para

exclusão de registro é ter um byte ou um bit extra, chamado marcador de exclusão,

armazenado em cada registro. Um registro é excluído ao se decidir o marcador de exclusão

com determinado valor. Um valor diferente para o marcador indica um registro válido (não

excluído). Os programas de pesquisa consideram apenas registros válidos em um bloco

quando realizam sua busca. Essas duas técnicas de exclusão exigem reorganização periódica

do arquivo para retornar o espaço não usado dos registros excluídos. Durante a reorganização,

os blocos de arquivo são acessados de maneira consecutiva, e os registros são compactados

pela remoção dos registros excluídos. Depois dessa reorganização, os blocos são preenchidos

até a capacidade mais uma vez.

2.2 - Arquivos de registros ordenados (arquivos classificados)

Podemos ordenar fisicamente os registros de um arquivo no disco com base nos

valores de um dos seus campos – chamado de campo de ordenação. Isso leva a um arquivo

ordenado ou sequencial. Se o campo de ordenação também for um campo-chave do arquivo –

um campo com garantias de ter valor exclusivo em cada registro –, então o campo é chamado

de chave de ordenação para o arquivo.

A ordenação não oferece quaisquer vantagens para o acesso aleatório ou ordenado dos

registros com base nos valores dos outros campos não ordenados do arquivo. Nesses casos,

realizam-se uma pesquisa linear para acesso aleatório. Para acessar os registros em ordem

5

---------------------------------------------------------------

baseados no campo não ordenado,

...