Single-Level Ordered

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.

Single-Level Index - Tipos

Primary

Indexa um atributo chave da relação (não se repete).

Clustered Index

Indexa um atributo que pode ter valores duplicados.

Os atributos estão agrupados.

Secondary Index

Indexa outros atributos (chave candidata ou não chave).

Podemos ter vários índices deste tipo