Homepage von Boris Haase




Vorherige | Nächste

#23: Erweiterung Sortieren und Suchen vom 17.09.2010

In allen Sortierverfahren, bei denen Werte mit einer Bitlänge von l = q a mit Adresslänge a sortiert werden, erhöht sich die Zeitkomplexität pro Wert von O(1) auf O(q). Wenn O(r) der Durchschnittswert von O(q) ist, ist also in der Zeitkomplexität des Sortierverfahrens mindestens ein O(n) durch O(r n) zu ersetzen. Ist s der Durchschnittswert der Anzahl der verschiedenen (!) Werte, die in einem Bucket nach Sortierung bis Bitlänge a landen und deren Bitlänge größer als a ist, so ist die Zeitkomplexität des Sortierverfahrens O((log s + r) n). Dabei werden die erwähnten Werte eines Buckets pro Bucket in einem AVL-Baum abgelegt (bzw. in einem B-Baum, wenn sie in einem zum Hauptspeicher relativ langsameren externen Speicher gespeichert werden). Dort wird jeweils immer nur mit dem signifikanten Teilwert von Adresslänge eines Wertes gearbeitet.

Wenn on darauf verzichtet, dass die Werte nach jedem Abarbeiten eines Wertes vollständig sortiert vorliegen, dann kann eine Zeitkomplexität O(r n) für die komplette Sortierung durch Verwendung von zwei Hauptspeicherbereichen erreicht werden. Die Werte werden zuerst bis Adresslänge in Buckets sortiert und dann Adresslänge für Adresslänge (d. h. Teilwert für Teilwert) Bucket für Bucket weitersortiert. Das Abarbeiten der Werte, deren zuvor abgearbeiteter Teilwert gleich ist, wird als ein Durchlauf gezählt. Hierbei wird vorausgesetzt, dass das Lesen und Schreiben der Teilwerte eines Wertes und seiner Adresse über alle Durchläufe durchschnittlich komplett als O(r) gezählt wird.

Der zweite Hauptspeicherbereich wird nach jedem Durchlauf gelöscht, um für den nächsten Durchlauf zur Verfügung zu stehen, bis der Bucket abgearbeitet ist. In den ersten Hauptspeicherbereich werden stets nur die Adressen in der aktuellen Sortierreihenfolge zurückgeschrieben, bevor die Werte mit gleichem soeben abgearbeitetem Teilwert weitersortiert werden. Jeder Wert ist zusammenhängend im Speicher abzulegen, damit auf jeden Teilwert schnell zugegriffen werden kann. Über die Zeitkomplexität lässt sich zugegebenermaßen streiten. Die Werte eines Buckets und alle Adressen sollten zusammen in den Hauptspeicher passen, um relativ lange Ladezeiten zu vermeiden.

Beide Verfahren können gut kombiniert werden: Erst das O(r n)-Verfahren für den Stamm, dann das O((log s + r) n)-Verfahren für das Laufende. Sortierte Daten können in O(n) in Hauptspeicher und AVL- bzw. B-Baum abgelegt werden. Damit können insbesondere schnell Indizes für nicht-indizierte Tabellenspalten in Datenbankabfragen aufgebaut werden. Bei umfangreichen Tabellen macht es einen deutlichen Unterschied, ob ein Index in O(r n) statt in O(r n log n) aufgebaut wird und dann ein Wert durchschnittlich in O(log s + r) statt in O(log n + r) oder schlechter gesucht werden kann. Bei geschickter Nutzung eines genügend großen Hauptspeichers können bequem mehrere Indizes gleichzeitig gehalten werden. Bei Zahlen ist r normalerweise recht klein in Abhängigkeit von der Genauigkeit und s bei entsprechender Verteilung ebenfalls. Ähnliches gilt für (komprimierte) Wörter, wenn die Speichergröße der heute handelsüblicher Rechner entspricht. Sortieren durch Mischen beliebig vieler sortierter Listen ist ebenfalls in O(r n) möglich. Die Implementierung eines entsprechenden Speichers mit relativ geringer Intelligenz ist zwar einfach und spart komplexere Prozessoren, aber durch Einsatz hinreichend vieler von diesen oder Parallelverarbeitung (z. B. parallele Nutzung von Speicherbereichen) kann der Term log s + r in O((log s + r) n) kleiner als 1 gemacht werden, wenn on nur AVL- bzw. B-Bäume einsetzt und hinterher die Ergebnislisten in O(n) mischt.


Zur Unterstützung des Sortierens und Suchens in heterogenen (verteilten) Datenbanken (etwa unterschiedlicher Datenbankmodelle) kann eine Datenbanksprache eingesetzt werden, die mithilfe aus diesen erstellter dynamischer Datenstrukturen eine vereinheitlichte Datenmanipulation (z. B. unter einer einheitlichen Oberfläche) erlaubt, solange die Datensätze einen irgendwie gleichartigen Aufbau haben. Sie kann aufgrund entsprechender Vorgaben dynamisch (evtl. vorausschauend) entscheiden, welche Manipulationsschritte durchzuführen sind. Ihr müssen nur die entsprechenden Speicherinformationen der Datenbanken mit dem Aufbau der Datenbankstrukturen zur Verfügung gestellt werden.

Programmcode- und Datenänderungen (wie die Integration weiterer Datenbanken) zur Laufzeit können vorgesehen werden, wenn ausreichende Sicherheitsmechanismen (einschließlich Berechtigungsprüfung und Setzen von Sperren) zur Verfügung stehen. Die Indizes können bspw. parallel oder zu lastarmen Zeiten in Abhängigkeit von ihrer Größe mit unterschiedlichen Datenstrukturen - angepasst an die individuelle Problemstellung bzw. optimiert - aufgebaut werden. Evtl. reicht ein temporäres Mischen oder paralleles Zugreifen aus. Leistungsfähige Standards können die Implementierung einer solchen Datenbanksprache deutlich erleichtern.

© 17.09.2010 by Boris Haase


Valid XHTML 1.0 • Haftungsausschluss • mail@boris-haase.de • PDF-Version • Literatur • Schlagwörter • Definitionen • Statistik • PHP-Code • RSS-Feed • Seitenbeginn