Árvore B
Árvore B foi criada por Rudolf Bayer e Edward M. McCreight no artigo intitulado “Organization and Maintenance of Large Ordered Indexes” no Boeing Scientific Research Labs (1970).
O foco principal das árvores B era resolver o problema de busca eficiente em grande conjuntos de dados, minimizando a quantidade de acessos ao disco durante as operações de busca, inserção e remoção.
Uma árvore B é uma estrutura de dados balanceada que organiza dados hierarquicamente.
Seus nós são chamados de páginas, podendo ser internos ou folhas. As folhas são chamadas de páginas externas, enquanto os nós intermediários são páginas internas.
Principais características:
- Cada página pode conter várias chaves, que são sempre ordenadas de forma crescente.
- Um nó interno com (k) chaves possui até (k+1) filhos, ligados por ponteiros:
- Ponteiro à esquerda: aponta para uma página com chaves menores.
- Ponteiro à direita: aponta para uma página com chaves maiores.
- Todas as folhas estão no mesmo nível, garantindo um balanceamento perfeito da estrutura.