Revisão Prova 2Métodos de Acesso:

BTree e Hash

AULA 20 Profa. Sandra de Amo

GBC053 – BCC2013-1

Discussão

Implementação dos operadores de SQL Técnicas usando Ordenação (Externa !)

Projeção – Junção - Conjuntos Técnicas usando Particionamento

Projeção – Junção – Conjuntos Técnicas usando Indice

Seleção Junção

REVISÃO – BTREE

Inserção: se nó onde deveria ocorrer a inserção já está cheio Variante 1 : Se nó está cheio divida e ajuste os nós

ancestrais. Variante 2 : Testa primeiro se pode redistrisbuir

num nó vizinho. Em caso negativo, divide.

Ideal Nós intermediários: sempre dividir, não redistribuir Nós Folha: procure redistribuir entre os vizinhos

Se tiver espaço no vizinho direito, redistribua. Caso contrário, verifica se tem espaço no

vizinho esquerdo, e redistribua Caso contrário: divida a folha cheia.

Inserção : Testando vizinho à direita

13 17 24 30

7*5* 14*16* 19*20* 22* 24*27*29* 33*34* 39*38*

Inserindo 6*

6*

14* 16*2* 3*

CHEIA !!

Inserção : Testando vizinho à direita

13 17 24 30

7*5* 14*16* 19*20* 22* 24*27*29* 33*34* 39*38*

Inserindo 6*

14*16*2* 3*

7*5*2* 3* 6*

Inserção : Testando vizinho à direita

13 17 24 30

5* 14*16* 19*20* 22* 24*27*29* 33*34* 39*38*

Inserindo 6*

14*16*2* 3*

7*5*2* 3* 6*

7*

7*

6*

Inserção : Testando vizinho à esquerda

8 17 24 30

7*5* 14*16* 19*20* 22* 24*27*29* 33*34* 39*38*

Inserindo 35*

8* 14* 16*2* 3*

33*34* 39*38*35*

Inserção : Testando vizinho à esquerda

8 17 24

7*5* 14*16* 19*20* 22* 24*27*29* 33* 35* 39*38*

Inserindo 35*

8* 14* 16*2* 3* 34*

34

Inserção : Vizinhos estão cheios Divisão da Folha

13 17 24 30

2* 3* 7*5* 13*14* 19*20* 22* 24*27*29* 33*34* 39*38*

Inserindo 8*

Cheia !

7* 8*55*

Cheia !

15*16*

2* 3* 7*5* 8*

Divisão de nós intermediários

13 17 24 305

2* 3* 7*5* 13*14* 19*20* 22* 24*27*29* 33*34* 39*38*7* 8*55* 15*16*

Divisão de nó intermediário

13 24 305

17

2* 3* 7*5* 14*16* 19*20* 22* 24*27*29* 33*34* 39*38*7* 8*55*

Deleção

Se ocupação não fica abaixo do mínimo, deleta, não altera ponteiros, nem nós ancestrais

Se ocupação fica abaixo do mínimo Tenta redistribuição com nó vizinho, se

possível Caso contrário junta com vizinho à direita

ou à esquerda (caso for o último nó).

Exemplo: Deleção

2* 3* 14*16* 19* 20*22* 24* 27* 29* 33*34* 39*38*

Removendo 19*

7* 8*5*

5 13 24 30

17

Deleção: Redistribuição nas folhas Com nó direito

Removendo 20*

5 13 24 30

17

2* 3* 14*16* 20* 22* 24* 27* 29* 33*34* 39*38*7* 8*5*

Deleção: Redistribuição nas folhas Com nó direito

Removendo 20*

5 13 27 30

17

2* 3* 14*16* 24* 27* 29* 33*34* 39*38*7* 8*5*

24

22*

Deleção: Redistribuição nas folhas Com nó esquerdo

Removendo 33*

5 13 30

17

2* 3* 14*16* 22* 24* 27* 29* 33*7* 8*5*

24

35*

Deleção: Redistribuição nas folhas Com nó esquerdo

Removendo 33*

5 13 30

17

2* 3* 14*16* 22* 24* 27*7* 8*5*

24

35*29*

29

Discussão

Distribuição nas folhas vizinhas não acarreta mudança - redução de ocupação dos nós pais

Portanto: Nós pais não ficam abaixo da ocupação mínima Não precisam ser juntados nem redistribuídos entre

seus vizinhos Não há redução da altura da árvore Modificações não se propagam para nós acima do nó-

pai

Deleção: Juntando FolhasCom nó à direita

2* 3* 14* 15* 22* 33*34* 39*38*

Removendo 24*

7* 8*5*

5 13 30

17

24*

27

27*29*22* 27* 29*

Não dá para redistribuir os vizinhosTamanho do vizinho direito = dVizinho à esquerda tem pai diferente

JUNTA COM O VIZINHO DA DIREITA

16*

40

Deleção: Juntando FolhasCom nó à direita

33*34* 39*38*

Removendo 24*

5 13 30

17

24*

27

27*22* 27* 29*

27

Quase vazia ! Não dá para distribuircom vizinho

30

2* 3* 14* 15*7* 8*5* 16*

17 40

Junção de nós intermediários

2* 3* 14* 16* 33*34* 39*38*7* 8*5*

30

24*

27

27*22* 27* 29*

305 13 30 3027305 13 30

Removendo 24* 1717 40

Deleção: Juntando FolhasCom nó à esquerda

2* 3* 14* 16* 49*50*

Removendo 16*

7*5*

5 13 60

45

45*46*

47

63* 65*

Deleção: Juntando FolhasCom nó à esquerda

2* 3* 14* 16* 49*50*

Removendo 16*

7*5*

5 13 60

45

45*46*

47

63* 65*

Deleção: Juntando FolhasCom nó à esquerda

2* 3* 14* 49*50*

Removendo 16*

7*5*

5 13 60

45

45*46*

47

63* 65*

Deleção: Juntando FolhasCom nó à esquerda

2* 3* 49*50*

Removendo 16*

7*5*

5 13 60

45

45*46*

47

63* 65*7* 14*5*

Deleção: Juntando FolhasCom nó à esquerda

2* 3* 49*50*

Removendo 16*

7*5*

5 60

45

45*46*

47

63* 65*14*

Devem ser juntadas

Deleção: Juntando FolhasCom nó à esquerda

2* 3* 49*50*

Removendo 16*

7*5*

5

45

45*46* 63* 65*14*

47 60

Redistribuição em nós intermediários

13 1755 13 27 30

22

17 20

2* 3* 5* 7* 8* 14*16* 17* 18* 20* 21* 22* 24* 29*27* 33* 34* 38* 39*

Removendo 24* : Não existe possibilidade de juntar nós intermediários

Redistribuição em nós intermediários

13 1755 13 30

22

17 20

2* 3* 5* 7* 8* 14*16* 17* 18* 20* 21* 22* 29*27* 33* 34* 38* 39*

Quase vazia

Redistribuição em nós intermediários

13 1755 13 30

22

17 20

2* 3* 5* 7* 8* 14*16* 17* 18* 20* 21* 22* 29*27* 33* 34* 38* 39*

Redistribuição em nós intermediários

13 1755 13 13 17520 3017

22

3* 5* 7* 8* 14*16* 17* 18* 20* 21* 22* 29*27* 33* 34* 38* 39*

REVISÃO – BULK LOADING

Exemplo

3* 4* 6* 9* 10* 11* 12* 13* 20* 22* 23* 31* 35* 36* 38* 41* 44*

Páginas restantes a alocar

Ordem da b-tree = 1

Exemplo

3* 4* 6* 9* 10* 11* 12* 13* 20* 22* 23* 31* 35* 36* 38* 41* 44*

Ordem da b-tree = 16* 10*

Páginas restantes a alocar

Exemplo

3* 4* 6* 9* 10* 11* 12* 13* 20* 22* 23* 31* 35* 36* 38* 41* 44*

6* 10* 12*

Precisa dividir

20*

Exemplo

3* 4* 6* 9* 10* 11* 12* 13* 20* 22* 23* 31* 35* 36* 38* 41* 44*

6* 12*10* 20*

Páginas restantes a alocar

Exemplo

3* 4* 6* 9* 10* 11* 12* 13* 22* 31* 35* 36* 38* 41* 44*

6* 12*

10*

20*

20*

23*

23*

Precisa dividir

35*

Exemplo

3* 4* 6* 9* 10* 11* 12* 13* 22* 31* 35* 36* 38* 41* 44*

6* 12*

10*

20*

23*

23*

20*

35*

Páginas restantes a alocar

Exemplo

3* 4* 6* 9* 10* 11* 12* 13* 22* 31* 35* 36* 38* 41* 44*

6* 12*

10*

20*

23*

23*

20*

35* 38* 44*

Precisa dividir

Exemplo

3* 4* 6* 9* 10* 11* 12* 13* 22* 31* 35* 36* 38* 41* 44*

6* 12*

10*

20*

23*

23*

20*

38* 44*

35*

Precisa dividir

Exemplo

3* 4* 6* 9* 10* 11* 12* 13* 22* 31* 35* 36* 38* 41* 44*

6* 12*

10*

20*

23*

23*

38* 44*

35*

20*

Exemplo:Entrada: Arquivo de indice de 9 páginas com 4 registros em cada uma. d = 2, k = 0, x = 1Saída: (3, <B0,B1,B2>) B0 = 18 páginas (folhas em amarelo) contendo 2 (= d + k) registros em cada uma B1 = Nível 1 da Btree = 5 páginas (azuis) de 3 (= d + x) registros cada (exceto a última) B2 = Nível 2 da Btree (raiz) = 1 página com 4 registros

Exemplo:Entrada: Arquivo de indice de 9 páginas com 4 registros em cada uma. d = 2, k = 0, x = 1Saída: (3, <B0,B1,B2>) B0 = 18 páginas (folhas em amarelo) contendo 2 (= d + k) registros em cada uma B1 = Nível 1 da Btree = 5 páginas (azuis) de 3 (= d + x) registros cada (exceto a última) B2 = Nível 2 da Btree (raiz) = 1 página com 4 registros

REVISÃO – HASH

Hash Estático

Função Hash não se altera Caso um bucket fique cheio cria-se páginas

de overflow para este bucket que ficou cheio.

Alguns buckets podem concentrar muito mais páginas que outros buckets.

Inserção

0

1

2

5

h

h(7) mod 6 = 1

7

…

…Inserindo < 7, * >

4

3

< 7, * >

Cheia

Supressão

0

1

2

5

h

h(25) mod 6 = 1

25

…

…Suprimindo < 25, * >

4

3

< 25, * >

Função Hash

Componente importante da técnica hash

Deve distribuir valores das chaves de maneira uniforme nos buckets.

Número de buckets = N = parâmetro

h(x) = a*x + b , a, b : parâmetros de ajuste

Custos

Páginas primárias do índice podem ser armazenadas em páginas de disco sucessivas.

Caso não haja overflow Busca no índice requer 1 I/O Inserção e Supressão requerem 2 I/O

Custo pode ser alto se existem muitas páginas de overflow.

Estratégia : criar inicialmente os buckets deixando 20% de área livre em cada um.

Hash (dinâmico) Extensível

Solução 1 : quando algum bucket ficar cheio Dobrar o número de buckets Distribuir as entradas nos novos buckets Defeito : o arquivo todo deve ser lido e reorganizado

e o dobro de páginas devem ser escritas. Espaço em alguns buckets é alocado bem antes de

sua utilização efetiva. Solução 2 : utilizar um diretório de ponteiros para

os buckets. Dobrar o número de entradas no diretório Separar somente os buckets que ficaram cheios.

Exemplo

00

01

10

11

2

Diretório dos Ponteiros

Profundidade Global

4* 12* 32* 16*

2

1* 5* 21*

2

10*

2

15* 7* 19*

2

Bucket A

Bucket B

Bucket C

Bucket D

Páginas do Indice

Profundidade Local

Exemplo – inserção

00

01

10

11

2

Diretório

4* 12* 32* 16*

2

1* 5* 21*

2

10*

2

15* 7* 19*

2

Páginas do Indice

Inserindo 13*

13*

Exemplo – inserção

00

01

10

11

2

Diretório

4* 12* 32* 16*

2

1* 5* 21*

2

10*

2

15* 7* 19*

2

Inserindo 20*

13*

4* 12* 20*

2

32* 16*

2

Exemplo – Inserção

00

01

10

11

2

Diretório

1* 5* 21*

2

10*

2

15* 7* 19*

2

Inserindo 20*

13*

4* 12* 20*

3

32* 16*

3

000

001

010

011

100

101

110

111

3

GlobalLocal

Bucket A1

Bucket A2

Bucket D

Bucket C

Bucket C

Exercicio: Busca 22*, 21*, 8*

Diretório

1* 5* 21*

2

10*

2

15* 7* 19*

2

13*

4* 12* 20*

3

32* 16*

3

000

001

010

011

100

101

110

111

3

Global

Bucket A1

Bucket A2

Bucket D

Bucket C

Bucket C

Local

Hash (Dinâmico) Linear

Assim como o Hash Extensível, o Hash Linear é ideal para inserções e supressões;

Vantagem sobre extensível Lida muito bem com colisões Oferece muita flexibilidade

Cadeias de overflow podem tornar o hash linear inferior em performance ao hash extensivel

Parâmetros e Contadores

Nivel = indica a rodada atual Inicializado com 0

Next = bucket que deve ser dividido, se necessário Inicializado com 0

Nm = número de buckets na rodada m N0 = N Nm = N*2m

Somente o bucket com número Next é dividido. Usa-se páginas de overflow para os outros buckets,

se ficarem cheios. Após divisão, Next é incrementado.

Esquema Geral : rodada k

Bucket Nexta ser dividido

Imagens dos buckets divididos

Bucket b

Bucket b + m

Buckets existentesno inicio da rodada k

m = número de buckets da rodada k

32* 44* 36*

9* 25* 5*

14*

31* 35* 7*

18* 10* 30*

11*

Páginas Primárias

Nivel = 0 , N = 4 = 22

Next = 0h0h1

00

01

10

11

000

001

010

011

Esta informação não é armazenada !

Inserção de 43*

h0(43) = 3 (11)

43*

Next = 1

44* 36*00

32*

9* 25* 5*

14*

31* 35* 7*

18* 10* 30*

11*

Nivel = 0 , N = 4 = 22h0h1

00

01

10

11

000

001

010

011

Busca de 18*

h0(18) = 2 (10)

43*

Next = 1

44* 36*00

2 > Next

Bucket 2 não foi dividido ainda

100

32*

9* 25* 5*

14*

31* 35* 7*

18* 10* 30*

11*

Nivel = 0 , N = 4 = 22h0h1

00

01

10

11

000

001

010

011

Busca de 32* e 44*h0(32) = 00

43*

Next = 1

44* 36*00

0 < Next

Bucket 0 já foi dividido ainda

h0(44) = 00

h1(32) = 000

h1(44) = 100Bucket 0 + 4

100

Inserção de 37*

32*

9* 25* 5*

14*

31* 35* 7*

18* 10* 30*

11*

00

01

10

11

000

001

010

011 43*

Next = 1

44* 36*00100

h0(37) = 01

37*

Inserção de 29*32*

9* 25* 5*

14*

31* 35* 7*

18* 10* 30*

11*

00

01

10

11

000

001

010

011 43*

Next =1

44* 36*00100

h0(29) = 01

37*

5* 37* 29*01101

Next =2

Incremento de Nível32*

9* 25*

66*

31* 35* 7*

18* 10* 34*

11*

00

01

10

11

000

001

010

011 43*

44* 36*00100

h0(50) = 10

5* 37* 29*01101

14* 30* 22*10110

h1(50) = 010

50*Next =3

Next =0Nivel = 1

31*111 11 7*

43* 11*