Gerenciamento de Chaves com
Duplicatas na B-TREE
AULA 14 – Parte I
Profa. Sandra de Amo
GBC053 – BCC
Gerenciando Duplicatas
Quando a chave do índice não contém chave candidata da
relação
Método 1 (Sybase):
• índice é agrupado
• Folhas não contém duplicatas.
• A entrada (k,rid) em uma folha: o rid = (np,ns) indica onde se
encontra a primeira ocorrência da chave k no arquivo de dados
• Para cada chave k que se repete, insere-se páginas de overflow
nos dados contendo os registros com esta chave.
EXEMPLO: GERENCIAMENTO DE DUPLICATAS – MÉTODO 1
Folhas da b-tree não
contém duplicatas
(8,(5,3)
Páginas de Dados contém duplicatas
Slot 3 da
Pág. 5 de
Dados
(pedro,7,6000)
(carlos,8,7000)
(saulo,8,5500)
(pedro,9,6000)
(caio,8,6500)
...
(maria,8,5500)
Página 5
(ana,8,6000)
Gerenciando Duplicatas
Método 2 (DB2, Oracle, MS SQL Server):
considera-se um identificador de tuplas,
eliminando-se as duplicatas.
Exemplo: (k,*) (k,*) ...  (k,id1,*) (k,id2,*),...
EXEMPLO: GERENCIAMENTO DE DUPLICATAS – MÉTODO 2
identificador
Folhas da b-tree não
contém duplicatas
(8,1,(5,3) (8,2,(5,4)
Páginas de Dados não
contém páginas de overflow !
(pedro,7,6000)
(carlos,8,7000)
(saulo,8,5500)
(pedro,9,6000)
Página 5
Slot 3
Slot 4
Comparação dos 2 métodos
•
Esforço de programação : Método 2 é melhor !
–
A manutenção do indice é idêntica à da b-tree sem duplicatas
–
Não há necessidade de projetar novos algoritmos de inserção e
remoção no indice
–
O Método 1 exige modificação nos algoritmos de inserção e remoção
de registros de dados para gerenciar as páginas de overflow.
–
O Método 2 não exige nenhuma modificação nos algoritmos de
inserção e remoção de registros de dados
•
Ocupação de espaço : os dois métodos têm pontos negativos
–
Método 2 ocupa mais espaco no índice
–
Método 1 ocupa mais espaço para os dados – páginas de overflow
podem ter muito espaço livre
•
Tempo de busca: O método 2 é um pouco inferior ao método 1 neste
quesito.
–
B-tree do Método 2 pode conter mais níveis do que a do Método 1, o
que pode aumentar seu tempo de busca.
Conclusão da Análise: Método 2 é mais vantajoso.
•
Método 3: Método Geral para
Gerenciamento de Duplicatas
• Folhas dos índices contém duplicatas !
• Algoritmos de inserção e remoção de chaves nas folhas
são adaptados para gerenciar chaves duplicatas.
• Algoritmos de inserção e remoção de registros no
arquivo de dados não sofrem alterações
Como são os nós internos da B-TREE ?
Pi = ponteiros que apontam para um núm. de página no nível imediatamente inferior
Ki = valor do atributo chave do índice OU O SIMBOLO “-”
P0 K1 P1 K2 P2 K3
...
Pi
K < Ki+1
Valores K da chave nesta página
são < Ki+1
Ki+1 Pi+1 ...
Km Pm
K ≥ Ki+1
Primeiras ocorrências de chaves K
nesta página são ≥ Ki+1
Como são os nós internos da B-TREE ?
Pi = ponteiros que apontam para um núm. de página no nível imediatamente inferior
Ki = valor do atributo chave do índice OU O SIMBOLO “-”
P0 K1 P1 K2 P2 ...
Ki-1 Pi-1
Ki-1 <= K < Ki+1
Valores K da chave nesta página
são < Ki+1 e >= Ki-1
-
Pi
Ki+1 ...
Pm
Ki-1 <= K < Ki+1
Todas as chaves K nesta página
são repetições de uma chave que
começou em páginas anteriores
K < Ki+1, K >= Ki-1
Método Geral para Gerenciamento de
Duplicatas
12
7
2* 3* 5*
7* 8*
95
9* 10*
13
17
11*12*
13
375
43
13
14* 14*15*15* 15* 37* 41*
17
43* 47*
A primeira chave diferente
é a 37
Exemplo: Vamos inserir 9 cópias da chave
23* na B-tree da figura, passo a passo
17
7
2* 3* 5*
7* 8*
95
13
17
9*10*13*13* 17*18*
37
43
5
37* 41*
13
17
43* 47*
Inserindo a 1a e 2a cópias da chave 23*
17
7
2* 3* 5*
7* 8*
95
13
17
37
9*10*13*13* 17*18* 23* 23*
1
2
43
5
37* 41*
13
17
43* 47*
Após a inserção da 3a cópia da chave 23*
17
7
2* 3* 5*
7* 8*
95
13
-
17
9*10*13*13* 17*18* 23*
1
23* 23*
2
3
375
37* 41*
13
43
17
43* 47*
Após a inserção da 4a e 5a cópias da chave 23*
17
7
2* 3* 5*
7* 8*
95
13
-
17
9*10*13*13* 17*18* 23*
1
375
23* 23* 23*23* 37* 41*
2
3
4
5
13
43
17
43* 47*
Após a inserção da 6a e 7a cópias da chave 23*
17
7
2* 3* 5*
7* 8*
95
13
-
17
9*10*13*13* 17*18* 23*
1
375
13
43
17
23* 23* 23*23* 23* 23* 37* 41* 43* 47*
2
3
4
5
6
7
Após a inserção da 8a cópia da chave 23*
17
7
2* 3* 5*
7* 8*
95
13
-
17
9*10*13*13* 17*18* 23*
1
375
13
41
17
23* 23* 23*23* 23* 23* 23* 37* 41* 43* 47*
2
3
4
5
6
7
8
Após a inserção da 9a cópia da chave 23*
17
7
2* 3* 5*
7* 8*
95
13
-
17
9*10*13*13* 17*18* 23*
1
-5
17
13
37
23* 23* 23*23* 23* 23* 23* 23* 37*
2
3
4
5
6
7
8
9
41* 43*47*
BUSCA NA B-TREE
Busca 17*
7
2* 3* 5*
7* 8*
17
95
9*
13
13* 13*13*
17
-
17*17*23*23* 23*
23*23*
23*23*
Recupera todos os 17*
Encontra 23*- pára
375
23* 23*
37*41*
43
13
17
43* 47*
BUSCA NA B-TREE
Busca 24*
7
2* 3* 5*
7* 8*
17
95
13
17
-
9* 13*13*13*17*17*
13*17* 23*
23*23* 23*
23*23*
23*23*
?
375
23* 23* 37*
37*41*
Não precisa ir mais adiante !
43
13
17
43* 47*
BUSCA NA B-TREE
Busca 23*
7
2* 3* 5*
7* 8*
17
95
9*
13
13* 13*13*
17
-
17*17*23*23* 23*
23*23*
23*23*
375
23* 23*
Recupera todos os 23*
Passa para a próxima folha ...
37*41*
43
13
17
43* 47*
Comparação do Método 3 com o
Método 1 e Método 2
Exercicio
Analise as vantagens e desvantagens do método geral
com relação aos métodos 1 e 2 quanto a:
• Esforço de implementação
• Ocupação de espaço
• Tempo de busca