Como funcionam os índices: estrutura de dados e algoritmos de busca

Hoje a gente vai mergulhar mais fundo na arquitetura dos índices e ver como eles realmente funcionam por trás dos panos. Porque entender como o índice é feito ajuda não só a sacar por que as queries ficam mais rápidas, mas também como escolher o índice certo pra cada situação.

Quando falamos da estrutura de um índice, é sobre como os dados são organizados dentro do índice pra garantir uma busca rápida. Imagina um armário cheio de documentos. Se os docs tão jogados numa pilha só, achar o que tu quer é difícil. Mas se o armário tá em ordem alfabética, fica bem mais fácil. Os índices funcionam desse jeito: eles organizam os dados pra que a busca pela informação seja o mais rápida possível.

Estrutura do índice B-TREE

B-TREE (balanced tree — árvore balanceada) é o tipo de índice mais usado no PostgreSQL. Basicamente, é uma estrutura em forma de árvore, onde os dados ficam organizados em nós, e a busca rola navegando da raiz da árvore até as folhas.

Como isso fica na prática:

         Raiz
          /       |       \
      Nó 1     Nó 2     Nó 3
     /   \       |       /   \
Folha1 Folha2  Folha3  Folha4 Folha5

Cada nó tem valores-chave que ajudam a direcionar a busca. Por exemplo, se o nó raiz tem os valores [10, 20, 30], então:

• Todos os dados menores que 10 ficam na Folha 1.
• Todos os dados entre 10 e 20 — na Folha 2, e por aí vai.

Vantagens do índice B-TREE:

• Busca rápida de dados: a complexidade da busca é O(log n), bem mais rápido que uma busca linear.
• Serve pra buscas por intervalos (tipo, achar todos os valores entre 10 e 50).

Exemplo: imagina que temos uma tabela students com a coluna age. Quando a gente cria um índice B-TREE nessa coluna:

CREATE INDEX age_idx ON students (age);

O PostgreSQL monta uma árvore balanceada pros valores de idade, o que permite achar rapidinho os estudantes de uma certa idade ou de um intervalo de idades.

Algoritmo de busca no B-TREE

Quando tu faz uma query, o PostgreSQL usa o índice pra buscar os dados assim:

1. Define a chave de busca (tipo, idade 25).
2. Começa pelo nó raiz.
3. Compara a chave com os intervalos de valores do nó e vai pro nó filho correspondente.
4. Repete o passo 3 até chegar numa folha.
5. Retorna os dados da folha que batem com a chave.

Exemplo de query:

SELECT * FROM students WHERE age = 25;

O índice reduz o tanto de dados que precisa ser escaneado, deixando a busca bem rápida.

Algoritmos de busca e performance

Os índices aceleram a busca porque diminuem a quantidade de linhas que precisam ser lidas. Sem índice, o PostgreSQL escaneia a tabela toda (isso é chamado de scan sequencial, ou Seq Scan). Com índice, rola o scan por índice (Index Scan), que é muito mais rápido.

Comparando scan sequencial e scan por índice

• Scan sequencial (Seq Scan):

  • O PostgreSQL lê cada linha da tabela, checa as condições da query e retorna as linhas que batem.
  • É usado se não tem índice ou se a query pega quase todas as linhas da tabela.

• Scan por índice (Index Scan):

  • O PostgreSQL usa o índice pra achar as linhas certas e só depois vai na tabela buscar elas.
  • Bem mais rápido pra tabelas grandes, se a query pega só uma parte pequena dos dados.

Exemplo: sem índice, buscar idades

SELECT * FROM students WHERE age = 25;

o resultado pode exigir ler 1 milhão de linhas. Com o índice B-TREE, por exemplo, o sistema lê só 100 linhas.

Como a estrutura do índice afeta a performance

Os índices são mais rápidos porque eles reduzem o volume de dados que precisa ser lido. Por exemplo, se a tabela tem milhões de linhas, o índice organiza elas de um jeito que a query só precisa ler alguns nós, não a tabela toda.

É muito importante entender a estrutura do índice. Saber como os índices funcionam te ajuda a entender por que algumas queries são lentas e como deixar elas mais rápidas.

Além disso, é importante saber qual índice usar. Pra busca por intervalos, o B-TREE é o ideal. Pra arrays ou JSONB — GIN. Se escolher o índice errado, o banco pode ficar mais lento.

Exemplos reais

Bora ver como os índices ajudam no dia a dia.

Índice pra ordenação

CREATE INDEX salary_idx ON employees (salary);
SELECT * FROM employees ORDER BY salary;

Com o índice B-TREE, o PostgreSQL pode devolver os dados já ordenados direto do índice, sem precisar ordenar depois.

Índice pra intervalos

CREATE INDEX price_idx ON products (price);
SELECT * FROM products WHERE price BETWEEN 100 AND 500;

O índice B-TREE deixa fácil achar as linhas que tão dentro do intervalo pedido.

Perguntas comuns e pegadinhas

Por que nem sempre vale a pena usar índices? Índices ocupam espaço no disco e deixam as operações de insert, update e delete mais lentas, porque a estrutura do índice precisa ser atualizada. Então, é importante criar índices só pras colunas que tu usa bastante nas queries.

Quando os índices não ajudam? Pra queries que pegam quase a tabela toda (tipo, WHERE true), o PostgreSQL prefere o Seq Scan, porque ler os nós do índice não traz vantagem.