Lorsqu'un noeud d'un arbre B est divisé, les clés du noeud d'origine sont-elles dupliquées dans les nouveaux noeuds? Quel est le but de faire cela? N'est-ce pas inefficace?Les clés des noeuds B-tree sont-elles dupliquées lorsque le noeud est divisé?
Non, il est fait avec des pointeurs. La moitié des pointeurs sont déplacés vers le nouveau noeud.
Bien sûr, il n'y a pas une telle chose comme un 'B-tree'. Il existe une myriade d'implémentations différentes. Je pourrais imaginer un dans lequel les clés sont réellement stockées dans les noeuds, comme un arbre où les clés sont ints. Mais ils ne seraient toujours pas 'dupliqués', juste les données copiées.
Si votre boeuf est le stockage laissé dans le nœud qui obtient divisé, eh bien, c'est un autre choix d'optimisation que pour libérer et réallouer plus petite ou non. Probablement pas, car plus d'insertions pourraient arriver dans la moitié de l'espace clé de ce nœud.
Je pense que vous voulez dire un arbre B +.
Dans un arbre B + que je l'ai écrit, je l'ai fait double emploi avec les valeurs clés du nœud parent lors d'une scission. La clé [pos] dans le parent a été définie sur la valeur la plus basse du nœud gauche et pointée sur le nœud de gauche. La valeur la plus basse du noeud droit est devenue la clé [pos + 1] dans le parent.