- Recentemente, ao ler Database Internals de Alex Petrov, encontrei conteúdos sobre como os mecanismos de armazenamento de DBMS são implementados, especialmente em relação à otimização da estrutura de dados B-Tree
- Quando aprendi B-Tree na universidade, entendi de forma simplificada como apenas uma “BST melhor”, então não ficou claro para mim por que ela era usada na prática
- Considerando I/O de disco, a estrutura B-Tree é adequada para armazenar grandes volumes de dados e permitir buscas rápidas
- Este texto apresenta por que a B-Tree é necessária, como ela funciona e que tipos de otimização são possíveis em implementações reais
- Entre as principais características está a ideia de reunir muitas chaves em um único nó para reduzir o número de acessos ao disco
Restrições causadas pelo disco
- Parte-se da situação em que todos os dados não cabem inteiramente na memória
- O disco tem a característica de ler e escrever em unidades de página
- O acesso a disco é muito mais lento do que o acesso à memória
- Portanto, a estrutura de dados precisa organizar os dados com foco em páginas e realizar o máximo possível de comparações de chaves com o mínimo de acessos ao disco
- Se um BST for armazenado no disco sem adaptação, seus nós ficam espalhados, o que faz com que o número de acessos ao disco cresça junto com o número de etapas da busca
- A B-Tree reúne várias chaves em um nó para que uma única leitura de disco permita comparar várias chaves
Slot pages
- Ao posicionar dados no disco, o gerenciamento é feito em unidades chamadas “páginas”
- Cada página contém um cabeçalho, células com dados de tamanho variável e um array de ponteiros de offset que armazena a posição dessas células
- A estrutura de slot page tem a vantagem de manter a ordem de classificação mesmo quando o tamanho das chaves é variável, sem o custo de grandes rearranjos
- Ao remover ou inserir chaves, costuma ser muito mais eficiente reorganizar apenas os ponteiros do que mover os dados reais
- Por exemplo, o SQLite usa uma free list dentro dessa estrutura de página para reutilizar o espaço de células removidas
Busca em B-Tree
- O algoritmo de busca em B-Tree é simples:
- Começar pelo nó raiz
- Observar a Separator Key do nó atual e encontrar o nó filho onde provavelmente está a chave buscada
- Percorrer a árvore recursivamente
- Se encontrar o nó folha que contém a chave, a busca termina; caso contrário, conclui-se que ela não existe
- Em nós internos, pode haver apenas as chaves separadoras em vez dos dados reais, e é comum que os dados reais fiquem armazenados apenas nos nós folha
- Para localizar chaves de forma eficiente dentro de um nó usando busca binária, as chaves de cada nó são mantidas em ordem
Redução de Separator Key
- A Separator Key dos nós internos não precisa necessariamente conter a chave real completa; basta ter informação suficiente para separar os intervalos
- Por exemplo, para distinguir entre 0xAAAAAA e 0xBBBBBB, não é obrigatório armazenar todo 0xBBBBBB; é possível separar com um prefixo mais curto
- Em bancos de dados com chaves longas, esse tipo de redução pode trazer uma grande economia de espaço
- Além da redução de Separator Key, também existem estratégias para reduzir prefixos (prefix) e sufixos (suffix) de forma eficiente
- Como há muito mais nós folha, existe a visão de que a compressão de prefixos contribui ainda mais para o desempenho
Overflow pages
- Quando um nó passa a ter tantas chaves que não cabe mais em uma única página, podem ser usadas overflow pages
- Em vez de mover toda a chave para a overflow page, o nó mantém apenas um prefixo curto e armazena o restante separadamente
- Assim, ao verificar a existência de uma chave ou fazer uma busca por intervalo, primeiro se confere apenas o prefixo presente no nó e a overflow page só é lida quando realmente necessário
- Mesmo com a alocação de páginas adicionais, essa estratégia reduz o custo total de busca
Ponteiros para irmãos
- Há implementações em que cada nó armazena ponteiros para os nós irmãos à esquerda e à direita
- Isso permite que, em buscas por intervalo, seja possível sair diretamente de um nó folha para o nó irmão e percorrer rapidamente chaves consecutivas
- Sem ponteiros para irmãos, seria necessário subir de volta ao nó pai e descer novamente repetidas vezes, aumentando o custo de I/O
- Como os intervalos de chaves entre nós irmãos não se sobrepõem, mover-se pelo ponteiro do irmão à direita garante chegar ao “próximo intervalo de chaves”
Variações de B-Tree
- Além da B⁺-Tree, existem várias outras estruturas derivadas
- A “Lazy B-Tree”, usada no WiredTiger, e a Lazy-Adaptive Tree aumentam o desempenho ao fazer buffer de operações de escrita
- A FD-Tree é uma estrutura projetada para as características de SSDs, levando em conta restrições físicas como escrita em blocos
- A Bw-Tree (Buzzword Tree) é uma estrutura de dados otimizada para alta concorrência e acesso à árvore em memória
Conclusão
- Entre o conceito abstrato de “B⁺-Tree” e uma implementação real como o “formato de banco de dados do SQLite”, existem muitas otimizações e diferenças nos detalhes de implementação
- As otimizações não mudam a complexidade Big-O, mas têm grande impacto no desempenho e na usabilidade do banco de dados em ambientes reais
- Além do que foi apresentado aqui, cada sistema de armazenamento específico exige muito ajuste fino
- Por trás da expressão “só é preciso um pouco de informação adicional” estão escondidas a complexidade de implementação e a dificuldade de debugging
- Como exemplo de uma representação mais realista da estrutura B-Tree, o diagrama de B-Tree de Designing Data Intensive Applications é marcante
1 comentários
Comentários no Hacker News
A estrutura da página é composta por cabeçalho, células e ponteiros de deslocamento, com a vantagem de poder armazenar dados de tamanho variável
Excelente artigo com animações sobre B-trees
Alguns anos atrás, implementei uma B-link Tree com recuperação concorrente com base na pesquisa de Ibrahim Jaluta
Criei um explorador de páginas de disco do SQLite e isso me ajudou a entender melhor B-trees
Falta conteúdo sobre B-link trees, concorrência e locking, mas isso talvez seja mais informação do que o necessário
Comentários antigos: Hacker News
Ótimo artigo, que explica bem a importância dos detalhes
Bom material sobre implementação de B-tree usando Golang
Sou um grande fã deste artigo e também tinha uma "compreensão vaga" parecida com a do autor