Wie würden Sie eine Hash-Tabelle Sammlung in einem Datenbank-Schema darstellen?

StackOverflow https://stackoverflow.com/questions/449202

Frage

Wenn Sie versuchen, ein Domäne-Objekt in einem Datenbankschema zu erstellen, in seinem Code des Domain-Objekt verfügt über ein Hash-Tabelle / Liste Mitglied, etwa so: 

public class SpaceQuadrant : PersistentObject
{

    public SpaceQuadrant()
    {
    }

    public virtual Dictionary<SpaceCoordinate, SpaceObject> Space
    {
        get;
        set;
    }
}

Ein Wörterbuch ist nur ein Hash-Tabelle / Liste Mapping-Objektschlüssel auf Wert-Taste, ich habe mit mehreren Möglichkeiten, um dies zu tun, verschiedene Techniken Tabellen oder Laden verbinden zu schaffen, aber sie alle Art in Hinblick auf die immer, dass O saugen (1) Zugriffszeit, die Sie in einer Hash-Tabelle erhalten.

Wie würden Sie die SpaceQuadrant, SpaceCoordinate und Raumobjekt in einem Datenbankschema darstellen? Ein einfaches Schema Code Beschreibung wäre schön, dh. 

table SpaceQuadrant
{
    ID int not null primary key,
    EntryName varchar(255) not null,
    SpaceQuadrantJoinTableId int not null
                 foreign key references ...anothertable...
}

aber alle Gedanken überhaupt wäre auch, vielen Dank für das Lesen schön!

Weitere Informationen:

Vielen Dank für die großen Antworten, schon habe ich abgeschöpft nur sie, und ich möchte einige Zeit über jedes Denken nehmen, bevor ich reagieren.

Wenn Sie denken, es gibt einen besseren Weg, um diese Klassen zu definieren, dann mit allen Mitteln zeigen Sie mir ein Beispiel, jede Sprache Ihres komfortabel mit cool

War es hilfreich?

Lösung

Zuerst engagierte Unterstützung für geo-lokalisierten Daten gibt es in vielen Datenbanken - verschiedene Algorithmen verwendet werden können (eine räumliche Version eines B-Baum existiert zum Beispiel), und die Unterstützung für die Nähe sucht, wird wahrscheinlich existieren

.

Da Sie eine andere Hash-Tabelle für jeden SpaceQuadrant haben, werden Sie so etwas wie müssen (herausgegeben von S. Lott des post): 

table Space {
    SpaceCoordinate,
    Quadrant Foreign Key SpaceQuadrant(ID),
    SpaceObject -- whatever the object is (by ID)
    Primary Key(SpaceCoordinate, Quadrant)
}

Dies ist ein (SpaceCoordinate, Quadrant) -> SpaceObjectId Wörterbuch.

=====

Nun, über Ihre O (1) Leistung betreffen, gibt es eine Menge Gründe, warum es falsch adressiert.

Sie können für speicherbasierte in vielen DB einen Hash-Index verwenden, Tabellen, wie jemand Ihnen gesagt. Aber wenn Sie persistenten Speicher benötigen, würden Sie zwei Tabellen aktualisieren müssen (der Speicher ein und hartnäckige) anstelle eines (wenn es keine eingebaute Unterstützung für diese ist). Um herauszufinden, ob das wert ist, Sie Benchmarks auf den tatsächlichen Daten benötigen würden (mit aktuellen Datengrößen).

Auch eine Tabelle in den Speicher zwingen kann schlimme Auswirkungen hat.

Wenn etwas jemals getauscht wird, du bist tot - wenn Sie ein B-Baum (das heißt normale Disk-basierten Index) verwendet hatte, seine Algorithmen würden die benötigten I / O haben minimiert. Andernfalls würden alle DBMS Hash-Tabellen verwenden und verlassen sich auf Swapping, statt B-Trees. Sie können versuchen, zu antizipieren, ob Sie in den Speicher passen wird, aber ...

Darüber hinaus B-Bäume sind nicht O (1), aber sie sind O (log_512 (N)), oder wie das Zeug (ich weiß, dass auf O (log N) zusammenbricht, sondern tragen mich auf diese). Sie müssen (2 ^ 9) ^ 4 = 2 ^ 36 = 64GiB für die 4 zu sein, und wenn man so viele Daten haben werden Sie einen großen Eisen Server benötigen ohnehin, dass in dem Speicher zu passen. Also, es ist fast O (1), und die konstanten Faktoren sind, was eigentlich zählt.
Schon gehört zu Niederspannungs- asymptotisch-Komplexität, großer konstanter Faktor Algorithmen, das nur auf unpraktische Datengrößen schneller als einfaches wäre?

Schließlich glaube ich, DB Autoren sind klüger als ich und du. Vor allem die deklarative Natur der SQL gegeben, von Hand zu optimieren es auf diese Weise ist nicht dafür bezahlen. Wenn ein Index in dem Speicher paßt, ich denke, sie wählen könnte zu bauen und eine Hash-Tabelle Version des Disk-Index zu verwenden, je nach Bedarf, wenn es es wert ist. Untersuchen Sie Ihre Dokumente für das.

Aber das Endergebnis ist, dass vorzeitige Optimierung Übel ist, vor allem wenn es von dieser Art (seltsame Optimierungen uns auf unserem eigenes Denken, wie es als Standard-SQL-Optimierungen gegen) und mit einer deklarativen Sprache.

Andere Tipps

Die Beziehungen sind nicht Hash-Tabellen; sie sind Sätze.

Ich würde die Datenbank unter Verwendung der Koordinaten als Schlüssel nicht organisieren. Was passiert, wenn ein Objekt ändert Standort? Stattdessen würde ich wahrscheinlich Koordinaten behandeln, als Attribute ein Objekt.

Auch nehme ich es eine feste Anzahl von Dimensionen ist, beispielsweise drei. Wenn ja, dann können Sie speichern diese Attribute eines Objekts in festen Spalten: 

CREATE TABLE SpaceQuadrant (
  quadrant_id INT NOT NULL PRIMARY KEY,
  quadrant_name VARCHAR(20)
  -- other attributes
);

CREATE TABLE SpaceObject (
  object_id INT NOT NULL PRIMARY KEY,
  x NUMERIC(9,2) NOT NULL,
  y NUMERIC(9,2) NOT NULL
  z NUMERIC(9,2) NOT NULL,
  object_name VARCHAR(20) NOT NULL,
  -- other attributes
  quadrant_id INT NOT NULL,
  FOREIGN KEY (quadrant_id) REFERENCES SpaceQuadrant(quadrant_id)
);

In Ihrer objektorientierten Klasse, es ist nicht klar, warum Ihre Objekte in einem Wörterbuch sind. Sie erwähnen sie in O (1) Zeit zugreifen, aber warum tun Sie das durch koordinative?

Falls Sie verwenden Objekte zu optimieren zu finden, die in der Nähe von einem bestimmten Punkt sind (das Raumschiff des Spielers, zum Beispiel), können Sie auch in Ihre SQL-Abfrage erstellen, die diese eine Berechnung eines jeden von diesem bestimmten Punkt Abstand des Objekts SpaceQuadrant auffüllt und die Ergebnisse nach Entfernung sortiert werden.

Ich weiß nicht genug über Ihr Programm zu wissen, ob diese Vorschläge relevant sind. Aber sind sie zumindest, dass Sie denken, verschiedene Möglichkeiten, die Daten zu organisieren?

Im einfachstenen Fall hat das Wörterbuch eine Taste, die den Primärschlüssel einer Tabelle zuordnen würde -. So, dass, wenn Sie die Werte des Schlüssels angeben, können Sie sofort die passenden Daten über eine einfache Lookup finden

In diesem Fall würden Sie eine Tabelle SpaceQuadrant mit einem allgemeinen benötigen (einwertig) Attributen, die einen Raum Quadranten beschreiben oder charakterisieren. Die SpaceQuadrant Tabelle würde einen Primärschlüssel, möglicherweise eine generierte ID, möglicherweise einen natürlichen Wert. Die Hash-Tabelle würde dann aus einer Tabelle mit dem Primärschlüsselwert für Querverweise die SpaceQuadrant, mit der Position (a SpaceCoordinate) und die Attribute des Quadranten und koordinieren.

Wenn Sie nun eine erweiterbare DBMS haben, können Sie einen benutzerdefinierten Typ für die SpaceCoordinate definieren; x, y, z oder r, theta, rho, zum Beispiel - - ersatzweise kann ein Trio von Spalten verwenden, um die Position (SpaceCoordinate) darzustellen

.

Generell ist die Struktur I beschreiben mich ist ganz ähnlich wie Bill Karwin ist; der Schlüssel (Wortspiel nicht beabsichtigt, bis ich die Nachricht wurde rereading) Unterschied ist, dass es in meinem Buch vollkommen in Ordnung ist, die Position als Teil des Primärschlüssels der Unterkoordinatentabelle zu haben, wenn Sie sicher sind, das ist die beste Art und Weise zu organisieren es. Sie könnten auch eine Objekt-ID-Spalte, die ein alternativer Kandidatenschlüssel ist. Alternativ kann, wenn Objekte eine Existenz unabhängig von der Raum Quadranten haben sie in in dem Moment geschehen sein (oder kann in mehreren Positionen bestehen - weil sie keine Punkte sind, sondern Raumstationen oder etwas), dann könnten Sie die SpaceObject in a haben separate Tabelle. Was am besten ist, hängt von Informationen, die wir uns nicht zur Verfügung stehen.

Sie sollten sich bewusst sein die Grenzen eines SpaceCoordinate als Teil des Primärschlüssel:

  • keine zwei Objekte können die gleiche Position einnehmen (dass eine Kollision in einer Hash-Tabelle genannt wird, sowie im 3D-Raum),
  • , wenn die Position ändert, dann müssen Sie die Schlüsseldaten aktualisieren, die als ein Update auf Nicht-Schlüsseldaten teurer ist,
  • Nähe Lookups wird schwer sein - genaue Lookups einfach genug sind
    • .

Das gleiche Ihres Wörterbuch im Speicher true; wenn Sie die Koordinaten ändern, müssen Sie den Datensatz aus der alten Position entfernen und es in den neuen Standort im Wörterbuch platzieren (oder die Sprache muss, dass hinter den Kulissen für Sie tun).

Ein Wörterbuch ist ein Tisch. Der Hash ist eine Frage, welche Art von Index verwendet wird. Die meisten RDBMS gehen davon aus, dass Tische sind groß und dicht gepackte, ein Hash-Index nicht geeignet zu machen. 

table SpaceQuadrant { 
    ID Primary Key,
    -- whatever other attributes are relevant
}

table Space {
    SpaceCoordinate Primary Key,
    Quadrant Foreign Key SpaceQuadrant(ID),
    SpaceObject -- whatever the object is
}

Your Space Objekte FK Verweise auf den Quadranten, in dem sie sich befinden.

auf Ihrem RDBMS Je könnten Sie in der Lage sein, einen Hash-basierter Index zu finden, die Ihnen die Leistung für Sie hoffen bekommt. Zum Beispiel MySQL, unterstützt die HEAP Speicher-Engine mit HASH Indizes.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top