Single-Level Ordered
Last updated
Last updated
São estruturas de um único nível que indexam um atributo da relação.
Armazena cada valor do atributo indexado e a respectiva localização do tuplo na relação (ponteiro para a estrutura física de dados da tabela).
Índices são ordenados o que permite pesquisa binária sobre o atributo.
Analogia: Índice de um livro (palavra – página).
Permite uma pesquisa binária com complexidade: log_2(bi) (bi - index blocks).
A cada etapa do algoritmo, a parte da estrutura do índice a pesquisar é reduzida num factor de 2.
Indexa um atributo chave da relação (não se repete).
Indexa um atributo que pode ter valores duplicados.
Os atributos estão agrupados.
Indexa outros atributos (chave candidata ou não chave).
Podemos ter vários índices deste tipo
