71
Hash e Btree Prof: Sergio Souza Costa

Hash e Btree

Embed Size (px)

Citation preview

Page 1: Hash e Btree

Hash e Btree

Prof: Sergio Souza Costa

Page 2: Hash e Btree

Sobre mim

Sérgio Souza CostaProfessor - UFMADoutor em Computação Aplicada (INPE)

[email protected]

https://sites.google.com/site/profsergiocosta/home

https://twitter.com/profsergiocosta

http://gplus.to/sergiosouzacosta

http://www.slideshare.net/skosta/presentations?order=popular

Page 3: Hash e Btree

Introdução

Banco de dados utilizam indices para recuperação de informação.

Arquivos de índices

Page 4: Hash e Btree

Objetivo:

Permitir um rápido acesso aleatório aos registros num arquivo.

O que é um índice?

Uma estrutura de dados adicional associada ao arquivo (tabela).

Introdução: Indexação

Page 5: Hash e Btree

Hash

Baseiam-se na distribuição uniforme dos valores determinados por uma função (função de hash).

Ordenados

Baseiam-se na ordenação dos valores.Mononível x Multinível

Introdução: Tipos de Indexação

Page 6: Hash e Btree

Exemplos de hash

bucket 0

bucket 1

bucket de overflow para o bucket 1bucket 2

bucket 3

Encadeamento (ou lista) de overflow para o bucket 3

Introdução: Hash

Page 7: Hash e Btree

Introdução: Mononível

Page 9: Hash e Btree

Como aproveitar as características de acesso constante de uma estrutura de dados contigua (vetor, arranjo) ?

Pense na matrícula de alunos em uma universidade ? Posso usá-la diretamente como um índice de um vetor ? Como seria a complexidade de busca ? Quais problemas ?

Hash

Page 10: Hash e Btree

Rafael24452

15600 Tancredo

Por exemplo:

struct aluno { int mat; char nome[81]; char email[41]; }; typedef struct aluno Aluno;

Quanto será o consumo de memoria ?

Hash

Page 11: Hash e Btree

Rafael24452

15600 Tancredo

Por exemplo:

struct aluno { int mat; // 4 bytes = 4 bytes char nome[81]; // 1 byte * 81 = 81 bytes char email[41]; // 1 byte * 41 = 41 bytes }; Total = 126 bytes typedef struct aluno Aluno;

Quanto será o consumo de memoria ?

Hash

Page 12: Hash e Btree

E se a matricula fosse composta por mais dígitos, por exemplo 8.

E se quiséssemos indexar por outra informação, ao invés da matricula, por exemplo o nome.

Hash

Page 13: Hash e Btree

Função

Page 14: Hash e Btree

h(k) = k mod m

Método da divisão

2139817328215132161321264

98

Para m igual a 100, concluam o mapeamento e me diz o que identificaram ?

Page 15: Hash e Btree

Função sobrejetora

Pode ocorrer que mais de um "índice" seja mapeado para um único valor.

Neste caso dizemos que ocorreu uma "colisão".

Page 16: Hash e Btree

Colisão

Colisão

Page 17: Hash e Btree

Funçao hash

Função hash é como uma função qualquer, porém o grande desafio é gerar funções onde ocorra poucas colisões.

Em rede e sistemas operacionais vocês verão alguns algoritmos, como o md5 e sha-1.

Como vocês acham que funciona a autenticação em um sistem unix ?

Page 18: Hash e Btree

Tabelas de espalhamento (Hash)

● Hash é uma generalização da noção mais simples de um arranjo comum,

sendo uma estrutura de dados do tipo dicionário.

● Dicionários são estruturas especializadas em prover as operações de

inserir, pesquisar e remover.

● A idéia central do Hash é utilizar uma função, aplicada sobre parte da

informação (chave), para retornar o índice onde a informação deve ou

deveria estar armazenada.

● Esta função que mapeia a chave para um índice de um arranjo é chamada

de Função de Hashing.

● A estrutura de dados Hash é comumente chamada de Tabela Hash.

Page 19: Hash e Btree

Função de

Hashing

123.456.781-00143.576.342-23345.365.768-93879.094.345-45

19

19 123.456.781-00; Fausto Silva; Av. Canal. Nº 45.

...37 143.576.342-23; Carla Perez; Rua Celso Oliva. Nº 27....50 345.365.768-93; Gugu Liberato; Av. Atlântica. S/N....85 879.094.345-45 ; Hebe Camargo; Rua B. Nº 100....

375085

20Tabela Hash

Tabelas de espalhamento (Hash)

Page 20: Hash e Btree

Função Hash

● A Função de Hashing é a responsável por gerar um índice a partir

de uma determinada chave.

● O ideal é que a função forneça índices únicos para o conjunto das

chaves de entrada possíveis.

● A função de Hashing é extremamente importante, pois ela é

responsável por distribuir as informações pela Tabela Hash.

● A implementação da função de Hashing tem influência direta na

eficiência das operações sobre o Hash.

● Tal função deve ser fácil de se computar

Page 21: Hash e Btree

Função Hash

Page 22: Hash e Btree

Função Hash

Considerem uma função hash que mapeia todos os valores para o mesmo indice. Qual será a complexidade de busca ?

Considerem uma função hash que mapeia apenas um valor para cada indice. Qual será a complexidade de busca?

Page 23: Hash e Btree

Como representar ?

Page 24: Hash e Btree

Como representar ?

Precisamos de uma função Hash

Page 25: Hash e Btree

Como representar ?

Precisamos de uma função Hash

Precisamos de um arranjo (vetor)

Page 26: Hash e Btree

Como representar ?

Precisamos de uma função Hash

Precisamos de um arranjo (vetor)

Precisamos tratar as colisões

Page 27: Hash e Btree

Tratando colisões

Endereçamento fechado

Endereçamento aberto

Page 28: Hash e Btree

Endereçamento fechado

Page 29: Hash e Btree

No endereçamento fechado, a posição de inserção não muda. Todos devem ser inseridos na mesma posição, através de uma lista ligada em cada uma.

0

1

2

3

4

20 mod 5 = 0 20

18 mod 5 = 3

1825 mod 5 = 0colisão com 20

25

Endereçamento fechado

Page 30: Hash e Btree

A busca é feita do mesmo modo: calcula-se o valor da função hash para a chave, e a busca é feita na lista correspondente.

Se o tamanho das listas variar muito, a busca pode se tornar ineficiente, pois a busca nas listas se torna seqüencial

0

1

2

3

20 4 0 88 32

15 11

60

Endereçamento fechado

Page 31: Hash e Btree

A função HASH deve distribuir as chaves entre as posições de maneira uniforme

0

0 1 2 3 4 5 6

15 10

31

4

88

13

20

Endereçamento fechado

Page 32: Hash e Btree

Chained-Hash-Search(T,k) procure um elemento com chave k na lista T[h(k)] e devolva seu ponteiro

Chained-Hash-Insert(T,x) insira x na cabeça da lista T[h(key[x])]

Chained-Hash-Delete(T,x) remova x da lista T[h(key[x])]

Endereçamento fechado

Page 34: Hash e Btree

Endereçamento aberto

No endereçamento aberto, todos os elementos são armazenados na própria tabela hash.

Para realizar uma inserção, examinamos/testamos sucessivamente a tabela hash ate que encontrarmos um slot vazio no qual a chave sera inserida.

Em endereçamento aberto, a tabela hash pode encher, de forma que não seja mais possível inserir elementos.

Page 35: Hash e Btree

9

0

1

Valores: 204, 44, 58, 10, 100, 25, 20

Endereçamento aberto - Inserção

Page 36: Hash e Btree

9

204

0

1

Valores: 204, 44, 58, 10, 100, 25, 20

Endereçamento aberto - Inserção

Page 37: Hash e Btree

Endereçamento aberto - Inserção

44

9

204

0

1

Valores: 204, 44, 58, 10, 100, 25, 20

Page 38: Hash e Btree

44

9

204

0

1

Valores: 204, 44, 58, 10, 100, 25, 20

Terminem de completar ....

Endereçamento aberto - Inserção

Page 39: Hash e Btree

Endereçamento aberto

Algoritmo de inserção● Usa a função hash para calcular o endereço● Caso esteja ocupado, procure um local vazio.● Se der uma volta completa, significa que esta cheia

Algoritmo de busca● Usa a função hash para calcular o endereço● Enquanto nao achar o valor procurado e nem um

espaço vazio.● Se der uma volta completa, significa que o valor não

está lá.

Page 40: Hash e Btree

Endereçamento aberto

Algoritmo de inserção● Usa a função hash para calcular o endereço● Caso esteja ocupado, procure um local vazio.● Se der uma volta completa, significa que esta cheia

Algoritmo de busca● Usa a função hash para calcular o endereço● Enquanto nao achar o valor procurado e nem um

espaço vazio.● Se der uma volta completa, significa que o valor não

está lá.

Quais conclusões que são possíveis tirar ?

Page 41: Hash e Btree

Endereçamento aberto

A tabela tem que ser tratada de modo circular, quando chega no fim da tabela a varredura reinicia na posição 0.

Quanto mais "cheia" a tabela estiver, pior será a eficiência.

Page 42: Hash e Btree

Em grandes bancos de dados os índices tendem a crescer e são armazenados em memoria secundária. Acesso a disco não é constante.

Btree

Page 43: Hash e Btree

Em memoria

Em disco

Árvores de Busca BináriaApropriada para memória principalIneficiente em memória secundária

Acesso: cerca de log2n passos.

Btree

Page 44: Hash e Btree

As árvores B são árvores multicaminhos (ou multidirecionais) balanceadas projetadas para trabalhar com dispositivos de armazenamento secundário como discos magnéticos.

Diferente das árvores binárias, cada nó em uma árvore B pode ter muitos filhos, isto é, o grau de um nó pode ser muito grande.

Elas visam otimizar as operações de entrada e saída nos dispositivos.

O tempo de acesso às informações em um disco é prejudicado principalmente pelo tempo de posicionamento do braço de leitura.

Btree

Page 45: Hash e Btree

Poucas operações de disco, 1000 chaves.

1000

1001

1000

1001

1000

1001

1000

1001

1000 1000 1000

0 disk ops1000 keys

1 disk ops1,001,000 keys

2 disk ops1,002,001,000 keys

Btree

Page 46: Hash e Btree

Á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.

O criador das árvores B, Rudolf Bayer, não definiu claramente de onde veio o B das árvores B.

Ao que parece, o B vem de balanceamento onde todos as folhas da árvore estão em um mesmo nível.

Também é possível que o B tenha vindo de seu sobrenome Bayer, ou ainda do nome da empresa onde trabalhava Boeing, no Boeing Scientific Research Labs.

Btree

Page 47: Hash e Btree

Árvore B é uma estrutura de dados que utiliza o recurso de manter mais de uma chave em cada nó da estrutura.

Ela proporciona uma organização de ponteiros de tal forma que as operações buscas, inserções e remoções são executadas rapidamente.

As árvores B são largamente utilizadas como forma de armazenamento em memória secundária. Diversos sistemas comerciais de Banco de dados e sistemas de arquivo, por exemplo, as empregam.

Btree

Page 48: Hash e Btree

Os elementos dentro de um nó estão ordenados.

O ponteiro situado entre dois elementos a e b aponta para a sub-árvore que contém todos os elementos entre a e b.

Btree: Estrutura

a b c

< a [a,b] [b,c] > c

Page 49: Hash e Btree

Btree: Definições (1)

Baseado no livro do Cormem

1. Seja T uma árvore-B com raiz (root[T]). Ela possuirá então as seguintes propriedades: 1. Todo o no X tem os seguintes campos:

a. n[x], o numero de chaves atualmente guardadas no nodo x,

b. As n[x] chaves, guardadas em ordem crescente, tal que key

1[x] <= key

2[x] <= … <= key

n[x]

c. leaf [x], Um valor booleano, TRUE se x e uma folha e FALSE se x e um nodo interno

MO637 – Complexidade de Algoritmos I Arvores B

Page 50: Hash e Btree

Baseado no livro do Cormem

2. Cada no interno x tambem contem n[x] + 1 apontadores c1[x], c2[x],...,cn[x]+1[x] para os filhos. As folhas tem seu apontador nulo

3. As chaves keyi[x] separam os intervalos de chaves guardadas em cada sub-arvore: se ki e uma chave guardada numa sub-arvore com raiz ci[x], entao:

k1 ≤ key

1[x] ≤ k

2 ≤ key

2[x] ≤...≤ key

n[x] ≤ k

n+1

4.Todas as folhas da árvore estão no mesmo nível.

Btree: Definições (2)

Page 51: Hash e Btree

5. Existe um número máximo e mínimo de filhos em um nó.

Este número pode ser descrito em termos de um inteiro fixo t

maior ou igual a 2 chamado grau mínimo.● Todo o nó diferente da raiz deve possuir pelo menos t-1 chaves. Todo

o nó interno diferente da raiz deve possuir pelo menos t filhos. Se a

árvore não é vazia, então a raiz possui pelo menos uma chave.

● Todo o nó pode conter no máximo 2t - 1 chaves. Logo um nó interno

pode ter no máximo 2t filhos. Dizemos que um nó é cheio se ele

contém 2t - 1 chaves.

Btree: Definições (3)

Page 52: Hash e Btree

De acordo com a definição a árvore B mais simples ocorre quando t=2. Neste caso todo o nó diferente da raiz possui 2, 3 ou 4 filhos. Esta árvore é também conhecida por árvore 2-3-4.

Btree

Page 53: Hash e Btree

Grau mínimo e Ordem

Cormen não fala em Ordem, apenas em grau mínimo t.

Diferentes definições para ordem:

● Bayer & McCreight 1972, número mínimo de chaves● Knuth 1997, número maximo de filhos

Page 54: Hash e Btree

Btree: Codificação

Considerando que os elementos dentro de um nó x da B-tree esteja organizado de forma linear, e que:

n[x] = quantidade de chaves no nó xkey

i[x] = valor da chave do nó x na posição i

leaf[x] = retorna verdadeiro caso o nó seja folha

Operações de acessoDisk-Read = operação de leitura do nó em discoDisk-Write = operação de leitura do nó em disco

Page 55: Hash e Btree

Btree: construtor

Page 56: Hash e Btree

Btree: Busca

A busca em uma árvore B é uma função parecida com a de busca em uma árvore de busca binária, exceto o fato de que se deve decidir entre vários caminhos.

Como as chaves estão ordenadas, pode-se realizar uma busca binária nos elementos de cada nó. ● Se a chave não for encontrada no nó em questão, continua-

se a busca nos filhos deste nó, realizando-se novamente a busca binária.

● Caso o nó não esteja contido na árvore a busca terminará ao encontrar um ponteiro igual a NULL.

Page 57: Hash e Btree

Busca

Page 58: Hash e Btree

Procedimento para pesquisa do número 13

30

3 4 8 9 11 13 17

10 20

25 28

40 50

33 36 42 45 48

52 55

Busca

Page 59: Hash e Btree

Procedimento para pesquisa do número 55

30

3 4 8 9 11 13 17

10 20

25 28

40 50

33 36 42 45 48 52 55

Busca

Page 60: Hash e Btree

Inserção

Localizar o nó folha X onde o novo elemento deve ser inserido.●Se o no X não estiver cheio, basta inserir. ●Se o nó X estiver cheio, realizar uma subdivisão de nós

●passar o elemento mediano de X para seu pai ●subdividir X em dois novos nós com t - 1 elementos ●inserir a nova chave

Se o pai de X também estiver cheio, repete-se recursivamente a subdivisão acima para o pai de X

No pior caso terá que aumentar a altura da árvore B para poder inserir o novo elemento

Page 61: Hash e Btree

Divisão do nodo - Split

Page 62: Hash e Btree

Divisão do nodo - Split

Page 63: Hash e Btree

T = 2

Divisão do nodo - Split

Page 64: Hash e Btree

Inserção

È o caso onde a árvore cresce

Insere na nova raiz

Page 65: Hash e Btree

Inserção

Page 66: Hash e Btree

Exemplo (1)

Page 67: Hash e Btree

Exemplo (2)

Page 68: Hash e Btree

Atividade

Segundo o algoritmo do Cormen, insira os seguintes elementos:

●Para t=2 e t = 3, insira 4,5,1,12,28,15●Para t=2 e t = 3, insira 12, 45, 67, 8,9, 15, 17 19

Page 69: Hash e Btree

A partir de uma árvore B vazia (t=2):●Insira os seguintes valores (20,30,50,80, 12, 15)●Agora remova o 50, 80

A partir de uma árvore B vazia (t=3)●Insira os valores [40,60,80,90,100,20,105,12]●Remova os valores [90,12,40,100]

Atividade

Page 70: Hash e Btree

Prática

Baixem o seguinte código, e concluem a codificação. Usando com referencia Cormen.