Indices (o poder da busca). Parte I

    Para falarmos dos indicies primeiramente precisamos entender a estrutura de busca de um SGDB à informação.
     A estrutura de busca por indicies das principais ferramentas de SGDB do mercado usa uma arquitetura de busca mais conhecida com B-Tree. 
     A arquitetura de busca B-Tree se baseia em um conceito de paginas de alocação de dados.
Vejamos a figura abaixo:

   
Nota-se claramente que temos 3 níveis, dai o nome B-TREE. Cada nível tem a denominação:

     Primeiro nível: Raiz;
     Segundo nível: Intermediário;
     Terceiro nível: Folhas.

      Em especial no SGDB SQL Server, cada página pode possuir até 8.060 Bytes de dados.
      Se guardarmos um valor de índice INT, (lembrando que para coluna de valor  INT são alocados 4 Bytes), teremos uma conta simples: 8.060 / 4 = 2.015 linhas que será armazenado em cada folha. Caso ultrapasse este valor, 2.016 linhas serão alocadas mais uma folha e a distribuição dos dados entre elas como podemos ver observando a figura de baixo para cima os valores de 1 a 500.

      Na primeira folha foi alocado 1 a 250, quando necessitou do alocamento do valor 201, subitamente quebrou-se a quantidade de dados suportados por uma pagina (8.060 Bytes), assim sendo, foi-se necessário adicionar mais uma pagina de dados para alocar o valor 251. Logo acima, foi criado mais um nível contendo as entradas para os níveis subsequentes. Como se fossem ponteiros onde teremos o ponteiro para o lado esquerdo informando: "Ei, do meu lado esquerdo temos os valores de 1 até 250, e do meu lado direito temos os valores de 251 em diante".. E assim sucessivamente.
  
      É muito difícil de que um SGDB tenha dados suficiente de índice para montar os três níveis, pela simples conta:
      Se cada nível pagina de folha consegue alocar 2.015 entras, ou seja, no nível abaixo temos para cada pagina podemos alocar 2.015 folhas temos a multiplicação de 2.015 folhas por 2015 entradas de dados do nível acima, dando o valo de 4.060.255. Ou seja, só é necessário apenas duas paginas para encontrar qualquer dado entre 1 a 4060255 linhas em uma tabela. "Isso mesmo, apenas duas paginas para 4 milhões de linhas".

     Este tipo de estrutura permite que o SGDB encontre linhas em tabelas extremamente grandes muito rapidamente.
     Como podemos notar a estrutura B-Tree de índices funciona praticamente como índice de um livro ou dicionário. Você abre o começo do livro, procura pela palavra/assunto que deseja e verifica a pagina que está palavra/assunto está. É muito mais ágil do que percorrer todo livro em busca da palavra/assunto que lhe convém.

Próximo post continuaremos com Índices e seus tipos.
Até..