Einführung in den B-Tree-Einfügeprozess

Im vorherigen Artikel https://www.jb51.net/article/154153.htm haben wir die Eigenschaften von B-Tree vorgestellt. In diesem Artikel stellen wir den Einfügevorgang von B-Tree vor.

Der Einfügevorgang und der Baumkonstruktionsprozess sind im Wesentlichen gleich, das heißt, beide führen Einfügevorgänge durch und passen den B-Baum nach dem Einfügen an.

Wir setzen die Reihenfolge des B-Baums auf 5. Konstruieren Sie einen B-Baum mit der Schlüsselfolge {1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}.

Da die Ordnung des Baums 5 ist, hat jeder Knoten höchstens 5 untergeordnete Knoten und die Anzahl der Schlüsselwörter in jedem Knoten beträgt 3 bis 4.

Der erste Schritt besteht also darin, 1, 2, 6, 7 als Knoten einzufügen.

Setzen Sie dann 11 ein und erhalten Sie 1, 2, 6, 7, 11. Da die Anzahl der Knoten 4 überschreitet, muss der Knoten aufgeteilt werden. Wählen Sie den mittleren Knoten 6 aus und stufen Sie ihn zum übergeordneten Knoten hoch. So erhalten wir:

Es gibt eine Regel, dass neu eingefügte Knoten immer auf Blattknoten erscheinen. Fügen Sie dann 4, 8 und 13 direkt ein und Sie erhalten

Dann setzen wir 10 ein. Wir erhalten

Da der untere rechte Knoten 5 Elemente enthält und damit die maximale Anzahl von 4 überschreitet, muss er aufgeteilt werden. Der mittlere Knoten 10 wird heraufgestuft, um zusammen mit 6 die folgende Struktur zu bilden.

Dann setzen wir 5, 17, 9, 16 ein und erhalten folgendes

Fügen Sie dann 20 ein. Nach dem Einfügen von 20 beträgt die Anzahl der Elemente im unteren rechten Knoten 5, was die maximale Anzahl von 4 überschreitet. Daher muss 16 erhöht werden, um die folgende Struktur zu bilden

Fügen Sie dann 3, 12, 14, 18 und 19 ein, um die folgende Struktur zu bilden.

Wenn Sie dann 15 einfügen, wird 13 zum Stammknoten befördert. Zu diesem Zeitpunkt hat der Stammknoten 5 Knoten. Dann wird 10 im Stammknoten erneut befördert, wodurch die folgende Struktur entsteht.

Beenden.

Zusammenfassen

Das Obige ist der vollständige Inhalt dieses Artikels. Ich hoffe, dass der Inhalt dieses Artikels einen gewissen Lernwert für Ihr Studium oder Ihre Arbeit hat. Vielen Dank für Ihre Unterstützung von 123WORDPRESS.COM. Wenn Sie mehr darüber erfahren möchten, schauen Sie sich bitte die folgenden Links an