Baumstrukturen
Aus Winfwiki
Inhaltsverzeichnis |
1 Einleitung
Baumstrukturen sind heutzutage in nahezu jeder Datenbankanwendung zu finden und bilden damit einen wesentlichen Bestandteil der anwendungsorientierten Programmierung.
Das Ziel der Arbeit war es einerseits, die theoretischen und praktischen Grundlagen von Baumstrukturen in der Informatik darzustellen und zu zeigen, welche verschiedenen Ausprägungen von Baumstrukturen zur Verfügung stehen. Andererseits sollte dargestellt werden, wo die Vor- und Nachteile der verschiedenen Strukturen liegen und welche Strukturen sich optimal für verschiedene Anwendungstypen eignen.
Informationstechnische Bäume bestehen grundsätzlich aus sogenannten Graphen. Obwohl die Anfänge der Graphentheorie bereits im 18. Jahrhundert gelegt wurden, entwickelte sie sich erst im 20. Jahrhundert als Teilgebiet der diskreten Mathematik und ist damit eine relativ junge und moderne mathematische Disziplin.
2 Bäume als Datenstruktur
2.1 Zeit-Probleme beim Datenzugriff
Wird ein Datenbestand im Hauptspeicher verwaltet, so sind die Zugriffszeiten auf die einzelnen Datenelemente derart gering, dass eine hohe Zahl von Zugriffen kaum weiter ins Gewicht fällt. Die Datenhaltung im Hauptspeicher ist jedoch nur möglich, wenn die Daten eine gewisse Größe nicht überschreiten. Für größere Datenbestände, z.B. für umfangreiche Adressverwaltungen müssen die Daten auf externen Speichermedien, wie z.B. der Festplatte abgelegt werden. Hierbei erhöht sich die Dauer eines Zugriffes maßgeblich.
Ein gängiger Arbeitsspeicher (z.B. „DDR2-667“) erlaubt ein Auslesen der Daten mit bis zu 5,3 GByte/s. Eventuell auftretende Latenzzeiten wie etwa die Zeit zwischen Speicheradressierung und Erscheinen der Daten an den externen Chip-Kontakten (CAS Latency) liegen im Nano-Sekunden-Bereich (CAS Latency beträgt bei DDR2-667 10 30 ns), und können somit vernachlässigt werden[1].
Um 1 KB Daten aus dem Hauptspeicher zu lesen, werden also ca. 0,1887 µs benötigt (die Chiphersteller berechnen die verschiedenen Potenzen mit 1000, nicht mit 1024). Liegen die Daten jedoch auf der Festplatte, anstatt im Hauptspeicher, so ist im schlimmsten Fall anzunehmen, dass die Datensätze ungeordnet über die Festplatte „verteilt“ sind. Für jeden Lese-Zugriff ist also eine Neupositionierung des Schreib-Lese-Kopfes notwendig.
Bei einer modernen Festplatte (z.B. bei der ATA-Festplatte „HD161HJ SpinPoint S166“ von Samsung) benötigt diese Neupositionierung etwa 10,4 ms. Das Auslesen der Daten erreicht hingegen eine Geschwindigkeit von ca. 61 MB/s. 1 KB wird also in 0,0164 ms ausgelesen (das Auslesen ist also etwa 630-mal schneller, als das vorherige Positionieren des Festplatten-Kopfes)[2].
Pro von der Festplatte gelesenem KB sind also 10,4164 ms nötig, d.h. das Auslesen dauert etwa 55.200 mal so lange, wie das Auslesen aus dem Hauptspeicher.
Eine hohe Anzahl an Zugriffen auf die Festplatte kann also eine Datenverwaltung derart verlangsamen, dass ein effektives Arbeiten mit den Daten nicht mehr möglich ist. Für die Speicherung von Daten auf einem externen Medium muss also eine Datenstruktur gefunden werden, die es erlaubt, mit einem Minimum an Zugriffen einen Datensatz zu finden, einzufügen oder zu löschen. Eine geeignete Datenstruktur ist beispielsweise der „Baum“.
2.2 Bäume vs. Listen
Bäume werden in der Informationstechnologie in erster Linie dazu verwendet, die Datenspeicherung in sortierten Listen zu ersetzen. Eine sortierte Liste hat den wesentlichen Nachteil, dass Zugriffsoperationen viel Zeit in Anspruch nehmen können.
Das Auffinden eines Datensatzes in einer Liste erfordert im Durchschnitt n/2 (einfach verkettete Liste)[3] bzw. n/3 (doppelt verkettete Liste, eigene empirische Untersuchung) Zugriffe, wobei „n“ für die Anzahl der Datensätze in der Liste steht.
Der Vorteil von Listen liegt im relativ leichten Einfügen und Löschen von Elementen. Nachteilig wirkt sich jedoch die hohe durchschnittliche Anzahl an Zugriffsaktionen beim suchen eines Wertes aus. Lineare Listen eignen sich daher kaum, um große Datenmengen zu verarbeiten. Hierfür ist die Verwendung eines Baumes sinnvoller. Anstatt alle Elemente in einer linearen Kette zu speichern, werden jedem Datenelement dabei mehrere Nachfolger zugeordnet, so dass eine Baumstruktur entsteht.
