Indexes e B+ trees qual será a relação dessa engraçada estrutura de dados com nossos queridos indexes do banco?

Conteúdo

• 1 Prólogo
• 2 O que são indexes
• 3 B Tree e B+ Tree
• 4 Vamos observar na prática
• 5 Conclusão
• 6 Referências

1 Prólogo

O que são indexes e como eles são usados para optimizar buscas? quantas vezes já não adicionamos indexes em colunas de tabelas com milhares de registros e magicamente as queries caíram de alguns segundos para milissegundos, nunca foi magica e sim Computer Science.

2. O que são indexes

Index são uma estrutura separada da estrutura dos registros tabela, sendo feita uma cópia de uma parte dos seus dados, que servem como um ponteiro para acessar um registro específico.

Quando pensamos em criar index existe um conceito que podemos seguir "As many as you need, As few as you can get away with", em outras palavras, você deve criar índices suficientes para acelerar as consultas e melhorar o desempenho, mas não deve criar muitos índices desnecessários, pois isso pode aumentar o espaço de armazenamento e a sobrecarga inserções no banco de dados, já que sempre que um registro for inserido vão ser criados também os indexes existentes.

Então como sei quais index criar? Para criar seus indexes é preciso olhar para queries que pretende executar, para montar um bom schema olhamos para os dados que vamos armazenar, já para bons indexes olhamos para as queries estamos executando ou pretendemos executar.

3. B Tree e B+ Tree

Como foi dito os indexes são partes dos seus dados armazenados em uma estrutura diferente, essa estrutura é a B+Tree, antes de entendermos ela precisamos compreender a B Tree.

B Tree é uma estrutura não lineares diferentes de um Array, que somente podemos ir para frente e para trás com as árvores podemos navegar para níveis e subníveis dentro dela.

A B Tree diferente a Binary Tree permite que armazenemos mais de um valor por nó, como na imagem de exemplo onde o primeiro nó tem 2 valores 20 e o 40 permitindo que tenhamos um bloco de valores em cada nó que recebem o nome de página.

B+tree é a estrutura de dados que está por trás das buscas optimizadas que o banco faz, é uma estrutura derivada das BTrees, mas com uma forma diferente de armazenar suas chaves de uma maneira que o processamento sequencial e aleatório de chaves fossem eficientes, sendo bastante usadas em bancos de dados como MYSQL e sistemas de arquivo como FTP.

A principal diferença de estrutura das duas é que a B+ os dados são armazenados apenas nas folhas(Nós finais, que não tem filhos), e seus nós internos armazenam ponteiros para os filhos e suas folhas são uma linked list facilitando assim uma busca sequencial de valores se adequando bem melhor para o contexto de bancos de dados, já a B Tree é mais versátil permitindo um uso em uma variedade maior de contextos.

4. Prática

Vamos observar como uma query usa index para encontrar os dados e como seria essa mesma busca se não usássemos os index.

SELECT * FROM users;  
EXPLAIN SELECT * FROM users WHERE name='Virux';

Como o SQL fez para encontrar um user baseado no nosso where ?

Sem um índice, o MySQL vai ler toda a tabela do início ao fim encontrando os valores desejados, conseguimos comprovar isso observando valor all no campo type que o EXPLAIN nos retorna, ou seja, quanto maior a tabela mais lenta a busca, como Virux é o registro 9 ele precisou ler 8 registros até encontrar o desejado.

Executando isso o SQL vai criar um index para esse campo

CREATE INDEX idx_name ON users (name(255));

Agora se a coluna name tiver um index executando a mesma busca será feita de uma forma mais optimizada, buscando na estrutura da B+Tree que o mysql montou com os seus dados, conseguimos identificar isso com o valor ref no campo type que o EXAPLAIN nos retorna.

Podemos encontrar esse registro com somente 3 etapas.

5. Conclusão

Com isso podemos concluir que buscar usando index são bem mais optimizadas, pois são feitas em uma estrutura de dados separada da sua tabela chamada B+Tree, mas precisamos criar nossos index com cuidado pensando nas queries que pretendemos executar, pois eles afetam diretamente a desempenho das inserções além de aumentar o espaço de armazenamento.

6. Referências

B+Tree Wiki
B+Tree Vizualize
Doc do mysql sobre index