Banco de Dados - Arvores

Índices e Arvores B-Tree – Banco de Dados

O que é o BTree ?
A tecnologia BTree é 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 porquê surgiu o BTree.
Quais as vantagens do BTree ?
A resposta a essa pergunta é fácil, porém não muito didática. No entanto, tentarei ser bem simplista no exemplo a seguir, e me perdoem aqueles que já conhecerem o algoritimo.
Vamos à 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 si. 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 "Árvore" e que nesta árvore existam vários galhos (ramos) e folhas, estes galhos são chamados de "nós" que nada mais são do que uma ramificação de uma informação; as folhas desses "nós" são blocos contendo referências à vários registros ou outros índices. Esta é uma estrutura de índice Btree.
Além disso, os índices BTree mantém-se atualizados com informações lógicas com todas as informações gravadas no banco de dados o que permite ao banco de dados distinguir dados que possuem algum nexo entre si dos que não possuem, dividindo-os em "nós" lógicos e "folhas" que serão apreciados pelo algoritmo BTree.
Dados com algum nexo entre si podem ser guardados num único "nó", ou dependendo do nexo que há, podem ser providos outros "nós" acima ou abaixo