Lista Invertida

Em ciência da computação, Lista Invertida ou Inverted List é uma estrutura de dados. Uma Lista de chaves primárias (Primary Keys) associada à uma outra lista, no caso de chaves secundárias.

Essas listas são índices para chaves grandes com repetições.

Funcionamento

O diretório é formado por dois grupos:

1. Listas-índice para valores de chaves.
2. Arquivo que aponta para os registros por valores de chave.

Organiza as tabelas de registros em blocos, otimizando as consultas percorrendo sempre a tabela principal. O registro é inserido em qualquer endereço vago. Sempre são removidas as entradas do índice correspondente ao que se deseja excluir. Após a pequisa ser feita é gerada uma nova tabela com os dados. As pesquisa ~booleanas são mais complexas, pois várias novas tabelas sáo geradas sempre iniciando com o valor da chave com menor número de ocorrências. Após a busca a alteração é feita no registro e gravada na mesma posição.

Vantagens

• Elimina a repetição das chaves secundárias, pois a mesma aponta para um lista de chaves primárias, permitindo a economia de espaço.

• Inserindo ou deletando um registro da tabela normalmente não é necessário alterar a tabela de chaves secundárias, movimentado os registros ou reordenando.

• Somente a lista invertida onde a chave primária será eliminada ou inserida, será atualizada.

Desvantagens

• A atualização é complicada, pois todos os arquivos de índices devem ser atualizados.

• Quanto mais índices mais complicada é a inserção.

Categories: Adabas