Um índice B-tree é uma estrutura de dados em árvore balanceada comumente utilizada em bancos de dados para organizar e buscar grandes volumes de dados de forma eficiente.
B-trees são muito semelhantes às árvores binárias de busca (BST), mas os nós em uma B-tree podem ter mais de dois filhos. Você pode aprender mais sobre BSTs no curso Visão Geral de Algoritmos e Estruturas de Dados.

B-tree armazena as chaves em ordem ordenada dentro dos nós, permitindo a recuperação rápida dos dados por meio da travessia hierárquica do nó raiz até os nós folha. A indexação B-tree é adequada para consultas de intervalo e buscas por igualdade, tornando-se uma escolha popular para otimização de desempenho em bancos de dados.

Como funciona?

O índice B-tree organiza os dados de forma hierárquica, com cada nó contendo um número fixo de chaves e ponteiros para nós filhos.
As B-trees mantêm o balanceamento garantindo que todos os nós folha estejam no mesmo nível, o que otimiza as operações de busca.
Ao buscar uma chave específica, o algoritmo B-tree percorre a árvore do nó raiz até os nós folha, utilizando busca binária para localizar de forma eficiente a chave desejada.

Busca por índice envolve percorrer a árvore até alcançar os nós folha, seguir a cadeia de nós folha para encontrar os registros correspondentes e recuperar os dados reais do disco.

Na figura, a busca pela chave 302 é ilustrada:

1. Uma estrutura de árvore de busca é um tipo de árvore em que cada nó possui dois ponteiros: o ponteiro esquerdo aponta para nós filhos com valores menores que o nó pai, e o ponteiro direito aponta para nós filhos com valores maiores que o nó pai;

2. Em uma B-tree, o nó raiz pode conter múltiplos valores de índice. Por exemplo, se a raiz contiver três valores distintos, terá três ponteiros, cada um indicando o intervalo de valores entre essas chaves;

3. Para buscar uma chave, como 302, a busca começa no nó raiz e segue os ponteiros apropriados até os nós folha. A busca é concluída após percorrer três blocos da árvore, conforme destacado em vermelho no diagrama;

4. Para buscar um intervalo de valores a partir de 302, é possível utilizar os ponteiros horizontais entre os nós folha. Por exemplo, a recuperação de valores de 302 a 502 é feita seguindo sequencialmente os nós folha.

Nota

A chave utilizada para busca em um índice B-tree provém dos valores armazenados na(s) coluna(s) indexada(s) da tabela do banco de dados. Por exemplo, se o índice está em uma coluna como "client_id", a chave de busca será o valor real de "client_id". Cada valor numérico único na coluna indexada serve como uma chave no índice B-tree, facilitando a localização e recuperação das linhas correspondentes na tabela do banco de dados.

Vantagens e desvantagens

Diferente da estrutura padrão de Árvore Binária de Busca, os nós de uma B-tree podem acomodar mais de 2 filhos. O número máximo padrão de filhos por nó geralmente é definido como 16.

Implementação de índice

Para criar um índice B-tree em uma coluna no PostgreSQL, utilize o seguinte comando SQL:

CREATE INDEX index_name ON table_name USING BTREE (column_name1, column_name2,...);

Como o índice B-tree é o índice padrão em SQL, também podemos utilizar a seguinte instrução para criá-lo:

CREATE INDEX index_name ON table_name(column_name1, column_name2,..);

Nota

Em SQL, ao criar uma tabela com uma restrição de chave primária, a maioria dos sistemas de gerenciamento de banco de dados cria automaticamente um índice na(s) coluna(s) especificada(s) como chave primária. Esse índice auxilia na aplicação da restrição de unicidade da chave primária e também melhora o desempenho de consultas que envolvem buscas ou junções baseadas na(s) coluna(s) da chave primária.