Schemas em SQL: Indexes e B+ trees
Tags: mysql, database, sql, algorithms
Published: 2023-10-19 18:21:27

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](#1)
- 2 [O que são indexes](#2)
- 3 [B Tree e B+ Tree](#3)
- 4 [Vamos observar na prática](#4)
- 5 [Conclusão](#5)
- 6 [Referências](#6)

### 1 Prólogo <a name="1"></a>

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 <a name="2"></a>

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 <a name="3"></a>

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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bo4g68okyoe0elfrms1a.png)

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. 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ow409mzr5socc0ywnpiq.png)

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 <a name="4"></a>
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';
```

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0ecmo4pq42mzl9kmcdv3.png)

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 
```sql
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**.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/t2299zfnubhexm3fojj0.gif)

### 5. Conclusão <a name="5"></a>
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 <a name="6"></a>
[B+Tree Wiki](https://en.wikipedia.org/wiki/B%2B_tree) 
[B+Tree Vizualize](https://www.cs.usfca.edu/~galles/visualization/BTree.html) 
[Doc do mysql sobre index](https://dev.mysql.com/doc/refman/8.0/en/mysql-indexes.html)