ResumoDeAssuntos1a-prova

Prévia do material em texto

RESUMO PARA A SEGUNDA CHAMADA
20/07/2011
Busca por Interpolação
Objetivo: Buscar x numa lista ordenada.
Ideia: Busca binária adaptativa. Ao invés de pegar sempre o valor do meio, estima-se, com base nos 
valores inicial e final do subvetor que se tem, onde estaria o x.
prox_posicao = i + x - v[i] (f - i)
 ----------
 v[f] - v[i]
 
Exemplo:
x = 4
v = [1, 2, 3, 4, 90, 100]
posprox = 1 + 4 - (1/99)*(5) = [4,95] = 5
v[5] == 4? Não! 
Como 4 < 90, olhar subvetor da esquerda.
v' = [1, 2, 3, 4]
posprox = 1 + 4 - (1/3)*(3) = 4
v[4] == 4? Sim!
Busca Auto-Ajustável
Mover para a frente:
Quando uma chave é localizada, ela é imediatamente movida para a 1a posição, e todo o resto é 
movido uma posição à frente, para que seja possível mover a chave.
Deve ser utilizado quando há memoria ilimitavel e a localidade da chave é importante. 
Exemplo: Se tenho um arquivo com as chaves "a b c d e" e utilizo o algoritmo "mover para a frente" 
para acessar as chaves na ordem "c a b e", teremos:
 
a b c d e (lê "c")
c a b d e (lê "a")
a c b d e (lê "b")
b a c d e (lê "e")
e b a c d
1
Recomendação: O algoritmo é apropriado quando o espaço não é limitado e quando queremos ter 
acesso rápido a uma chave que é utilizada com mais frequência.
Transposição: Esse algoritmo troca a chave procurada com seu antecessor, a nao ser que ele ja 
esteja na primeira posicao. Uma chave deve ser acessada muitas vezes ate ser movida para o inicio 
da lista, fazendo dele mais lento que o algoritmo de mover para a frente, porem mais estavel. Deve 
ser usado quando o espaco é escasso.
Contador de acessos: Conta o numero de acessos de cada chave, organizando o arquivo sempre 
em ordem de frequencia. Como precisa de memoria para armazenar os contadores, so deve ser 
utilizado quando os contadores sao necessarios para alguma outra coisa.
Coalesced Hashing
É um método de resolução de colisões que utiliza ponteiros para conectar os elementos que colidem 
numa mesma posição.
A inserção é feita sempre na última posição disponível da tabela.
 
Variações: Queremos reduzir a aglomeração das chaves, diminuindo o custo das buscas e 
aumentando a eficiência. Elas podem ser de 3 maneiras:
 
- Organização da tabela (se tem ou não área de overflow)
- A maneira de "linkar" as chaves 
- A maneira de escolher endereços desocupados
A versão padrão deste algoritmo é chamada LISCH (Late insertion standard coalesced hashing), e 
um exemplo da inserção pode ser visto abaixo:
 Inserir registros com as seguintes chaves 73, 15, 44, 37, 30, 59, 49 e 99 na menor tabela com fator de 
armazenamento <= 85% usando uma função hash chave mod P e LISCH (Late Insertion Standard 
Coalesced Hashing) como método de resolução de colisão.
 
2
Na tabela da esquerda, temos o hash dos elementos a serem inseridos, e na direita, a inserção. Podemos ver que 
o 73, o 15 e o 44 são inseridos sem problemas. Porém, quando inserimos o 37, colidimos com o 15. Colocamos 
o 37 na última posição livre (no caso o 10) e verificamos o ponteiro da posição 4. Como ele aponta para NULL, 
deve passar a apontar pra posição do novo elemento cujo endereço é 4, ou seja, pra posição 10. Não temos 
problema algum ao inserir o 30, mas o 59 gera uma nova colisão. Procuramos novamente a última posição livre, 
que agora se trata do 9, e inserimos o 59 lá. Desta vez, o ponteiro de 4 aponta para 10, então pulamos para o 
ponteiro da posição 10 e este, por sua vez, aponta pra NULL, o que significa que é “o último da lista”. Sendo 
assim, ele passa a apontar pro novo elemento e recebe o 9. O 49 é inserido na posisão 5 sem problemas e, o 99 
colide com o 44, na posição 0. Desta vez, a última posição disponível é o 6. Então ele é inserido lá e o link do 
44 passa a apontar para o novo elemento em 6.
- Esse algoritmo é chamado “Late Insertion” porque os elementos que colidem formam uma lista, e os novos 
elementos são sempre inseridos no final desta lista. Na posição 4 do exemplo anterior, por exemplo, temos 15 -> 
37 -> 59
- O nome coalesced (que significa aglutinados/juntos) também se diz respeito à essa técnica, já que os elementos 
que colidem são linkados uns aos outros. 
EISCH:
O Coalesced Hashing possui variações, como mencionado acima. Uma delas é o EISCH (Early Insertion 
Coalesced Hashing). Este, atua da mesma forma que a tradicional, porém sua diferença é na hora de utilizar 
os ponteiros para elementos que colidem na mesma posição. Ao invés do elemento colidido ser linkado como 
último da lista, neste método ele passa a ser o segundo da lista, ou seja, o ponteiro da chave que está em seu 
local de origem recebe imediatamente a posição do elemento mais recente. Veja abaixo o exemplo acima 
utilizando o EISCH:
73, 15, 44, 37, 30, 59, 49 e 99 
Repare que a diferença entre os 2 só é notável quando há mais de 1 colisão na mesma posição. Caso contrário, 
ambas tabelas serão idênticas. Normalmente o EISCH `tem um custo 4% menor em relação ao LISCH. 
Progressive Overflow: 
Quando há colisão na tabela, tenta inserir na posição seguinte, até encontrar uma posição vazia ou a posição de 
origem pela 2a vez (tabela cheia).
3
Não é um método prático para lidar com colisões devido aos agrupamentos secundários (2 ou mais chaves 
associadas ao mesmo endereço), e ao alto custo de busca referente à esses agrupamentos.
Inserindo as mesmas chaves dos exemplos anteriores, temos:
Computed Chaining
Neste método, Ao invés de links, utilizamos pseudolinks, que indicam a posição da próxima chave a ser buscada 
quando temos uma colisão. Ao inserir uma chave cuja posição esteja ocupada, devemos seguir os passos:
- Verificar se a chave que está na posição que queremos inserir está em sua posição de origem. Se não estiver, 
Devemos remové-la (assim como todas as posições linkadas à ela), inserir a chave que estamos tentando 
inserir, e re-inserir a(s) chave(s) removida(s) em seguida. Caso a chave esteja em sua posição de origem e seu 
pseudolink está vazio, calculamos o incremento da chave (atenção, não é o incremento da chave a ser inserida, 
e sim da que já ocupa a posição!) e usamos esse incremento para buscar a próxima posição vazia, onde vamos 
inserir a chave. O pseudolink vai receber o número de vezes q precisamos usar o incremento até encontrar uma 
posição vazia. Lembrando que, se o pseudolink da posição desejada não estiver vazio, devemos, utilizando os 
incrementos das chaves em questão, seguir até a posição em que o pseudolink seja null. 
Exemplo: Inserindo as mesmas chaves dos exemplos anteriores em Computed Chaining (h(x) = x % 11 e I(x) = 
x/11) 
Como nos anteriores, inserimos o 73, o 15 e o 44 sem problemas. Ao inserir o 37, há uma colisão com o 15 
na posição 4. O incremento de 15 nos dá 1, logo, “pulamos 1 casa” pra baixo e verificamos se a posição está 
vaga. Como está, inserimos o 37 na posição 5. O 30 vai diretamente para a posição 8. Quando inserimos o 59, 
4
mais uma colisão acontece na posição 4. O link de 4 aponta para o 37, na posição 5, então devemos seguir os 
pseudolinks até achar uma chave que não aponte pra mais ninguém. Esse é o caso do 37 na posição 5, então 
calculamos seu incremento (3) e buscamos a próxima posição vazia para inserir o 59. Essa posição é a posição 
8, mas já está ocupada. O mesmo acontece para a posição 0. Encontramos finalmente uma posição vaga na 
posição 3, então colocamos o 59 lá e setamos o pseudolink do 37 como 3 (que foi o número de vezes q usamos 
o incremento). Agora tentamos inserir o 49 na posição 5, mas ela já está ocupada pelo 37. Verificamos também 
que a posição 5 não é a posição de origem do 37, então ele é removido, assim como o 59 que está linkado à ele. 
Inserimos o 49 em sua posição de origem e re-inserimos o 37 e 59, respectivamente. O 37 cai na posição6, e o 
pseudolink da posição 4 é atualizado para 2. Já o 59, vai para a posição 9 e o pseudolink do 6 vai para 1. O 99 é 
inserido na posição 1, após 3 tentativas de inserí-lo com o incremento de 44. Assim finalizamos a tabela como 
está acima. 
Algoritmo de Boyer e Moore
Como Funciona: O algoritmo de Boyer e Moore, diferente dos demais algoritmos de busca por 
subcadeias em cadeias, compara as palavras buscadas de trás para frente. Vamos supor que 
queremos encontrar na cadeia S, a subcadeia T: "ANPANMAN". Primeiramente o algoritmo vai 
verificar a 8a posição (última letra de T) para verificar se ela contém um “N”. Caso encontre, ele 
move para a 7a posição e procura por um “A”, e assim sucessivamente, até encontrar o primeiro “A” 
da subcadeia. 
O motivo do algoritmo começar a busca pelo fim da subcadeia fica claro a partir do momento que 
temos uma falha na comparação: Supondo que a 8a posição mencionada acima fosse um “X”, 
ao invés de “N”. Sabemos que o “X” não ocorre na subcadeia buscada, então isso significa que a 
palavra não pode estar entre as 7 primeiras posições, e nem as 7 posteriores, pois em ambos os 
casos ocorreria um “X” na subcadeia. Então podemos pular para a posição 16 da cadeia e recomeçar 
a busca pela subcadeia. Vale lembrar que, quanto maior a subcadeia, mais rápido a encontraremos. 
O algoritmo pré-computa 2 tabelas para processar a informação obtida em cada falha de 
comparação. Uma tabela computa quantas posições pular para recomeçar a busca baseando-se na 
letra que não satisfez a comparação, e a outra tabela faz uma computação similar, se baseando em 
quantas letras satisfizeram a comparação antes de encontrar um erro. (as 2 tabelas retornam um 
valor de quantas posições devem ser puladas para reiniciar a busca. Utiliza-se a que retornar o maior 
valor)
O algoritmo nos permite encontrar subcadeias em tempo O(1) devido às tecnicas utilizadas para 
“pular posições”. As tabelas do exemplo citado acima estão no site:
http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
Quociente Linear
Neste método, temos 2 funções: Uma função hash e uma função para o incremento, utilizada em casos de 
colisões.
5
O processo de inserção é simples. Utilizamos a função hash para descobrir a posição a ser inserida. Caso a 
posição esteja vaga, a chave é inserida. Senão, somamos o incremento da chave à posição que queremos inserir, 
até encontrar uma posição vaga. 
Método de Brent
O método de Brent é o primeiro método dinâmico dentre os descritos até então. Nosso objetivo com este 
método é diminuir a média da busca de todos os itens da tabela. Consideramos 2 variáveis, i (número de buscas 
necessárias para encontrar o item a ser movido no seu endereço de origem) e j (número de buscas adicionais 
para encontrar o item a ser movido). A idéia é minimizar a soma (i + j). No caso de i = j, escolhemos minimizar 
o i. Logo, tendo como s o número de buscas necessárias para uma chave sem nenhum movimento ter sido feito, 
tentamos todas as combinações em que (i + j) < s, sempre minimizando (i + j). Quando não há redução do 
número de buscas, nenhum movimento é feito. 
As chaves 73, 15 e 44 são inseridas normalmente em seus endereços de origem. Ao inserir o 37, temos uma 
colisão. O número de buscas necessárias se inserirmos o 37 usando seu incremento é 3 (e esse é o valor de s). 
Então tentamos minimizar isso com (i + j) < 3. com i=1, j=1, tentamos mover o que está na posição de origem 
do 37 para a próxima posição (no tentamos mover o 15 para a posição 5). Como é possível, movemos o 15 e 
inserimos o 37 na posição de origem. Inserimos o 30 na posição 8. Com o 59, obtemos outra colisão. Como o s 
6
de 59 é 2, não temos possibilidade de diminuir o numero de buscas, e ele é armazenado na posição secundária 
9. Ao inserir o 49, temos outra colisão na posição 5. O s de 49 é 3, então tentamos minimizar. Para i=1, j=1, 
tentamos mover o 15 para a sua próxima posição para armazenar o 49 na posição de origem. Isso é possível, 
então o fazemos.15 vai para a posição 6 e o 49 é armazenado na posição 5. Por último, temos o 99 a ser inserido 
na posição 0, mas há colisão. O s para 99 é 5, então tentamos minimizar. Para i=1, j=1, tentamos mover o 
44 para a sua posição secundária (4), mas não é possível. Para i=1, j=2, tentamos mover o 44 duas posições, 
para inserí-lo na posição 8, mas também não é possível. Para i=2, j=1, tentamos mover a chave que ocupa a 
posição secundária do 99, que é o 59, para a sua próxima posição, que é o 3. Como é possível, movemos o 59 e 
armazenamos o 99 em 9 e finalizamos a tabela. 
0 44
1
2
3 59
4 37
5 49
6 15
7 73
8 30
9 99
10
Recuperação de Chaves Secundárias: 
Multilistas:
O método de organização de arquivos por multilistas adiciona um link para cada campo escolhido 
como chave secundária. Cada link aponta para o próximo registro com mesmo valor no campo 
associado à ele, e assim temos ligados todos os registros com certa característica em comum (Por 
exemplo, todos os programadores).
- Melhora a performance da busca por chaves secundárias
7
- Tem como desvantagem o fato de que, por utilizar muitos links, necessita mais memória para 
armazenar, e precisa ser atualizado sempre que um registro é movido.
- Não é apropriado para métodos de resoluções de colisões cujos registros são movidos.
- O usuário deve decidir quais chaves secundárias terão prioridade para criar a chave primária
INSERÇÃO E REMOÇÃO: http://www2.dcce.ufs.br/images/b/bc/10Multilista.pdf
Arquivos Invertidos:
São arquivos adicionais que servem como indexes dentro do arquivo primário. O arquivo primário 
pode ter acesso direto, e pré-processamos as informações para criar os indexes. Os arquivos 
invertidos podem existir para cada campo/atributo em que gostaríamos de resgatar registros com 
valores específicos de chaves secundárias.
- Em um arquivo completamente invertido, temos que todas as chaves secundárias possuem arquivo 
invertido.
- Se invertemos muitos, desperdiçamos memória, e se invertemos muito poucos, podemos perder 
tempo no processamento, diminuindo a performance.
- Diferente das multilistas, a área de dados não é alterada. O encadeamento é feito em uma estrutura 
separada.
- Quando os endereços são mantidos como índices, os dados são acessados diretamente, mas nem 
sempre é possível. 
- Os ponteiros podem ser de 2 formas: (1) Podem apontar para o endereço do registro, ou (2) para 
o registro em si. No (2), deve-se utilizar uma função hash no registro para descobrir sua posição/
endereço atual. Apesar de não ser direto como o (1), a vantagem de utilizar o ponteiro para o registro 
é que, se movemos um registro (utilizando algum método dinamico), não precisamos atualizar nada, 
ao contrário da primeira forma, cujos ponteiros devem ser todos atualizados. 
árvores de assinaturas e páginas com assinaturas
(Um breve resumo sobre recuperação de chaves secundárias: http://www2.dcce.ufs.br/images/f/fc/
09RecChaveSec.pdf)
Árvore com assinatura
Aqui tem um pdf bem legal explicando. É meio grande, mas acho que vale a pena: http://
www2.dcce.ufs.br/images/e/e3/12Assinaturas.pdf
 
Diferentes dos arquivos multilistas e dos invertidos, onde tem-se índices para cada atributo 
secundário, nas árvores de assinaturas, todas as informações referentes a chaves secundárias são 
mantidas num único índice – em código binário.
(A explicação abaixo foi feita por mim (Rennan) de acordo com oq entendi da matéria. Se estiver 
errado, me corrijam...)
Supondo que temos um banco de dados com informações referentes à “alunos de Org 2 do Mitre”. 
Esses alunos podem ser classificados como “Sexo”, “condição”, e “que fizeram o trabalho”.
Para setar os bits, temos: 1- masculino | 2- feminino
 3- Bem | 4- Mais ou menos | 5- Ferrado | 6- Muito ferrado
87- Fez o trabalho | 8- Não fez o trabalho
Sexo – 2 posições Condição – 4 posições Fizeram trabalho – 2 
posições
Logo, as posições de 1 até 2, decidem o sexo, de 3 até 6 decidem a condição do aluno e os 2 ultimos 
se eles fizeram o trab.
Supondo que temos o banco de dados:
Nome Sexo Condição Trabalho
Rennan Masculino Muito ferrado Fez o trabalho
Patrícia Feminino Muito ferrado Fez o trabalho
Marcos Masculino Muito ferrado Fez o trabalho
Vitor Masculino Mais ou Menos Fez o trabalho
Priscila feminino Bem Fez o trabalho
Pedro Masculino Mais ou Menos Fez o trabalho
 
As assinaturas:
Nome Sexo Condição Trabalho
Rennan 1 0 0001 10
Patrícia 0 1 0001 10
Marcos 1 0 0001 10
Vitor 1 0 0100 10
Priscilla 0 1 1000 10
Pedro 1 0 0100 10
 
Ou seja, minha assinatura (Rennan) de 8 bits é formado por 10 0001 10.
Ótimo, temos nosso banco de dados formado por assinaturas. Agora, vamos supor que quero 
buscar alguém que esteja “Bem" na matéria (oq será uma árdua tarefa rs). Para isso, criamos uma 
“assinatura de busca”, que seria formada por 00100000 (pois o bit 3 é quem determina se alguém 
foi bem). Somente os registros que tiverem o bit 3 iguais a 1 serão verificados. E aí entram as 
árvores de assinatura, de fato. Não seria muito mais simples se eu pudesse “filtrar” esses resultados 
sobrepondo assinaturas e formando novos blocos representados por essas “super assinaturas”? 
Dessa forma teríamos:
 10 0001 10
9
 11 0001 10 01 0001 10
 10 0001 10
 
 10 0100 10
11 1100 10 01 1000 10
 10 0100 10
 
1 0 0 0 0 1 1 0
0 1 0 0 0 1 1 0
1 1 0 0 0 1 1 0
Logo, ao efetuar a busca, automaticamente ignoramos os primeiros 3 registros pois como o bit 3 é igual a 
0, sabemos que os códigos contidos naquele bloco não contém nenhum aluno que foi bem. Já no segundo, 
temos q o bit 3 é igual a 1, então fazemos a busca ali. 
Lembrando que a cada sobreposição de códigos, chegamos a um diferente nivel na “arvore”. Sobrepondo as 2 
assinaturas do nivel 2, chegamos ao nivel 3 com uma única assinatura, que seria a raiz da nossa arvore. 
A árvore de assinatura funciona como um filtro, que reduz o número de registros a serem buscados. 
Na raiz também temos o endereco para os registros.
Página com Assinatura
Registros com o mesmo valor de um certo atributo são armazenados na mesma página. 
Como resultado, em vez de ter que procurar o arquivo inteiro, apenas partes do arquivo com 
registros que contém características parecidas com o desejado precisam ser examinadas.
O método associa uma assinatura para cada página, o que captura a essência de todos os 
registros daquela página. Essa assinatura é formada fazendo um OU lógico das assinaturas dos 
registros da página.
● Para busca, apenas aquelas páginas que podem conter o dado procurado precisam ser 
analisadas;
● Não apenas a informação de um registro é condensada para formar uma assinatura, mas 
também é condensada para formar a assinatura da página.
10
11
12
13
Passo à passo de como montar uma página de assinatura: (Por Rennan)
Usando de base o exemplo acima do caderno, temos 3 chaves secundárias que formam uma 
assinatura de 8 bits. Temos também 3 funções hash: h1, h2 e h3 que definirão a página de cada 
registro, e 3 funções h’1, h’2 e h’3, que formarão a assinatura de busca. Então:
- Por se tratar de 8 bits, temos 8 páginas, que vão de 000 até 111.
- Utilizamos a função hash em cada chave secundária que queremos procurar, que vão retornar 1 ou 
0 cada uma.
- Fazendo isso, teremos um endereço (do tipo 000, 001, 110, etc), que representa a página onde se 
encontra o registro.
- Se eu quiser buscar somente 2 chaves, dentre as 3, o bit da chave que não estou buscando pode 
ser 0 ou 1, e no caso, teríamos que buscar o que eu quero em pelo menos 2 paginas (utilizando o bit 
como 0 e o bit como 1).
- Podemos otimizar esta busca utilizando as funções h’. Utilizamos as funções para formar uma 
assinatura de busca. No exemplo do caderno que está acima, um aluno que estuda biologia e mora 
em niterói tem assinatura 01 00 1000.
- PS: As assinaturas das páginas são geradas por sobreposição das assinaturas dos registros que 
elas contém. 
Vantagens: Uma vantagem entre utilizar as páginas de assinatura ao invés de árvores é que, 
quando um registro é inserido, deletado ou atualizado numa página, somente a assinatura para 
aquela página precisa ser modificado. 
Desvantagens: 
Filtro de Bloom
O filtro de Bloom é uma estrutura de dados que tem o objetivo de compactar a representação de 
um conjunto de dados, ou seja, ele utiliza um vetor de bits para representar um conjunto de dados, 
usando funções hash para isso.
Vantagem: Economia de espaço. (errado!!!! O Mitre disse que não há economia de espaço. Ele 
apenas usa pouco espaço mas n reduz o espaço utilizado)
Desvantagem: “Falsos Positivos”. Ele considera que o elemento já foi inserido, mas pode não ter 
sido. Quanto maior o número de inserções, maior a chance de ocorrência de falsos positivos.
Esse vídeo mostra como funciona a inserção e a busca de forma resumida (mostra também o caso 
de “falso positivo”):
http://www.youtube.com/watch?v=TBzKpAu0NYU&playnext=1&list=PL46EAF1E9FCB752D1
Exemplo: Inserir os elementos (k): 27, 18, 29 e 28
Função: f(k) = k mod 5
Duas funções hash para um filtro de Bloom de 16 bits: 
h1(k) = k mod 16
h2(k) = k mod 14 + 2
14
Após a inserção temos:
 k
0 28
1
2 27
3 18
4 29
(O elemento “28” seria inserido na posição 3, mas ja estava ocupada, então ele faz progressive 
overflow, de cima pra baixo, procurando a primeira posição livre, no caso, o 0)
Usando h1 e h2 temos as posições que serão “setadas” como “1” no filtro:
1 1 1 1 1 1 1
 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Podemos ver que h1(18) e h2(28) são iguais a 2, logo, temos dois acessos à essa posição no filtro 
de Bloom, o que pode gerar o “falso positivo”.
Considerando 
● n o número de funções, 
● m o tamanho do filtro de Bloom,
● k a quantidade de registros armazenados e 
● t o tamanho do universo;
Temos algumas probabilidades interessantes à prova de 2ª chamada:
Probabilidade do bit i ser 1 por causa da função hj = 1/m
Probabilidade de ser 0 = 1 - 1/m
Probabilidade do bit i ser 0 após as n funções = (1 - 1/m)n
Probabilidade do bit i ser 0 após as n funções
para os k registros = (1 - 1/m)nk
Probabilidade do bit i ser 1 após as n funções
para os k registros = 1 - (1 - 1/m)nk
Probabilidade de uma consulta responder 
“não sei” = (1 - (1 - 1/m)nk)n 
Probabilidade de falso positivo = (1 - k/t) * (1 - (1 - 1/m)nk)n = p
15
Dispersão por Classificação
PS: Essa explicação é de um email enviado ao professor por uma aluna de 2010/1.
 Bom, a classification hashing serve, nada mais nada menos, para identificar
 se um dado registro existe com uma certa combinação de campos. O que eu
 quero dizer com isso?
 Suponha que você tem numa empresa vários funcionários e na "ficha de
 cadastro" temos as seguintes informações:
 - Nome (chame primária - não vai haver homônimos)
 - Gerente (pode ser Ana, Gabriel ou Patrícia)
 - Departamento (pode ser RH, Contabilidade, Financeiro, Marketing ou
 Administrativo)
 - Setor :: (pode ser A, B, C, D, E ou F)
 Daí, como funcionários, podemos ter:
 Lucas:: Gerente = Ana, Dpto = RH, Setor = F
 Vera:: Gerente = Ana, Dpto = Financeiro, Setor = E
 Pedro:: Gerente = Gabirel, Dpto = Administrativo, Setor = F
 José:: Gerente = Patrícia, Dpto = Administrativo, Setor= B
 Bom, quero saber, se existir, qual funcionário cujo gerente é Ana e está no
 Departamento RH. No caso seria só o Lucas mesmo.
 A classification hashing então vai se resumir a classificar esses
 funcionários para depois poder procurá-los de maneira mais rápida, reduzindo
 assim o número de registros que serão "olhados". Esse método parte do
 princípio de que é melhor se procurar num conjunto menor de dados do que no
 conjunto todo.
 Assim, temos que nos preocupar primeiro em classificar os registros. Depois
 serão feitas as buscas.
 Como classificar os registros?
 Primeiramente, deve ser especificado uma constante m que define o "número
 de bits da classificação". No caso, o senhor escolheu 4. Nesse método, temos
 também uma função hash (que para o trabalho deve ser criada por nós, acho)
 que deve ser aplicada a cada um dos campos do registro que comporão a
 classificação do registro.
 No meu caso, quero usar os campos gerente, departamento e setor para
 classificar um registro e meu m também vai ser 4.
 Assim, aplicamos a função hash() no campo gerente, no campo departamento e
 no campo setor para cada um dos funcionários.
 Supondo que essa função retornou:
 LUCAS:: Gerente: 1, Departamento: 3, Setor: 1
 VERA:: Gerente: 1, Departamento: 0, Setor: 0
 PEDRO:: Gerente: 2, Departamento: 1, Setor: 1
 JOSÉ:: Gerente: 3, Departamento: 1, Setor: 2
16
 --> Eu esqueci de dizer, mas essa função vai retornar valores entre 0 e
 m-1. Nesse exemplo, então, ela vai retornar valores entre 0 e 3.
 Cada valor retornado pela função hash() indica qual bit da classificação do
 registro deve ser setado para 1 (os demais serão 0)
 Assim, temos que os registros de LUCAS, VERA, PEDRO e JOSÉ serão
 classificados em:
 LUCAS: 0101 (bit 1 e 3)
 VERA: 1100 (bit 0 e 1)
 PEDRO: 0110 (bit 1 e 2)
 JOSÉ: 0111 (bits 1, 2 e 3)
 Até agora tudo bem.. acho que já sei como classificar os registros. Agora
 me interessa saber mais duas coisas:
 1) Onde guardar isso, quero dizer, as classificações e os registros?
 2) Como fazer a busca?
 A má notícia é que eu não sei como deve-se guardar esses
 registros/classificações. Eu tive uma ideia, mas não sei se é dessa maneira
 que devemos implementar, uma vez que não li nada a respeito no livro (se
 tinha, eu passei direto :p)
 Bom, pensei em criar um vetor de 2^m posições. No caso, esse meu vetor
 teria 16 posições. Em cada uma dessas posições eu teria outro vetor (pensei
 inclusive numa lista encadeada.. Seria como um vetor de listas encadeadas..)
 que guardaria os registros.
 Eu não entendi a entrada da primeira linha para o exercício 2. Ele diz que
 vai ser x/4. Por quê? O que esse x representa. É o tamanho da tabela?
 De qualquer forma, anexei uma imagem de como seria a minha estrutura.
 Ok, função hash() implementada, registros armazenados. Como fazer a busca?
 Quero procurar, por exemplo, quais os nomes dos funcionários que têm como
 gerente Ana e trabalham no Departamento RH? (Seria o Lucas)
 Daí, aplicamos a função hash (a mesma usada para classificar lá os
 registros) em Ana e em RH. Assim:
 hash(Ana) = 1
 hash(RH) = 3
 O registro vai ser classificado como x*1*x*1*. Esse 'x' indica que pode
 ser 0 ou 1 o bit.
 Logo, temos que procurar os registros nas posições:
 0*1*0*1*
 0*1*1*1*
 1*1*0*1*
 1*1*1*1*
 *
 *
 Logo, vou olhar só as posições 5 (0101), 7 (0111), 13 (1101) e 15 (1111) do
 meu vetor.
 Assim que for buscar na posição 5 um registro, vejo o Lucas. Olho para os
 campos Gerente e Departamento e vejo que possuem os valores que estava
 procurando.
17
 Se tiver mais registros nessa posição do vetor, continuo vendo seus campos
 e verificando se 'gerente' e 'departamento' conferem com os que estou
 buscando (no caso, Ana e RH, respectivamente).
 Esse processo também vai se repetir para as posições 7, 13 e 15 do vetor.
 Feito isso, terei retornado os registros que possuem Ana com gerente e RH
 como departamento. 
Vantagens: Dispersão com classificação se mostra útil para recuperação de documentos e chaves 
secundárias nas quais queremos recuperar todos os registros com certa característica. Essa técnica 
nos permite estreitar/melhorar a busca consideravelmente com um esforço relativamente baixo. 
Check Hashing (ele não colocou na lista para a P2) (mas acabou caindo na PF)
O check hashing é da forma "triple hashing", ou seja, vamos ter 3 funções de hashing:
h1, h2 e h3, 
Sendo que h1 vai nos dar a posição de origem, ou "home adress" que é onde devemos tentar inserir 
inicialmente a chave k.
Já h2 é a função que vai nos dar o incremento para o caso de colisões (da mesma forma que nos capitulos 
anteriores) e finalmente temos a função h3 que nos dá o valor da "check hash".
Exemplo: Inserir os números 23, 51, 48, 11 e 73
h1(k) = k mod 7
h2(k) = (k/7) mod 7
h3(k) = (k mod 5) +1
Posição Check Hash Registro (opicional)
0
1
2 4 (23)
3 2 (51)
4 2 (11)
5
6 4 (48)
Enfim, tentamos inserir o 73. O h1(73) = 3, h2(73) = 3 e h3(73) = 4. Logo, tentamos inserir na posição 3, que já 
está ocupada pelo check de 51, no caso o 2. Comparamos os checks (2 com 4). Como eles são diferentes, uso 
o incremento (h2(73) = 3) e vou até a posição 6, onde se encontra o 4 (check de 48). Comparando, vemos que 
são iguais. O que fazemos? Nada. O 73 simplesmente não é inserido, pois consideramos que sua codificação 
(4) já está lá, e essa é justamente uma falha do Check Hashing, onde temos alguns erros na busca (como no 
18
false positive do filtro de bloom). Porém, o livro ressalta que essa taxa de erro é bem baixa.
Árvore B
http://www.lcad.icmc.usp.br/~nonato/ED/B_arvore/btree.htm
clahttp://www.cos.ufrj.br/~azevedo/OrgDadoII_ArvoreB1.pdf
Simulador de Árvores B em Java:
http://slady.net/java/bt/view.php
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.
Exclusão
● Primeiro pesquise a chave para ter a certeza de que esta existe na árvore.
● Se existir, verifique se está em folha, e faça a exclusão.
● Se existir e não estiver em folha, substitua esta chave pela menor chave do filho a direita.
● Se o número de chave no nó, for maior do que (Ordem/2 - 1), então termine a rotina.
● Senão redistribua as chaves entre os nós vizinhos.
Busca
● Indique a chave que será procurada.
● Pesquise desde a raiz até encontrá-la, e então retorne o nó e a posição desta.
● Se a chave não for encontrada, continue o laço até encontrar um nil das folhas.
Árvore B
● Inserção;
● Remoção;
● Busca;
● Alteração (Busca, Remove, Insere)
● Permite o acesso sequencial eficiente através de um percurso simétrico (esquerdo, pai, 
direito) em árvores. No processamento de um nó, o prcessamento de um registro Rk 
acontece depois do processamento de Pk-1 e antes do de Pk.
Ponto Negativo da árvore B: Uso de memória.
19
No pior caso, pode utilizar apenas 50% da memória reservada. A ordem de inserção influencia no 
fator de utilização.
Exemplo 1:
a) Insira os números, a seguir, numa árvore B com d=2 e calcule o fdu (Fator de Utilização).
b) Reordene a fim de encontrar um fdu menor.
c) Reordene a fim de encontrar um fdu maior.
fdu = 10/16
b) fdu menor (10/20; 10/24; 10/28): Não é possível para este caso porque, para o caso de 20 
espaços reservados teríamos 2 preenchidosem cada folha (4) + 3 na raiz, o que daria 8+3 = 11 
preenchidos.
c) fdu maior (10/12): Não é possível para este caso porque, para o caso de 12 espaços reservados 
teríamos 4 preenchidos em cada folha (2) + 1 na raiz, o que daria 8+1 = 9 preenchidos. 
Exemplo 2:
a) Insira os números, a seguir, numa árvore B com d=2 e calcule o fdu (Fator de Utilização).
20
b) Reordene a fim de encontrar um fdu menor.
c) Reordene a fim de encontrar um fdu maior.
fdu = 11/16
b) fdu menor (11/20; 11/24; 11/28): É possível para este caso porque, seriam 20 espaços reservados 
e teríamos 2 preenchidos em cada folha (4) + 3 na raiz, o que daria 8+3 = 11 preenchidos. Isso 
acontece quando inserimos em ordem crescente.
c) fdu maior (11/12): Não é possível para este caso porque, para o caso de 12 espaços reservados 
teríamos 4 preenchidos em cada folha (2) + 1 na raiz, o que daria 8+1 = 9 preenchidos.
B#
http://www.cos.ufrj.br/~azevedo/OrgDadoII_ArvoreB2.pdf 
21
Em árvores B, após as inserções, temos normalmente uma média de 50% do uso do espaço da 
árvore em si, devido às divisões constantes que fazemos ao sofrer overflow em um nó. As divisões, 
além de aumentar o espaço não utilizado, também aumentam a altura da árvore, o que significa 
diminuição na eficiencia da busca. Para amenizar este problema, foi criada a variação B#, cuja 
prioridade é diminuir essas divisões, aumentando a utilização do espaço e tornando a busca mais 
rápida. 
O método de inserção continua sendo o mesmo da árvore B, porém, ao encontrar um overflow em 
um nó, devemos:
1. verificar se há espaço vazio nos “irmãos” 
2. Se houver, vamos utilizar a fórmula: [(r+1) / n] para calcular o registro que substituirá o registro 
comparador acima. Sendo que r é o número de registros a serem redistribuidos e n é o numero de 
nós que temos para distribuir (no caso os irmaos do nó cheio). A formula vai retornar a posição do 
elemento que “vai subir”. (PS: o registro “raiz” dos nós também conta no r)
Exemplo:
Supondo que temos a árvore acima e, na 2a imagem, quando tentamos inserir o 75, nos deparamos 
com um overflow no nó esquerdo. Podemos perceber que o nó da direita possui espaço vazio, entao 
podemos reorganizar a árvore. Usamos a fórmula acima e temos [9/2] = 4. Esse resultado nos dá a 
posição do 70, que é o registro que vai subir no lugar do 80. Agora reorganizamos tudo e temos a 
imagem 3. 
22
B+
http://www.cos.ufrj.br/~azevedo/OrgDadoII_ArvoreB3.pdf 
http://pt.wikipedia.org/wiki/%C3%81rvore_B+
Simulador de Árvores B+:
http://www.seanster.com/BplusTree/BplusTree.html
Prova 2 (2010-2)
Questão 1: (2,0) Comparar os três seguintes metodos de recuperação por chave secundaria: 
árvores de assinaturas (signature trees), paginas com assinaturas (page signature), dispersão por 
assinaturas (classification hashing).
A motivação para se usar classification hashing, é que você procura, através dos bits “setados” 
se determinado registro existe nessa árvore, ou seja, você economiza tempo, já que não vai procurar 
o conteúdo, ou seja, o próprio registro. Mais ou menos assim:
“Vamos ver se o cara tá aqui. Não bateu a assinatura.... Nesse também não...opa! Nesse aqui 
bateu a assinatura, agora vou ver se é o cara mesmo que está nesse registro.”
Não batendo a assinatura, ele nem perde o tempo dele para saber se é aquele registro que está 
sendo procurado.
(Lembrando que to falando com o que eu sei, então posso estar errado. Por favor, corrijam)
Uma vantagem de usar o método de páginas ao invés de árvores, é que quando um registro é 
inserido, deletado ou atualizado, apenas a assinatura da página precisa ser modificada.
Alguém lembra o que ele falou pra Priscila, dizendo uma vantagem da arvore sobre as paginas?
Questão 2: (2,0) Inserir os numeros 30; 32; 12; 70; 83; 45; 56; 24; 42; 16 usando
signature hashing. A funcão hashing e f(x) = x mod 17, a função incremento é i(x) = (x mod 10) + 1, 
e a função de assinatura e s1(x) = x mod 20; si(x) = (si1(x)+1)i(x) mod 20, para i>=2.
Questão 3: (2,0) Descreva a técnica de “Filtro de Bloom". Apresente um
exemplo, com justificativa, em que a aplicação dessa técnica seria
util.
Exemplo: Em um supermercado, por exemplo, quando a pessoa vai pagar usando seu cartão de 
crédito, a atendente faz a verificação de seu cartão. Ela busca um grupo de “maus” clientes, ou seja, 
os que devem, usam cartão roubado, enfim, quem não estaria apto a usar o cartão. Nesse exemplo, 
o que acontece é que ela não busca numa base de dados de todos os cartões existentes, o que 
levaria muito tempo, mas o que ela faz (obviamente ela não faz ideia disso =] ) é procurar numa base 
de dados de clientes “maus”, ou seja, os dados foram filtrados para uma outra base, já que o número 
de clientes “maus” é significantemente menor que o número de clientes “corretos”.
23
Questão 4: (2,0) Descreva a tecnica de “check hashing". Apresente exemplo,
com justicativa, em que a aplicaão dessa tecnica seria util. (ESSA NÃO CAI)
Questão 5: (2,0) Descreva os passos da inserção em uma árvore-B+.
1. 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*/ 
2. SE existir espaço disponível ENTÃO 
2.1. Inserir o registro (de forma ordenada). 
3. SENÃO 
3.1. Dividir o nó folha onde ocorreu overflow. 
3.1.1. 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. 
3.1.2. 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. 
3.2. Processar a chave que foi recentemente elevada para a estrutura de índice como 
uma inserção em uma árvore B.
Uma desvantagem da B+ em relação à B é a memória utilizada, e uma vantagem é que é geralmente 
mais “rasa”, o que torna a busca mais rápida. Pq a B+ tem todos as chaves primárias duplicadas
PROVA FINAL
Matéria: Toda
Tópicos essenciais (by Rennan, Patty)
- Algoritmo de Boyer e Moore
- Métodos do quociente linear, Brent e Árvore Binária
- Coalesced Hashing (LISCH, EISCH)
- Computed Chaining
- Multilistas / Arquivos Invertidos
- Dispersão por Assinaturas, Árvores de Assinaturas e Páginas de assinaturas
- Filtro de Bloom
- Árvores B. B# e B+
PROVAS DO PERIODO
24
25
26
Algumas provas do ano passado:
27
1) LISCH tem coalescencia e computed chaining nao.
Os métodos que usam ponteiros (por exemplo, o LISCH), são mais rápidos e usam listas 
encadeadas. Os que não
utilizam deste artifício (por exemplo o computed chaining), utilizam menos espaço, e a função 
incremento.
28
Prova 2 - 2011 / 1
Questão 4) Inserir as seguintes chaves em uma árvore B, de ordem d = 1, inicialmente vazia: 15, 77, 
44, 23, 31, 85,
80, 30, 26, 25, 24. Depois remover as chaves: 26, 77, 24.
Position: Inline - Fixed
29
30
Algumas provas do ano passado:
31
32
33
1) LISCH tem coalescencia e computed chaining nao.
Os métodos que usam ponteiros (por exemplo, o LISCH), são mais rápidos e usam listas encadeadas. Os que não 
utilizam deste artifício (por exemplo o computed chaining), utilizam menos espaço, e a função incremento. 
34
Prova 2 - 2011 / 1
Questão 4) Inserir as seguintes chaves em uma árvore B, de ordem d = 1, inicialmente vazia: 15, 77, 44, 23, 31, 85, 
80, 30, 26, 25, 24. Depois remover as chaves: 26, 77, 24.
35