Ordenação de arquivos, Busca binária e árvore B
Por: Tercio Barbosa Silva • 20/3/2016 • Trabalho acadêmico • 5.023 Palavras (21 Páginas) • 400 Visualizações
Universidade Estadual da Paraíba
Centro de Ciência e Tecnologia
Curso de Licenciatura em Computação
Disciplina Organização de Arquivos
Professora Sabrina
ALUNO: TERCIO BARBOSA SILVA
Ordenação de arquivos, busca binária e árvore B
Campina Grande – PB
SUMÁRIO
1 – INTRODUÇÃO .................................................................................................................................... 3
2 - ORDENAÇÃO DE ARQUIVOS ............................................................................................................... 4
2.1 - Arquivos de registros desordenados (arquivos de heap) ........................................................... 4
2.2 - Arquivos de registros ordenados (arquivos classificados) .......................................................... 5
2.3 - Técnicas de hashing .................................................................................................................... 7
2.3.1 - Hashing interno .................................................................................................................... 7
2.3.2 - Hashing externo para arquivos de disco .............................................................................. 8
2.3.3 - Técnicas de hashing que permitem a expansão dinâmica do arquivo ................................ 8
3 - BUSCA BINÁRIA ................................................................................................................................ 10
4 - ÁRVORE B ......................................................................................................................................... 13
4.1 - Característica da árvore B: justificativa do nome ..................................................................... 13
4.2 - Concatenação e divisão de nós ................................................................................................. 15
4.3 - Custo das operações ................................................................................................................. 15
4.4 - Árvore B+ ................................................................................................................................... 17
4.5 – Correspondência de índices ..................................................................................................... 18
5 - CONCLUSÃO ..................................................................................................................................... 20
REFERÊNCIAS BIBLIOGRAFIAS ............................................................................................................... 21
1 – INTRODUÇÃO
Algumas atividades são de fundamental importância para o desempenho do sistema
computacional. Atividades de geração, atualização e exclusão de arquivos são constantes durante
todo o processamento das informações realizadas pelas instruções dos programas ou nas próprias
estruturas de armazenamento. Devido a tal fato é necessário rotinas de organização, e
consequentemente de ordenação dos arquivos, propiciando maior eficiência e conveniência nos
sistemas computacionais. Neste trabalho discutiremos sobre algumas formas de ordenação dos
arquivos como, por exemplo, as técnicas de heap e hashing. Logo após, discutiremos sobre as
técnicas de ordenação veremos uma técnica de busca usada pelos sistemas computacionais para
maximizar o aproveitamento do tempo na busca de informações contidas nos arquivos, a chamada
busca binária. Por fim, trataremos sobre outra técnica de busca, porém com a utilização de árvores
binárias, conhecidas também como árvore B, utiliza mecanismos de divisão de procura para
encontrar a informação ao qual se deseja.
3
2 - ORDENAÇÃO DE ARQUIVOS
Os dados costumam ser armazenados na forma de registros. Cada registro contém uma
coleção de valores ou itens de dados relacionados, no qual cada valor é formado por um ou
mais bytes e corresponde a um campo em particular do registro. Os registros normalmente
descrevem entidades e seus atributos. Uma coleção de nomes de campo e seus tipos de dados
correspondentes constituem uma definição de tipo de registro ou formato de registro. Um tipo
de dado, associado a cada campo, especifica os tipos de valores que um campo pode assumir.
O tipo de dado de um campo normalmente é um dos tipos de dado padrão usados na
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
...