O banco de dados Firebird, assim como a maioria dos banco de dados cliente/servidor no mercado baseiam-se num algorítimo de pesquisa que é chamado de BTree ou "arvore binária", esse algorítimo revolucionou a forma de como localizar informações dentro de um arquivo gigante de dados.
Vamos tentar entende-lo
um pouco ?
A palavra BTree (Binary
Tree) significa "arvore binária" que é uma espécie de índice
que permite uma busca rápida em gigantescas bases de dados, praticamente
todos os bancos de dados SQL baseiam-se nesse padrão de buscas. É
muito interessante que você entenda este conceito, pois ele não somente
é aplicável ao Firebird como irá lhe ajudar a compreender aspectos
de performance em qualquer banco de dados.
Vamos a um pouquinho de história, sei que a muitos detestam essa parte, mas
ela é realmente é necessária para entender porque surgiu o
BTree.
Depois que os velhos ENIAC foram aposentados, logo surgiria uma
nova aplicação para o computador que não fosse para fins militares
: armazenamento de dados, ou simplesmente apelidados de banco de dados. Desde então,
os computadores não pararam de evoluir, na realidade essas evoluções
eram empurradas pela demanda por aplicações de banco de dados.
As indústrias de hardware para computador evoluiram rápidamente seus
produtos, um exemplo disso foram os fabricantes de discos magnéticos que
aumentavam a capacidade de armazenamento em curtissimo período e não
demorou muito tempo para que tais fabricantes tornassem o armazenamento de dados
algo de tamanho ilimitado, isto é, acrescentava-se novos discos vazios e
a capacidade de armazenamento dos bancos de dados aumentava.
Mas também não demorou muito até que alguns começaram a notar que os sistemas baseados em banco de dados estavam cada vez mais lentos, obviamente notou-se que isso ocorria a medida que acumulavasse ainda mais informações. Essas "lentidões" eram notadas principalmente em pesquisas, não havia lentidão por exemplo, quando necessitava-se de novas inclusões, o que apenas aumentava o problema : rápido para incluir, lento para pesquisar o que acabou de incluir.
Foi gratificante ver que a indústria de software não
demorou muito para responder a este tipo de problema, a demora nas pesquisas foram
resolvidas com um conceito bastante prático e que é usado ainda nos
dias de hoje : uso de índices associado à tabelas, também
conhecídos como flat-tables por sua característica linear de armazenar
dados como se fosse uma planilha de linhas e colunas.
A idéia de usar índices começou a fomentar a indústria
de software, e abriu-se as comportas para uma nova geração de banco
de dados : Banco de dados relacionais.
- Com o conceito relacional podia-se procurar por um número de seguro-social e não somente descobrir o nome do titular, mas também de dependentes relacionados a este mesmo número.
Oque a indústria de software conseguiu com isso ? Basicamente duas coisas :Com tantas novidades, era natural que os banco de dados fossem se tornando cada vez mais dependentes de hardwares mais rápidos e confiáveis para resolver pesquisas em base de dados cada vez maiores.
A indústia de hardware e software prosperava como nunca antes !
Porém, não demorou muito tempo para que as pesquisas em bases de
dados fossem se tornando lentas, mesmo usando o conceito de indices.
A razão disso era fácil descobrir, mesmo usando tais indices, os hardwares
da época eram lentos para executar pesquisas em bases de dados tão
grandes.
Por muito tempo esse problema permaneceu sem solução, e então foram sendo criadas soluções criativas para aliviar a situação. Uma dessas idéias tão criativa foi a idéia de usar um arquivo morto-digital. Os programadores criavam sistemas que permitissem transferir dados antigos e pouco acessados para uma outra base de dados e consequentemente a base de dados original ficaria com o seu tamanho reduzido, o que ganharia com isso ? Simplesmente em razão do tamanho reduzido da base de dados a performance permaneceria a mesma de outrem. Essa idéia foi tão bem sucedida que mesmo hoje ainda é utilizada em flat-tables.
Foi apenas em 1.979 que a indústria de software conseguiu resolver o problema para base de dados que não paravam de crescer. Conseguiram aplicar uma formula matématica algorítimica criada em 1.972 por alguns ciêntistas matématicos duma universidade renomada, essa fórmula algorítimica é chamada de BTree, ou arvore binária, essa formula cria uma lógica diferente para o uso de índices de forma a tornar as pesquisas rápidas em banco de dados gigantescos.
Assim nasceu o BTree, uma solução que não apenas resolvia o problema com software de banco de dados, como apresentava um algorítimo muito melhor para ser praticado aos mais diversos dispositivos de hardware : memória, disco, processadores,...
A resposta a essa pergunta é fácil, porém não muito
didática para explicar.
No entanto, tentarei ser bem simplista no exemplo a seguir e me perdoem aqueles
que já conhecerem o algoritimo.
Vamos a um banco de dados com tabelas usando índices comuns (não
BTree), digamos que exista uma tabela com 150 registros.
Para encontrar um único registro dentro dessa tabela serão necessários
dois acessos físicos : um para o índice e outro para a tabela em sí.
Não importa o tamanho da tabela serão sempre dois acessos, um para
o índice e outro para a tabela, essa é a regra para flat-tables com
índices comuns.
Num índice Btree, vamos chamar o banco de dados de "Arvore" e que nesta
arvore existam vários galhos(ramos) e folhas, estes galhos são chamados
de "nós" que nada mais é do que uma ramificação de uma
informação, as folhas desses "nós" são blocos contendo
referencias a vários registros ou outros índices, essa é uma
estrutura de índice Btree. Além disso, os índices BTree mantem-se
atualizado com informações lógicas com todas as informações
gravadas no banco de dados que permite o banco de dados distinguir dados que possuem
algum nexo entre sí dos que não possuem, dividindo-os em "nós"
lógicos e "folhas" que serão apreciados pelo algorítimo BTree.
Dados com algum nexo entre sí podem ser guardados num único "nó", ou dependendo do nexo que há, podem ser providos outros "nós" em cima ou abaixo deste. Lembrando que nesses "nós" existem "folhas". É como se houvesse um livro (arvore) com tópicos (nós) e sub-tópicos (sub-nós) que contém o assunto (folhas) em uma única página, várias páginas (ou vários registros) ou então referencias a outros tópicos (em diferentes "nós" ou até mesmo "índices").
É interessante saber que esses "nós" são inteiramente lógicos e nada tem a ver com o formato interno de arquivo que o seu banco de dados utiliza. Cada banco de dados, seja ele Firebird, Oracle, Sybase, Postgre possuirá seu próprio formato interno de arquivo que utilizará o algoritimo BTree em suas pesquisas. Por isso quando alguns falam de BTree com banco de dados, dizem "índices BTree" porque apenas "Btree" refere-se a um algorítimo, e "índices BTree" referem-se a índices usando o algorítimo de arvore binária (BTree).
Uma curiosidade interessante é dizer que nem sempre índices BTree
são mais rápidos do que os índices comuns. Como assim, talvez
voce me pergunte ?
Como foi dito, num índice comum temos sempre dois acessos físícos
: um para pesquisar o índice e outro para encontrar o registro na tabela.
Numa base de dados com índices BTree não existem tabelas na forma que conhecemos em flat-tables, existem apenas "nós", e esses "nós" podem representar uma tabela inteira ou apenas uma parte da informação, mas o importante é que o "nó" sempre possuirá algum nexo com os "nós" acima dele ou os "nós" e "folhas" abaixo dele. Portanto, para procurar o mesmo registro nessa arvore com apenas 150 registros poderiam ser feitos de 4 até 20 acessos físicos dentro de um banco de dados usando índices BTree, isto é, será um acesso físico por cada "nó" alcançado até que o registro seja encontrado. Trocando em míudos, uma base de dados pequena usando índice BTree possui quantidade de acessos físicos bem superior a índices comuns, a vantagem do BTree está apenas sobre enormes bases de dados. A seguir vamos explanar esse assunto melhor e ver as diferenças entre o índices BTree e índices comuns.
Na realidade um índice BTree não tem nada a ver com os índices usados em flat-tables (paradox, access, dbase,...), nos flat-tables os índices são lidos sequencialmente embora possa haver váriações. Num índice BTree, a complexidade é muito maior, porém muito melhor como poderemos var mais adiante.
Em flat-tables comuns, os índices podem ser externos ao arquivo de dados
ou internamente. Quando de forma interna, como no caso do access, existem terminadores
internos que determinam separação de workspaces separados para cada
objeto, é como arquivos compactados que podem trazer dentro de sí
outros arquivos, eles podem parecer um arquivo único vistos por fora, mas
por dentro há uma separação interna de tabelas e índices.
Já nos banco de dados SQL, não existe uma forma única de apresentar
tabelas e índices, mas que em geral podem ser :
- Um arquivo separado por objeto do banco de dados (como no Postgre);
- Todos os objetos de um mesmo "database" num único arquivo sem workspaces
internamente (como no Firebird) ;
- Todos os "databases" dentro de um único arquivo (que passa a chamar-se
"device") e cada database com seus próprios objetos (como no SQLServer).
Quando todos os objetos são armazenados num mesmo database (ex.: Firebird),
ou varios databases num único device (Ex.: SQL Server) o grau de complexidade
do formato interno de arquivo aumenta muito, deveras a maioria das informações
acabam misturadas dentro do banco de dados e só podem ser distinguidas uma
das outras através das informações lógicas armazenadas
em tabelas de sistemas. Nestes bancos de dados, as tabelas de sistemas que armazenam
dados lógicos sobre todos os objetos do banco de dados são uma parte
vital, pois se elas forem perdidas ou corrompidas, todo database ou device não
passa de apenas lixo, pois não há como distinguir, por exemplo dados
de fornecedores com os dados de clientes, pois esses dados se misturam dentro de
um único arquivo ou device e essa é uma grande diferença para
os índices comuns que não podem trabalhar com este grau de complexidade,
já para os índices BTree...
Uma outra diferença é que com índices comuns sempre há uma pesquisa sequencial dentro de um arquivo de índice até encontrar o chave procurada. Devido a esse procedimento quanto mais para o final do índice a chave procurada estiver, maior será o tempo de localização. Por isso, os programadores criam dois índices "ascendente" e "descendente" para facilitar pesquisas com campos do tipo data, para realizar buscas nos dois sentidos. Apesar da idéia ser boa, sempre requer criação de índices extras.
Já em bases com índices BTree, as informações são dispostas de forma diferente, cada tipo de informação é pesquisa aprofundando-se nos "nós" (Depth nodes) que possuem alguma semelhanca (seletividade) com o item a ser pesquisado. De fato, pode-se aprofundar em "nós" até um ponto máximo e será nesse ponto máximo que estará os limites onde efetuar-se-à pesquisa. Percebeu a diferença ? Não há necessidade de varrer um índice inteiro, apenas uma parte do índice.Trabalhando com flat-talbles com índices comuns somos obrigados a separar informações semelhantes em tabelas diferentes apenas para não acumular dados em excesso numa única tabela e assim prejudicar a performance do sistema.
Usando o banco de dados SQL com índices BTree não existe divisão interna tal como existe em flat-tables, como no BTree haverá "nós" de buscas, não fará muita diferença separar dados em tabelas diferentes se ambas estiverem no mesmo banco de dados. Isso apenas aumentará o grau de complexidade na hora de aplicar os JOIN's.
Na realidade, só poderá haver divisão de tabelas separadas
em bases BTree se houver algum ganho racional nisso, é o caso por exemplo
de dividir tabelas que aplicariam quantidade de índices diferentes se a tabela
fosse separada uma da outra, ficou nebuloso ? Vou dar-lhe um exemplo :
Todos devem saber que uma tabela de followup's cresce assustadoramente de tamanho
e que em geral são divididos em duas etapas : agendar followups (insert)
e realizar followups(update). Se ambas as etapas forem armazenadas numa única
tabela, o que ocorreria ?
Vejamos...relatórios e consultas de followup em geral são feitas de
tudo quanto é maneira : pesquisa por data, atendente, cliente, ... então
deveríamos ter vários índices associados a tabela de followup,
certo ?
Mas com tantos índices associados a tabela de followup, o que ocorreria com
os agendamentos, que são basicamente inserts ?
Também ficariam lentos, pois para cada INSERT todos os índices associados
a tabela de followups precisariam também ser atualizados.
Então nesse caso, separar em duas tabelas diferentes e para cada tabela os
seus respectivos indices seria a melhor maneira, e com o uso de uma "view" (visão)
poderíamos ver ambas as tabelas como se fossem apenas uma única tabela
desde que ambas estejam com relacionamento de "1 para 1".
Percebeu ? Usando a racionalidade num banco de dados, o que podemos chamar de "normatização", todos os problemas fazem parte de uma lógica a ser resolvida que determinará ou não a divisão de tabelas.
Um banco de dados com gigabytes de informações com uma pesquisa usando BTree será resolvida da seguinte forma : percorrerá os "nós" dentro do índice e cada "nó" alcançado separará fisicamente dados que não estejam dentro de uma "seletividade" até atingir uma profundidade máxima, será nessa profundidade máxima que estabelecerá os limites para a pesquisa. A palavra "seletividade" pode confundir alguns, porém "seletividade" é apenas o termo que usamos quando algum "nó" possui algum nexo, isto é, semelhança ou aproximação com o que estamos procurando.
O esquema abaixo exemplifica como será feita uma pesquisa, usando um exemplo
de "nó" e "seletividade", siga o esquema :
1) Vamos a uma tabela com 10.000 linhas, quero a linha com elemento de número
51 (boa idéia) :
2) Database com 10.000 linhas será submetido a uma pesquisa em arvore-binária
(BTree-Search) :
|
database com 10.000 linhas |
3) 10.000 linhas é
muita coisa para pesquisar, então dividimos em 8 nós, ou pedaços
:
| 0 ao 1.250 |
1.251
ao 2.500 |
2.501
ao 3.750 |
3.751
ao 5.000 |
5001
ao 6.250 |
6251
ao 7500 |
7501
a 8.750 |
8.751
ao 10.000 |
4) Dos oito "nós" que vemos acima, se estou procurando o elemento número 51, então só há um "nó" com seletividade : "0 ao 1.250". Outros "nós" são descartados.
5) Entre "0 e 1.250"
ainda há muitas linhas, quebra-se novamente em 8 "nós" :
| 0
ao 156 |
157
ao 313 |
314
ao 470 |
471
ao 627 |
628
ao 784 |
785
ao 941 |
942
ao 1.098 |
1.099
ao 1.250 |
6) Das opções acima, o único nó com seletividade é "0 até 156", porém ainda existem muitas opções, novamente este "nó" será quebrado em 8 partes :
| 0
ao 19 |
20
ao 39 |
40
ao 59 |
60
ao 79 |
80
ao 99 |
100
ao 119 |
120
ao 139 |
140
ao 156 |
7) O algoritimo btree aprofundou-se até determinar os limites exatos em que se baseará a pesquisa, no exemplo acima, o elemento número 51, estará no "nó" que atende a região "40 ao 59" que passa a ser uma folha de nossa maravilhosa arvore. Este foi o fim da pesquisa binária, a partir deste ponto o banco de dados prossegue normalmente com a busca, porém apenas na "folha" indicada que possui apenas 19 linhas (40 ao 59). Isso é muito mais vantajoso do que realizar a busca de 1 entre 10.000 linhas como seria usando um índice comum.
8) Nesse exemplo acima, foram 3 acessos no índice BTree e mais um 1 acesso para determinar a linha correta com o elemento número 51, no total foram 4 acessos físicos. Note a semelhança duma arvore binária :
O exemplo acima foi
apenas didático, o btree não vai dividir o seu índice sempre
em 8 "nós", na realidade os dados já estão logicamente armazenados
como arvore binária em seus índices, não há necessidade
de buscar e dividir, apenas aprofundar nos diversos "nós" até que
a seletividade termine.
Usando o banco de dados Firebird podemos saber a quantidade de "nós" existentes num índice por usar o aplicativo IBConsole no seu menu de estatísticas acessando Database->Maintenance->Database Estatistics e repare que nos índices usado por suas tabelas aparece uma frase semelhante à :
"Depth: 1, leaf
buckets: 1, nodes: 94" que traduzido quer dizer : "Profundidade:
1, objetos folha: 1, nós: 94"
Estes 3 valores juntos
determinam o balanceamento de nosso índice BTtree. Por que eu estou dizendo
isso ?
Porque o índice BTree pode perder o "balanceamento" - Como assim perder "balanceamento",
talvez você diga.
Acontece que dependendo do uso duma tabela, com o tempo o índice BTree vai
possuir tantos "nós" que alguns deles poderiam ter atalhos menores ou então
pior haveria "nós" completamente desnecessários apenas inchando o
seu índice BTree. Isso ocorre porque o BTree em razão de sua característica
de arvore, a exclusão de registros dentro de uma arvore binária dar-se-à
apenas de modo lógico, pois se fosse uma exclusão de modo físico
então todos os "nós" e "seletividades" dentro índice BTree
teriam de ser novamente re-alinhados o que causaria grande perda de performance.
Isso não é apenas com o Firebird, mas com qualquer banco de dados
SQL que utilize índices BTree. Em razão desse inchaço, o re-balanceamento
torna-se necessário em algumas circunstâncias.
É por esta razão que o próximo sub-tópico tratará
de como melhorar o balançeamento em arvores binárias no Firebird.
Finalmente é
neste ponto do artigo que vamos abordar um assunto que é exclusivo do firebird
(ou interbase), vamos à uma pequena dica para melhorar o balanceamento de
seu índice BTree. Apenas 3 comandos são necessários para recompor
tais índices :
Nota : Os comandos abaixo devem ser executados de preferencia com somente você usando o Firebird devido a demora que eles levam para completar a operação.
ALTER INDEX nome_do_indice
INACTIVE;
Vamos desativar temporáriamente o indice
de nossa tabela, com isso o índice ficará marcado como "off-line"
em nosso banco de dados.
Ninguém acessará mais este índice
até que voce coloque-o em "on-line" novamente.
ALTER INDEX nome_do_indice
ACTIVE;
Ops! enganamos o Firebird, pois vamos
re-ativar o índice em seguida. Isso é necessário, porque o
Firebird só reconstroi um índice no momento de sua ativação,
isto é, quando um índice tem de passar para o estado de "on-line".
É na reconstrução que uma nova arvore será criada com
novos "nós" e "folhas" .
SET ESTATISTICS
INDEX nome_do_indice;
A linha acima irá recalcular a
estatistica no índice, produzindo novas e melhores "seletividades".
Esta dica é
especialmente útil para aqueles que já por muito tempo usam o banco
de dados sem nunca ter precisado re-balancear seus índices. De fato, essa
opção deveria ser pouco utilizado, porém sempre existem aqueles
maníacos por performance. Essa informação de como re-balancear
os índices também é importante porque muitos aprenderam que
isso só é possivel através dum backup/restore e acabam fazendo
isso períodicamente.
Com o backup tudo bem, além de guardar uma cópia de segurança,
limpa o banco de dados de coisas que já foram enviadas para a lixeira há
muito tempo e isso consequentemente melhora a performance.
Mas o Restore !? Como voce deve saber, o restore do Firebird segue a seguinte
consequencia :
É na re-criação dos índices que o próprio Firebird
recriará também um índice BTree novo, consequentemente um balanceamento
da arvore melhorada.
Mas voce não vai fazer um "Restore" todos os dias só para ter um balanceamento
novo todo dia, vai ?
Se voce for como eu, que não pode restaurar 2 a 4GB de dados só para
ter uma balançeamento inédito todos os dias, então usufrua
das 3 linhas acima que detalhei, ela é muito mais prática que "Restore"
períodicos. Até porque um índice BTree demora muito tempo para
perder seu balanceamento, e seu balanceamento pode ser feitos por tabelas individualmente,
pois não são todas as tabelas que precisam de balanceamento, tabelas
que por exemplo, nunca existe exclusão raramente precisará de um balanceamento.
Mais uma vez peço
desculpas pela simplicidade do com que detalhei um assunto tão profundo,
mas este foi o melhor modo para que aqueles que não entendem o que é
Btree pudessem entender do assunto, afinal de contas se eu explicasse de uma forma
:
para calcular a profundidade dos "nós" numa arvore
binária ou então outras formulas mais complexas para calculo de seletividade,
então certamente poucos entenderiam, e na realidade devemos nos preucupar
menos com este assunto, pois o que importante é que algorítimo funciona
!