B+Baum innere Knoten erstellen

[Loddakwin]

Hallo,

versuche gerade die inneren Knoten eines B+Baumes zu erstellen, jedoch scheitere ich an der Umsetzung. Was ich bisher habe:

  /**
   * Builds a valid inner level of this B+ tree with the minimal number of inner
   * nodes for the specified list of child nodes. This method returns a sorted
   * list of the inner nodes created in the process (sorted with respect to the
   * keys in the nodes). The children in an inner node are supposed to point
   * to the respective child nodes.
   *
   * @param children a sorted list of child nodes for which the next inner level
   *  is built
   *
   * @return a sorted list of all inner nodes created in the process, or
   *  <tt>null</tt> if there are no children to connect
   */
private List<BPNode<Key>> buildInnerLevel (final List<BPNode<Key>> children) {
    // deal with trivial cases
    if ((children == null) || children.isEmpty()) {
      return null;
    }

    List<BPNode<Key>> currentLevel = new ArrayList<BPNode<Key>>();
  
    BPNode<Key> temp = new BPNode<Key>(degree());
  
    for(int i = 1; i < children.size(); i++) {
        temp.addKey(children.get(i).key(0));
        if(temp.keys().size() > (degree() - 1)) {
      
        }
    }
  
    currentLevel.add(temp);
  
    System.out.println(currentLevel.get(0).key(0));
  
    return currentLevel;
  }

Bin mir aber ziemlich sicher das es so nicht funktionieren kann. Vielleicht muss es rekursiv umgesetzt werden?

LG

 

[otti.steinhauer]

Hallo Loddakwin,

ein B+-Baum ist ein balancierter Baum, richtig? (Ist schon eine Weile her, dass ich Informatik studiert habe).
Prinzipiell wird zum Einfügen in einen Baum rekursiv die richtige Stelle gesucht und dann ein zusätzliches Blatt dort angehängt. Anschließend muss der Baum wieder ausbalanciert werden. Die Suche nach der richtigen Stelle kann nur dann nicht rekursiv gemacht werden, wenn die genaue Höhe des Baums und die Anzahl seiner Elemente bekannt sind, das ist in der Regel nicht der Fall, besonders nicht, wenn noch zusätzlich eingefügt werden soll.
Also musst Du eine Suchen-Funktion definieren, der Du zunächst die Wurzel des Baums übergibst. In dieser Funktion testst Du, ob Du die richtige Stelle gefunden hast -> return, oder wo weiter gesucht wird. Dieses Element übergibst Du rekursiv wieder der Funktion suchen, es ist jetzt die neue Wurzel des Teilbaums.
Irgendwann hast Du die passende Stelle gefunden, nun hängst Du dort das neue Blatt an ggf. muss evtl. der Knoten geteilt werden, wenn er sonst zu voll würde.
Ein Code-Beispiel gibt es auf GitHub: https://gist.github.com/mikelikesbikes/4742901

Hoffe es hilft weiter.

Otti

 

[Loddakwin]

Hallo Otti,

danke für deine Antwort. Ja es ist ein balancierter Baum. Die Anzahl der Element die eingefügt werden ist bekannt du meinst erst zu Laufzeit oder?. Mein großes Problem ist das ich nicht weiß, wie ich die Blätter(Liste children) so bearbeite, dass jedes erste Element eines Blattes zum ersten inneren Knoten wird und falls hier ein overflow passiert muss der Knoten gesplittet werden. Heißt erstelle 2 weiter Knoten einer auf selber Ebene mit dem neuen Schlüssel der den Overflow herbeiruft und einer steigt auf mit dem key ceil(m/2). M steht für pointer. Also ein Knoten hat bei m = 5 maximal m - 1 schlüssel bzw keys.

Die Blätter konnte ich schon richtig sortieren es geht jetzt nur mehr um die inneren Knoten und ich glaube das ich das eben nur rekursiv lösen kann, aber wie soetwas ausschauen soll hab ich echt ka.

LG

 

[otti.steinhauer]

nehmen wir einmal das Beispiel. Der Knoten ist ein Blatt, vier Schlüssel sind drin,bei m=5 passen auch nur vier rein, d.h. das Blatt ist voll. Für dieses Blatt gibt es ein Element oberhalb, das genau auf das Blatt zeigt, nennen wir es Wurzel.
Beim Einfügen müssen jetzt korrekt zwei neue Blattkonten erzeugt werden und ein Element des bisherigen Blatts wird zur Wurzel des neuen Teilbaums, das Element soll ceil(m/2) heißen. Nun muss der Zeiger der Wurzel umgehängt werden, er muss auf ceil(m/2) zeigen. Es müssen also drei Zeiger initialisiert werden:
Wurzel ->ceil(m/2),
ceil(m/2) -> neues Blatt1,
ceil(m/2) -> neues Blatt2

Es ist also sinnvoll beim Abbruch des rekursiven Suchvorgangs die Wurzel des Teilbaums zurück zu geben, beim Einfügen dann einmal das richtige Element zu suchen und dann hast Du sämtliche Elemente und kannst Zeiger umhängen ohne dass Dir Infos verloren gehen.

Gruß

Otti