Die allgemeine Frage

Was sind die Unterschiede zwischen Algorithmen, die Datenstrukturen verwenden, und Algorithmen, die Datenbanken verwenden?

Ein Kontext

Dies ist eine Frage, die mich seit einiger Zeit nervt, und ich konnte keine überzeugende Antwort darauf finden.

Derzeit arbeite ich daran, mein Verständnis von Algorithmen zu verbessern, die natürlich stark mit Datenstrukturen verbunden sind. Dies sind grundlegende Strukturen wie Bag, Queue, Stack, Priority Queue und Heap.

Ich verwende auch täglich Datenbanken, um die Daten zu speichern, die vom Endbenutzer verarbeitet und übermittelt oder vom Programm verarbeitet wurden. Ich rufe die Daten ab und sende sie über eine DAL, die über eigene Datenstrukturen verfügt, die basierend auf den Tabellen in der Datenbank generiert werden.

Meine Fragen kommen, wenn ich die Möglichkeit habe, die Daten mithilfe der Datenbank zu sortieren, um sie in aufsteigender / absteigender Reihenfolge geordnet an mich zurückzusenden oder die Daten abzurufen und in meine Logik zu laden, diese Daten in einer Prioritätswarteschlange zu verarbeiten und den Heap zu sortieren alles davon. Oder eine andere Möglichkeit besteht darin, mithilfe der Datenbank nach Datensätzen zu suchen, anstatt eine Teilmenge der Datensätze zu laden und mithilfe einer binären Suche den Datensatz oder die Datensätze zu finden, an denen ich interessiert bin.

In meinen Gedanken würde ich versuchen, möglichst viele Vorgänge auf der Datenbankebene durchzuführen, bevor sie gesendet werden, da die Kommunikation teuer ist. Ich frage mich daher auch, wann Sie Algorithmen und Datenstrukturen verwenden, die streng in Ihrer eigenen Logik definiert sind, um Daten zu verarbeiten, anstatt die der Datenbank.

Also hier sind die Fragen ...

Fragen

1. Was sind die Unterschiede zwischen Datenstrukturen und Datenbanken?
2. Wann verwenden wir Algorithmen, die Datenstrukturen verwenden, die ausschließlich in Ihrer eigenen Logik und nicht in der der Datenbank definiert sind?
3. @ Harvey post: Wann werden die Methoden in der Datenbank weniger effizient als Methoden in Ihrer eigenen Logik?
   • @mirculixx post: Was macht eine Methode effizient?
4. @ Harvey Post: Wie ist die Verarbeitung von Daten mit Datenstrukturen schneller als die Verarbeitung in der Datenbank?

Klarstellungen

1. @Grant post: Die Datenbanken, mit denen ich normalerweise arbeite, sind relational, und diese Fragen ergeben sich aus der Arbeit mit ihnen. Ich denke jedoch, dass diese Fragen auf jedes Persistenz-Framework anwendbar sind (wenn ich Framework sage, meine ich das im allgemeinsten Sinne).

Ich weiß, dass Antworten ohne einen bestimmten Kontext schwierig sind. Denkanstöße, Ratschläge oder Diskussionspunkte sind hauptsächlich das, wonach ich suche und würden mich sehr freuen!

Datenstrukturen sind zum größten Teil:

1. Speicherresident,
2. Vorübergehend,
3. Begrenzte Größe,
4. Kein Wiedereintritt ohne Hinzufügen von Parallelitätsmechanismen wie Sperren oder Unveränderlichkeit,
5. Nicht ACID- konform,
6. Schnell, wenn sorgfältig ausgewählt.

Datenbanken sind zum größten Teil:

1. Festplattengebunden,
2. Hartnäckig,
3. Groß,
4. Sicher gleichzeitig,
5. ACID-konform, mit Transaktionsfunktionen ,
6. Langsamer als Datenstrukturen

Datenstrukturen sollen von einem Ort zum anderen weitergegeben und intern in einem Programm verwendet werden. Wann haben Sie das letzte Mal Daten von einer Webseite mithilfe einer Datenbank an einen Webserver gesendet oder eine Berechnung für eine Datenbank durchgeführt, die sich vollständig im Speicher befand?

Datenbanksysteme verwenden Datenstrukturen als Teil ihrer internen Implementierung. Es ist eine Frage der Größe und des Umfangs; Sie verwenden Datenstrukturen in Ihrem Programm, aber ein Datenbanksystem ist ein eigenständiges Programm.

Was sind die Unterschiede zwischen Datenstrukturen und Datenbanken?

Auf abstrakter Ebene gibt es keine - eine Datenbank ist eine Datenstruktur.

Auf einer bestimmten Ebene haben Datenbanken normalerweise den Zweck, Daten zu speichern, normalerweise in einem Format, das entweder für Einfügungen, Aktualisierungen, Abrufen, Verbinden oder einen anderen Zweck (oder eine Kombination) optimiert ist.

Wenn Sie beispielsweise eine Tabelle in einem RDBMS mit einem Datenarray vergleichen, kann der Unterschied in der Laufzeit des Algorithmus, der Menge an Code, die Sie schreiben müssen, der Menge an Speicher, die Sie zum Ausführen des Algorithmus benötigen, oder liegen die Flexibilität, von außerhalb Ihres Programms / Algorithmus zu arbeiten / auf die Daten zuzugreifen.

Wann verwenden wir Algorithmen, die Datenstrukturen verwenden, die ausschließlich in Ihrer eigenen Logik und nicht in der der Datenbank definiert sind?

In der Tendenz würde ich argumentieren

a) Verwenden einer Datenbank, wenn Sie Daten auf eine Weise beibehalten müssen, auf die über die Laufzeit oder den Zweck des jeweiligen Algorithmus hinaus zugegriffen werden kann.

b) Verwenden Sie Ihre eigene (speicherinterne) Datenstruktur, wenn die Laufzeitgeschwindigkeit eine Rolle spielt oder keine Persistenz erforderlich ist

Wenn Ihr Algorithmus beispielsweise Kundendatensätze verarbeitet, möchten Sie diese Kundendatensätze möglicherweise speichern (z. B. um alle Kunden in einem bestimmten Bereich zu finden), um sie später von einem anderen Programm / Algorithmus zu verwenden und für einen ganz anderen Zweck (z. B. um die wertvollsten Kunden zu finden) ). In diesem Fall ist es wahrscheinlich eine gute Idee, eine Datenbank zum Speichern der Daten zu verwenden.

Beachten Sie jedoch, dass es das Konzept von In-Memory-Datenbanken gibt, bei denen Daten aus Leistungsgründen nicht unbedingt beibehalten werden. ZB Redis oder HANA .

Wann sind die Methoden in der Datenbank weniger effizient als Methoden in Ihrer eigenen Logik?

Die Antwort hängt sehr stark von den Umständen und der (Art der) verwendeten Datenbank ab. Ich würde die Frage umformulieren zu "Was macht eine Methode effizient?" Anschließend werden die Methoden (= Algorithmus) bewertet, die Sie für Ihre eigene Datenstruktur verwenden würden, im Vergleich zu den von der Datenbank verwendeten Methoden. Siehe auch nächster Punkt.

Wie ist die Verarbeitung von Daten mit Datenstrukturen schneller als die Verarbeitung in der Datenbank?

Dies hängt wiederum von den Besonderheiten ab. Im Allgemeinen ist die Verarbeitung von Daten im Arbeitsspeicher, auf die der Prozess, auf dem Ihr Algorithmus ausgeführt wird, direkt zugreifen kann, schneller als das Senden einer Anforderung an einen anderen Prozess (auf demselben Computer oder über ein Netzwerk) und das Zurücksenden der Ergebnisse . Wenn sich die Daten jedoch bereits in der Datenbank befinden, kann das Senden eines Befehls - beispielsweise einer SQL-Anweisung zum Verknüpfen zweier Tabellen und zum Berechnen einer Aggregatfunktion - und das Abrufen nur einer kleinen Zusammenfassung oder Teilmenge der Daten wesentlich effizienter sein als das erstmalige Übertragen aller Daten Daten und Berechnung der Ergebnisse lokal (unter Verwendung Ihrer eigenen Datenstrukturen).

Der Festplattenzugriff ist bei diesem Vorgang in erster Linie am teuersten als der Netzwerkzugriff (http://serverfault.com/questions/238417/are-networks-now-faster-than-disks). Sofern sich Ihre Datenbank nicht in einem 1-Gbit / s-Netzwerk und im selben Netzwerk wie Ihr Web- / Anwendungsserver befindet, ist die Netzwerkleistung für größere Datenmengen nicht so wichtig wie die Festplattenleistung. Oder wenn sich Ihre Daten zufällig auf sehr schnellen Solid-State-Festplatten befinden, die schneller sind als der typische Netzwerkzugriff. Außerdem bieten Datenbanken normalerweise einen IPC-Mechanismus wie Named Pipes anstelle von TCP / IP, wenn sich die Datenbank auf demselben Server wie Ihr Anwendungsserver befindet.

Wenn Sie den größten Teil der gesamten Datenstruktur zwischen den Anforderungen im Speicher behalten können, ist dies im Allgemeinen die schnellste Wahl. Wenn Sie dies nicht können, ist es schwierig, eine gute Datenbankstruktur mit normalisierten Tabellen und geeigneten Indizes für die Such- und Aktualisierungsleistung für andere als kleine Datensätze zu übertreffen, insbesondere in einem System mit Millionen von Datensätzen.

Relationale Datenbanken verwenden normalerweise einen B + -Baum oder eine Variante davon unter der Haube und haben viele Optimierungen wie die Datenausrichtung auf Festplatten- und Pufferpools für Datensätze, auf die häufig zugegriffen wird. Dadurch können sie große Datenmengen schnell verarbeiten, insbesondere wenn es um Aggregation oder Filterung geht.

Was meinst du mit einer Datenbank? Meinen Sie eine relationale Datenbank wie MySQL oder SQL Server? Eine relationale Datenbank ist eine Metadatenstruktur, die eine Teilmenge der vom relationalen Modell definierten Operationen unterstützt . Die Theorie des relationalen Modells, die in den 60er Jahren hauptsächlich von Edgar Codd ausgearbeitet wurde.

Das relationale Modell ist sehr universell und flexibel, aber das bedeutet, dass es die Struktur der Daten oder Zugriffsmuster nicht ausnutzen kann. Datenstrukturen sind nützlich, wenn Sie etwas über die Daten wissen und wissen, wie auf sie zugegriffen wird. Wenn Sie beispielsweise wissen, dass die letzten Daten, die Sie in eine Datenstruktur einfügen, die ersten Daten sind, die Sie ausgeben möchten, können Sie einen Stapel verwenden.

Ich habe die relationale Datenbank als Metadatenstruktur bezeichnet, da es sich im Allgemeinen um ein ziemlich großes Softwarepaket handelt, das viele Datenstrukturen wie Stapel, Warteschlangen, Bäume und Listen verwendet, um die abstrakte Datenstruktur einer relationalen Tabelle zu erstellen.