Árvore B*

Uma árvore B* é uma estrutura de dados na ciência da computação e uma variação da árvore B proposta em 1973 por Donald E. Knuth. Esta apresenta mecanismos de inserção, remoção e busca muito semelhantes aos realizados em árvores B, mas com a diferença em que a técnica de redistribuição de chaves também é empregada durante as operações de inserção. Dessa maneira a operação de split pode ser adiada até que duas páginas irmãs estejam completamente cheias e, a partir daí, o conteúdo dessas páginas irmãs é redistribuído entre três páginas (uma nova criada e as duas páginas irmãs anteriormente cheias). Tal técnica é conhecida como divisão two-to-three split, ou no português divisão de dois para três, que proporciona propriedades diferentes das árvores B na qual utiliza a divisão usual conhecida como one-to-two split. A grande melhoria direta proporcionada por essa abordagem é o melhor aproveitamento de espaço do arquivo, pois, no pior caso, cada página apresenta no mínimo 2/3 do número máximo de chaves que esta pode armazenar, enquanto na divisão usual cada página apresenta, no pior caso, metade do número máximo de chaves.