Hashing, árvores B/B+ e organização de arquivos

Como um banco de dados encontra um registro entre bilhões lendo só três ou quatro blocos do disco? Hoje vamos ver duas respostas: calcular onde o dado está (hashing) e usar árvores largas e baixas, feitas para o disco (árvores B e B+).

k mod mTabelas hasha chave diz onde o dado está ▤ ▤ ▤Arquivosregistros, blocos e índices [ 20 | 40 ]Árvores B e B+poucos níveis, nós do tamanho de um bloco ✓ 6Práticaexercícios com correção automática

Navegação: ← → trocam de etapa · V alterna entre etapas e página única · M sumário · F tela cheia · + − tamanho do texto · dentro do código, Ctrl+Enter executa.

Todo código desta aula pode ser editado e executado aqui mesmo. Altere os exemplos à vontade; o botão ↺ restaura o original. Suas alterações ficam salvas neste navegador; em Progresso você pode baixá-las em um arquivo e continuar em outro computador.

As visualizações mostram os algoritmos passo a passo: altere os dados, use Próximo passo ou Animar. Nos exercícios, o botão ✓ Verificar testa seu código com várias entradas.

Buscar sem procurar

Até aqui, buscar era comparar: O(n) na busca sequencial, O(log n) na binária. Dá para fazer melhor?

Se as chaves fossem números pequenos, por exemplo matrículas de 0 a 999, bastaria um vetor de 1000 posições e usar a própria chave como índice: alunos[427]. Isso é endereçamento direto, O(1).

O problema: chaves reais vêm de universos enormes (CPF, placas, nomes). A ideia do hashing é usar uma função que transforma qualquer chave em um índice de uma tabela pequena:

posição = h(chave), com 0 ≤ h(chave) < m

O dict e o set do Python são tabelas hash. É por isso que x in conjunto foi tão mais rápido que x in lista na aula de complexidade.

Funções hash

Uma boa função hash é:

determinística: a mesma chave sempre dá a mesma posição;
rápida: O(1) para números, O(tamanho) para textos;
espalhadora: distribui as chaves por igual entre as m posições.

Método	Fórmula
divisão (inteiros)	`h(k) = k mod m`, com `m` primo
polinomial (textos)	`h = (h × 31 + código do caractere) mod m`
djb2 (textos)	`h = h × 33 + c`, começando em 5381

Por que m primo? Com m = 10, k mod 10 só olha o último dígito: chaves terminadas em 0 colidem todas. Um primo usa todos os dígitos.

Colisões são inevitáveis

Uma colisão acontece quando duas chaves diferentes caem na mesma posição: h(a) == h(b).

Com mais chaves possíveis do que posições, sempre existem chaves diferentes com a mesma posição (princípio da casa dos pombos). E acontecem muito antes de a tabela encher: é o paradoxo do aniversário. Com só 23 pessoas, a chance de duas fazerem aniversário no mesmo dia já passa de 50%.

Então toda tabela hash precisa de uma estratégia de tratamento de colisões. Veremos duas famílias:

encadeamento: cada posição guarda uma lista;
endereçamento aberto: procura outra posição livre na própria tabela.

Tratamento por encadeamento

Cada posição da tabela aponta para uma lista com todas as chaves que caíram ali. Inserir é acrescentar na lista; buscar é calcular h(k) e percorrer só aquela lista.

Com n chaves e m posições, as listas têm em média α = n / m elementos: o fator de carga. Buscar custa O(1 + α) em média.

Se mantivermos α limitado (por exemplo, até 1), a busca é O(1) em média.

Pior caso: uma função hash ruim (ou azar) manda todas as chaves para a mesma lista. A tabela vira uma lista encadeada e a busca cai para O(n). Experimente inserir 3, 10, 17, 24 com m = 7.

Uma TabelaHash com encadeamento

Cada posição é uma lista de pares [chave, valor]. As três operações começam do mesmo jeito: calcular h(chave) e olhar só a lista daquela posição.

Operação	Média	Pior caso
`inserir`	O(1)	O(n)
`buscar`	O(1)	O(n)
`remover`	O(1)	O(n)

inserir percorre a lista antes de acrescentar para não duplicar chaves: se a chave já existe, só atualiza o valor, exatamente como d[chave] = valor num dict.

A função _h transforma a chave em texto e usa o hash polinomial, então funciona para números e nomes.

class TabelaHash:
    def __init__(self, m=7):
        self.m = m
        self.listas = [[] for _ in range(m)]   # uma lista por posição
        self.n = 0

def _h(self, chave):
        h = 0
        for c in str(chave):
            h = (h * 31 + ord(c)) % self.m
        return h

def inserir(self, chave, valor):
        lista = self.listas[self._h(chave)]
        for par in lista:
            if par[0] == chave:       # já existe: atualiza
                par[1] = valor
                return
        lista.append([chave, valor])
        self.n += 1

def buscar(self, chave):
        for c, v in self.listas[self._h(chave)]:
            if c == chave:
                return v
        return None

def remover(self, chave):
        lista = self.listas[self._h(chave)]
        for i in range(len(lista)):
            if lista[i][0] == chave:
                lista.pop(i)
                self.n -= 1
                return True
        return False

t = TabelaHash()
for nome, fone in [("Ana", "1111"), ("Bia", "2222"), ("Caio", "3333"), ("Duda", "4444")]:
    t.inserir(nome, fone)
print(t.buscar("Caio"), t.buscar("Zeca"))
t.remover("Bia")
for i, lista in enumerate(t.listas):
    print(i, lista)
print("fator de carga:", round(t.n / t.m, 2))

Endereçamento aberto: sondagem linear

Sem listas: todas as chaves ficam dentro da própria tabela. Se a posição h(k) está ocupada, tenta a próxima, e a próxima, dando a volta no fim: (h(k) + i) mod m para i = 0, 1, 2, …

A busca segue a mesma sequência de posições e para quando encontra a chave ou uma posição vazia (se a chave existisse, estaria ali).

Vantagem: nada de ponteiros, tudo em um vetor (bom para cache e para disco). Limite: no máximo m chaves, α ≤ 1.

Agrupamento primário: chaves que colidem formam blocos contíguos, e qualquer chave que caia em um bloco o faz crescer. Insira 37, 48 e 59 acima e veja o bloco aumentar e as sondagens também.

Teste de mesa: sondagem linear

Tabela com m = 5. Antes de avançar, preveja em que posição cada chave vai parar. Repare na chave 3: ela colide com uma chave que tinha h(k) diferente.

Sondagem quadrática e hash duplo

Para quebrar os agrupamentos, os saltos não podem ser sempre de 1 em 1.

Estratégia	Tentativa i
linear	`(h(k) + i) mod m`
quadrática	`(h(k) + i²) mod m`
hash duplo	`(h(k) + i × h₂(k)) mod m`

No hash duplo, o tamanho do salto depende da própria chave (aqui, h₂(k) = 1 + k mod (m − 1)): chaves que colidem na primeira posição seguem caminhos diferentes.

Compare: mude a estratégia na visualização entre linear, quadrática e hash duplo com as mesmas chaves e insira 37. Quantas sondagens cada uma precisou?

Na quadrática, a sequência pode não visitar todas as posições: com m primo e α ≤ 0,5 há garantia de achar lugar. Teste com m = 8 e várias chaves iguais em h(k).

Remoção: o marcador “apagado”

No endereçamento aberto, a busca para na primeira posição vazia. Se removermos uma chave deixando a posição vazia (None), quebramos o caminho de quem colidiu ali e foi parar mais adiante.

A solução é marcar a posição como apagada (em inglês, tombstone):

a busca trata “apagado” como ocupado e continua;
a inserção pode reaproveitar a posição.

Na visualização da sondagem linear, remova 4 e depois busque 15 e 26, que colidiram na posição 4. O × no lugar do 4 é o marcador que mantém o caminho.

Com muitas remoções, os marcadores se acumulam e as buscas ficam longas; de tempos em tempos a tabela é reconstruída (rehash).

Fator de carga e rehash

O desempenho depende de α = n / m, e não de n sozinho. O programa ao lado mede quantas sondagens a sondagem linear precisa, em média, conforme a tabela enche.

Para manter α baixo, quando ele passa de um limite (0,75 é comum) a tabela é redimensionada:

cria uma tabela com cerca do dobro de posições;
reinsere todas as chaves, pois k mod m muda quando m muda.

O rehash custa O(n), mas, como acontece cada vez mais raramente, cada inserção continua custando O(1) amortizado, o mesmo raciocínio do vetor dinâmico.

`dict` e `set` no Python

O dict e o set são tabelas hash com endereçamento aberto e redimensionamento automático. Inserir, buscar (in) e remover custam O(1) em média.

A posição depende de hash(chave). Se a chave mudasse depois de inserida, seu hash mudaria e ela ficaria “perdida” na posição antiga. Por isso as chaves precisam ser imutáveis (hasháveis): números, strings, tuplas. Listas, dicts e sets não podem ser chaves.

O hash() de strings no Python muda a cada execução do programa (proteção contra ataques). Por isso, nos exemplos desta aula, usamos funções hash próprias: os resultados ficam iguais sempre.

Desafio: rehash automático

Complete a tabela com encadeamento (chaves inteiras, h(k) = k mod m):

em inserir, depois de acrescentar, se n / m passar de 0.75, chame _redimensionar();
em _redimensionar, crie 2 × m listas vazias e reinsira todas as chaves nas novas posições.

Execute e confira: α nunca deve ficar acima de 0,75 depois de uma inserção, e cada chave precisa estar na lista k mod m do novo m.

Mostrar uma solução

Quiz: tabelas hash

Responda mentalmente (ou no caderno) antes de clicar.

Memória × disco

Dados que não cabem na memória (ou que precisam sobreviver ao desligamento) ficam em arquivos, no disco. E o disco é muito mais lento.

Onde	Tempo de um acesso
cache do processador	≈ 1 ns
memória RAM	≈ 100 ns
SSD	≈ 100 µs (1.000 × a RAM)
HDD (disco rígido)	≈ 10 ms (100.000 × a RAM)

O disco não lê um byte por vez: lê e grava blocos (páginas) inteiros, tipicamente de 4 KB a 16 KB. Ler 1 byte ou o bloco todo custa praticamente o mesmo.

Regra de ouro dos dados em disco: o custo de um algoritmo é o número de blocos lidos. Comparações na memória são quase de graça perto disso.

Registros de tamanho fixo e variável

Um arquivo de dados é uma sequência de registros (por exemplo, um aluno: matrícula, nome, curso), cada um com campos.

Tamanho fixo	Tamanho variável
todo registro ocupa `TAM` bytes	cada registro ocupa o que precisa
o i-ésimo começa em `i × TAM`: acesso direto, como um vetor	separadores (`;`, `\n`) ou um prefixo com o tamanho
desperdiça espaço com campos curtos	para achar o i-ésimo, lê desde o início

Em Python, arquivo.seek(i * TAM) seguido de arquivo.read(TAM) lê o i-ésimo registro de um arquivo de verdade. Aqui no navegador, simulamos o arquivo com uma string.

Arquivo sequencial × arquivo ordenado

A classe Disco simula um arquivo dividido em blocos e conta quantos blocos são lidos.

Arquivo sequencial (registros na ordem de chegada): buscar exige ler bloco por bloco: O(b), com b = número de blocos.
Arquivo ordenado pela chave: busca binária sobre os blocos. Lê o bloco do meio; se a chave é menor que a primeira do bloco, vai para a esquerda; se maior que a última, para a direita: O(log b).

O preço do arquivo ordenado: inserir no meio obriga a deslocar registros (reescrever blocos). Arquivos reais deixam espaço livre nos blocos ou usam áreas de overflow.

class Disco:
    """Simula um arquivo dividido em blocos; conta os blocos lidos."""
    def __init__(self, registros, por_bloco):
        self.blocos = [registros[i:i + por_bloco] for i in range(0, len(registros), por_bloco)]
        self.lidos = 0

def ler(self, b):
        self.lidos += 1
        return self.blocos[b]

def busca_sequencial(d, chave):
    for b in range(len(d.blocos)):
        if chave in d.ler(b):
            return b
    return -1

def busca_binaria(d, chave):
    ini, fim = 0, len(d.blocos) - 1
    while ini <= fim:
        meio = (ini + fim) // 2
        bloco = d.ler(meio)
        if chave < bloco[0]:
            fim = meio - 1
        elif chave > bloco[-1]:
            ini = meio + 1
        else:
            return meio if chave in bloco else -1
    return -1

chaves = list(range(0, 200000, 2))      # 100 mil registros ordenados
for alvo in [12, 99998, 150001]:
    d1, d2 = Disco(chaves, 100), Disco(chaves, 100)
    busca_sequencial(d1, alvo)
    busca_binaria(d2, alvo)
    print(f"alvo {alvo:6}: sequencial leu {d1.lidos:4} blocos | binária leu {d2.lidos:2}")

Índices e arquivos hash

Um índice é um arquivo pequeno de pares (chave, endereço) que aponta para o arquivo de dados, como o índice remissivo de um livro.

Índice denso: uma entrada por registro. Funciona mesmo com dados fora de ordem.
Índice esparso: uma entrada por bloco (a primeira chave). Bem menor, mas exige dados ordenados.
Arquivo hash: h(chave) escolhe um bloco (bucket). Ideal para busca exata: cerca de 1 acesso. Inútil para intervalos (“matrículas de 200 a 300”), porque o hash espalha chaves vizinhas.

Se o índice cabe na memória, a busca nele é de graça e só 1 bloco de dados é lido. Se não cabe… precisamos de um índice para o índice. Essa é a ideia da árvore B.

Por que árvores B?

Uma árvore binária de busca balanceada com 1 milhão de chaves tem cerca de 20 níveis. Na memória, ótimo. No disco, cada nó visitado pode ser um bloco lido: 20 × 10 ms = 0,2 s por busca.

A árvore B (Bayer e McCreight, 1972) troca nós com 1 chave e 2 filhos por nós do tamanho de um bloco, com centenas de chaves e filhos. A árvore fica larga e baixa: 3 ou 4 níveis para milhões de chaves.

Dentro de cada nó, a busca é na memória (sequencial ou binária); o que importa é que ela lê um bloco por nível.

Praticamente todo banco de dados relacional (PostgreSQL, MySQL, SQLite, Oracle) e muitos sistemas de arquivos (NTFS, ext4, Btrfs, APFS) usam árvores B ou B+.

Propriedades da árvore B

Uma árvore B de ordem m (no máximo m filhos por nó) obedece a quatro regras:

cada nó tem no máximo m − 1 chaves, em ordem crescente, e até m filhos;
todo nó, exceto a raiz, tem no mínimo ⌈m/2⌉ − 1 chaves (pelo menos meio cheio);
um nó interno com k chaves tem exatamente k + 1 filhos; as chaves separam os intervalos dos filhos;
todas as folhas estão no mesmo nível: a árvore é sempre perfeitamente balanceada em altura.

[ 20 | 40 ]→filho 0: < 20 · filho 1: entre 20 e 40 · filho 2: > 40

A busca generaliza a da árvore binária: em cada nó, encontra entre quais chaves o alvo está e desce pelo ponteiro correspondente.

Use Buscar com 17, 8 e 30 e conte os nós lidos. Mude o máximo de chaves por nó: a árvore é reconstruída com as mesmas chaves.

Inserção: divide e sobe

A árvore B nunca cresce para baixo. A chave nova sempre entra em uma folha; se a folha estourar, ela se divide e a chave do meio sobe para o pai.

Desça da raiz até a folha onde a chave deveria estar.
Insira em ordem na folha.
Se ficou com mais de m − 1 chaves: divida em duas metades e suba a mediana para o pai.
Se o pai estourar, repita. Se a raiz estourar, cria-se uma nova raiz com a mediana: a altura aumenta em 1, para todas as folhas ao mesmo tempo.

Insira 60, 70 e 80 (máximo de 2 chaves por nó) e acompanhe as divisões em cascata até a raiz.

Por crescer pela raiz, a árvore B mantém todas as folhas no mesmo nível sem nenhuma rotação. Inserir e buscar custam O(log n) acessos a disco, com base de log enorme.

Árvore B em Python: busca e inserção

inserir_rec desce até a folha e, na volta da recursão, cada nó verifica se estourou. Se sim, divide-se e devolve ao pai a mediana e o novo nó da direita; o pai os encaixa em suas listas.

Se a raiz dividir, inserir cria uma raiz nova com dois filhos.

buscar devolve também quantos nós (blocos) foram lidos.

A sequência de chaves é a mesma da visualização do slide Propriedades da árvore B, com no máximo 3 chaves por nó. Compare o resultado de mostrar com o desenho.

E a remoção?

Remover pode deixar um nó com menos chaves que o mínimo. Aí ele pega emprestada uma chave de um irmão com sobra (passando pelo pai) ou se funde com um irmão, puxando uma chave do pai. A fusão pode se propagar até a raiz, e a árvore diminui de altura por cima.

class NoB:
    def __init__(self, folha=True):
        self.chaves = []
        self.filhos = []
        self.folha = folha

MAX = 3      # no máximo 3 chaves por nó (ordem 4)

def buscar(no, k, lidos=0):
    lidos += 1                        # cada nó = um bloco lido
    i = 0
    while i < len(no.chaves) and k > no.chaves[i]:
        i += 1
    if i < len(no.chaves) and no.chaves[i] == k:
        return True, lidos
    if no.folha:
        return False, lidos
    return buscar(no.filhos[i], k, lidos)

def inserir_rec(no, k):
    """Insere k; se o nó estourar, devolve (mediana, novo nó da direita)."""
    i = 0
    while i < len(no.chaves) and k > no.chaves[i]:
        i += 1
    if no.folha:
        no.chaves.insert(i, k)
    else:
        subiu = inserir_rec(no.filhos[i], k)
        if subiu:
            med, direito = subiu
            no.chaves.insert(i, med)
            no.filhos.insert(i + 1, direito)
    if len(no.chaves) > MAX:          # estourou: divide
        meio = len(no.chaves) // 2
        direito = NoB(no.folha)
        med = no.chaves[meio]
        direito.chaves = no.chaves[meio + 1:]
        no.chaves = no.chaves[:meio]
        if not no.folha:
            direito.filhos = no.filhos[meio + 1:]
            no.filhos = no.filhos[:meio + 1]
        return med, direito
    return None

def inserir(raiz, k):
    subiu = inserir_rec(raiz, k)
    if subiu:                         # a raiz dividiu: cresce para cima
        med, direito = subiu
        nova = NoB(folha=False)
        nova.chaves = [med]
        nova.filhos = [raiz, direito]
        return nova
    return raiz

def mostrar(no, nivel=0):
    print("    " * nivel + str(no.chaves))
    for f in no.filhos:
        mostrar(f, nivel + 1)

raiz = NoB()
for k in [10, 20, 5, 6, 12, 30, 7, 17, 3, 25]:
    raiz = inserir(raiz, k)
mostrar(raiz)
print(buscar(raiz, 17))
print(buscar(raiz, 8))

Árvore B+

A variação mais usada na prática. Os nós internos guardam só separadores; todos os registros ficam nas folhas, que são ligadas em uma lista da esquerda para a direita.

	Árvore B	Árvore B+
dados	em todos os nós	só nas folhas
busca exata	pode parar no meio	sempre vai até a folha
intervalo	percurso em ordem pela árvore	desce 1 vez e segue as folhas
nós internos	chaves + dados	só chaves: cabem mais por bloco

Clique em Consultar intervalo: a árvore desce até a folha de 14 e depois só anda pelas folhas, como em SELECT * FROM alunos WHERE nota BETWEEN 14 AND 32.

Na divisão de uma folha da B+, a chave do meio sobe como cópia e continua na folha da direita. Nos nós internos, a divisão é igual à da árvore B. Insira 33, 34 e 35 para ver.

Quiz: arquivos e árvores B

Leia, decida e só então clique. Use as visualizações para conferir.

Prática 1: dicionários

Escreva sua solução no editor. ▶ Executar roda com a entrada que você quiser; ✓ Verificar roda os testes automáticos e mostra o que falta. Os dois problemas têm solução O(n) graças ao dict.

1. Palavra mais frequente básico

Leia um texto em uma linha. Sem diferenciar maiúsculas de minúsculas, mostre a palavra mais frequente e quantas vezes ela aparece. Em caso de empate, vence a que aparece primeiro no texto. Conte com um dict, sem usar count() dentro de um laço (isso seria O(n²)).

Entrada	Saída esperada
a b c b c c	Mais frequente: c Ocorrências: 3

Mostrar uma solução

2. Primeiro caractere único básico

Leia um texto e mostre o primeiro caractere que aparece uma única vez, ignorando os espaços: Primeiro único: x. Se todos se repetem, mostre Nenhum. Faça em duas passadas: uma para contar (com dict) e outra para achar o primeiro com contagem 1.

Entrada	Saída esperada
abacabad	Primeiro único: c
aabbcc	Nenhum

Mostrar uma solução

Prática 2: tabelas hash

Agora é você quem implementa a tabela. Use a visualização de sondagem linear para conferir seus resultados à mão.

3. Simulando a sondagem linear médio

Leia m e, na linha seguinte, chaves inteiras distintas. Insira cada uma com h(k) = k % m e sondagem linear, mostrando k -> posição p. Se não houver posição livre, mostre Tabela cheia: k. No fim, mostre a tabela (- nas vazias, separadas por espaço) e o total de colisões, contando cada posição ocupada visitada, inclusive nas tentativas que falharam.

Entrada	Saída esperada
7 10 20 15 3 17	10 -> posição 3 20 -> posição 6 15 -> posição 1 3 -> posição 4 17 -> posição 5 Tabela: - 15 - 10 3 17 20 Colisões: 3

Mostrar uma solução

4. Encadeamento com hash de texto médio

Leia m e uma linha de palavras. Insira cada palavra (sem repetir) em uma tabela com encadeamento, usando o hash polinomial: começando com h = 0, para cada caractere faça h = (h * 31 + ord(c)) % m. Mostre as posições não vazias como i: palavras na ordem de inserção, depois o tamanho da maior lista e o fator de carga com 2 casas.

Entrada	Saída esperada
7 maçã uva pera kiwi uva limão	0: limão 4: maçã pera 5: kiwi 6: uva Maior lista: 2 Fator de carga: 0.71

Mostrar uma solução

Prática 3: arquivos e árvores B

Contar blocos lidos e níveis de árvore é o que importa quando os dados estão no disco.

5. Busca binária em blocos médio

Leia quantos registros cabem por bloco, as chaves do arquivo (em ordem crescente) e o alvo. Divida as chaves em blocos consecutivos. Faça busca binária sobre os blocos: leia o bloco do meio; se o alvo é menor que a primeira chave, vá para a esquerda; se maior que a última, para a direita; senão, o alvo está nesse bloco ou não existe. Mostre Encontrado no bloco b ou Não encontrado, Blocos lidos: k e quantos blocos a busca sequencial leria (até o bloco do alvo, ou todos, se ausente).

Entrada	Saída esperada
3 2 5 8 11 14 17 20 23 26 31 20	Encontrado no bloco 2 Blocos lidos: 2 Busca sequencial leria: 3

Mostrar uma solução

6. Altura de uma árvore B desafio

Leia a ordem m (máximo de filhos por nó, m ≥ 3) e o número de chaves n ≥ 1. Mostre o menor e o maior número de níveis que uma árvore B com essas características pode ter.

Dicas: com h níveis, a árvore cabe no máximo m^h − 1 chaves (todos os nós cheios) e precisa de pelo menos 2·t^h−1 − 1 chaves, com t = ⌈m/2⌉ (raiz com 1 chave, demais nós com o mínimo). Use laços com inteiros, sem logaritmos.

Entrada	Saída esperada
3 7	Altura mínima: 2 Altura máxima: 3

Mostrar uma solução

Laboratório livre

Espaço para testar ideias durante a aula. Sugestões: compare a distribuição de 1000 nomes com a função polinomial e com a soma dos códigos dos caracteres; implemente sondagem quadrática na TabelaHash; insira 1 a 100 em ordem na árvore B do slide de Python e veja a altura com MAX = 3 e MAX = 9.

Hashing, árvores B/B+ e organização de arquivos

Buscar sem procurar

Funções hash

Colisões são inevitáveis

Tratamento por encadeamento

Uma TabelaHash com encadeamento

Endereçamento aberto: sondagem linear

Teste de mesa: sondagem linear

Sondagem quadrática e hash duplo

Remoção: o marcador “apagado”

Fator de carga e rehash

dict e set no Python

Desafio: rehash automático

Quiz: tabelas hash

Memória × disco

Registros de tamanho fixo e variável

Arquivo sequencial × arquivo ordenado

Índices e arquivos hash

Por que árvores B?

Propriedades da árvore B

Inserção: divide e sobe

Árvore B em Python: busca e inserção

E a remoção?

Árvore B+

Quiz: arquivos e árvores B

Prática 1: dicionários

1. Palavra mais frequente básico

2. Primeiro caractere único básico

Prática 2: tabelas hash

3. Simulando a sondagem linear médio

4. Encadeamento com hash de texto médio

Prática 3: arquivos e árvores B

5. Busca binária em blocos médio

6. Altura de uma árvore B desafio

Laboratório livre

`dict` e `set` no Python