Qu'est-ce que ce B-tree ressembler?

Question

Le B-tree est de l'ordre 4, ce qui signifie qu'un noeud peut contenir 4 pointeurs et 3 clés.

Le texte suivant est inséré: A G I Y

Comme ils ne peuvent pas tous tenir dans un seul nœud, je sais que le noeud sera divisé. Donc, je sais qu'il va être un nœud racine avec 2 nœuds enfants après ces choses sont insérés, mais je ne sais pas exactement ce qu'ils vont ressembler.

Answer 1

A

A est inséré

AG

G est inséré

AGI

I est inséré

  G
 / \
A   I

Pendant l'insertion, le noeud Y est pleine, divisée en 2 noeuds et laisser passer le milieu, G

  G
 / \
A   IY

Y est inséré

Answer 2

Voici une animation des opérations:

http://ysangkok.github.io/js-clrs-btree/btree.html# { "actions": [[ "initTree", { "clés": []}, 2], [ "insérer", "A"], [ "insérer", "G"], [ "insérer", "I "], [" insérer », "Y"]]}

Le second paramètre à « initTree » est l'ordre, mais en utilisant une autre défintion. Le nombre maximum de clés dans ce programme est 2 * ordre 1. Je me suis donc l'ordre de 2 et correspond à votre exemple.