| Einleitung |
Heutzutage ist die Informationsflut so groß geworden, daß es ohne entsprechenden Mehraufwand nicht mehr möglich ist, gezielt Informationen zu suchen und vor allem zu finden, ein Tribut der Informationsgesellschaft. Es gilt, geeignete Techniken und Hilfsmittel zu finden, um den Daten Herr zu werden. Um die Realisierung von effektiven, zukünftig erweiterbaren Algorithmen zu gewährleisten, kapselt man die gesamte Funktionälität in Datenbanken. Diese bestehen einerseits aus den ursprünglichen Daten und andererseits aus diversen redundanten Datenstrukturen. Die Schnittstelle, die Datenbanken bereitstellen, beschränkt sich zumindest auf die primitivsten Funktionen zur Arbeit mit Daten: Hinzufügen, Ändern, Löschen, Abfragen. Das Ziel ist es, diese Funktionen möglichst schnell auszuführen, wie das geschieht, kann und soll dem Benutzer egal sein, dem interessierten Informatiker, vielleicht dem Programmierer eines solchen Retrieval-Systems, aber nicht. Man bedient sich der Indexe, um die Daten oder Verweise auf sie nach verschiedenen Gesichtspunkten zu sortieren, um ein effizientes Suchen nach ihnen zu ermöglichen. Gängige Datenbanken benutzen hierfür die Datenstruktur des B-Baumes, der nach seinem Erfinder Rudolf Bayer benannt ist. Dieser Baum, zusammen mit den auf ihn ausführbaren Funktionen, hat alle Eigenschaften, die Datenbanken verlangen: Schneller, zeitlich nach oben hin abgrenzbarer, Zugriff auf alle Elemente der Datenbasis.
| Beweggrund |
Eine effektive Implementierung kann nur erreicht werden, wenn die verwendete Programmiersprache möglichst hardwarenah ist und einen optimierenden Compiler besitzt. C ist deshalb prädestiniert als Programmiersprache für die Implementierung eines in der Ausführung aufwendigeren Algorithmus. Deshalb war es mir ein Anliegen, statt eines Programms mit viel Oberfläche und wenig Know-How, mich an der Implementierung eines Datenbankindex zu versuchen. Oberflächen sind in anderen Umgebungen leichter und besser zu programmieren, welche ja meistens auch wieder Schnittstellen zu "shared objects" bzw. "dynamic link libraries" zur Verfügung stellen. Im Sinne von dem unter Unix bekannten Baukastensystem, soll das Ziel dieses Beleges ein kommandozeilenorientiertes Programm sein, daß das Management eines Index erlaubt, da dieser trotz logischer Redundanz nebst den Daten der essentielle Bestandteil einer Datenbank ist, und das Programm somit unabhängig von Formaten der jeweiligen Datenbasis bleibt. Um dieses Ziel zu erreichen, war die Schaffung weiterer Programme zum Test der hier vorgestellten B-Baum-Implementierung notwendig. Die Wahl des Betriebssystems fiel auf Linux, da hier über die Makefiles ein effektiver Apparat existiert, um auf die Kompilierung Einfluß zu nehmen. Hinzu kommt, daß die sofortige Kompilierung auf jedem Unix möglich ist, da fast überall der Gnu-C-Compiler zur Verfügung steht.
| Installation |
Die Datei "runimage.tgz" beinhaltet sämtliche zum Beleg gehörenden ausführbaren Dateien und kann leicht mit "tar -xvzf runimage.tgz" (evtl. Pfad anpassen) ins aktuelle Verzeichnis ausgepackt werden. Diese Vorgehensweise ist anzuraten, da hierdurch die Ausführungsrechte automatisch richtig gesetzt werden. Nach erfolgreicher Installation liegen alle Programme bzw. Skripte für die weitere Verwendung vor. Je nach Plattform, auf der das Programm ausgeführt werden soll, ist eine Neukompilierung aus den Quellen vorzunehmen. Da der Funktionsumfang des im Beleg vorgestellten Programms "index" begrenzt ist, war es unerläßlich, eine geeignete Umgebung zu schaffen, die das Programm durch geeignete Kapselung benutzt. Diese beinhaltet eine Vielzahl awk- und Shellskripts, die die Eingaben für das Programm vorformatieren und die Ausgaben auch wieder auf die Datenbasis anwenden.
| Bedienungsanleitung |
Syntax: indexDie einzelnen Programmbeschreibungen sowie Beschreibungen der diesem Programm hinterlegten Bibliothek (B-Baum-Implementierung) bitte ich unten herunterladbarer Dokumentation zu entnehmen.[options] Aktionen: -h, --help Gibt eine kurze Beschreibung des Programms aus -c, --create Erstellt initial einen Index aus Schlüssel-Werte-Paaren an der Standardeingabe -a, --add Fügt dem Index Schlüssel-Werte-Paare an der Standardeingabe hinzu -d, --delete Löscht Schlüssel aus dem Index, die über die Standardeingabe übergeben werden. Hier dürfen nur die Schlüssel übergeben werden -r, --range Führt eine Bereichsabfrage über den Index aus. Dazu werden zwei Schlüssel der Standardeingabe entnommen. -l, --list Gibt die Eigenschaften des Index aus. Dazu gehören die Definition der Schlüssel- und Wertlängen, die Ordnung und die Anzahl der Schlüssel. Optionen: -f, --file Gibt die Datei des zu verwaltenden Indexes an -p, --parse Über diese Option werden die Schlüssel- und Wertelängen angegeben, die über die Standardeingabe eingelesen werden sollen. Diese Option wird nur für -c benötigt, da bei einem einmal erstellten Index der Aufbau der Schlüssel nicht mehr geändert werden kann. z.B. -p 5,10 für 5 Byte Schlüssel und 10 Byte Wert -o, --order Gibt die Ordnung an, in der der Indexbaum aufgebaut werden soll Diese Option hat ebenfalls nur beim Erstellen des Index eine Wirkung. Default: 16 -n, --newline Gibt an, wieviel Byte zwischen den Schlüssel-Werte-Paaren im Eingabestrom überlesen werden sollen. Default: 0 -v, --verbose Ausführliche Ausgabe (Abschließende Statusmeldung) -vv, --verbosev Ausführlichere Ausgabe (zusätzlich Ausgabe des akt. Schlüssels)
| Download |