05 - Indices V-0'781

Prévia do material em texto

BANCO DE DADOS II 
Índices 
 
Versão dos Slides: 0.781 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
 
 
 
DCC-UFLA, Lavras 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Motivação, Introdução e Terminologia 
 Índices Primários 
 Índices Secundários 
 Índices Compostos 
2 
3 
armazenamento externo 
serviços de arquivos 
controle de propagação 
estruturas de 
armazenamento 
caminhos de 
acessos lógicos 
estruturas de 
dados lógicas C5 
C4 
C3 
C2 
C1 
Camada 3: 
Estruturas de Armazenamento 
4 
armazenamento externo 
serviços de arquivos 
controle de propagação 
estruturas de 
armazenamento 
caminhos de 
acessos lógicos 
estruturas de 
dados lógicas 
interface de registros internos 
armazenamento de registros (na B*-tree) 
unidades de endereçamento: 
registros intern., B*-trees, tabelas hash 
estruturas auxiliares: 
índices de páginas, tabelas de endereços 
unidades de endereçamento: 
páginas, segmentos 
C5 
C4 
C3 
C2 
C1 
Camada 3: 
Estruturas de Armazenamento 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Representação de Relações 
 Solução naive: 
• Registros representando tuplas de uma relação 
espalhados ao longo de vários blocos 
• Considere a consulta: 
− SELECT * FROM R 
• Todos os blocos do sistema de armazenamento teriam 
que ser pesquisados exaustivamente 
 Uma solução melhor: 
• Armazenamento de relação em conjunto específico de 
blocos ou cilindros 
• Entrentanto pouco speedup é obtido para responder 
este tipo de consulta: 
− SELECT * FROM R WHERE a=10 
 
5 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices: Intuição 
 Estruturas de dados que recebem como entrada 
uma determinada propriedade de registros (e.g., 
o valor de um ou mais campos) e encontra os 
registros que satisfazem esta propriedade 
“rapidamente” 
• Apenas uma fração dos registros do sistema de 
armazenamento são consultados 
6 
valor Índice 
Blocos 
contendo 
registros 
registros 
qualificados 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices: Conceitos Iniciais 
 Definem caminhos de acesso aos dados 
 Estruturas de dados armazenadas em memória 
secundária (e.g., disco) 
• Como dados regulares do BD, acesso a dados de 
índices requer requisições para C2 
• Muitas implementações possíveis: árvores, tabelas 
hash, listas, etc 
 Podem ser ordenados ou não ordenados 
 Podem ser definidos sobre arquivos de dados 
ordenados ou não ordenados 
7 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices: Aplicação 
 Índices são usados massivamente em SGBDs com 
diversas finalidades: 
• Estabelecimento da ligação lógica entre blocos que 
compõem o arquivo que representa uma relação 
• Manutenção de arquivos de dados ordenados 
• Implementação de restrições de integridade (muitos 
SGBDs criam índices automaticamente quando 
atributos são especificados com restrições como 
PRIMARY KEY, FOREIGN KEY e UNIQUE) 
• Mecanismo para acelerar a execução de consultas 
• Implementação de estratégias para processamento de 
transações 
 8 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Terminologia: Chaves e Ponteiros 
 Chave de busca: um ou mais campos do arquivo 
indexado sobre os quais um índice é definido 
• Note que o termo chave é usado em outros contextos: 
chave de relação (primária, estrangeira e candidata) e 
chave de ordenamento 
• Chave de busca K no arquivo de índice é associada com um 
ponteiro para um ou mais registros do arquivo de dados 
que possuem a chave de busca 
• Registros com valores NULL em chaves de busca podem 
ser considerados ou ignorados pelo índice: política 
específica para tratar valores NULL varia entre diferentes 
SGBDs 
 Ponteiros: associados com chaves no índice 
• Ponteiros são representados por RIDs: identificador da 
página e entrada na tabela de offsets 
 
 
9 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Terminologia: Arquivos 
 Arquivo de dados: representação de uma relação do banco 
do banco de dados em C3 
 Heap: arquivo de dados com registros ordenados por 
ordem de inserção 
• Nenhuma outra ordenação pode ser inferida a partir dos valores 
dos registros 
 Arquivo de índice: conjunto pares formados por chaves e 
ponteiros 
• No restante deste material iremos assumir que o arquivo de 
índice é ordenado pela chave 
• Notem entretanto, que existem implementações de índices, 
como índices baseados em hashing, que não definem qualquer 
ordenação sobre as chaves 
 Arquivo sequencial: arquivos de dados logicamente 
ordenado, cuja ordenação é definida pela ordenação das 
chaves de um índice associado 
 
 
10 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Terminologia: Tipos de Índices 
 Índices primários: índices onde ordem da chave 
de busca do índice é a mesma que a ordem do 
arquivo sequencial 
 Índices agrupados (clustering indexes): definição 
alternativa para índices primários 
 Índices secundários: a ordem da chave de busca 
do índice não é a mesma que a ordem do arquivo 
indexado 
 Índices não-agrupados (nonclustering indexes): 
definição alternativa para índices secundários 
 11 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Terminologia:Tipos de Índices 
 Índices densos: índices que possuem uma 
entrada no arquivo de índices para cada registro 
do arquivo de dados 
 Índices esparsos: índices que possuem uma 
entrada no arquivo de índices para cada bloco do 
arquivo de dados 
 Índices simples: índices definidos sobre apenas 
um campo do arquivo indexado 
 Índices compostos: índices definidos sobre mais 
de um campo do arquivo indexado 
 
12 
Terminologia: Tipos de Consultas 
 Consulta pontuais: consultas que retornam no máximo uma 
tupla 
SELECT nome /* matricula é chave da relação */ 
FROM Aluno 
WHERE matr=11111 
 Consultas multipontuais: consultas baseadas em 
comparações de igualdade que podem retornar várias tuplas 
SELECT matricula 
FROM Aluno 
WHERE nome =‘Jose’ 
 Consultas baseadas em intervalos: consultas que retornam 
todas tuplas com valores dentro de um determinado intervalo 
SELECT nome, matricula 
FROM Aluno 
WHERE ano_matricula BETWEEN 2008 AND 2010 
 
 
 
13 
Terminologia: Índices e Consultas 
 Seja 𝐼 um índice e 𝐶 uma consulta 
 𝐼 é elegível para 𝐶: 𝐼 pode ser usado para 
reponder 𝐶 
• Normalmente, 𝐼 é definido sobre atributos (campos) 
referenciados por condições em 𝐶 
 𝐼 cobre 𝐶: 𝐼 pode permite reponder 𝐶 usando 
apenas o arquivo de índice correspondente 
• Normalmente, 𝐼 é definido sobre todos atributos 
(campos) referenciados por condições em 𝐶 e na 
cláusula SELECT 
• Termos covering index ou index-only evaluation são 
comuns na literatura 
14 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Motivação, Introdução e Terminologia 
 Índices Primários 
 Índices Secundários 
 Índices Compostos 
15 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Primários 
 Índices primários definem uma restrição de ordenação 
na organização do arquivo sequencial associado 
 Ordenação lógica dos registros no arquivo sequencial é 
a mesma que a do arquivo de índice 
 Notem que apenas os valores das chaves de busca – no 
arquivo de índice e nos registros do arquivo sequencial 
– são considerados na ordenação 
 Vamos assumir que blocos logicamente adjacentes são 
ligados entre si através de ponteiros (similar a uma lista 
duplamente encadeada), de maneira que é possível 
percorrer sequencialmente um arquivo sequencial 
16 
chave de busca do 
índice primário 
Índices Primários e 
Arquivos Sequenciais 
17 
30 
40 
50 
60 
70 
80 
90 
10010 
20 
registros 
blocos 
ordenação 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Ordenação Lógica vs. 
Ordenação Física 
 Quando um índice primário é criado, a ordenação 
física, tanto no arquivo de índice quanto no arquivo 
sequencial, irá coincidir com a ordenação lógica 
• Isto é, registros ou chaves logicamente próximos estarão 
armazenados no disco em posições próximas (dados 
agrupados fisicamente) 
 Entretanto, inserções ou modificações de registros 
podem resultar na criação de blocos de overflow, que 
podem estar armazenados fisicamente distantes do 
bloco original(veja material sobre representação de 
dados) 
 Como resultado, teremos degradação do agrupamento 
físicos dos dados e, com isso, divergência entre a 
ordenação lógica e a ordenação física 
18 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Primários 
 Pode existir apenas um índice primário definido 
sobre uma relação 
 Índices primários podem ser densos ou esparsos 
• A maioria dos SGBDs suportam índices primários de um 
tipo ou de outro, mas não ambos 
 Certos SGBDs suportam apenas índices primários 
definidos sobre a chave primária da relação ao 
passo que outros não impõem qualquer restrição 
sobre qual atributo o índice primário pode ser 
definido 
19 
Índices Primários Densos 
20 
30 
40 
50 
60 
70 
80 
90 
100 
10 
20 
10 
20 
30 
40 
50 
60 
70 
80 
90 
100 
110 
120 
Arquivo 
de 
Índice 
Arquivo 
de 
Dados 
O valor da chave de busca de cada registro é armazenado no índice 
 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Busca usando Índices Densos 
 Procedimento de busca para consultas 
pontuais*: 
1. Seja 𝐾 o valor especificado na condição da 
consulta; encontre uma chave de busca igual a K 
arquivo de índice 
− se nenhuma chave for encontrada, o resultado é vazio 
2. Siga o ponteiro associado com a chave e retorne 
o registro correspondente no arquivo de dados 
21 
* Iremos considerar consultas multipontuais mais adiante quando 
discutirmos índices com valores duplicados 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Busca usando Índices Densos 
 Procedimento de busca para consultas 
baseadas em intervalos: 
1. Encontre a chave de busca de menor valor no 
arquivo de índice que esteja dentro do intervalo 
especificado na consulta 
− se nenhuma chave for encontrada, o resultado é vazio 
2. Siga o ponteiro associado com a chave e encontre o 
registro correspondente 
3. A partir deste ponto, percorra o arquivo sequencial 
até encontrar o primeiro registro que esteja fora do 
intervalo 
4. Retorne os registros encontrados, incluindo o 
primeiro registro acessado e excluindo o último 
22 
Por que Busca Baseada 
em Índices é Eficiente? 
 Tamanho do arquivo de índices << tamanho do 
arquivo de dados 
 Ponteiros ocupam, normalmente, muito menos espaço 
que um registro 
 Como chaves são ordenadas, busca binária pode ser 
usada para encontrar o bloco do arquivo de índices 
onde a chave de busca correspondente está 
armazenada 
 log2 𝑛 para um arquivo de índices de 𝑛 blocos 
 Quando índices podem permancer na memória 
principal, o tempo de acesso para um registro 
qualquer é 1 operação de IO. 
 Busca de chaves dentro do arquivo de índice envolve 
apenas acessos na memória principal 
 
23 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 1 
 Considere uma relação de 10,000,000 de tuplas, 
onde 10 tuplas podem ser armazenadas em 
blocos de 4KB 
• 1,000,000 blocos 
 Espaço total do arquivo de dados: 4GB 
• Pode não ser possível mantê-lo em memória 
 Considere uma chave de busca ocupando 30 
byte e ponteiros de 8 bytes: 100 entradas do 
índices podem ser armazenados em um bloco 
24 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 1 
 Índice denso requer 100,000 entradas, ou 400MB de 
espaço 
• Pode ser possível mantê-lo em memória (melhores 
chances que o arquivo de dados) 
 Busca no arquivo de índice: log2 100000 ≅ 16 acessos 
a blocos 
 Buscas binárias iniciam-se em um subconjunto dos 
blocos (o bloco do meio, o blocos entre os pontos ¼ e 
¾, etc) 
 Na prática, mantendo os blocos mais importantes em 
memória, registros podem ser acessados para qualquer 
chave com bem menos que 16 acessos ao disco 
 
25 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Localização do Arquivo de Índices 
 Necessidade de um mecanismo (rápido) para 
acesso ao arquivo de índices 
 Opções: 
• Região reservada na memória principal (se existir 
espaço de memória suficiente) 
• Acesso via outra camada de índice (mais adiante) 
• Árvores B (mais adiante) 
26 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Primários Esparsos 
 Mantém uma chave por bloco do arquivo de 
dados 
 Apenas o valor da chave de busca do primeiro 
registro de cada bloco é armazenado no índice 
(juntamente com o ponteiro para este registro) 
 Alternativa para índices densos 
 Requer menor espaço de armazenamento 
 
27 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Esparsos 
28 
30 
40 
50 
60 
70 
80 
90 
100 
10 
20 
10 
30 
50 
70 
90 
110 
130 
150 
170 
190 
210 
230 
Arquivo 
de 
Índice 
Arquivo 
de 
Dados 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 
 Considere novamente o Exemplo 1 
 Arquivo de dados possui 1,000,000 de blocos 
 Um bloco pode conter 100 entradas do índice 
 Portanto, o arquivo de índices irá conter 
10,000 blocos que ocupam 40MB 
• Pode ser mantido facilmente em memória nas 
arquiteturas modernas de computadores 
29 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Busca usando Índices Esparsos 
 Procedimento de busca para consultas 
pontuais 
1. Seja 𝐾 o valor especificado na condição da 
consulta; encontre a chave de busca de maior 
valor que seja menor ou igual a 𝐾 
2. Siga o ponteiro associado com a chave, e 
encontre o primeiro registro do bloco 
correspondente 
3. Realize uma busca sequencial dentro do bloco 
para encontrar o registro desejado 
 
30 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Busca usando Índices Esparsos 
 Procedimento de busca para consultas baseadas em 
intervalos: 
1. Seja 𝐾1 o valor da esquerda do intervalo especificado na 
consulta; encontre a chave de busca de maior valor que 
seja menor ou igual a 𝐾1 
2. Siga o ponteiro associado com a chave, e encontre o 
primeiro registro do bloco 
3. Realize uma busca sequencial dentro do bloco para 
encontrar o primeiro registro dentro do intervalo 
4. A partir deste ponto, percorra o arquivo sequencial até 
encontrar o primeiro registro que esteja fora do intervalo 
5. Retorne os registros encontrados dentro do intervalo 
31 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Densos vs. 
Índices Esparsos 
 Índices densos dispensam buscas sequenciais 
dentro de blocos para consultas pontuais 
• O registro referenciado pelo ponteiro é acessado 
diretamente 
 Mais importante, índices densos podem cobrir 
certas consultas 
• Isto é, consultas podem ser respondidas usando 
apenas o arquivo de índice 
 Por exemplo, considere as três consultas a seguir. 
32 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Densos vs. 
Índices Esparsos 
1. SELECT * /*Índice denso sobre Alunos.matr*/ 
 FROM Alunos 
 WHERE matr = 55555 
2. SELECT * /*Índice denso sobre ic.matr*/ 
 FROM Alunos a 
 WHERE EXISTS (SELECT * 
 FROM Iniciacao_Cientifica ic 
 WHERE a.matr = ic.matr) 
3. SELECT dno, count(*) /*Índice densosobre dno*/ 
 FROM Alunos 
 GROUP BY dno 
 
33 
Índices Densos vs. 
Índices Esparsos 
 Na consulta 1, acesso ao arquivo de dados não é 
necessário caso não exista nenhuma chave com o valor 
especificado na consulta no índice denso sobre 
Alunos.matr 
 Na consulta 2, a subconsulta é coberta pelo índice denso 
sobre Iniciacao_Cientifica.matr 
 Na consulta 3, o índice denso sobre o atributo Alunos.dno 
pode cobrir a consulta em certas situações: caso valores 
NULL também sejam indexados (ex.: DB2) ou exista a 
restrição NOT NULL definidas sobre este atributo 
• Além disso, a organização para representação de índices com 
chaves duplicadas que será apresentada mais adiante não 
suporta cobrimento de consultas envolvendo agrupamento 
34 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Densos vs. 
Índices Esparsos 
 As três consultas anteriores não poderiam ser 
cobertas por um índice esparsos 
• Acesso ao arquivo de dados seria necessário 
 Além disso, buscas adicionais dentro do bloco 
ainda seriam necessárias 
 
35 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Densos vs. 
Índices Esparsos 
 Por outro lado, índices esparsos são 
consideravelmente menores que índices índices 
densos 
• Índices esparsos são menores por um fator igual à 
quantidade aproximada de tuplas por bloco 
 Por serem menor, operações de IO podem ser 
evitadas para acessar blocos do arquivo de índice 
 Portanto, índices esparsos podem resultar em 
melhor performance para certas consultas que 
índices densos 
 
36 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices de Múltiplos Níveis 
 Mesmo usando busca binária para encontrar a 
entrada desejada, o acesso ao bloco desejado do 
arquivo de índice pode requerer muitas 
operações de IO 
 Solução: construir um índice de múltiplos níveis 
• Informalmente, um índice sobre um índice 
 Índices de primeiro nível podem ser densos ou 
esparsos 
 Do segundo nível em diante, os índices são 
esparsos 
37 
38 
Índices de Múltiplos Níveis 
30 
40 
50 
60 
70 
80 
90 
100 
10 
20 
10 
30 
50 
70 
90 
110 
130 
150 
170 
190 
210 
230 
10 
90 
170 
250 
330 
410 
490 
570 
1º. Nível 2º. Nível 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 3 
 Considere um índice de segundo nível sobre o 
índice esparso de primeiro nível do Exemplo 2 
 Como índice primário ocupa 10,000 blocos e 
um bloco pode 100 entradas de índice, temos 
que o índice de segundo nível irá ocupar 
apenas 100 blocos 
39 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices com Chaves 
de Busca Duplicadas 
 Quando índices são aplicados sobre atributos 
que não são chaves de uma relação, podem 
existir chaves de busca duplicadas 
 Podemos usar índices densos ou esparsos 
para representar chaves de busca duplicadas 
sobre arquivos sequenciais 
• Cada estratégia possui um algoritmo de busca 
diferente 
40 
41 
Índices Primários Densos 
com Chaves Duplicadas 
10 
20 
20 
30 
30 
30 
40 
50 
10 
10 
10 
20 
30 
40 
50 
... 
... 
... 
Obs.: Notem que esta organização 
economiza espaço mas permite o 
cobrimento de consultas envolvendo 
agrupamentos 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Busca usando Índices Densos com 
Chaves Duplicadas 
1. Uma chave é associada com um ponteiro para o 
primeiro registro com a chave de busca K 
2. Para encontrar os registros restantes, é realizada 
uma busca sequencial no bloco até que seja 
encontrado o primeiro registro R com chave 
maior que K 
3. Caso R não seja encontrado no bloco atual, a 
busca prossegue no bloco seguinte 
 Exemplo: Na figura anterior, considere um acesso 
ao índice com chave de busca de valor 20 
42 
43 
Índices Esparsos 
com Chaves Duplicadas 
10 
20 
20 
30 
30 
30 
40 
50 
10 
10 
10 
10 
20 
30 
40 
... 
... 
... 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Esparsos com Chaves 
Duplicadas: Algoritmo de Busca 
1. Encontre a última entrada do índice com chave menor ou 
igual a chave de busca; vamos denotar esta entrada por E1 
2. A partir de E1, movendo-se em order descrescente pelo 
índice, encontre a primeira entrada cujo valor seja 
estritamente menor que a chave de busca; vamos denotar 
estar entrada por E2. Caso o ínicio do índice seja 
encontrado, então a primeira entrada corresponde a E2. 
(note que E2 pode ser igual a E1). 
3. Todos os blocos que podem conter registros com a chave 
de busca estão entre os blocos referenciados por E1 e E2, 
inclusive 
 Exemplos: Na figura anterior, considere acessos ao índice 
com chave de busca de valor 20 e 10 
 
44 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Motivação, Introdução e Terminologia 
 Índices Primários 
 Índices Secundários 
 Índices Compostos 
45 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Secundários 
 Índices secundários não determinam a 
organização do arquivo de dados indexado 
 Heaps e arquivos sequenciais podem ser 
indexados 
• No caso de arquivos sequenciais, a ordenação 
deste é definida por outro índice primário 
 Vários índices secundários podem ser 
definidos sobre uma mesma relação 
 Índices secundários são sempre densos 
 
46 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Secundários 
 Aplicados tipicamente sobre campos não-
chaves para ajudar o processamento de 
Exemplo: 
• SELECT * FROM Aluno 
 WHERE aniversário=‘07.09.1982’ 
• Um índice primário sobre a chave matricula não 
é elegível nesta consulta. 
• Um índice secundário sobre aniversário é 
elegível 
47 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Secundários 
48 
10 
20 
50 
30 
10 
50 
60 
20 
20 
40 
10 
10 
20 
20 
20 
30 
40 
50 
50 
60 
30 
40 
50 
60 
70 
80 
90 
100 
10 
20 
chave 
primária 
índice 
primário 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Secundários 
 Conjunto de entradas para um determinado valor 
pode ter ponteiros para vários blocos não 
consecutivos do arquivo de dados 
 No pior caso, cada entrada associada com um 
valor “aponta” para um bloco de dados diferente 
• Considere o valor 20 na Figura anterior 
 Observem que não é possível evitar a repetição 
da chave de busca no arquivo de índice como no 
caso do índice primário denso porque o arquivo 
sequencial não é ordenado pelo índice 
secundário 
49 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Nível de Indireção 
em Índices Secundários 
 Índice secundários normalmente contém 
chaves de busca duplicadas 
 A repetição de entradas com o mesmo valor 
pode ser evitada usando um nível adicional de 
indireção chamado buckets 
 Resulta em economia de espaço quando o 
tamanho da chave é menor que um ponteiro e 
cada valor aparece em média duas vezes 
 
50 
51 
Nível de Indireção 
em Índices Secundários 
10 
20 
50 
30 
10 
50 
60 
20 
20 
40 
10 
20 
30 
40 
50 
60 
buckets 
arquivo de índice 
arquivo de dados 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Processando Consultas 
Usando Buckets 
 Considere a seguinte consulta: 
SELECT nome 
FROM Aluno 
WHERE cidade=‘Lavras‘ AND aniversario=‘07.09.82‘ 
 Se existem índices secundários definidos sobre 
cidade e aniversario, é possível indentificar os 
ponteiros para os registros da resposta através 
da intersecção dos buckets em memória 
 
52 
Prof. Dr.-Ing. Leonardo AndradeRibeiro 
Processando Consultas 
Usando Buckets 
53 
buckets 
de aniversario 
buckets 
de cidade 
Lavras 
... 
índice cidade 
07.09.82 
... 
índice aniversario 
Índices Primários vs. 
Índices Secundários 
 Para consultas mutipontuais e baseadas em 
intervalos, índices primários são mais vantajosos, 
porque é possível realizar busca no arquivo 
sequencial 
 Acessos usando índices secundários resultam 
inevitavelmente em acessos randômicos ao disco 
• Problemas de performance se a fração de blocos 
acessados para responder a consulta for muito grande 
• Uma regra informal, bastante usada, diz que é preferível 
realizar o scan sequencial sobre toda relação se a 
porcentagem de blocos da mesma a serem acessados 
randômicamente for maior que 15% 
 
 
 
54 
Índices Primários vs. 
Índices Secundários 
 Notem que índices primários deixarão de ser 
vantajosos se modificações no arquivo 
sequencial degradar a ordenação física dos 
dados 
• Neste caso, o índice precisará ser reconstruído 
para recuperar a ordenação física 
55 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Primários vs. 
Índices Secundários 
 Para consultas pontuais, índices primários e 
secundários possuem a mesma performance 
 É possível definir vários índices secundários 
sobre uma relação para reduzir acesso ao 
arquivo de dados 
 
56 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Primários vs. 
Índices Secundários 
 No exemplo anterior, índices secundários 
sobre cidade e aniversário fazem com que o 
arquivo de dados precise ser acessado apenas 
nos ponteiros resultantes da interseção de 
buckets: 
SELECT nome 
FROM Aluno 
WHERE cidade=‘Lavras‘ AND aniversario=‘07.09.82‘ 
 
57 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Motivação, Introdução e Terminologia 
 Índices Primários 
 Índices Secundários 
 Índices Compostos 
58 
Índices Compostos 
 Índices compostos possuem múltiplas chaves de 
busca 
• Ex.: <matricula, nome>, <nome, cidade>, ou 
<matricula, nome, cidade> 
 Ordem das chaves de busca na definição do 
índice determina a ordem do arquivo de índice 
• As entradas são ordenadas de acordo com a primeira 
chave, entradas com o mesmo valor para a primeira 
chave são ordenadas de acordo com a segunda chave, 
e assim por diante 
 Índices compostos podem ser primários ou 
secundários 
 No caso de índices primários, os mesmos podem 
ainda ser densos ou esparsos 59 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Compostos 
60 
44444 João Lavras 
55555 Maria Itajubá 
66666 Maria Lavras 
77777 José Varginha 
matricula nome cidade 
Itajubá 
João Lavras 
Maria Lavras 
José Varginha 
<cidade, nome> 
Maria 
João Lavras 
José Varginha 
Maria Lavras 
Maria Itajubá 
<nome, cidade> 
Arquivo sequencial ordenado 
por matricula 
Ín
d
ic
es
 s
ec
u
n
d
ár
io
s 
co
m
p
o
st
o
s 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Compostos 
 Normalmente, um índice composto é elegível 
para um determinada consulta quando o 
conjunto de atributos especificados em condições 
da consulta constituem um prefixo da sequência 
de chaves de busca do índice 
• Por exemplo, um índice definido sobre <nome, 
cidade> pode responder consultas especificando 
condições sobre nome ou nome e endereço, mas não 
sobre cidade apenas 
• Observação: alguns SGBDs, como Oracle, possuem 
uma implementação que não possui esta limitação 
61 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Compostos 
 Índices compostos são popularmente usados para 
cobrir consultas que são executadas frequentemente 
• Mesmo quando não cobrem a consulta, índices compostos 
ainda podem reduzir drasticamente o acesso ao arquivo de 
dados 
 Também são úteis para garantir a unicidade de 
conjuntos de atributos 
• Ex.: Considere a chave composta formada por <matricula, 
disciplina, semestre>: um aluno pode cursar várias 
disciplinas em um semestre, uma disciplina pode ter vários 
alunos matriculados em um semestre, mas nenhum pode 
estar matriculado na mesma disciplina no mesmo 
semestre 
 
62 
Índices Compostos vs. 
Índices Secundários 
 Índices compostos são normalmente mais 
eficientes que soluções baseadas em múltiplos 
índices secundários simples 
 Novamente, considere a consulta 
SELECT nome 
FROM Aluno 
WHERE cidade=‘Lavras‘ AND aniversario=‘07.09.82‘ 
 Se existirem muitos alunos em ‘Lavras’, mas poucos alunos 
com aniversário em ‘07.09.82‘, então um índice composto 
sobre <aniversario, cidade> será mais eficiente que dois 
índices simples sobre aniversario e cidade 
• Bucket para cidade em índice secundário simples 
conterá muitos RIDs 
 
63 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Perfomance e Ordem das Chaves 
 Notem que a ordem dos atributos é importante para 
a performance do índice em responder certas 
consultas 
 Considere as seguintes consultas: 
1. SELECT * 
 FROM Alunos 
 WHERE aniversario=‘07.09.82‘ AND cidade = ‘Lavras ‘ 
2. SELECT * 
 FROM Alunos 
 WHERE aniversario BETWEEN ‘01.01.82‘ AND ‘01.01.92‘ 
 and cidade = ‘Lavras ‘ 
 
 
 
64 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Perfomance e Ordem das Chaves 
 No slide anterior, um índice composto definido 
sobre <ano, cidade> provalmente resultará em 
boa performance em responder consulta 1, mas 
não consulta 2 
• A razão é que provavelmente uma boa porção do 
arquvio de índice terá que ser acessada para 
encontrar entradas dentro intervalo especificado para 
ano na consulta 2 
 Conclusão: Em um índice composto, atributo 𝐴 
deve vir antes que atributo 𝐵, se consultas 
tendem a especificar mais restrições em 𝐴 
65 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Compostos: Desvantagem 
 Índices compostos são maiores que índices 
simples 
• Possivelmente, mais operações de IO serão 
necessárias para buscar entradas no arquivo de 
índices 
 Atualizações em qualquer atributo sobre o 
qual um índice composto está definido 
requerem a atualização deste índice 
66