B + Baum Einfügen Verständnis

Question

Ich versuche, einen B + Baum mit der folgenden Sequenz, erstellen

10 20 30 40 50 60 70 80 90 100

alle Indexknoten haben mindestens 2 und maximal 3 Tasten sollen. Ich konnte bis 90 einfügen, aber sobald 100 einfügen, erhöht es die Höhe von 2 bis 3.

Das Problem ist das zweite Kind der Wurzel hat einen Knoten, und ich kann es nicht beheben. Es sollte mindestens 2 haben, oder? Kann mich jemand führen?

UPDATE: Ich folge diesem Algorithmus

If the bucket is not full (at most b - 1 entries after the insertion), add the record. 
Otherwise, split the bucket. 
Allocate new leaf and move half the bucket's elements to the new bucket. 
Insert the new leaf's smallest key and address into the parent. 
If the parent is full, split it too. 
Add the middle key to the parent node. 
Repeat until a parent is found that need not split. 
If the root splits, create a new root which has one key and two pointers. (That is, the value that gets pushed to the new root gets removed from the original node) 

P. S: Ich bin es manuell zu tun, mit der Hand, um den Algorithmus zu verstehen. Es gibt keinen Code!

Answer 1

Ich glaube, Ihr B + Baum O.K ist, vorausgesetzt, die Reihenfolge der B + Baum ist 3. Wenn der Auftrag ist m, jeder interne Knoten ⌈ m/2 ⌉ zu m keine Kinder haben. In Ihrem Fall kann jeder interne Knoten 2 bis 3 Kinder haben. Wenn in einem B + -Baum ein Knoten nur 2 Kinder hat, benötigt er nur 1 Schlüssel, so dass von Ihrem B + -Baum keine Einschränkungen verletzt werden. Wenn Sie immer noch verwirrt sind, sehen Sie sich diese B+ Tree Simulator an. Versuch es.

Answer 2

Um den Baum zu erhalten, den Sie nach dem Einfügen der Werte 10 bis 100 gezeichnet haben, muss die Reihenfolge Ihres Baumes 4 nicht 3 sein. Ansonsten ist die Antwort korrekt: Reihenfolge m erlaubt m-1 Schlüssel in jedem Blatt und jedem Knoten. Danach wird die Wikipedia-Beschreibung etwas verwirrend, da sie sich auf Kinder und nicht auf Schlüssel konzentriert und nicht erwähnt, was mit Rundung zu tun ist. Der Umgang mit nur Schlüssel, die Regeln sind:

Max keys for all nodes = Order-1 
Min keys for leaf nodes = floor(Order/2) 
Min keys for internal nodes = floor(maxkeys/2) 

So können Sie in mit einem Schlüssel in den Knoten richtig sind (order = 4, max = 3, minleaf = 2, minnode = 1). Sie können diese Seite nützlich finden, da es eine Online-JavaScript-Version der Prozesse sowie Dokumentation von sowohl Einsatz und löschen:

http://goneill.co.nz/btree.php