Árvores B e índices de banco de dados

O que é uma B-tree?

• A B-tree serve como base para muitos softwares, especialmente sistemas de gerenciamento de banco de dados (DBMS)

• MySQL, Postgres, MongoDB, Dynamo e outros dependem de B-trees para realizar consultas eficientes por meio de índices

• Vamos aprender como B-trees e B+trees funcionam, por que os bancos de dados as usam em índices e por que usar UUID como chave primária pode ser uma má ideia

• A B-tree armazena pares de dados conhecidos como chaves e valores no que programadores chamam de uma estrutura semelhante a uma árvore

• A B-tree é composta por nós (retângulos) e ponteiros para filhos (linhas que conectam os nós)

• O nó no topo é chamado de nó raiz, os nós no nível mais baixo são chamados de nós folha, e todos os demais são chamados de nós internos

• Abaixo está a definição de uma B-tree:

  • Cada nó armazena N pares chave/valor (onde N é maior que 1 e menor ou igual a K)
  • Cada nó interno tem no mínimo N/2 pares chave/valor (nó interno é o nó que não é folha nem raiz)
  • Cada nó tem N+1 filhos
  • O nó raiz tem pelo menos um valor e dois filhos, a menos que seja o único nó
  • Todas as folhas estão no mesmo nível

• Outra característica central da B-tree é a ordenação. Dentro de cada nó, os elementos são mantidos em ordem

• Por causa dessa ordenação, é possível buscar chaves com muita eficiência. A busca começa no nó raiz e:

  1. verifica se a chave procurada está contida no nó
  2. se não estiver, encontra no nó a posição onde a chave seria inserida
  3. nesse ponto, segue o ponteiro para filho até o próximo nível e repete o processo

• Ao buscar dessa forma, basta visitar um nó em cada nível da árvore para encontrar uma chave

• A B-tree foi especialmente projetada para funcionar bem quando há uma quantidade muito grande de dados que também precisa persistir em armazenamento de longo prazo (disco). Isso acontece porque cada nó usa uma quantidade fixa de bytes

• Em uma B-tree, a quantidade de valores que cada nó pode armazenar varia de acordo com o número de bytes alocados para ele e com a quantidade de bytes consumida por cada par chave/valor

B+tree (otimizada para bancos de dados)

• A B+tree é parecida com a B-tree, mas com as seguintes mudanças nas regras:
  • Os pares chave/valor são armazenados apenas nos nós folha
  • Os nós não folha armazenam apenas chaves e ponteiros para filhos associados
• Há duas regras adicionais específicas da forma como o MySQL implementa B+trees em índices:
  • Nós não folha armazenam N ponteiros para filhos em vez de N+1
  • Todos os nós também incluem ponteiros para "próximo" e "anterior", permitindo que cada nível da árvore também funcione como uma lista duplamente encadeada
• Existem dois motivos pelos quais a B+tree é mais adequada para bancos de dados:
  1. como nós internos não precisam armazenar valores, é possível colocar mais chaves em cada nó interno. Isso ajuda a reduzir a profundidade da árvore
  2. todos os valores ficam armazenados no mesmo nível e podem ser percorridos em ordem por meio da lista encadeada do nível inferior

Como o MySQL usa B+trees

• O MySQL suporta vários mecanismos de armazenamento, e o mais usado é o InnoDB, que depende fortemente de B+trees
• Na prática, o InnoDB depende tanto delas que armazena todos os dados da tabela em uma B+tree, usando a chave primária da tabela como chave da árvore
• Sempre que você cria uma nova tabela InnoDB, precisa definir uma chave primária
• O MySQL cria uma B+tree para cada nova tabela, e o valor definido como chave primária se torna a chave da árvore. O valor são os demais valores de coluna de cada linha, armazenados apenas nos nós folha
• O tamanho de cada nó dessa B+tree é definido por padrão como 16k
• Sempre que o MySQL precisa acessar um fragmento de dados (chave, valor etc.), ele carrega do disco a página inteira associada (nó da B+tree), mesmo que não precise das outras chaves ou valores
• Também é comum criar índices secundários em tabelas InnoDB. Para cada índice secundário, é construída uma B+tree persistente adicional, em que a chave é a coluna escolhida pelo usuário para indexação, e o valor é a chave primária da linha associada

Escolha da chave primária: inserção

• Como a forma de organização dos dados da tabela na B+tree depende da chave escolhida, a escolha da PRIMARY KEY afeta o layout em disco de todos os dados da tabela
• Duas opções comumente escolhidas como chave primária são:
  • sequência de inteiros (BIGINT UNSIGNED AUTO_INCREMENT, por exemplo)
  • UUID (existem várias versões)
• Considerando o resultado de usar UUIDv4 como chave primária, durante inserções:
  1. não é possível prever com antecedência quais nós serão visitados para a inserção
  2. não é possível prever qual será o nó folha de destino da inserção
  3. os valores das folhas não ficam ordenados
• Os problemas 1 e 2 acontecem porque, ao longo de muitas inserções, muitos nós (páginas) da árvore precisam ser visitados. Esse excesso de leituras e gravações leva à queda de desempenho
• Ao usar BIGINT UNSIGNED AUTO_INCREMENT como chave primária:
  1. ao inserir novos valores, o caminho seguido é sempre o mais à direita
  2. folhas são adicionadas apenas no lado direito da árvore
  3. no nível das folhas, os dados ficam ordenados na sequência em que foram inseridos
• Por causa dos itens 1 e 2, muitas inserções feitas em sequência revisitam o mesmo caminho de páginas, reduzindo as requisições de I/O ao inserir muitos pares chave/valor

Escolha da chave primária: leitura de dados em ordem

• É comum consultar dados em ordem cronológica em um banco de dados
• Se UUIDv4 for usado como chave primária, a sequência de valores do resultado da consulta ficará espalhada por vários nós folha não sequenciais
• Ao buscar valores inseridos sequencialmente, todas as páginas que contêm o resultado da consulta ficam adjacentes. Ao consultar várias linhas, elas podem até estar todas adjacentes dentro de uma única página
• Para esse padrão de consulta, usar uma chave primária sequencial pode reduzir o número de páginas que precisam ser lidas

Escolha da chave primária: tamanho

• O tamanho da chave primária também é um fator importante. A chave primária deve sempre:
  1. ser grande o suficiente para não se esgotar
  2. ser pequena o suficiente para não consumir espaço de armazenamento em excesso
• No caso de sequências inteiras, tabelas menores podem usar MEDIUMINT (16 milhões de valores únicos) ou INT (4 bilhões de valores únicos)
• Para tabelas grandes, usa-se BIGINT por segurança (1,8e19 valores possíveis). BIGINT tem 64 bits (8 bytes)
• UUID normalmente tem 128 bits (16 bytes), o dobro do maior tipo inteiro do MySQL
• Como os nós da B+tree têm tamanho fixo, usar BIGINT permite colocar mais chaves por nó do que UUID. Isso leva a árvores mais rasas e buscas mais rápidas

B+tree, páginas e InnoDB

• Uma das grandes vantagens da B+tree é que você pode definir o tamanho dos nós como quiser
• No InnoDB, os nós da B+tree normalmente são definidos com 16k, que é o tamanho da página do InnoDB
• Durante o processamento de consultas (e, portanto, ao percorrer a B+tree), o InnoDB não lê linhas e colunas individuais do disco. Sempre que precisa acessar um fragmento de dados, ele carrega do disco a página inteira associada
• O InnoDB tem algumas técnicas para amenizar isso, e a principal é o buffer pool. O buffer pool é um cache em memória para páginas do InnoDB, posicionado entre as páginas em disco e a execução de consultas do MySQL
• Quando o MySQL precisa ler uma página, ele primeiro verifica se ela já está no buffer pool. Se estiver, lê dali e evita a operação de I/O em disco. Se não estiver, localiza a página no disco, adiciona-a ao buffer pool e depois continua a execução da consulta
• O buffer pool melhora enormemente o desempenho das consultas. Sem ele, seria necessário realizar muito mais operações de I/O em disco para lidar com a carga de consultas

Outros cenários

• Aqui o foco foi principalmente comparar chaves sequenciais com chaves aleatórias/UUID, mas esses princípios são úteis independentemente do tipo de chave primária ou secundária que você esteja considerando
• Por exemplo, você pode considerar usar o timestamp user.created_at como chave de índice, que tem características parecidas com as de um inteiro sequencial. A menos que você insira dados legados, as inserções normalmente sempre seguem pelo caminho mais à direita
• Por outro lado, algo como a string user.email_address tem características mais parecidas com uma chave aleatória. Como usuários não criam contas em ordem alfabética de e-mail, as inserções acontecem por toda a B+tree

Conclusão

• Cobrimos bastante coisa sobre B+trees, índices e a escolha da chave primária
• Na superfície isso pode parecer simples, mas existem diferenças sutis a considerar se você quiser extrair o máximo de desempenho possível do banco de dados
• Para experimentar mais, vale visitar este site interativo de B+tree

[GN⁺]

Comentários do Hacker News

• Mantemos a wiki útil usando uma estratégia de organização como uma B-Tree

  • Quando há páginas de entrada demais, movemos links e parágrafos para subpáginas
  • Links semelhantes e antigos são movidos para páginas irmãs adequadas ao tema
  • No fim, documentos antigos acabam ficando três níveis abaixo da página de entrada
  • Documentação acaba se resumindo a um problema de busca
  • É uma boa forma de passar uma tarde de sexta-feira sendo produtivo

• Eu estava procurando algo assim há muito tempo, post incrível

  • Gostaria que houvesse uma seção sobre índices compostos

• Obrigado pelos visuais incríveis

  • Trabalhei em suporte a indexação BTree+ sobre o Aerospike
  • Remover chaves expiradas da BTree+ foi um desafio
  • Decidimos fundir uma ramificação de um nível apenas dentro do primeiro nó folha irmão
  • Adicionamos sharding sobre a BTree+ para aumentar a velocidade e reduzir contenção de locks
  • A BTree+ pode ficar desbalanceada durante o processo de limpeza
  • Oferecemos uma função de reconstrução de índice para evitar trabalho extra de limpeza

• O modal de cookies não funciona no Firefox Mobile

  • Deveriam permitir que o usuário configurasse isso no navegador

• Você não deveria usar uma coluna UUID como chave primária

  • É preciso copiar um int de 128 bits em todos os aspectos dos relacionamentos
  • Na maioria dos casos, ele é totalmente aleatório
  • Para relacionamentos internos entre tabelas, deveria usar um PK bigserial (64 bits), e UUID (128 bits) para identificadores em nível de aplicação e chaves naturais
  • O banco de dados vai ficar muito mais feliz

• Excelente material didático

  • Esses demos interativos ajudam bastante

• Se blocos de disco e nós da B-Tree têm 16k, e chave, valor e ponteiro de filho têm todos 8 bits, então dá para armazenar 682 pares de chave/valor e 683 ponteiros de filho por nó

  • Uma árvore de três níveis pode armazenar mais de 300 milhões de pares de chave/valor
  • Cada elemento teria que ter 8 bytes

• Excelente artigo

  • O fato de o InnoDB armazenar os dados na própria B-tree é chamado de índice clusterizado
  • O MyISAM era um índice não clusterizado
  • Oracle e outros permitem escolher

• Perguntando o que v0, v1, ...v10 significam no gráfico

  • Queria saber se isso significa páginas diferentes

• Visualização interativa linda

  • De altíssimo nível em termos de educação e popularização