Camada Zero · 22 · Índices: B-tree vs LSM-tree

Todo banco precisa achar uma linha rápido sem varrer a tabela inteira. Os dois jeitos dominantes de fazer isso puxam pra lados opostos: a B-tree otimiza leitura, a LSM-tree otimiza escrita. Insere as mesmas chaves nas duas aqui embaixo e olha a estrutura crescer de formas diferentes.
← voltar à trilha
B-tree read-optimized
LSM-tree write-optimized
0B-tree: altura
—B-tree: nós lidos (busca)
0LSM: SSTables
—LSM: read amplification
0LSM: writes físicos
Insere algumas chaves nas duas estruturas e depois busca uma. Repara: a B-tree acha em poucos nós (altura baixa); a LSM precisa checar a memtable e cada SSTable até encontrar.
Os dois resolvem o mesmo problema (achar uma chave sem full scan), mas com filosofias opostas de I/O. A B-tree atualiza a página no lugar: ótima leitura, mas o write é aleatório no disco. A LSM só faz append (memtable em RAM, depois SSTables ordenadas): write rápido e sequencial, mas a leitura paga por checar vários níveis.
 B-treeLSM-tree
Writein-place (aleatório)append (sequencial)
Readpoucos I/Ovários níveis + bloom
Brilha emleitura / OLTPescrita pesada
Usado porPostgres, MySQLCassandra, RocksDB, LevelDB

B-tree (o nó é uma página de disco)

type BNode struct {
    keys     []int
    children []*BNode
    leaf     bool
}
// cada nó = 1 página (4-8 KB), então guarda
// dezenas/centenas de chaves. Nó largo =
// árvore rasa = menos I/O por busca.

LSM (memtable → SSTable)

func (t *LSM) Put(k, v []byte) {
    t.mem.Insert(k, v) // rápido, em RAM
    if t.mem.Size() >= threshold {
        t.flush() // vira SSTable ordenada no disco
    }
}
// read: memtable, depois SSTables (nova→velha);
// bloom filter pula as que não têm a chave.

🧠 Desafio — Índices

Insere e busca nas duas estruturas aqui de cima antes de responder. As duas últimas são de reflexão: escreve a sua e só então revela o modelo.