Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
ESTRUTURAS DE INDEXAÇÃO
Adriano Maranhão
DEFINIÇÃO
um índice é uma estrutura (ou arquivo) auxiliar associado a uma tabela. Sua função é acelerar o tempo de acesso às linhas de uma tabela, criando ponteiros para os dados armazenados em colunas específicas. O banco de dados usa o índice de maneira semelhante ao índice remissivo de um livro, verifica um determinado assunto no índice e depois localiza a sua posição em uma determinada página.
Fonte: wikipédia
TIPOS DE ÍNDICE
Índices Compostos: fazem referência a mais de uma coluna.
Índices Simples: fazem referência a uma única coluna.
Índices internos: a chave está contida dentro da tabela.
Índices externos: quando existe uma tabela de chaves separada que associa ponteiros à registros de uma tabela.
EX: ÍNDICE COMPOSTO
EX:ÍNDICE PRIMÁRIO
ÍNDICE PRIMÁRIO
índice cuja chave especifica a ordem sequencial do arquivoíndice denso:
há uma entrada no índice para cada valor de chave que ocorre em um registro de dados a entrada aponta para o primeiro registro que contém aquele valor de chave
índice esparso:
há um entrada no índice apenas para alguns valores de chave a entrada aponta para o primeiro registro que contém aquele valor de chave para localizar um registro com chave K, procura-se a entrada E do índice com o maior valor de chave menor ou igual a K e pesquisa-se o arquivo a partir do registro apontado por E
ÍNDICE SECUNDÁRIO
índice cuja chave não é aquela da ordem
sequencial do arquivo
organização:
há uma entrada no índice para cada valor de
chave que ocorre em um registro de dados a
entrada aponta para todos os registros que
contém aquele valor de chave x
ÁRVORES-B+
árvore de busca de ordem n a raíz possui no
mínimo 2 filhos
cada folha possui no mínimo ©(n-1)/2ª valores
de chave
cada nó interior possui no mínimo ©n/2ª filhos
todos os ramos tem o mesmo comprimento
EX: ÁRVORES-B+
CONT: ÁRVORES-B+
as folhas formam um índice denso para o arquivo:
contém todos os valores de chave, em ordem ascendente
o ponteiro precedendo um valor de chave k aponta para
um bloco de ponteiros apontando para os registros com chave k
o último ponteiro de uma folha aponta para a próxima folha
os nós internos formam um índice esparso para as chaves contidas nas folhas
HASHING
memória secundária dividida em B buckets(tipicamente, B=2n)
função de hash h mapeia as chaves em inteiros no intervalo [0,B]
buckets pode ficar "cheios" (bucket overflow):
use o primeiro bucket com espaço vazio (linear probing), ou
crie uma lista encadeada de buckets (overflow chaining)
EX:HASHING
EX: ÍNDICE NO MYSQL
CREATE INDEX name_do_meu_indice ON
minha_tabela (coluna_name(10));