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

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