Estrutura B-Tree

Antes de começarmos a falarmos de índice no SQL, devemos primeiro entender a sua utilidade e o conceito de B-tree. O índice foi introduzido no SQL para facilitar as consultas à base de dados. Isso porque muitas vezes em tabelas com uma grande quantidade de registros, o processamento das consultas era muito demorado.

Compreendido de forma simples a utilidade dos índices, vamos botar a mão na massa e explicar como os índices são organizados.

· Como os índices são organizados?

Tanto o índice clusterizado como o índice não-clusterizado se baseiam na estrutura conhecida com B-Tree.

Entendendo o B-Tree:

Na figura acima, vocês podem observar de forma simplificada o funcionamento de uma estrutura B-Tree. Imagine que existe no seu banco de dados 2000 números cadastrados, que variam de 1 a 2000. (Não que isso tenha alguma utilidade, mais só a titulo de exemplo).

Dessa maneira, o SQL inicialmente alocaria todos os números em uma página (Lembrando que o conceito de página foi tratado no post anterior). Como sabemos uma página comporta até 8168 bytes, sendo que apenas 8060 estão reservados para armazenar os dados, já que o restante é reservado para guardar informações relativas à localização da página. Sendo assim, vamos pensar.

Se um dado do tipo INT ocupa 4 bytes de memória, poderíamos armazenar até 2015 linhas nesta página (já que 4 * 2015 = 8060 bytes), caso contrário o espaço não seria suficiente para que todos os dados ficassem armazenados dentro da página. Caso tivéssemos 2016 registros na nossa tabela do tipo INT, uma página não comportaria todos os dados, dessa forma seria necessário realizar uma divisão de páginas. Neste caso, a página que alocava todos os dados inicialmente (Nível Raiz), será deslocada para o nível folha, sendo que seria necessária uma outra página no nível folha para que metade dos dados da primeira página se “transportasse” para outra (Assim dessa maneira cada página possuiria 1.023 linhas, m o que não ultrapassaria os 8.060 bytes por folha). Também seria necessário alocar mais uma página no nível Raiz de maneira que o nível raiz contivesse os primeiros registros do nível folha (No caso, dois).

Observe que em nenhum momento eu mencionei o nível intermediário. Uma página de nível intermediário só seria criada se, no nível Raiz existem 2016 registros e a página de nível Raiz precisasse sofrer divisão de páginas.

Entendido o funcionamento básico do B-Tree e os conceitos de divisão de páginas e nível raiz, intermediário e nível folha, voltemos à figura. No caso, a figura possui os três níveis (Raiz, intermediário e Folha) Caso eu quisesse localizar o número 1056 na minha tabela, o SQL percorreria o nível raiz e verificaria que o número 1056 está entre os números 1000 e 1500, então ele percorreria apenas a página que contém valores de 1000 a 1500. No nível intermediário ele verificaria que o número 1056 está entre os números 1000 e 1250 então ele percorreria a página no nível folha que iniciasse por 1000 e localizaria o registro.

No outro post, falarei sobre os tipos de índice no SQL.