Warning: include_once(/var/www/html/pmwiki-2.2.86/cookbook/soap4pmwiki/soap4pmwiki.php): failed to open stream: No such file or directory in /var/www/html/fields/dbp15/local/config.php on line 4

Warning: include_once(): Failed opening '/var/www/html/pmwiki-2.2.86/cookbook/soap4pmwiki/soap4pmwiki.php' for inclusion (include_path='.:/opt/php/lib/php') in /var/www/html/fields/dbp15/local/config.php on line 4

Warning: Cannot modify header information - headers already sent by (output started at /var/www/html/fields/dbp15/local/config.php:4) in /var/www/html/pmwiki-2.2.86/pmwiki.php on line 1250
Datenbankpraktikum SS 2015 - D - Bstar

B*-Baum als Indexstruktur

Quelldatei: https://github.com/OsnaCS/uosql-server/blob/master/server/src/storage/bstar.rs

Die Implementierung des B*-Baumes wurde so weit abgeschlossen, dass eine persistente, iterierbare Indexstruktur erzeugt werden kann mit den Funktionen Lookup, Insert und Delete.

756:  1 => 216 ;  9 => 648 ;
|----216:  1 => 0 ;  4 => 108 ;  7 => 432 ;
|----|----0:  1 => 2 ;  2 => 2 ;  3 => 2 ;
|----|----108:  4 => 2 ;  5 => 2 ;  6 => 2 ;
|----|----432:  7 => 2 ;  8 => 2 ;
|----648:  9 => 324 ;  12 => 540 ;
|----|----324:  9 => 2 ;  10 => 2 ;  11 => 2 ;
|----|----540:  12 => 2 ;  13 => 2 ;

In dem Beispiel geben die Zahlen am Anfang einer Zeile die Adressen der Indexknoten in der B*-Datei an, nach dem Doppelpunkt folgt eine Liste mit Schlüssel-Adress Paaren (Schlüssel => Adresse). Die Adressen in den Knoten des Baumes beziehen sich dabei jeweils auf die Adresse des Datenrecords einer Tabelle, zu dem der entsprechenden Schlüssel gehört (im Beispiel ist diese Adresse immer die Dummy-Adresse 2)

Speicherprotokoll

Eine B*-Indexstruktur speichert 2 Dateien auf der Festplatte:

  1. Metadaten
  2. Baumknoten

In der Metadatendatei wird gespeichert, an welcher Adresse in der Baumknotendatei die Wurzel steht, wie viele Elemente enthalten sind, welcher Ordnung der B* Baum ist und wo in der Baumknotendatei die nächste freie Adresse für einen neuen Knoten ist. Des weiteren wird dort festgehalten, auf welche Datenrecord Datei sich die Indexstruktur bezieht (Die Adressen der Blätter beziehen sich auf diese Record-Datei)

Die Baumknotendatei speichert nur die Knoten der Indexstruktur. Dazu gehört pro Knoten sein linker und rechter Bruder (für den Iterator).

Effektive Speichernutzung

Um nach Löschen und Wiedereinfügen nicht unnötigen Speicher zu verbrauchen führt die Metadatendatei die nächste freie Adresse der Baumknotendatei mit. An der spezifizierten Stelle in der Baumknotendatei steht dann die darauf folgende freie Adresse. So lässt sich durch nur ein zusätzliches Feld der Metadatendatei und einen geringfügen Verwaltungsaufwand effektives Speichermanagement erreichen.

Flexible Schlüssel

Der Baum wurde so implementiert, dass als Schlüssel jede Datenstruktur übergeben werden kann, für die eine Ordnungsfunktion (PartialOrd von Rust) und ein von mir entwickeltes Interface "KnownSize" implementiert wurde.

pub trait KnownSize {
    /// returns the fixed maximum size of all objects that
    /// will ever be created
    fn size() -> u64;
 
    /// reads the object from file, at address if specified.
    /// if the address is not specified, the object will be read
    /// from wherever the current seek is
    fn read(&mut File, Option<u64>) -> Result<Self>;
 
    /// writes the object to file, at address if specified.
    /// if the address is not specified, the object will be written
    /// to wherever the current seek is
    fn write(&self, &mut File, Option<u64>) -> Result<()>;
 
    /// writes a defaultversion of the Type to file
    /// if no address is specified, the default will be written
    /// to wherever the current seek of the file is.
    fn write_default(&mut File, Option<u64>) -> Result<()>;
}

Iterator

Der B*-Baum ist iterierbar mit einem anpassbarem Iterator. Der Iterator kann bei einem beliebig übergebenen Schlüssel starten (inklusive oder exklusive Schlüssel) und vorwärts oder rückwärts laufen. Dies ermöglicht eine effektive Umsetzung von Bereichsabfragen in SQL-Queries.

Verbesserungen

Als nächstes sollte die Möglichkeit implementiert werden, den B*-Baum nicht nur persistent sondern auch im RAM zu speichern um bei Select-Queries eine Indexstruktur bereitstellen zu können.

Auch kann implementiert werden, dass der B*-Baum duplizierte Schlüssel zulässt, um als Sekundärindex zu dienen.

Die Umsetzung des B*-Baumes als Engine mit Crud-Funktionalität ist ein weiteres Ziel.


Autor: Hendrik Langebrake


Page last modified on September 25, 2015, at 02:31 PM