B-tree x LSM-tree: por dentro do índice do seu banco

Escolher banco de dados sem saber qual estrutura ele usa por baixo é escolher no escuro. As duas famílias que dominam (B-tree e LSM-tree) resolvem o mesmo problema com filosofias opostas, e cada uma cobra em um lugar diferente.

Primeiro: por que o disco muda tudo#

Em memória, ler qualquer endereço custa mais ou menos igual. No disco, não.

O disco não lê byte: lê bloco, tipicamente quatro ou oito kilobytes. Ler um byte ou ler quatro kilobytes custa praticamente o mesmo.

E cada acesso a um lugar diferente é caro: em SSD, dezenas a centenas de microssegundos; em disco mecânico, milissegundos, porque o braço precisa se mover.

Isso inverte o critério de projeto. Na memória, você minimiza comparações. No disco, você minimiza acessos.

Uma árvore binária com um milhão de itens tem vinte níveis. Se cada nível for um acesso a disco, são vinte acessos, o que é inaceitável.

A solução é fazer cada nó ser grande, do tamanho de um bloco, com centenas de filhos em vez de dois. A árvore fica baixinha.

B-tree: leitura previsível#

Cada nó ocupa uma página de disco e guarda centenas de chaves com seus ponteiros. Com fator de ramificação de umas trezentas, uma árvore de três níveis endereça vinte e sete milhões de registros.

Três acessos no pior caso, e os dois primeiros níveis quase sempre estão em memória, então na prática é um.

A variante que todo banco relacional usa é a B+tree: os dados ficam só nas folhas, e as folhas são ligadas entre si numa lista. Isso deixa os nós internos mais enxutos (cabem mais chaves por página) e transforma varredura por faixa em caminhar numa lista encadeada, sem subir e descer.

Escrita: a página é lida, alterada e regravada. Se encheu, racha em duas e o pai é atualizado. Escrita aleatória: cada update mexe numa página diferente do disco.

Resultado: leitura previsível e rápida, inclusive por faixa e ordenação. Escrita mediana em volume alto.

Quem usa: Postgres, MySQL/InnoDB, Oracle, SQL Server, SQLite. Praticamente todo o mundo relacional.

LSM-tree: escrita sequencial#

A LSM-tree parte de uma premissa diferente: escrita aleatória é cara, então nunca faça escrita aleatória.

Toda escrita vai para uma estrutura ordenada em memória (a memtable) e para um log sequencial no disco, o WAL, que existe para recuperar em caso de queda.

Quando a memtable enche, ela é despejada no disco de uma vez, como um arquivo ordenado e imutável: um SSTable. Escrita sempre sequencial, sempre rápida.

O preço aparece na leitura. Um registro pode estar na memtable ou em qualquer um dos arquivos, do mais novo para o mais velho. Para não abrir todos, cada arquivo tem um Bloom filter, que responde na hora "com certeza não está aqui", e economiza a leitura.

E como os arquivos se acumulam, existe a compactação: um processo de fundo que junta arquivos, descarta versões antigas e remove o que foi apagado.

Quem usa: Cassandra, RocksDB, LevelDB, HBase, ScyllaDB, e o motor de armazenamento de várias coisas que você usa sem saber, incluindo muitos bancos de série temporal.

Amplificação: as três contas#

Este é o vocabulário que permite comparar os dois de forma honesta.

Amplificação de escrita: quanto o disco realmente escreve para cada byte que você gravou.

Na LSM, o mesmo dado é reescrito em cada nível de compactação. Um megabyte que você gravou pode virar dez megabytes de escrita real. Isso desgasta SSD e consome banda de I/O.

Na B-tree, você reescreve a página inteira para alterar uma linha. Isso também amplifica, mas de forma mais previsível.

Amplificação de leitura: quantos acessos são necessários para achar um registro.

Na B-tree, é o número de níveis: pequeno e constante.

Na LSM, é o número de arquivos que precisam ser consultados: variável, e é por isso que o Bloom filter importa tanto.

Amplificação de espaço: quanto espaço é ocupado além do dado útil.

Na LSM, versões antigas ainda não compactadas ocupam espaço.

Na B-tree, páginas deixam espaço livre de propósito para caber inserção futura: fragmentação por desenho.

A tabela de decisão#

Escolha B-tree quando

• ·leitura por faixa e ordenação são frequentes
• ·latência previsível importa mais que pico de vazão
• ·você precisa de transações ACID ricas
• ·o padrão é mais leitura que escrita

Escolha LSM quando

• ·volume de escrita é alto e contínuo
• ·o acesso é por chave, não por faixa
• ·compressão importa: arquivo imutável e ordenado comprime melhor
• ·você tolera variação de latência

O detalhe que decide na prática#

A variação de latência da LSM durante compactação é real e é o que mais surpreende quem migra.

O p50 pode ser excelente e o p99 saltar quando uma compactação grande está rodando. Se o seu produto tem SLO agressivo de cauda, isso precisa entrar na conta, e existem estratégias de compactação diferentes (por nível, por tamanho) que trocam amplificação por previsibilidade.

Do outro lado, a B-tree sofre com escrita concorrente na mesma página e com fragmentação ao longo do tempo, o que aparece como degradação lenta que só um VACUUM ou REINDEX resolve.

Nenhuma das duas é grátis. A pergunta certa nunca é "qual é melhor", e sim "qual conta eu prefiro pagar".

O que isso muda no seu dia#

Três coisas concretas:

1. Ao escolher banco, procure na documentação qual estrutura ele usa. Isso te diz mais sobre o comportamento sob carga do que a página de marketing.

2. Ao investigar latência irregular num banco LSM, olhe as métricas de compactação antes de qualquer outra coisa.

3. Ao investigar degradação lenta num banco B-tree, olhe fragmentação, bloat e estatísticas desatualizadas.

Saber o nome da estrutura transforma "o banco está estranho" em uma hipótese testável.