ADMBD-Parte02-2013

Prévia do material em texto

18/03/2013
1
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
Parte II
Estruturas Indexadas para 
Arquivos
43
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
Revisão dos conceitos básicos 
sobre indexação
• Índices são estruturas de acesso auxiliares 
utilizadas para acelerar a recuperação de 
registros em resposta a determinadas 
condições de pesquisa.
• Possibilitam o acesso eficiente a registros 
com base nos campos de indexação que são 
utilizados para construir o índice.
44
18/03/2013
2
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Nos índices ordenados, os valores no índice 
são ordenados para permitir uma busca 
binária.
• Há vários tipos de índices ordenados como 
os índices primários, clustering e 
secundários.
45
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Índices primários ou principais
– Especificados no campo chave de ordenação de 
um arquivo de registros ordenado.
– O número total de entradas no índice é o 
mesmo número de blocos de disco do arquivo 
de dados ordenado.
– É um índice não-denso (esparso) pois possui 
uma entrada no índice para cada bloco de disco 
do arquivo de dados ao invés de para cada 
registro.
46
18/03/2013
3
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 47
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Índices por Clustering
– Se os registros de um arquivo estiverem 
fisicamente ordenados por um campo que não 
seja chave, este campo é chamado de campo 
clustering.
– Podemos criar o índice clustering para acelerar a 
recuperação de registros que possuem o mesmo 
valor para o campo clustering.
– É um índice não denso pois possui uma entrada 
para cada valor distinto do campo de indexação.
48
18/03/2013
4
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 49
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Índices secundários
– Especificado em qualquer campo não-ordenado 
de um arquivo.
– Podem existir muitos índices secundários para o 
mesmo arquivo.
– Duas alternativas:
• Índice secundário num campo chave que possui um 
valor distinto para cada registro.
• Índice secundário em um campo que não é chave. 
50
18/03/2013
5
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 51
ÍN
D
IC
E 
SE
CU
N
D
ÁR
IO
 
D
EN
SO
 
EM
 
CA
M
PO
 
CH
AV
E
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 52
ÍN
D
IC
E 
SE
CU
N
D
ÁR
IO
 
EM
 
CA
M
PO
 
N
ÃO
 
CH
AV
E
18/03/2013
6
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Índices de múltiplos níveis
53
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
– Terminologia de estruturas de dados do tipo 
árvore:
• Uma árvore é formada de nós.
• Cada nó da árvore, exceto um nó especial chamado raiz, 
possui um nó pai e diversos (zero ou mais) filhos.
• O nó raiz não possui pai.
• Um nó que não possua nenhum nó filho é chamado de 
nó folha.
• Um nó que não seja folha é chamado de nó interno.
• O nível de um nó é um a mais que o nível do seu pai, 
sendo o nível do nó raiz igual a zero.
• Uma subárvore de um nó consiste daquele nó e todos 
os seus nós descendentes.
54
18/03/2013
7
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Árvore B
55
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Exercício:
– Baseado no resultado da árvore anterior, incluir 
as seguintes chaves:
• 2, 4, 11, 15
56
18/03/2013
8
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Exercício:
– Resposta:
57
5
2 8 11
1 3 4 6 7 9 12 15
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
– Árvore B ou B-Tree é uma estrutura de dados 
pertencente ao grupo das árvores, e é muito 
utilizada em banco de dados e em sistemas de 
arquivos;
– Está sempre balanceada, ou seja, os nós folhas 
estão sempre no mesmo nível.
– Cada valor do campo de pesquisa aparece uma 
vez em algum nível da árvore, juntamente com 
um ponteiro de dados.
58
18/03/2013
9
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
– Todo nó da árvore tem um número mínimo de 
elementos, que é dado pela metade do valor da 
ordem do nó, truncando o número caso a 
árvore seja de ordem ímpar, exceto para a raiz 
da árvore, que pode ter o mínimo de um 
registro. 
– Por exemplo, os nós de uma árvore de ordem 5, 
devem ter, no mínimo 5/2 = 2,5 registros, ou 
seja, dois registros.
59
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
– A quantidade de filhos que um nó pode ter é 
sempre a quantidade de registros do nó mais 1 
(V+1). 
– Por exemplo, se um nó tem 4 registros, este nó 
terá obrigatoriamente 5 apontamentos para os 
nós filhos.
60
18/03/2013
10
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
– Para uma árvore com ordem p, cada nó interno 
possui no máximo p e no mínimo teto(p/2) 
ponteiros de árvore. A raiz é exceção e possui 
pelo menos dois ponteiros de árvore.
– A estrutura do nós internos e das folhas é <P1, 
<K1, Pr1>, P2, <K2, Pr2>, ... <K(q-1), Pr(q-1)>, 
Pq), sendo K o valor do campo de pesquisa , Pr o 
ponteiro de dados e q<=p.
– Seja X um valor de busca. Se X < K, devemos 
percorrer a subárvore à esquerda de K. Se X > K, 
percorreremos a subárvore à direita de K.
61
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
– Para inserir ou remover variáveis de um nó, a 
quantidade de descendentes no nó não poderá 
ultrapassar sua ordem e nem ser menor que sua 
ordem dividida por dois (fator de 
preenchimento). 
– Árvores B não precisam ser rebalanceadas como 
são freqüentemente as árvores de busca 
binária. 
– Árvores B têm vantagens substanciais em 
relação a outros tipos de implementações 
quanto ao tempo de acesso e pesquisa aos nós.
62
18/03/2013
11
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Forma geral:
– Uma árvore B de ordem "m" é uma árvore que 
atende as seguintes propriedades:
1.Cada nó tem no máximo "m" filhos
2.Cada nó (exceto araíz e as folhas) tem pelo 
menos "m/2" filhos
3.A raiz tem pelo menos dois filhos se ela 
mesma não for uma folha
4.Todas as folhas aparecem no mesmo nível e 
carregam informação
5.Um nó não-folha com "k" filhos deve ter k-1 
chaves
63
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
– Inserção
• Primeiro pesquise a chave, para ter a certeza de que esta não existe na 
árvore.
• Depois, busque a posição onde esta será inserida. Teste para ver se o nó 
está cheio.
• Se nó estiver vazio, insira o valor dentro dele, senão execute uma 
subdivisão do nó da seguinte forma:
– Verifique se o nó-pai está vazio, se sim execute
» Passe o elemento do meio do nó para seu pai.
» Divida o nó em dois nós iguais.
– Se o nó pai estiver cheio, repita as duas linhas acima 
recursivamente.(Caso todos os nós-pai estiverem cheios, inclusive 
a raiz, deve ser criada uma nova raiz aumentando assim a altura da 
árvore.
– Somente após satisfazer todas divisões necessárias, insira nova 
chave.
64
18/03/2013
12
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Exemplo:
– Inserir as chaves 1,2,3,4,5,6,7 em uma árvore B 
de ordem 3:
• Ou seja, numa árvore-B de ordem m, o número 
máximo de chaves em uma página é m-1. 
• Então 3-1 = 2 chaves por página (nó);
65
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 66
1
18/03/2013
13
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 67
1 2
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 68
2
1 3
18/03/2013
14
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 69
2
1 3 4
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 70
2 4
1 3 5
Obs: cada página tem no máximo m descendentes (ordem).
18/03/2013
15
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 71
2 4
1 3 5 6
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 72
4
2
1
6
3 5 7
18/03/2013
16
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Exercício:
– Baseado no resultado da árvore anterior, inclua 
as chaves:
• 8, 9, 10, 11, 12, 13
73
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Exercício:
– Resultado:
74
4 8
2 10 12
1 3 9 11 13
6
5 7
18/03/2013
17
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Vantagens
– Melhor desempenho por ter um número menor de nós 
do que uma árvore binária, por exemplo. Menos nós, 
significa menos altura que resulta em menos acessos ao 
disco.
– Por garantir poucos ponteiros entre os nós, há uma 
economia de espaço.
– Maior rapidez em buscas pela utilização de chaves 
primárias.
– Sua estrutura é dinâmica, ajustando automaticamente o 
balanceamento da árvore, a cada inclusão/exclusão.
– Permite um tempo de acesso de dados menor, em uma 
busca aleatória, por causa de suas ramificações.
75
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Desvantagens
– Nó não folha com n chaves, é visitado n vezes, 
portanto o processo de busca às vezes pode se 
tornar lento.
– As árvores B+ sempre mantém uma cópia de 
todos os dados nas folhas, o que em caso de 
necessidade de imprimir toda ela, por exemplo, 
permite uma rápida busca linear, fazendo com 
que a Árvore B, em comparação, tenha menor 
performance.
76
18/03/2013
18
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Exercício:
– Insira as chaves a seguir em uma Árvore B de 
ordem 5;
– 3, 9, 2, 1, 7, 8, 10, 13, 6, 11
77
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Exercício:
– Resultado:
78
3 9
1 2 6 7 8 10 11 13
18/03/2013
19
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Exercício:
– Insira as chaves a seguir em uma Árvore B de 
ordem 5;
– a, g, f, b, k, d, h, m, j, e, s, i, r, x, c, l, n, t, u, p
79
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Exercício:
– Insira as chaves a seguir em uma Árvore B de 
ordem 5;
– a, g, f, b, k, d, h, m, j, e, s, i, r, x, c, l, n, t, u, p
80
18/03/2013
20
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 81
a b f g
Em uma árvore B de ordem m, o número máximo de chaves em uma página é m-1, 
então 5-1 = 4
a, g, f, b, k, d, h, m, j, e, s, i, r, x, c, l, n, t, u, p
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 82
f
a b g k
cada nó (exceto a raíz e as folhas) tem pelo menos "m/2" filhos, 
então 5/2 = 2,5 trunc = 2
a, g, f, b, k, d, h, m, j, e, s, i, r, x, c, l, n, t, u, p
18/03/2013
21
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 83
f
a b d g h k m
a, g, f, b, k, d, h, m, j, e, s, i, r, x, c, l, n, t, u, p
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 84
f j
a b d g h k m
a, g, f, b, k, d, h, m, j, e, s, i, r, x, c, l, n, t, u, p
18/03/2013
22
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 85
f j r
a b d e g h k m
a, g, f, b, k, d, h, m, j, e, s, i, r, x, c, l, n, t, u, p
i s x
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 86
c f j r
a b
a, g, f, b, k, d, h, m, j, e, s, i, r, x, c, l, n, t, u, p
d e g h i k m s x
18/03/2013
23
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 87
c f j r
a b
a, g, f, b, k, d, h, m, j, e, s, i, r, x, c, l, n, t, u, p
d e g h i k l m n s t u x
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 88
c f
j
r
a b
a, g, f, b, k, d, h, m, j, e, s, i, r, x, c, l, n, t, u, p
d e g h i lk s t u x
Obs: cada página tem no máximo m descendentes (ordem), nesse caso, 5
m
n p
18/03/2013
24
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Pesquisa:
– Remoção de elementos em árvoreB
• Trazer metodologia, exercício completo e explicar 
como funciona;
89
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Árvores B+
90
18/03/2013
25
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
– Está sempre balanceada, ou seja, os nós folhas 
estão sempre no mesmo nível.
– Os ponteiros de dados estão armazenados 
somente nos nós folhas da árvore. 
– A definição da ordem p da árvore B+ é igual a da 
árvore B.
– pfolha é o número máximo de ponteiros de 
dados para um nó folha.
– A estrutura dos nós folhas difere da estrutura 
dos nós internos.
91
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
– A estrutura do nó interno é (P1, K1, P2, K2, 
...P(q-1), K(q-1), Pq), sendo K o valor do campo 
de pesquisa e q<=p.
– A estrutura do nó-folha é (<K1, Pr1>, <K2, Pr2>, 
...<K(q-1), Pr(q-1)>, Ppróximo), sendo K o valor 
do campo de pesquisa, Pr o ponteiro de dados e 
q<=p.
– Os nós folhas são interligados através de um 
ponteiro para fornecer um acesso ordenado no 
campo de pesquisa. Esta é uma grande 
vantagem da árvore B+ em relação à árvore B.
92
18/03/2013
26
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
– Seja X um valor de busca. Se X <= K, devemos 
percorrer a subárvore à esquerda de K. Se X > K, 
percorreremos a subárvore à direita de K.
93
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Forma geral
– Variante da árvore B. 
– Os nós não folha armazenam as chaves dos 
registros e não os registros inteiros. 
– Em nó interno de uma árvore B+ cabe mais 
registros do que o de uma árvore B. 
– Consequentemente a altura da árvore B+ é 
menor do que a da árvore B. 
– Os registros são armazenados em nós folha. 
– Nó não folha agem como se fossem uma 
estrutura de índice para nós que contém os 
dados. 
94
18/03/2013
27
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
– Diferentemente da árvore B, a árvore B+ tem a 
estrutura de índices separada da estrutura de 
dados. 
– Para acessar qualquer registro é necessário o 
mesmo número de acessos, já que todos ficam 
no mesmo nível.
95
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Vantagens: 
– Na maioria das vezes a árvore B+ tem altura 
menor do que a árvore B para os mesmos 
registros, o que significa que menos operações 
de E/S são necessárias durante a busca. 
– Não é necessário subir e descer na árvore para 
acessar sequencialmente os registros. 
– Tanto o acesso direto como o acesso sequencial
são melhores que na árvore B. 
96
18/03/2013
28
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
– Uma árvore B+ é uma árvore B na qual os 
registros dados são armazenados em nós folha e 
os nós não folha armazenam apenas os valores 
das chaves, formando um índice para os nós de 
dados. 
– Melhoria no acesso sequencial é obtida 
interligando os nós de dados. Como resultado 
não é necessário mover através da árvore mas 
apenas processar uma lista encadeada formada 
pelos nós não folha. 
– Pela própria definição da árvore B, os registros 
dos nós folha estão automaticamente 
ordenados na lista encadeada. 
97
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 98
18/03/2013
29
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
– Dado que os registros não mais armazenados 
nos nós não folha, o procedimento de busca é 
modificado a fim de que, numa comparação 
igual, a busca prossiga à esquerda ou à direita 
para localizar o nó folha apropriado. 
Arbitrariamente, escolheremos ir à esquerda – o 
que é importante ser definido a priori. 
– As principais diferenças entre a árvore B e a 
árvore B+ está na inserção em um nó folha e no 
que acontece quando ocorre overflow. 
99
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
– Quando ocorre overflow, realiza-se a divisão do 
nó, mas apenas a chave do registro do meio é 
promovida para o nível mais alto. 
– Como nós folha e nós de índice têm funções 
diferentes em uma árvore B+, a inserção do 
primeiro registro de uma árvore B+ é um caso 
especial. 
– O registro é armazenado em um nó folha e sua 
chave é armazenada em um nó de índice, com 
um ponteiro para o nó folha, por exemplo: 
100
18/03/2013
30
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 101
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
– Algoritmo de Inserção em árvore B+ 
• Navegar nos nós não folha da árvore B+ com um 
índice a fim de localizar o nó folha apropriado para 
inserir um novo registro. 
• Se ≤, seguir à esquerda, se > e existe outro registro à 
direita, repetir a comparação anterior (de ≤), senão 
seguir a ramificação da direita.
/*Ao encontrar o nó folha*/ 
102
18/03/2013
31
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• SE existir espaço disponível ENTÃO 
– Inserir o registro (de forma ordenada). 
• SENÃO 
– Dividir o nó folha onde ocorreu overflow. 
» Subir a chave do registro do meio para a estrutura de 
índice. O registro do meio é escolhido entre os 
registros do nó que sofreu overflow e o registro sendo 
inserido, considerando-os de forma ordenada. 
» Dividir os registros do nó que sofreu overflow, 
incluindo o registro sendo inserido, entre dois nós tal 
que todos os registros com chave menores do que a 
chave do registro sendo inserido e o registro sendo 
inserido sejam armazenados no nó da esquerda. Os 
demais são armazenados no nó da direita. 
– Processar a chave que foi recentemente elevada para a 
estrutura de índice como uma inserção em uma árvore B.
103
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Exemplo: 
– Inserir as chaves a seguir em uma árvore b+ de 
ordem 4
– 85, 60, 52, 70, 58, 37, 54, 110, 230, 56
104
18/03/2013
32
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 105
85, 60, 52, 70, 58, 37, 54, 110, 230, 56
52 60 85
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 106
85, 60, 52, 70, 58, 37, 54, 110, 230, 56
60
•As M-1chaves serão divididas em dois grupos:
•As (M-1 div 2) chaves menores ficam na folha esquerda;
•As (M-1 div 2) chaves maiores ficam na folha direita;
•A maior chave da esquerda é copiada para o nó pai. 
52 60 70 85
18/03/2013
33
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 107
85, 60, 52, 70, 58, 37, 54, 110, 230, 56
60
5258 60 70 85
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 108
85, 60, 52, 70, 58, 37, 54, 110, 230, 56
52 60
58 60 70 8537 52
18/03/2013
34
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 109
85, 60, 52, 70, 58, 37, 54, 110, 230, 56
52 60
54 58 60 70 85 11037 52
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 110
85, 60, 52, 70, 58, 37, 54, 110, 230, 56
52 60 85
54 58 60 70 8537 52 110 230
18/03/2013
35
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 111
85, 60, 52, 70, 58, 37, 54, 110, 230, 56
54 56 58 6037 52 70 85
56
52 56 60 85
110 230
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Pesquisa
– Semelhante à pesquisa em árvore B;
– A pesquisa sempre leva a uma página folha;
– A pesquisa não pára se a chave procurada for 
encontrada em uma página índice.
112
18/03/2013
36
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Exemplo:
– Procurar a chave 60
113
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Remoção
– Caso 1:
• A chave X aparece apenas em um nó folha;
– A chave X é simplesmente removida e a folha é 
reorganizada; 
– Exemplo: remover a chave 80;
114
18/03/2013
37
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 115
Antes:
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 116
Depois:
18/03/2013
38
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Remoção
– Caso 2:
• A chave X aparece também em nós internos (índice)
– A chave X é removida; 
– A folha é reorganizada; 
– A chave X não é removida dos nós internos.
– Exemplo: remover a chave 85;
117
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Antes:
118
18/03/2013
39
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Depois:
119
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Remoção com concatenação
– Exemplo:
• Remover a chave 110;
120
18/03/2013
40
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Antes
121
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Depois
122
18/03/2013
41
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
– Quando uma chave é retirada de um nó folha, o 
número de chaves restantes pode ser menor 
que (M-1)/2.
– Tratamentos:
• Concatenação
• Redistribuição
123
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Remoção com Concatenação
– Duas páginas P e Q são chamadas irmãos 
adjacentes se têm o mesmo pai W e são 
apontadas por ponteiros adjacentes em W.
– P e Q podem ser concatenadas se são irmãos 
adjacentes e juntas possuem menos de M-1 
chaves.
– A concatenação agrupa as entradas de duas 
páginas em uma só;
– No nó pai deixa de existir uma entrada: aquela 
da chave que se encontra entre os ponteiros 
para Pe Q.
124
18/03/2013
42
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
– Essa chave é simplesmente removida do nó pai.
– Então:
125
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 126
- Remover a chave 110 (cont.)
18/03/2013
43
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
– Como foi retirada uma chave do nó W, caso ele 
passe a ter menos de (M-1)/2chaves, o processo 
se repete;
– Ou seja, a concatenação é um processo 
propagável;
– Se a propagação atingir a raiz, a árvore 
diminuirá de altura.
– Então:
127
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 128
– Remover a chave 110 (propagação) continuação
18/03/2013
44
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Outro exemplo:
– Remover a chave 80 (antes);
129
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Outro exemplo:
– Remover a chave 80 (depois);
130
18/03/2013
45
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Remoção com Redistribuição
– Se a página P e seu irmão adjacente Q possuem 
em conjunto M-1 ou mais chaves, estas podem 
ser equilibradamente distribuídas:
• Concatena-se P e Q;
• Efetua-se a cisão da página resultante.
131
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 132
- Remover a chave 80 (redistribuição);
18/03/2013
46
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Exercício:
– Incluir as chaves 8, 5, 1, 7, 3, 12, 9, 6
– Em uma árvore B+ de ordem 3;
133
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 134
5 8
8, 5, 1, 7, 3, 12, 9, 6
18/03/2013
47
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 135
5
8, 5, 1, 7, 3, 12, 9, 6
1 5 8
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 136
3 5
8, 5, 1, 7, 3, 12, 9, 6
1 3 5 7 8
18/03/2013
48
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 137
3
8, 5, 1, 7, 3, 12, 9, 6
1 3 5 7 8
5
8
12
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 138
3
8, 5, 1, 7, 3, 12, 9, 6
1 3 5 7 8
5
8
9 12
18/03/2013
49
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 139
3
8, 5, 1, 7, 3, 12, 9, 6
1 3 5 6 7
5
7 8
9 128
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Bancode Dados – Prof. Anderson Nascimento
• Comparação entre consultas com Árvores B 
e B+
– Exemplo: 
– n=100
– Arquivo com 1.000.000 valores de chave de 
busca (K)
– Pesquisa acessa apenas 4 nós em árvore B+
– Pesquisa acessa 20 nós em árvore B 
140
18/03/2013
50
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Índices de Hash
– Hashing pode ser usado não apenas para a 
organização do arquivo, mas também para a 
criação da estrutura de índices.
– Um índice hash organiza as chaves de busca (K) 
com os seus ponteiros de registro (P) 
associados.
– Uma vez que uma entrada K é encontrada no 
arquivo de índice, o ponteiro P é utilizado para 
localizar o registro correspondente no arquivo 
de dados.
141
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
• Comparação entre indexação ordenada e hashing
– Indexação ordenada:
• Razoavelmente eficiente para pesquisa de igualdade 
pois a busca binária é utilizada.
• Eficiente para pesquisas de intervalo de valores.
– Hashing: 
• Eficiente para pesquisa de igualdade.
• Ineficiente para recuperar registros de maneira 
ordenada.
-
142
18/03/2013
51
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento
Exercício
• Utilizando uma estrutura de índices baseada 
em Árvores B+, insira os valores a seguir, 
utilizando árvore de ordem p=4: 
• C S D T A M P I B W N G U R K E H O L J Y Q Z 
F X V
143
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 144
C D S
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
número de chaves em cada nó P-1 => 3
18/03/2013
52
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 145
D
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D S T
número de chaves mínimos => trunc(P/2) => 2
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 146
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
D
A C D M S T
18/03/2013
53
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 147
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
D P
A C D M P S T
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 148
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
D P
A C D I M P S T
18/03/2013
54
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 149
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
B D P
C D I M P S TA B
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 150
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
B D P
C D I M P S T WA B
18/03/2013
55
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 151
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
B D P
C D I M P S T WA B
número máximo de nós filhos = P => P=4 então, 4 nós
N
M
D
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 152
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D I M S T WA B
D
B D M P
N P
18/03/2013
56
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 153
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D G I M S T WA B
D
B D M P
N P
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 154
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D G I M S T WA B
D
B D M P
N P
U
18/03/2013
57
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 155
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D G I M S TA B
D
B D M P T
N P U W
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 156
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D G I M R S TA B
D
B D M P T
N P U W
18/03/2013
58
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 157
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D G I M R S TA B
D
B D M P T
N P U W
K
I
M
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 158
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D G K M R S TA B
D
B D M P T
N P U W
M
I
I
18/03/2013
59
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 159
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D G K M R S TA B
D
B D M P T
N P U W
M
I
IE
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 160
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D G K M R S TA B
D
B D M P T
N P U W
M
I
IE
H
G
18/03/2013
60
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 161
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D G K M R S TA B
D
B D M P T
N P U W
M
I
IE H
G
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 162
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D G K M R S TA B
D
B D M P T
N O P U W
M
I
IE H
G
18/03/2013
61
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 163
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D G K M R S TA B
D
B D M P T
N O P U W
M
I
IE H
G
L
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 164
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D G K M R S TA B
D
B D M P T
N O P U W
M
I
IE H
G
L
J
K
18/03/2013
62
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 165
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D G K M R S TA B
D M
B D M P T
N O P U W
I
I
IE H
G
L
K
J
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 166
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D G K M R S TA B
D M
B D M P T
N O P U W Y
I
I
IE H
G
L
K
J
18/03/2013
63
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administraçãode Banco de Dados – Prof. Anderson Nascimento 167
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D G K M R S TA B
D M
B D M P T
N O P U W Y
I
I
IE H
G
L
K
J
Q
R
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 168
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D G K M R S TA B
D M
B D M R T
N O P U W Y
I
I
IE H
G
L
K
J
P
Q
18/03/2013
64
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 169
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D G K M R S TA B
D M
B D M R T
N O P U W Y
I
I
IE H
G
L
K
J
P
Q
Z
W
R
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 170
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D G K M R S TA B
D I R
B D M R T
N O P U W
I
IE H
G
L
K
J
P
Q
M
M
Z
W
Y
18/03/2013
65
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 171
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D K M R S TA B
D I R
B D M R T
N O P U W
I
IH
G
L
K
J
P
Q
M
M
Z
W
YGE F
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 172
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D K M R S TA B
D I R
B D M R T
N O P U W Z
I
IH
G
L
K
J
P
Q
M
M
Y
W
XGE F
18/03/2013
66
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 173
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C D K M R S TA B
D I R
B D M R T
N O P U W Z
I
IH
G
L
K
J
P
Q
M
M
Y
W
XGE F V
Escola de Ciência e Tecnologia
Curso: Sistemas de Informação
Disciplina: Administração de Banco de Dados – Prof. Anderson Nascimento 174
Fim da Parte II