06 indexacao indice multinivel

Prévia do material em texto

Rodrigo Salvador MonteiroRodrigo Salvador Monteiro
ESTRUTURAS DE INDEXAESTRUTURAS DE INDEXAÇÇÃOÃO
ÍÍNDICES MULTINNDICES MULTINÍÍVELVEL
Slides adaptados do Prof Sean Siqueira (sean@uniriotec.br)
ÍÍndices ndices MultinMultiníívelvel
■ Uma pesquisa binária sobre um um índice com bi blocos 
► requer aproximadamente (log2bi) acessos a blocos
► cada etapa do algoritmo reduz a parte do arquivo índice que 
continuamos a pesquisar por um fator de 2.
■ índice multinível
► Visa reduzir a parte do índice que continuamos a pesquisar 
através de bfri (fator de bloco para o índice) maior do que 2.
■ bfri = fan-out (fo) do índice multinível.
■ Pesquisar em um índice multinível requer aproximadamente 
(logfobi) acessos a blocos
► número muito menor do que a pesquisa binária se o fan-out for 
maior do que 2.
ÍÍndices ndices MultinMultiníívelvel (cont.)(cont.)
■ primeiro nível ou nível base
► arquivo ordenado com um valor distinto para cada K(i).
■ Índice de segundo nível 
► índice principal para o primeiro nível
► uma entrada para cada bloco do primeiro nível.
► bfri para o segundo nível – e para todos os níveis subseqüentes
■ mesmo que para o índice do primeiro nível...
■ Suponha... 
► Índice de primeiro nível com r1 entradas e bfri = fo
► Então... o primeiro nível precisa de ┌ r1/fo ┐blocos, que é portanto 
o número de entradas r2 necessárias no segundo nível de índice.
ÍÍndices ndices MultinMultiníívelvel (cont.)(cont.)
■ O terceiro nível 
► índice principal para o segundo nível
►uma entrada para cada bloco do segundo nível
■ número de entradas do terceiro nível seja r3 = ┌ r2/fo ┐.
■ Quando um segundo nível é necessário?
►se o primeiro precisar de mais do que um bloco de 
armazenamento de disco 
► terceiro nível somente se o segundo precisar de mais 
do que um bloco, e assim sucessivamente...
■ Até que todas as entradas de algum nível t do índice 
caibam em um único bloco. 
► t é chamado de nível de índice superior.
ExemploExemplo
ExemploExemplo
■ Suponha que o índice secundário denso do exemplo anterior seja 
convertido em um índice multinível. Calculamos o fator de bloco do índice 
bfri = 68 entradas de índice por bloco, que é também o fan-out fo para o 
índice multinível; o número de blocos de primeiro nível b1 = 442 blocos 
também foi calculado. 
■ Qual é o número de blocos de segundo nível?
■ Qual é o número de blocos de terceiro nível?
■ Qual é o número de blocos de quarto nível?
■ Qual e o índice superior?
■ Quantos acesos a blocos são necessários para acessar um registro 
utilizando este índice multinível?
b2 = 
┌ b1/fo ┐ = ┌ 442/68 ┐ = 7 blocos
b3= 
┌ b2/fo ┐ = ┌ 7/68 ┐ = 1 bloco
Não tem quarto nível
t = 3; o terceiro é o nível superior do índice
3 + 1 = 4
Problemas com Problemas com ÍÍndices ndices MultinMultiníívelvel
■ Inclusões e exclusões
►Todos os níveis de índices são arquivos fisicamente 
ordenados
►Solução:
■ Adotar um índice multinível que deixa algum espaço em 
cada um de seus blocos para inserir novas entradas.
■ Índice multinível dinâmico
ÁÁrvores de busca...rvores de busca...
RevisãoRevisão de de estruturaestrutura de de áárvorervore
■ Uma árvore é formada por nós;
■ Cada nó tem um pai (exceto o nó raiz) e vários nós 
filhos (zero ou mais)
■ Nó que não possui filhos chama-se nó folha;
■ Nó que não é nó folha é chamado nó interno;
■ O nível de um nó é sempre uma unidade maior que 
seu pai, com o nível do nó raiz sendo zero;
■ Uma subárvore de um nó consiste daquele nó e todos 
os seus descendentes
ÁÁrvoresrvores--BB
■ Árvore sempre balanceada
■ Espaço desperdiçado através da exclusão, caso haja 
algum, nunca se torne excessivo
■ Algoritmos para inclusão e exclusão mais complexos
ÁÁrvoresrvores--BB
■ Uma árvore-B de ordem p quando utilizada como uma 
estrutura de acesso em um campo chave para 
pesquisar registros em um arquivo de dados pode ser 
definida da seguinte maneira:
►Cada nó interno da árvore-b é da forma <P1, <K1,Pr1>, 
P2, <K2,Pr2>, ..., <Kq-1,Prq-1>,Pq>, onde q≤p.
►Dentro de cada nó, K1 < K2 <...<Kq-1
►Para todos os valores X do campo chave de pesquisa 
na subárvore referenciada por Pi, temos: Ki-1<X<Ki para 
1<i<q; X<Ki para i=1; e Ki-1 < X para i = q
►Cada nó possui no máximo p ponteiros de árvore
ÁÁrvoresrvores--B (cont.)B (cont.)
►Cada nó, exceto os nós raiz e as folhas, possui pelo 
menos ┌(p/2)┐ = ponteiros de árvore. O nó raiz possui 
pelo menos dois ponteiros de árvore a não ser que ele 
seja o único nó na árvore.
►Um nó com q ponteiros de árvore, q≤p, possui q-1 
valores de campo chave de pesquisa (e portanto possui 
q-1 ponteiros de dados).
►Todos os nós folhas encontram-se no mesmo nível. 
►Os nós folhas possuem a mesma estrutura que os nós 
internos, exceto pelo fato de que todos os seus 
ponteiros de árvore Pi são nulos.
Uma Uma áárvorervore--B de ordem p=3B de ordem p=3
5 8
1 3 6 7 9 12
Uma Uma áárvorervore--b de ordem p=3b de ordem p=3
8
Inserção dos valores 8, 5, 1
85
Uma Uma áárvorervore--b de ordem p=3b de ordem p=3
Inserção dos valores 8, 5, 1, 7
5
1 8
Uma Uma áárvorervore--b de ordem p=3b de ordem p=3
Inserção dos valores 8, 5, 1, 7, 3
5
1 7 8
Uma Uma áárvorervore--b de ordem p=3b de ordem p=3
Inserção dos valores 8, 5, 1, 7, 3,12
1 73 8
5
12
Uma Uma áárvorervore--b de ordem p=3b de ordem p=3
Inserção dos valores 8, 5, 1, 7, 3, 12, 9
5
1 7 123
8
Uma Uma áárvorervore--b de ordem p=3b de ordem p=3
Inserção dos valores 8, 5, 1, 7, 3, 12, 9, 6
5
1 73
8
129
Uma Uma áárvorervore--b de ordem p=3b de ordem p=3
Inserção dos valores 8, 5, 1, 7, 3, 12, 9, 6
5 8
1 3 6 7 9 12
ExemploExemplo
■ Suponha que:
►O campo de pesquisa seja V = 9 bytes de tamanho
►O tamanho do bloco seja B = 512 bytes
►Um ponteiro de registro (dados) seja Pr = 7 bytes
►Um ponteiro de bloco seja P = 6 bytes
■ Quantos ponteiros de árvore (ou ordem p) poderemos 
ter em cada nó de modo que cada nó da árvore-B 
corresponda a um bloco de disco?
(p*P) + ((p-1)*(Pr+V)≤B
(p*6) + ((p-1)*(7+9)≤512
(22*p) ≤528
p ≤ 24 p=23
ExemploExemplo
■ Suponha que:
► o campo de pesquisa seja um campo chave sem ordenação
► construímos uma árvore-b nesse campo
► cada nó da árvore-B esteja 69% cheio
■ Quantos ponteiros e valores teremos em média em cada nó?
■ Qual é o fan-out médio?
■ Supondo uma árvore-B até o nível 3, quantos nós, entradas e 
ponteiros temos em cada nível?
cada nó, em média, terá p * 0,69 = 23*0,69 = 15,87 ou 
aproximadamente 16 ponteiros e portanto 15 valores de campos chave
fan-out médio (fo) = 15
Raiz 1 nó 15 entradas 16 ponteiros
Nível 1 16 nós 240 entradas 256 ponteiros
Nível 2 256 nós 3840 entradas 4096 ponteiros
Nível 3 4096 nós 61.440 entradas