Níveis de índices no SQL Server

Olá Pessoal,

No post de hoje resolvi falar um pouco sobre os Níveis de Índices, tentar explicar o que acontece dentro do SQL Server. Espero que tire pelo menos algumas dúvidas sobre o assunto. Divirtam-se !!

Níveis de índices

Todos aqueles que já estudaram um pouco do conceito de índices sabem que a estrutura utilizada pelo SQL Server para construir e manter os índices é a chamada B-Tree. O conceito de uma B-Tree já está bem definido no seu próprio nome que quer dizer “árvore balanceada”. Você jamais encontrará uma B-Tree sem ser simétrica, ou seja, o mesmo número de páginas contidas na parte esquerda será o mesmo da parte direita. Veja na figura abaixo:

O primeiro nó da árvore é chamado de root node. O último  nível é chamado de Leaf Level e entre o root node e o leaf level temos o nível intermediário(intermediate level).

Os níveis raiz e intermediário do índice são construídos pegando a primeira entrada de cada página no nível abaixo, junto com um ponteiro para a página de onde o valor de dados veio.

O numero de níveis de um índice e o número de páginas dentro de cada nível de um índice são determinados por matemática simples. No SQL Server, uma página de dados possuem 8.192 bytes de tamanho dos quais podem ser usados para armazenar até 8.060 bytes de dados. Com base nessa informação e sabendo o tipo de dados você pode calcular o número de linhas por página que são armazenadas utilizando apenas cálculos simples.

Para exemplificar isso que estou falando suponhamos que você quer construir um índice em uma coluna do tipo INT. Lembrando que o tipo INT utiliza 4 bytes para armazenamento ou seja cada linha da tabela exigirá 4 bytes para guardar no índice.

Se a tabela que possuímos armazenada no nosso banco possui 1.500 linhas de dados, você precisará de 6.000 bytes. Mas como??  Veja o cálculo que é feito:

1.500 linhas x 4 bytes = 6.000 bytes

Como eu disse anteriormente é SIMPLES! Diante dessa informação podemos afirmar que todas as entradas caberiam em apenas uma única página de dados, pois ainda temos 2.060 bytes para completar os 8.060 que temos direito. Esse índice seria tanto a página raiz como a pagina folha. Na realidade a nossa página de dados pode armazenar até 2.015 linhas e ainda assim alocar penas uma página para o índice. Isso por que:

 2.015 linhas x 4 bytes = 8.060 bytes (uma página tem exatamente 8.060)

Mas o que iria ocorrer se eu adicionasse mais uma linha? Uma coisa é certo, passaríamos a ter 2.016 linhas, porém o que mais aconteceria?

Todas as entradas não caberiam mais em uma única pagina. Nesse momento vai acontecer um processo chamado page splitting (divisão de página) . Duas páginas adicionais serão alocadas para o índice, a página raiz existente é empurrada para baixo na estrutura para se tornar uma página do nível folha. O SQL Server pega metade dos dados da página de índice e os coloca em uma das páginas recentemente alocadas. A outra página nova é alocada no topo da estrutura do índice para se tornar a nova página raiz.

A última etapa do processo é pegar a primeira entrada em cada uma das páginas de nível folha e gravar as entradas na página raiz recentemente criada. Agora você tem um índice com uma página raiz e duas páginas de nível folha. Esse índice não precisa de um nível intermediário, pois a página raiz pode conter todos os valores no inicio das páginas de nível folha. Nesse ponto, localizar qualquer linha na tabela exige percorrer exatamente duas paginas no índice.

Você pode continuar a adicionar linhas na tabela, sem afetar o número de níveis no índice, até atingir 2.015 páginas, ou seja, 4.060.225 linhas.

1 página              ————————–    2.015 linhas

2.015 páginas   ————————–    x linhas

x = 4.060.225 linhas.

A página raiz terá 2.015 entradas correspondente à primeira linha em cada uma das páginas do nível folha. Portanto para o SQL Server encontrar qualquer linha dentro das 4.060.225 linhas da tabela, seria necessário ler exatamente duas páginas. Quando a 4.060.226 linha de dados é adicionada na tabela, outra página precisa ser alocada para o índice no nível folha, mas a página raiz não pode conter 2.016 páginas, pois isso faria exceder os 8.060 bytes permitidos.

Desse modo o SQL Server passará novamente pelo processo de divisão de página. A página do nível raiz anterior se torna uma página do nível intermediário, com uma segunda página alocada no nível intermediário. A antiga página raiz sofre uma divisão de página para mover metade das entradas para a página de nível intermediário recentemente alocada e a primeira entrada em cada uma das duas páginas de nível intermediário é gravada na página raiz recentemente alocada.

Como você pode ver esse tipo de estrutura permite que o SQL Server localize linhas em tabelas grandes rapidamente. Espero ter conseguido ajudá-los a entender um pouco mais sobre índices.

Até a próxima!!