Indexação de Dados

Prévia do material em texto

Unidade 3 - Indexação 
2
Unidade 3: Indexação 
n Conceitos básicos
n Índices ordenados
n Arquivos de índice de árvore B+
n Arquivos de índice de árvore binária
n Exercícios
3
Conceitos básicos 
n Mecanismos de indexação usados para agilizar o acesso aos dados desejados.
l Por exemplo, catálogo de autores na biblioteca
n Chave de busca - atributo ou conjunto de atributos para pesquisar registros em um 
arquivo.
n Um arquivo de índice consiste em registros (chamados entradas de índice) na forma
n Arquivos de índice normalmente são muito menores do que o arquivo original
n Dois tipos básicos de índices:
l Índices ordenados: chaves de busca são armazenadas em ordem classificada
l Índices de hash: chaves de busca são distribuídas uniformemente entre “baldes” 
usando uma “função de hash”.
chave de busca ponteiro
4
Métrica de avaliação de índice 
n Tipos de acesso admitidos com eficiência. Por exemplo, 
l registros com um valor especificado no atributo
l ou registros com um valor de atributo caindo em um 
intervalo especificado de valores.
n Tempo de acesso
n Tempo de inserção
n Tempo de exclusão
n Sobrecarga de espaço
5
Índices ordenados 
n Em um índice ordenado, as entradas de índice são 
armazenadas classificadas pelo valor da chave de busca. 
Por exemplo, catálogo de autor na biblioteca.
n Índice primário: em um arquivo ordenado seqüencialmente, 
o índice cuja chave de busca especifica a ordem seqüencial 
do arquivo.
l Também chamado índice de agrupamento
l A chave de busca de um índice primário normalmente, mas não 
necessariamente, é a chave primária.
n Índice secundário: um índice cuja chave de busca 
especifica uma ordem diferente da ordem seqüencial do 
arquivo. Também chamado índice não de agrupamento.
n Arquivo seqüencial indexado: arquivo seqüencial ordenado 
com um índice primário.
6
Arquivos de índice denso 
Índice denso — O registro de índice aparece para cada valor de 
chave de busca no arquivo. 
7
Arquivos de índice esparso 
n Índice esparso: contém registros de índice para somente alguns valores de 
chave de busca.
l Aplica-se quando os registros são ordenados seqüencialmente por 
chave de busca
n Para localizar um registro com o valor de chave de busca K:
l Encontramos o registro de índice com o maior valor de chave de busca 
< K
l Pesquisamos o arquivo seqüencialmente, começando no registro para o 
qual o registro de índice aponta
n Menos espaço e menos sobrecarga de manutenção para inserções e 
exclusões.
n Geralmente mais lento do que o índice denso para localizar registros.
n Boa escolha: índice esparso com uma entrada de índice para cada bloco no 
arquivo, correspondente ao menor valor de chave de busca no bloco.
8
Exemplo de arquivos de índice esparso 
9
Índice multinível 
n Se o índice primário não couber na memória, o acesso se torna dispendioso.
n Para reduzir o número de acessos de disco aos registros de índice, trate o 
índice primário mantido em disco como um arquivo seqüencial e construa 
um índice esparso sobre ele.
l índice externo – um índice esparso do índice primário
l índice interno – o arquivo de índice primário
n Se até mesmo o índice externo for muito grande para caber na memória 
principal, outro nível de índice pode ser criado, e assim por diante.
n Os índices em todos os níveis precisam ser atualizados na inserção ou 
exclusão no arquivo.
10
Índice multinível (cont.) 
11
Atualização de índice: exclusão 
n Se o registro excluído foi o único registro no arquivo com seu 
valor de chave de busca específico, a chave de busca também é 
excluída do índice.
n Exclusão de índice de único nível:
l Índices densos a exclusão da chave de busca é semelhante à ‑
exclusão de registro do arquivo.
l Índices esparsos se houver uma entrada para a chave de ‑
busca no índice, ela é excluída substituindo a entrada no índice 
pelo próximo valor de chave de busca no arquivo (em ordem de 
chave de busca). Se o próximo valor de chave de busca já tiver 
uma entrada de índice, a entrada é excluída em vez de ser 
substituída.
12
Atualização de índice: inserção 
n Inserção de índice de único nível:
l Realize uma pesquisa usando o valor de chave de busca que 
aparece no registro a ser inserido.
l Índices densos se o valor da chave de busca não aparecer no ‑
índice, insira-o.
l Índices esparsos se o índice armazena uma entrada para ‑
cada bloco do arquivo, nenhuma mudança precisa ser feita no 
índice, a menos que um novo bloco seja criado. Nesse caso, o 
primeiro valor de chave de busca que aparece no novo bloco é 
inserido no índice.
n Algoritmos de inserção multinível (além de exclusão) são simples 
extensões dos algoritmos de único nível
13
Índices secundários 
n Freqüentemente, alguém deseja encontrar todos os registros cujos 
valores em um certo campo (que não seja a chave de busca do índice 
primário) satisfazem alguma condição.
l Exemplo 1: No banco de dados conta armazenado seqüencialmente 
por número de conta, podemos querer encontrar todas as contas em 
determinada agência
l Exemplo 2: como antes, mas onde queremos encontrar todas as 
contas com um saldo especificado ou intervalo de saldos
n Podemos ter um índice secundário com um registro de índice para 
cada valor de chave de busca; o registro de índice aponta para um 
balde que contém ponteiros para todos os registros reais com esse 
valor de chave de busca específico.
14
Índice secundário sobre o campo saldo
de conta 
15
Índices primários e secundários 
n Índices secundários precisam ser densos.
n Índices oferecem benefícios substanciais quando procuram 
registros.
n Quando um arquivo é modificado, cada índice no arquivo precisa 
ser atualizado. A atualização de índices impõe sobrecarga na 
modificação do banco de dados.
n A varredura seqüencial usando índice primário é eficiente, mas 
uma varredura seqüencial usando um índice secundário é 
dispendiosa.
l cada acesso a registro pode apanhar um novo bloco do disco
16
Arquivos de índice de árvore B+ 
n Desvantagem dos arquivos seqüenciais indexados: o desempenho 
diminui quando o arquivo aumenta, pois muitos blocos de estouro 
são criados. É preciso reorganizar periodicamente o arquivo inteiro.
n Vantagem dos arquivos de índice B+: reorganiza-se 
automaticamente com pequenas mudanças locais, em face a 
inserções e exclusões. A reorganização do arquivo inteiro não é 
necessária para manter o desempenho.
n Desvantagem das árvores B+: trabalho extra de inserção e exclusão, 
sobrecarga de espaço.
n Vantagens das árvores B+ superiores às desvantagens, e por isso 
software muito usadas.
17
Arquivos de índice de árvore B+ (cont.) 
Uma árvore B+ é uma árvore com raiz satisfazendo as
seguintes propriedades:
n Todos os caminhos da raiz até a folha são do mesmo 
tamanho
n Cada nó que não é uma raiz ou uma folha tem entre [n/2] e n 
filhos.
n Um nó de folha tem entre [(n–1)/2] e n–1 valores
n Casos especiais: 
l Se a raiz não for uma folha, ela tem pelo menos 2 filhos.
l Se a raiz for uma folha (ou seja, não houver outros nós 
na árvore), ela pode ter entre 0 e (n-1) valores.
18
Estrutura de nós da árvore B+ 
n Nó típico
l Ki são os valores de chave de busca
l Pi são ponteiros para os filhos (para nós não de folha) ou 
ponteiros para registros ou baldes de registros (para nós de 
folha)
n As chaves de busca em um nó são ordenadas
 K1 < K2 < K3 < . . . < Kn–1
19
Nós de folha nas árvores B+ 
n Para i = 1, 2, . . ., n–1, o ponteiro Pi ou aponta para um registro de arquivo com valor de 
chave de busca Ki, ou para um balde de ponteiros para registros de arquivo, cada registro 
tendo valor de chave de busca Ki. Só precisa de estrutura de balde se a chave de buscanão 
formar uma chave primária.
n Se Li, Lj forem nós de folha e i < j, os valores de chave de busca de Li são menores que os 
valores de chave de busca de Lj
n Pn aponta para o próximo nó de folha na ordem da chave de busca
20
Nós não de folha nas árvores B+ 
n Os nós não de folha formam um índice esparso multinível sobre os nós de 
folha. Para um nó não de folha com m ponteiros:
l Todas as chaves de busca na sub-árvore à qual P1 aponta são 
menores que K1
l Para 2 ≤ i ≤ n – 1, todas as chaves de busca na sub-árvore à qual Pi 
aponta têm valores maiores ou iguais a Ki–1 e menores que Km–1
21
Exemplo de uma árvore B+ 
Árvore B+ para arquivo conta (n = 3)
22
Exemplo de árvore B+ 
n Árvore B+ para arquivo conta (n = 5)
n Nós de folha precisam ter entre 2 e 4 valores
((n–1)/2 e n –1, com n = 5).
n Nós não de folha diferentes da raiz precisam ter entre 3 e 5 filhos 
((n/2 e n com n =5).
n Raiz precisa ter pelo menos 2 filhos.
23
Observações sobre árvores B+ 
n Como as conexões entre nós são feitas por ponteiros, blocos 
“logicamente” próximos não precisam estar “fisicamente” 
próximos.
n Os níveis não de folha da árvore B+ formam uma hierarquia de 
índices esparsos.
n A árvore B+ contém uma quantidade relativamente pequena de 
níveis (logarítmica no tamanho do arquivo principal), de modo que 
as buscas podem ser conduzidas de modo eficiente.
n Inserções e exclusões no arquivo principal podem ser tratadas de 
modo eficiente, pois o índice pode ser reestruturado em tempo 
logarítmico (conforme veremos).
24
Consultas em árvores B+ 
n Encontre todos os registros com um valor de chave de busca k.
H Comece com o nó raiz
4 Examine o nó em busca do menor valor de chave de busca > k.
4 Se esse valor existir, considere que é Kj. Depois siga Pi até o nó 
filho
4 Caso contrário, k ≥ Km–1, onde existem m ponteiros no nó. Depois, 
siga Pm até o nó filho.
H Se o nó alcançado seguindo-se o ponteiro acima não for um nó de 
folha, repita o procedimento sobre o nó e siga o ponteiro 
correspondente.
H Por fim, alcance um nó de folha. Se, para algum i, a chave Ki = k, siga 
o ponteiro Pi até o registro ou balde desejado. Se não, não há um 
registro com valor de chave de busca k.
25
Consultas em árvores B+ (cont.)
n No processamento de uma consulta, um caminho é atravessado na árvore 
da raiz até algum nó de folha.
n Se houver K valores de chave de busca no arquivo, o caminho não será 
maior do que log n/2(K).
n Um nó geralmente tem o mesmo tamanho de um bloco de disco, 
normalmente 4 kilobytes, e n normalmente fica em torno de 100 (40 bytes 
por entrada de índice).
n Com 1 milhão de valores de chave de busca e n = 100, no máximo 
log50(1.000.000) = 4 nós são acessados em uma pesquisa.
n Compare isso com uma árvore binária balanceada com 1 milhão de valores 
de chave de busca cerca de 20 nós são acessados em uma pesquisa.‑
l a diferença acima é significativa, pois o acesso a cada nó pode 
precisar de uma E/S de disco, custando em torno de 20 milissegundos!
26
Exercícios
1. Suponha que uma chave inteira utilize 2 bytes, um ponteiro utilize 4 
bytes e um registro de uma certa tabela utilize 20 bytes. Considere 
blocos de 60 bytes (ignore os cabeçalhos). Considere índices 
contendo pares chave-ponteiro. Quantos blocos serão necessários 
para armazenar dados e índice se a tabela possuir 90 registros, 
utilizando-se: a) um índice denso; b) um índice esparso.
2. Esquematize e explique como se pode montar uma estrutura de 
índice secundário com 2 níveis de índice.
3. Por que uma árvore B recupera registros dos nós intermediários 
mais rapidamente que uma árvore B+?
4. Esquematize um nó folha de uma árvore B+.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26