dbis-btree 1.1.2

RWTH Aachen Computer Science i5/dbis assets for Lecture Datenbanken und Informationssysteme

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)

Parameter	Typ	Beschreibung
name	str | int	Eindeutiger Name des Knotens
elements	list	Liste der im Knoten gespeicherten Werte

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).

Parameter	Typ	Beschreibung
parent	str | int	Name des Elternknotens
child	str | int	Name des Kindknotens
n_child	int	Zeigerposition im Elternknoten (ab 1)

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

Methode	Beschreibung
getNode(name)	Gibt den Knoten mit diesem Namen zurück, oder None falls nicht vorhanden.
getRootNode()	Gibt den Wurzelknoten zurück, oder None falls kein eindeutiger Wurzelknoten existiert.
deleteNode(name)	Entfernt den Knoten aus dem Baum. Gibt eine Warnung aus, falls der Knoten nicht existiert.
valueIsInBbaum(value)	Gibt True zurück, falls der Wert in einem Knoten des Baums gespeichert ist.
isLeafNode(node)	Gibt True zurück, falls der Knoten ein Blattknoten ist (keine Kinder).
getSibling(node, getLeft)	Gibt den linken (True) oder rechten (False) Geschwisterknoten zurück.
get_leaf_nodes()	Gibt eine Liste aller Blattknoten zurück.

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.