Seite 2: Computer Science 1x1

Inhaltsverzeichnis

Verkettete Listen

Wer einen Abschluss in Informatik oder in einem vergleichbaren Fach besitzt, dem sind Algorithmen und Datenstrukturen bestens vertraut. Bei der Bewertung von Algorithmen oder Datenstrukturen spielen beispielsweise Komplexität in Bezug auf Verarbeitungszeit oder Speicherplatzbedarf eine Rolle. Vielen mag auch noch die O-Notation (ein Landau-Symbol) als Kürzel zur Bezeichnung der Komplexität in Erinnerung geblieben sein.

• O(1) oder konstant, wenn der Zugriff auf ein Element in einer Struktur konstanten Aufwand verursacht, selbst wenn die Anzahl der Elemente zunimmt
• O (log n) oder logarithmisch, wenn der Zugriff auf ein Element in einer Struktur eine weitere Operation erfordert, sobald sich die Anzahl der Elemente verdoppelt
• O (n) oder linear, wenn die Anzahl der für den Zugriff auf ein Element erforderlichen Operationen proportional mit der Anzahl der Elemente zunimmt
• O (m log n) oder linearithmisch, wenn eine Operation ein zusätzliches Vielfaches von O (log n) verursacht
• O (n^m) oder polynominal, wenn die Anzahl der Operationen, die für den Zugriff auf ein Element erforderlich sind, exponentiell (oder in anderer Weise polynominal) mit der Anzahl der Elemente zunimmt

Im Allgemeinen sollte der Aufwand möglichst gering bleiben, es sei denn, die Anzahl der Elemente ist klein und begrenzt. In diesem Fall kann ein moderner Computer sie schnell ausführen.

Vor diesem theoretischen Hintergrund lässt sich betrachten, wie sich die Dinge in der Praxis im Zusammenhang mit dem Aufbau eines Datenbankmanagementsystems verhalten. Den Anfang macht eine einfache, ungeordnete Liste mit einzelnen Verbindungen (Abb. 1).

Für nicht konkurrierende Einträge mit einer Komplexität von O(1) ist diese verkettete Liste sehr günstig. Für Lesezugriffe beträgt die Komplexität jedoch O(n), was bedeutet, dass die Performance abnimmt, je größer die Liste wird.

Das heißt nicht automatisch, dass verkettete Listen nicht ihren Nutzen haben: Für nicht-konkurrierende Schreibszenarien sind sie weiterhin sinnvoll, für konkurrierende Schreibszenarien und insbesondere für Lesevorgänge sind sie jedoch weniger geeignet. Konfliktfrei replizierte Datentypen (CRDTs) sowie blockierungsfreie Programmierungsstrategien helfen dabei, Schreibkonflikte zu vermeiden. Hier zeigt sich aber, dass die O-Notation beim Aufeinandertreffen von Theorie und Praxis nur einen Anhaltspunkt und keine belastbare Garantie bietet.

Binärbäume

Baumstrukturen können helfen, dieses Ungleichgewicht zwischen Lesen und Schreiben auszugleichen. Sowohl für Lesezugriffe als auch für Schreibzugriffe auf einen Baum gilt typischerweise O(log n). Zudem werden Schreibkonflikte verringert, da ein Baum (auch ein einfacher Binärbaum) mehr Bindungspunkte als eine Liste aufweist (Abb. 2).

B-Baum-Varianten werden seit langem für die Modellierung von Datenbanken genutzt, wobei die inneren Knoten (non-leaf) einen Index der tatsächlichen Datensätze liefern, die in den Blättern enthalten sind. Das macht es möglich, die zahlreichen Indexeinträge im schnellen Arbeitsspeicher zu halten und gleichzeitig die weniger zahlreichen Dateneinträge auf die Festplatte zu schreiben.

Baumstrukturen eignen sich gut für einmalige Nachschlagevorgänge oder für Schreibvorgänge mit der Komplexität O(log n). Auch bei größeren Datenmengen in Milliardenhöhe ist die Anzahl der erforderlichen Operationen für einzelne Lookups handhabbar.

Bei der Betrachtung von Bäumen im Kontext einer Graphdatenbank, in der viele Traversierungen erforderlich sind, um die verbundenen Daten auszulesen, sollte ein weniger komplexer Zugriff bevorzugt werden. Der Unterschied zwischen O(n), also der Komplexität für n Hops bei O(1), und O(m log n) in Bezug auf I/O-Operationen auf das Laufwerk, summiert sich schnell und mindert die Performance.

Natürlich gibt es in jedem DBMS eine Mischung verschiedener Strukturen, die jeweils dem nativen Workload entsprechen. Erst wenn die Auswahl solcher Datenstrukturen im Kontext des nativen Datenmodells und der Workloads getroffen wird, kann ein kohärentes DBMS-Design entstehen. Dabei ist klar: Jedes DBMS zeigt seine Stärke für das Modell, in dem es originär konzipiert wurde. Das gilt auch für Graphdatenbanken.