Trilha Internals de Bancos de Dados: tudo o que estudar, tópico por tópico

O papel de um mecanismo de armazenamento dentro de um SGBD, a separação entre armazenamento e processamento de consultas, e a distinção fundamental entre mecanismos de atualização in-place (B-Tree) e append-only (LSM)

Como os registros são organizados em páginas de tamanho fixo alinhadas a blocos de disco, cabeçalhos de página, registros de tamanho fixo vs variável e por que a página é a unidade fundamental de E/S

A organização de página com slots que armazena um diretório de slots com offsets no início da página e células de tamanho variável crescendo a partir do fim, permitindo exclusões, atualizações e compactação in-place

Como os arquivos de banco de dados codificam células, chaves, valores e ponteiros; codificação binária, ordem de bytes, números mágicos, versionamento e checksums que tornam um formato legível e durável

A árvore de busca balanceada e de alto fan-out no coração da maioria dos bancos de dados: invariantes de ocupação, altura logarítmica, por que o alto fan-out minimiza buscas em disco e a busca de chaves dentro de um nó

A variante B+Tree que armazena valores apenas nas folhas e encadeia as folhas em uma cadeia sequencial, otimizando varreduras de intervalo e separando chaves de roteamento nos nós internos dos dados nos nós folha

Como B-Trees permanecem balanceadas em inserções e exclusões: dividir nós cheios e propagar o separador para cima, fundir ou rebalancear nós subocupados, e o custo das modificações estruturais

Otimizações práticas de B-Tree: B-Trees copy-on-write, B-Trees lazy e escritas adiadas, Bw-Trees com cadeias de delta, ponteiros entre irmãos (B-link trees) e ideias de cascading fracionado

Como os índices mapeiam chaves para dados: índices clusterizados (primários) que armazenam linhas em ordem de chave vs índices secundários não clusterizados que armazenam referências, e o custo de manter múltiplos índices

A log-structured merge-tree: bufferizar escritas em memória, descarregar runs ordenados imutáveis para o disco e mesclá-los em segundo plano para trocar custo de leitura por throughput de escrita

A estrutura ordenada em memória (frequentemente uma skip list ou árvore balanceada) que absorve escritas antes de serem descarregadas para uma SSTable, o ciclo de vida de memtable ativa/em descarga e seu pareamento com o WAL

Sorted String Tables: arquivos imutáveis em disco com pares chave-valor ordenados, com uma seção de blocos de dados, índice esparso e rodapé, permitindo buscas e mesclagens eficientes entre runs

Mesclagem em segundo plano de SSTables para recuperar espaço e limitar o custo de leitura: compactação size-tiered vs leveled, seus trade-offs de amplificação de escrita/espaço e coleta de lixo de tombstones

Filtros probabilísticos de pertinência usados para pular SSTables que não podem conter uma chave: como múltiplas funções de hash ativam bits, o significado de falsos positivos e o dimensionamento para uma taxa-alvo de falsos positivos

Os três fatores de amplificação que governam os trade-offs do mecanismo de armazenamento e a conjectura RUM: como B-Trees e variantes de LSM se posicionam em pontos diferentes da superfície leitura/escrita/espaço

O cache em memória de páginas que media todo acesso ao disco: tabelas de páginas, fixação (pinning) e contagens de referência, rastreamento de páginas sujas e o latching que mantém o acesso concorrente seguro

Escolher qual página despejar quando o buffer pool está cheio: LRU e seus problemas de resistência a varreduras, CLOCK/segunda chance, variantes LRU-K e LFU, e interações com prefetching

O mecanismo de durabilidade que registra mudanças em um log sequencial antes de aplicá-las às páginas: a invariante do WAL, registros de log e LSNs, políticas de steal/force e group commit

O algoritmo de recuperação de falhas ARIES e suas três fases — análise, redo e undo — com repetição da história, registros de log de compensação, checkpoints e a tabela de páginas sujas

O que uma transação garante e como um mecanismo de armazenamento implementa ACID: atomicidade via logging, consistência, isolamento via controle de concorrência e durabilidade via WAL e fsync

Os níveis de isolamento do SQL e as anomalias de leitura/escrita que eles permitem: leituras sujas, leituras não repetíveis, phantoms, write skew e a diferença entre serializabilidade e isolamento de snapshot

Controle de concorrência pessimista com bloqueios: modos de bloqueio compartilhado/exclusivo, bloqueio em duas fases e 2PL estrito para serializabilidade, granularidade de bloqueio, detecção de deadlock e escalonamento de bloqueio

MVCC: manter múltiplas versões de cada linha para que leitores nunca bloqueiem escritores, visibilidade de versões via timestamps/snapshots de transação, coleta de lixo de versões antigas e validação otimista

Detectar falhas de nós em um armazenamento distribuído: heartbeats e timeouts, a impossibilidade de distinguir perfeitamente lento de morto, detectores phi-accrual e disseminação baseada em gossip

Manter cópias de dados consistentes: replicação baseada em líder vs sem líder, propagação síncrona vs assíncrona, quóruns de leitura/escrita e anti-entropia via árvores de Merkle e read repair

Concordar sobre um único valor ou ordem de log entre nós apesar de falhas: as metas de segurança/vivacidade do consenso, as ideias centrais do Paxos e como o Raft estrutura eleição de líder e replicação de log