3 - Tipos de índices ordenados de único nível
Para uma tabela de dados com determinada estrutura de registro consistindo em vários campos, um índice normalmente é definido em um único campo da tabela, chamado campo de índice (ou atributo de indexação). O índice costuma armazenar cada valor do campo de índice junto com uma lista de ponteiros para todos os blocos de disco que contêm registros com esse valor de campo.
Os valores no índice são ordenados de modo que possamos realizar uma pesquisa binária no índice: verdadeiro se satisfaz a condição de pesquisa ou falso se não satisfaz. Se tanto o arquivo de dados quanto o arquivo de índice estiverem ordenados, e visto que este normalmente é muito menor do que o arquivo de dados, a procura no índice que usa pesquisa binária é uma opção mais eficiente (já vimos anteriormente que o algoritmo de árvore binária é capaz de localizar valores com extrema eficiência).
-
Existem vários tipos de índices ordenados. Um índice primário é especificado no campo de chave de ordenação de um arquivo ordenado de registros (chave primária). Lembre-se que um campo de chave de ordenação é usado para ordenar fisicamente os registros de arquivo no disco, e cada registro tem um valor único para esse campo. Veja este exemplo.
Se o campo de ordenação não for um campo de valor exclusivo (único), ou seja, se diversos registros no arquivo puderem ter o mesmo valor para o campo de ordenação, outro tipo de índice, chamado índice de agrupamento (clustering), pode ser utilizado.
|
Observe que um arquivo pode ter apenas um campo de ordenação física, de modo que pode ter apenas um índice primário ou um índice de agrupamento, mas não ambos. |
Um terceiro tipo de índice, chamado índice secundário, pode ser especificado em qualquer campo de uma tabela. Um arquivo de dados pode ter vários índices secundários além de seu método de acesso primário. Vamos estudar agora os tipos de índices e calcular o número de operações que eles levam para encontrar os resultados.
Veja este exemplo
Por exemplo, suponha que uma tabela FUNCIONÁRIO, possua os campos ID_Funcionário, Nome, CPF e Data_Nascimento. Se a chave primária for ID_Funcionário, os registros serão fisicamente armazenados na sequência do ID_Funcionário (exemplo: 1 – Marcelo, 2 – Ana, 3 – Cláudio, ...). Se a chave primária for Nome, os registros serão fisicamente armazenados na sequência alfabética (exemplo: 2- Ana, 3 – Cláudio, 1 – Marcelo, ...). Perceba que nessa segunda forma, toda vez que um novo funcionário é cadastrado na tabela, a tabela precisa ser reorganizada alfabeticamente para satisfazer a condição de índice primário. O mesmo aconteceria se a chave primária fosse baseada no CPF do funcionário, os registros precisariam ser reordenados sempre que inserções ou alterações surgissem. Já quando utilizamos como chave primária um número sequencial, sempre um novo elemento é agregado ao final da tabela, evitando a reordenação dos demais dados.
X