dbis-btree

Python-Tool zur Visualisierung von B-Bäumen und B+-Bäumen, entwickelt vom Lehrstuhl i5/DBIS der RWTH Aachen für die Vorlesung Datenbanken und Informationssysteme.

Im DBIS-Image des JupyterHub der RWTH ist dieses Package bereits vorinstalliert. Für eine lokale Installation:

pip install dbis-btree
# in Jupyter Notebooks:
!pip install dbis-btree

Inhaltsverzeichnis

• B-Baum (BTree)
  • Initialisierung
  • Knoten hinzufügen
  • Kanten hinzufügen
  • Weitere Methoden
  • Copy-Text generieren
• B+-Baum (BplusTree)
  • Unterschiede zum B-Baum
  • Verwendung
• Häufige Fehler

B-Baum (BTree)

Import

from dbis_btree.BBaum import BTree

Initialisierung

Erzeugen Sie eine neue Instanz der Klasse BTree mit dem gewünschten M-Wert:

M = 4
bbaum = BTree(M)
bbaum.draw()

Knoten hinzufügen

add_node(name, elements)

Der erste hinzugefügte Knoten wird automatisch als Wurzelknoten behandelt. Wird ein bereits vorhandener Name verwendet, wirft die Methode einen AssertionError.

bbaum = BTree(4)

bbaum.add_node("A", [10, 20])
bbaum.add_node("B", [1, 2])

bbaum.draw()

Kanten hinzufügen

add_edge(parent, child, n_child)

Fügt eine Kante vom parent-Knoten zum child-Knoten ein. n_child bestimmt, an welcher Zeigerposition im Elternknoten die Kante eingehängt wird (1-basiert).

bbaum = BTree(4)

bbaum.add_node("A", [10, 20])
bbaum.add_node("B", [1, 2])

bbaum.add_edge("A", "B", 1)  # B hängt am 1. Zeiger von A

bbaum.draw()

Weitere Methoden

Copy-Text generieren

Mit generate_copy_text() kann der aktuelle Zustand des Baums als ausführbaren Python-Code exportiert werden. Das ist nützlich, um einen Zwischenstand weiterzugeben oder in eine neue Zelle zu kopieren.

print(bbaum.generate_copy_text())
# Ausgabe:
# b = BTree(4)
# b.add_node('A', [10, 20])
# b.add_node('B', [1, 2])
# b.add_edge('A', 'B', 1)

B+-Baum (BplusTree)

Import

from dbis_btree.BBaum import BplusTree

Unterschiede zum B-Baum

BplusTree erweitert BTree und ergänzt die Visualisierung um die charakteristischen Eigenschaften eines B+-Baums (Verkettung der Blattknoten).

Die gesamte API (Knoten, Kanten, Hilfsmethoden, Copy-Text) ist identisch mit BTree.

Verwendung

from dbis_btree.BBaum import BplusTree

bp = BplusTree(4)

# Innere Knoten
bp.add_node("Root", [20])
bp.add_node("Inner1", [10])
bp.add_node("Inner2", [30])

# Blattknoten
bp.add_node("L1", [1, 5])
bp.add_node("L2", [10, 15])
bp.add_node("L3", [20, 25])
bp.add_node("L4", [30, 35])

# Struktur aufbauen
bp.add_edge("Root", "Inner1", 1)
bp.add_edge("Root", "Inner2", 2)
bp.add_edge("Inner1", "L1", 1)
bp.add_edge("Inner1", "L2", 2)
bp.add_edge("Inner2", "L3", 1)
bp.add_edge("Inner2", "L4", 2)

bp.draw()

Die Blattknoten L1 -> L2 -> L3 -> L4 werden automatisch mit gestrichelten Kanten verbunden.

generate_copy_text() funktioniert auch für BplusTree und gibt den korrekten Klassennamen aus:

print(bp.generate_copy_text())
# b = BplusTree(4)
# ...

Häufige Fehler

Warning: node A, port f6 unrecognized

Der Parameter n_child in add_edge ist ungültig. Ein Knoten mit M=4 hat die Zeigerpositionen 1 bis 5. Eine Position außerhalb dieses Bereichs führt zu dieser Warnung.

AssertionError: Bitte nutze einen anderen Namen für diese Node.

Es wurde versucht, einen Knoten mit einem bereits vorhandenen Namen hinzuzufügen. Jeder Knoten benötigt einen eindeutigen Namen.

UserWarning: Node ID: X does not exist.

deleteNode wurde mit einem Namen aufgerufen, der im Baum nicht vorhanden ist.