Acho que você tem a criação da sua página de cabeça para baixo. Quando um nó é dividido, ele não cria mais nós na hierarquia (nós filhos na sua nomenclatura). Em vez disso, cria mais para cima , em direção à raiz. Como o livro diz
Observe que o crescimento está no topo da árvore, e essa é uma característica intrínseca de uma árvore B para garantir as propriedades importantes de que ela sempre tem todas as folhas no mesmo nível e que cada nó diferente da raiz é pelo menos 50% completo.
(Minha ênfase.)
No e-book vinculado:
Definição 5.1 AB - árvore da ordem m (m ≥ 3) ... cada nó contém no máximo m - 1 chaves
O exercício é para m = 3, portanto, no máximo 2 chaves por nó.
As duas primeiras chaves são fáceis - elas entram na primeira página:
A:[1,2]
Vou usar arte ASCII. Vou rotular cada página na sequência em que foram criadas e mostrar as chaves / ponteiros dentro da página. Portanto, a página P contendo os valores-chave k1 e k2 será P:[k1,k2].
Agora a chave 3 aparece. De acordo com a Seção 5.2.1 ... Inserção, a primeira tarefa é pesquisar. Isso determina que a chave 3 deve estar na página A - a única página que temos. Além disso "se [esse nó] estiver cheio, ele será dividido em dois nós". A página está cheia e deve ser dividida. Agora temos
A:[1,2] B:[3, ]
Mas isso não é uma árvore! Como o livro diz:
o ponteiro para [o novo nó], .. é inserido no nó pai .. do [nó atual], repetindo a operação de inserção nesse nó [isto é, o nó pai]. Esse processo de divisão e movimentação pode continuar, se necessário, até a raiz e, se for necessário dividir, um novo nó raiz será criado.
(Minha ênfase em mostrar o processamento continua na árvore em direção à raiz, não nas folhas.)
Portanto, devemos colocar um ponteiro para a nova página (B) no pai da página atual (A). Deve haver um novo nó raiz:
C:[2,3]
/ \
A:[1,2] B:[3, ]
Eu tenho os ponteiros em páginas que não são folhas, apontando para o valor mais alto em um nó filho (filho). Seu texto vinculado pode fazer isso de maneira diferente, mas o resultado será equivalente.
O valor-chave 4 chega; seguindo o algoritmo, procuramos encontrar em qual página ela deve estar. Deve ser a página B. Há espaço para isso; portanto, atualizamos essa página e o ponteiro na página C:
C:[2,4]
/ \
A:[1,2] B:[3,4]
Em seguida, inserimos a chave 5. Ela deve aparecer na página B, mas está cheia. Portanto, divide
C:[2,4]
/ \
A:[1,2] B:[3,4] D:[5, ]
Nós devemos atualizar o nó pai. Ele também está cheio e se divide:
C:[2,4] E:[5, ]
/ \ \
A:[1,2] B:[3,4] D:[5, ]
A divisão se propaga e um novo nó raiz se forma:
F:[4,5]
/ \
C:[2,4] E:[5, ]
/ \ \
A:[1,2] B:[3,4] D:[5, ]
Ao crescer para cima, a árvore mantém uma profundidade idêntica em cada ramo. Isso é importante para o desempenho previsível. (Alguns dizem que o B na Árvore B significa "equilibrado" por essa mesma razão.)
Quanto à segunda parte - "É possível inserir os registros com chaves em uma ordem diferente para ter uma árvore de menor altura?" Com 5 chaves e duas chaves por nó, precisamos de pelo menos 3 nós de folha para armazenar todos os valores e uma altura de 3 para formar a árvore. Portanto, meu arranjo é ideal para os dados, sequência e algoritmo fornecidos.
O livro usa um arranjo de ponteiro muito diferente do que eu uso e um arranjo de divisão de página diferente. Isso será significativo, levando a páginas parcialmente cheias. O fato de haver uma seção na página 42 chamada "Carregamento de dados" que mostra como as páginas mais completas podem ser obtidas carregando a sequência de teclas suporta o meu palpite. No entanto, espero ter fornecido indicadores suficientes e você poderá usar a estrutura de indicadores do livro para resolver isso por si próprio.
Eu me deparei com esta simulação interativa de como uma B-Tree cresce.
