Indeces
2925 palavras
12 páginas
Banco de Dados I2007
Módulo V: Indexação em Banco de Dados
(Aulas 1, 2 e 3)
Clodis Boscarioli
Agenda:
Estruturas de Índices;
Conceitos;
Tipos de Índices:
Primários;
Secundários;
Clustering;
Multiníveis;
Árvore B e B+;
Hash;
Exemplos.
Índice - Conceitos
Estrutura de dados que recebe como entrada uma propriedade de registro (por exemplo, um valor de um ou mais campos) e encontra os registros com essa propriedade rapidamente;
Um índice permite localizar um registro sem ter que examinar mais que uma pequena fração dos registros possíveis;
O(s) campo(s) cujos valores o índice se baseia formam a chave de pesquisa;
Índices são, portanto, estruturas de dados auxiliares cujo único propósito é tornar mais rápido o acesso a registros baseado em certos campos, chamados campos de indexação.
índice(valor)
Blocos contendo registros Registros coincidentes Estruturas de índices
Índice primário - baseado na chave de ordenação;
Índice de agrupamento (clustering) - baseado no campo de ordenação não-chave de um arquivo;
Índice secundário - baseado em qualquer campo não ordenado de um arquivo;
Índices multiníveis;
Árvores B e B+;
Tabelas Hash;
Índices sobre Arquivos Seqüenciais
Tipos de índices
Densos: uma entrada no arquivo de índices p/cada registro no arquivo de dados
10
10
20
20
30
40
Esparsos: apenas alguns registros de dados são representados no arquivo de índices
10
30
50
70
30
40
50
60
60
110
60
130
70
150
80
Um índice denso sobre um arquivo de dados seqüenciais
30
90
50
80
20
40
50
70
10
70
80
Um índice esparso sobre um arquivo de dados seqüenciais
Tipos de índices
Índice Denso
Seqüência de blocos contendo apenas as chaves dos registros e os ponteiros para os próprios registros
Índice denso = (chave-ponteiro, registro)
Índice Esparso
Usa menos espaço de armazenamento que o índice denso ao custo de um tempo um pouco maior para localizar um registro dada a sua chave
Índice esparso = (chave-ponteiro, blocos de dados)
Aponta para o 1o.