Arquivos indexados, são arquivos que possuem uma entrada auxiliar, denominada índice, que possui um tamanho bem menor que o arquivo de dados, o qual otimiza as buscas aleatórias de registros, com uma determinada chave.

Um índice é um mapeamento de chaves, que é utilizada para fins de otimização na busca, permitindo uma localização mais rápida de um determinado registro em um arquivo, e eles também são armazenados em arquivos em disco.

Tipos de índices

Existem seis tipos de índices para arquivos indexados:

Primários
Secundários
Diretos
Indiretos
Densos
Esparsos

Índice Primário

Os índices primários seguem a mesma ordem do arquivo de dados, podendo ser baseados ou não na chave primária. Esse tipo de índice, podem apontar para blocos de registros, índices esparsos.

Esses tipos de índices tem um bom desempenho, pois ele tem menos registros do que o arquivo de dados, resultando em uma quantidade menor de bytes transferidos do disco rígido, implicando em menos movimentações do cabeçote de leitura e escrita, facilitando a busca.

Índice Secundário

Índices secundários não seguem a mesma ordem dos arquivos de dados, tendo as chaves de busca diferentes da chave primária. A chave pode ser qualquer composição de campos do arquivo de dados, como:

Um campo;
Uma parte dele;
Uma combinação de campos;
O resultado de um processamento com um ou mais campos.

Índice Direto

Índices diretos, são índices que contém as informações para apontar diretamente para a posição do registro, no arquivo de dados.

Índice Indireto

Índices indiretos, são índices que apontam para um índice direto, normalmente, baseado na chave primária, que por sua vez , aponta para o arquivo de dados.

Índice Denso

Os índices densos, possuem uma entrada para cada registro no arquivo de dados.

Índice Denso = (chave-ponteiro, registro)

Índice Esparso

Os índices esparsos, possuem entradas para cada bloco do arquivo de dados, podendo ser feito por agrupamento, faixas, ou critério de seleção, o que usa menos espaço de armazenagem que o índice denso. Por ser organizado em blocos de arquivos de dados, só pode haver um índice esparso por arquivo de dados.

Para encontrar algum dado, é feita uma pesquisa pelo maior argumento que seja menor ou igual ao índice. Uma vez encontrado a entrada no índice, a página no arquivo de dados é acessada, e o registro é recuperado.

Índice Esparso = (chave-ponteiro, blocos de dados)

Um problema desse tipo de índice, é a exclusão de diversos registros, o que pode modificar os registros de âncora.

Referência Bibliográfica:

KUTOVA, Marcos. Algoritmos e Estruturas de Dados III. Belo Horizonte, 2017. Apostila.

KUTOVA, Marcos. Slides e Vídeo-aulas no AVA. Acessado em: 18 de maio de 2017.

BRAGANHOLO, Vanessa. Arquivos Indexados. Disponível em:<http://www2.ic.uff.br/~vanessa/material/ed2/09-ArquivosIndexados.pdf>. Acessado em: 18 de mai. 2017.

MOUSINHO, Matheus. Arquivos - Acesso Indexado. Disponível em:<http://www.ebah.com.br/content/ABAAAfm-YAH/arquivos-acesso-indexado>. Acessado em: 18 de mai. 2017.

Wikipédia. Índice (estruturas de dados). Disponível em:<https://pt.wikipedia.org/wiki/%C3%8Dndice_(estruturas_de_dados)>. Acessado em: 18 de mai. 2017.

Universidade Estadual de Maringá – UEM. Organização de Arquivos Indexados. Disponível em:<http://www.din.uem.br/~yandre/AEDEP/organizacao-indexado.pdf>. Acessado em: 18 de mai. 2017.

ESTRUTURAS DE ÍNDICES. Disponível em:<https://view.officeapps.live.com/op/view.aspx?src=http://www.facom.ufu.br/~guliato/disciplinas/gbd2/estruturas%20de%20indice.doc>. Acessado em: 20 de mai. 2017.

BOSCARIOLI, Clodis. Módulo V: Indexação em Banco de Dados. Disponível em:<http://www.inf.unioeste.br/~clodis/BDI/BDI_2007_Modulo5_1.pdf>. Acessado em: 20 de mai. 2017.