AGB  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Algorithmen, Datenstrukturen und Klassendesign FreePascal Suche Datenstruktur für Index in Datei und RAM - Kombination Array+indexed AVL-Baum?

Suche Datenstruktur für Index in Datei und RAM - Kombination Array+indexed AVL-Baum?

Offene Frage von "himitsu"
Ein Thema von Laser · begonnen am 15. Apr 2012 · letzter Beitrag vom 16. Apr 2012
Antwort Antwort
Laser

Registriert seit: 1. Jan 2009
Ort: Ubunutu 10.10
18 Beiträge
 
FreePascal / Lazarus
 
#1

Suche Datenstruktur für Index in Datei und RAM - Kombination Array+indexed AVL-Baum?

  Alt 15. Apr 2012, 16:39
Hallo,

ich bin dabei, eine Datenstruktur für einen Index auszuwählen. Eine Datenbank soll nicht verwendet werden. Zu Lasten der RAM-Verwendung soll eine extreme Beschleunigung erreicht werden. Könnt Ihr meine bisherigen Überlegungen bitte kommentieren, was man vielleicht anders oder besser machen könnte. Vielen Dank.

Der Index besteht aus Int64 auf der Festplatte und ist aufsteigend sortiert.

furtbichler hat hier schon einmal ein paar Kriterien für die Entscheidung benannt.
Auf den Index wird sehr häufig zugegriffen.
90% Lesen, Zugriff auf neu eingefügte Datensätze ist wahrscheinlicher als auf alte Datensätze
10% Einfügen, hinten anhängen ist unwahrscheinlich (ohne die Sortierung zu verlieren)
0% Löschen, kommt nicht vor

Die Datei wird komplett in ein Array eingelesen (blockread). Die Datei wird in der Regel < 1 GiB groß sein.
Neue Datensätze werden in einen indexierten AVL-Baum (TIndexedAVLTree) eingefügt.
Beim Lesezugriff wird im Array und im AVL-Baum gesucht.
Beim Schließen der Indexdatei werden Array und Baum gemergt und sortiert auf die Platte geschrieben.

Vorteile:
Hohe Lesegeschwindigkeit durch kompletten Index im RAM.
Schnelles Einfügen neuer Datensätze in den Baum.

Nachteile:
Zusätzlicher Speicherbedarf für out-of-place natural merge sort.
Index muss bei ungeplantem Programmabbruch neu aufgebaut werden.


Was meint Ihr?
Liebe Grüße
Laser
  Mit Zitat antworten Zitat
Patito

Registriert seit: 8. Sep 2006
97 Beiträge
 
#2

AW: Suche Datenstruktur für Index in Datei und RAM - Kombination Array+indexed AVL-Ba

  Alt 16. Apr 2012, 08:23
Als Datensuruktur wäre statt AVL-Tree sicher auch ein RedBlack-Tree oder ein B-Tree passend.
B-Trees scheinen ja für File-orientierte Angelegenheiten recht gut zu sein. Persönlich verwende ich zur Zeit immer RedBlack-Trees.
Ein AVL-Tree ist aber sicher auch eine gute Wahl.
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
1.553 Beiträge
 
FreePascal / Lazarus
 
#3

AW: Suche Datenstruktur für Index in Datei und RAM - Kombination Array+indexed AVL-Ba

  Alt 16. Apr 2012, 08:42
Nachteile:
  1. Zusätzlicher Speicherbedarf für out-of-place natural merge sort.
  2. Index muss bei ungeplantem Programmabbruch neu aufgebaut werden.
  1. Denke ich nicht. Da alles sortiert ist (Minimum findet man im AVL-Baum ja auch schnell), kannst du immer durch das Mergen einen Puffer füllen, den du dann auf die Platte schreibst und wiederverwendest.
  2. Du könntest neu in den Index eingefügte Datensätze ungeordnet auf die Platte schreiben, dann musst du nicht denn ganzen Index neu erstellen, sondern kannst den AVL-Baum neu aufbauen. Da müsste man sich noch sicherstellen, dass ein Datensatz erst dann als "sicher" eingefügt gilt (und so an den Clienten gemeldet wird), wenn er auch im Index ist (zumindest in der Sicherungsdatei, flushen nicht vergessen). Das wäre der Aufwand, den dir eine Datenbank abnehmen würde
Robert

Geändert von BUG (16. Apr 2012 um 08:44 Uhr)
  Mit Zitat antworten Zitat
Iwo Asnet

Registriert seit: 11. Jun 2011
313 Beiträge
 
#4

AW: Suche Datenstruktur für Index in Datei und RAM - Kombination Array+indexed AVL-Ba

  Alt 16. Apr 2012, 10:04
Ich würde auch einen BTree + Cache nehmen. Es existieren diverse Delphi-Implementierungen im Netz.
Der große Vorteil wäre der, das das Ding komplett skalierbar ist und auch bei 200 PetaByte noch schnell genug ist.

Richtig fix wird es durch die Verwendung eines MRU-Caches, bei dem die letzten N benötigten Seiten im Speicher gehalten werden.

Eine 'Seite' entspricht einem Blatt/Knoten des BTree-Baumes und ist i.A. 8k groß (weil das die Systempage-Größe von Windows ist).

Wenn Du das Teil fertig hast, könnte man sich überlegen, ob eine Indexierung per Hashmap oben drauf nicht noch besser wäre.

Riesenvorteil: Der Btree erzeugt gleichzeitig die Datei mit den Daten. Wenn deine Anwendung selten gestartet wird, dann kannst Du die DB am Anfang komplett einlesen (also die Schlüssel) und die Recordnummern / Position der Daten in der Datei in der Hashmap ablegen.

Dann suchst Du über die Hashmap in optimal kurzer Zeit und bist auch beim Einfügen noch schnell. Leider ist ein Btree beim Einfügen nicht wirklich sauschnell. Abhilfe schafft hier eine art Transaktionskontrolle: Beim Einfügen mehrerer Datensätze werden einzelne Seiten verändert. Um das redundante mehrfach hintereinander stattfindende Schreiben einer Seite zu optimieren, könntest Du die zu schreibenden Seiten vormerken und erst beim 'Commit' (oder einem 'Flush'-Befehl) einmalig speichern.

Überlege dir noch, ob nicht eine einfache simple DB ausreicht, denn eigentlich programmierst du mit dem o.g. Verfahren eine generische DB.
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
27.553 Beiträge
 
Delphi XE3 Professional
 
#5

AW: Suche Datenstruktur für Index in Datei und RAM - Kombination Array+indexed AVL-Ba

  Alt 16. Apr 2012, 10:24
'ne eigene Cache braucht man nicht unbedingt zu implementieren, wenn man nicht das Cachingmuster (was wann wie geladen und freigegeben wird) selbst implementieren will, sondern einem 'nen einfaches Verhalten ausreicht

Zugriffe über TStream oder über eine MMF werden eh über die Windows File Cache umgeleitet.


Wenn man es schaft den Speicher des BTree (oder sonstewas) als einen zusammenhängenden Speicherblock (oder als ein paar Blöcke) im RAM abzubilden (z.B. die einzelnen Einträge nicht über Delphi-Referenz durchsuchenNew, sondern in einem statischen Array), dann könnte man diesen auch in eine MMF legen.
Dann könnte das Programm abstürzen, aber die Daten blieben erhalten.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014

Geändert von himitsu (16. Apr 2012 um 10:49 Uhr)
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 04:13 Uhr.
Powered by vBulletin® Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2014 by Daniel R. Wolf