Posted onOct 19, 2023

Schemas em SQL: Indexes e B+ trees

#mysql #database #sql #algorithms

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

O que sãoindexes e como eles são usados paraoptimizar 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 simComputer Science.

2. O que são indexes

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

Quando pensamos em criarindex 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 paraacelerar as consultas e melhorar o desempenho, mas não deve criar muitos índices desnecessários, pois isso podeaumentar 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 osindexes existentes.

Então como sei quais index criar? Para criar seus indexes é preciso olhar paraqueries que pretende executar, para montar um bomschema olhamos para os dados que vamos armazenar, já para bonsindexes olhamos para asqueries 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 é aB+Tree, antes de entendermos ela precisamos compreender aB Tree.

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

AB Tree diferente aBinary Tree permite que armazenemos mais de um valor por nó, como na imagem de exemplo onde o primeiro nó tem 2 valores20 e o40 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 dasbuscas optimizadas que o banco faz, é uma estrutura derivada dasBTrees, 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 embancos de dados como MYSQL esistemas de arquivo como FTP.

A principal diferença de estrutura das duas é que aB+ os dados são armazenados apenas nas folhas(Nós finais, que não tem filhos), e seus nós internosarmazenam ponteiros para os filhos e suas folhas são umalinked list facilitando assim uma busca sequencial de valores se adequando bem melhor para o contexto de bancos de dados, já aB 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 umuser baseado no nossowhere ?

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

Executando isso o SQL vai criar um index para esse campo

CREATEINDEXidx_nameONusers(name(255));

Agora se a colunaname tiver um index executando a mesma busca será feita de uma forma mais optimizada, buscando na estrutura daB+Tree que o mysql montou com os seus dados, conseguimos identificar isso com o valorref no campotype que oEXAPLAIN nos retorna.

Podemos encontrar esse registro com somente3 etapas.

5. Conclusão

Com isso podemos concluir que buscar usandoindex são bem mais optimizadas, pois são feitas em uma estrutura de dados separada da sua tabela chamadaB+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.