B-Tree: remove, Löschen der Wurzel

Benutzeravatar
SophiaLi1
Kernelcompilierer
Kernelcompilierer
Beiträge: 542
Registriert: 5. Jan 2014 11:48

B-Tree: remove, Löschen der Wurzel

Beitrag von SophiaLi1 » 18. Jul 2017 13:35

Hallo,
ich hatte gerade folgenden Fall, bei dem ich die Lösung nicht nachvollziehen kann:
b1.PNG
b1.PNG (23.99 KiB) 610 mal betrachtet
Es soll also der Schlüssel der Wurzel gelöscht werden. Da der rechte Kindknoten mehr als M-1 Schlüssel hat, kann keine Merge-Operation durchgeführt werden, wie man es sonst häufig macht.
Im Folgenden sind die ersten Schritte der Lösung. Ich verstehe nicht, was hier gemacht wurde. Selbst wenn man die 42 in den linken Kindknoten rotieren würde, dürfte man noch nicht auf die Wurzel absteigen, weil sie nicht M Schlüssel hat. Was habe ich übersehen?
b2.PNG
b2.PNG (59.95 KiB) 610 mal betrachtet
Edit: Irgendwie kann man die Bilder nicht größer anzeigen, also hier nochmal Links:
https://picload.org/view/rppplail/b1.png.html
https://picload.org/view/rppplaii/b2.png.html

steffen12
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 205
Registriert: 14. Okt 2009 16:28

Re: B-Tree: remove, Löschen der Wurzel

Beitrag von steffen12 » 1. Aug 2017 18:16

Hallo,

für die Wurzel des B-Baumes gelten spezielle Regeln. Dort ist die Restriktion auf die Anzahl der Schlüssel nicht gegeben.
Wie du sagst "auf die Wurzel hinabsteigen" ist in gewisser Weise keine Thema, denn die Iteration beginnt einfach an der Wurzel. Ohne wenn und aber.

VG Steffen

Antworten

Zurück zu „Archiv“