Um índice B-tree é uma estrutura de dados em árvore balanceada comumente utilizada em bancos de dados para organizar e pesquisar 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.

A B-tree armazena chaves em ordem classificada dentro dos nós, permitindo a recuperação rápida de 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 otimizar o desempenho de 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 da B-tree percorre a árvore do nó raiz até os nós folha, utilizando busca binária para localizar a chave desejada de forma eficiente.

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 onde 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 o nó raiz contiver três valores distintos, ele 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.

Vantagens e desvantagens

Ao contrário da estrutura de dados padrão Á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 usar a seguinte instrução para criá-lo:

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