Comment représenteriez-vous une collection de hashtables dans un schéma de base de données?

Question

Si vous tentiez de créer un objet de domaine dans un schéma de base de données et que, dans votre code, cet objet de domaine comporte un membre hashtable / list, comme suit:

public class SpaceQuadrant : PersistentObject
{

    public SpaceQuadrant()
    {
    }

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

Un dictionnaire est juste un objet de mappage hashtable / list, menant de clés à valeur. J'ai mis au point plusieurs méthodes pour ce faire, créant différentes tables de jointure ou techniques de chargement, mais elles sont vraiment nulles pour obtenir cet O (1) le temps d'accès que vous obtenez dans une table de hachage.

Comment représenteriez-vous les objets SpaceQuadrant, SpaceCoordinate et Space dans un schéma de base de données? Une simple description du code de schéma serait bien, c'est à dire.

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

mais toute pensée serait bien aussi, merci de votre lecture!

Plus d'informations:

Merci pour les bonnes réponses, je les ai déjà écrasées et je veux prendre le temps de réfléchir à chacune d’elles avant de répondre.

Si vous pensez qu'il existe un meilleur moyen de définir ces classes, montrez-moi un exemple, toutes les langues avec lesquelles vous êtes à l'aise sont cool

Answer 1

Tout d'abord, de nombreuses bases de données sont compatibles avec les données géolocalisées. Différents algorithmes peuvent être utilisés (une version spatiale d'un arbre B existe, par exemple), et la prise en charge des recherches de proximité existera probablement.

Puisque vous avez une table de hachage différente pour chaque SpaceQuadrant, vous avez besoin de quelque chose comme (édité à partir du message de S.Lott):

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

Ceci est un (SpaceCoordinate, Quadrant) - > Dictionnaire SpaceObjectId .

=====

Maintenant, en ce qui concerne votre problème de performances O (1), il existe de nombreuses raisons pour lesquelles il est mal adressé.

Vous pouvez utiliser dans de nombreuses bases de données un index de hachage pour les tables basées sur la mémoire, comme quelqu'un vous l'a dit. Mais si vous avez besoin d'un stockage persistant, vous devez mettre à jour deux tables (la mémoire et la persistante) au lieu d'une (s'il n'y a pas de support intégré pour cela). Pour déterminer si cela vaut la peine, vous devez analyser les données réelles (avec leur taille réelle).

De plus, le fait de forcer une table dans la mémoire peut avoir des conséquences plus graves.

Si quelque chose est interverti, vous êtes mort - si vous aviez utilisé un arbre B (c'est-à-dire un index basé sur disque normal), ses algorithmes auraient minimisé les E / S nécessaires. Sinon, tous les SGBD utiliseraient des tables de hachage et s'appuieraient sur la permutation au lieu des arbres B-Trees. Vous pouvez essayer d’anticiper si vous allez tenir dans la mémoire, mais ...

De plus, les arbres B ne sont pas O (1) mais bien O (log_512 (N)), ou des choses comme ça (je sais que s’effondre en O (log N), mais supportez-moi là-dessus). Vous auriez besoin de (2 ^ 9) ^ 4 = 2 ^ 36 = 64GiB pour que ce soit 4, et si vous avez autant de données, vous aurez de toute façon besoin d'un gros serveur de fer pour qu'il puisse tenir dans la mémoire. Donc, c'est presque O (1), et les facteurs constants sont ce qui compte vraiment.
Avez-vous déjà entendu parler d’algorithmes à faible complexité asymptotique, à grand facteur constant, qui seraient plus rapides que de simples algorithmes juste pour des tailles de données peu pratiques?

Enfin, je pense que les auteurs de DB sont plus intelligents que vous et moi. Surtout compte tenu de la nature déclarative de SQL, l'optimisation manuelle de cette façon ne va pas payer. Si un index tient en mémoire, je suppose qu'ils pourraient choisir de créer et d'utiliser une version hashtable de l'index de disque, si nécessaire, si cela en valait la peine. Examinez vos documents pour cela.

Mais, au fond, l'optimisation prématurée est néfaste, en particulier lorsqu'elle est de ce type (optimisations bizarres que nous pensons nous-mêmes, par opposition aux optimisations SQL standard), et avec un langage déclaratif.

Answer 2

Les relations ne sont pas des tables de hachage; ce sont des ensembles.

Je ne voudrais pas organiser la base de données en utilisant les coordonnées comme clé. Et si un objet change d'emplacement? Au lieu de cela, je traiterais probablement les coordonnées comme des attributs d’un objet.

De plus, je suppose qu’il existe un nombre fixe de dimensions, par exemple trois. Si tel est le cas, vous pouvez stocker ces attributs d’un objet dans des colonnes fixes:

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)
);

Dans votre classe orientée objet, la raison pour laquelle vos objets sont dans un dictionnaire n'est pas claire. Vous mentionnez y avoir accédé dans le temps O (1), mais pourquoi le faites-vous par coordonnée?

Si vous l'utilisez pour optimiser la recherche d'objets se trouvant à proximité d'un certain point (le vaisseau spatial du joueur, par exemple), vous pouvez également intégrer à votre requête SQL qui remplit ce SpaceQuadrant un calcul de la distance de chaque objet par rapport à ce point donné. et triez les résultats par distance.

Je ne connais pas suffisamment votre programme pour savoir si ces suggestions sont pertinentes. Mais vous font-ils au moins penser à différentes façons d’organiser les données?

Answer 3

Dans le cas le plus simple, le dictionnaire comporte une clé qui mapperait la clé primaire d’une table. Ainsi, lorsque vous spécifiez les valeurs de la clé, vous pouvez immédiatement trouver les données correspondantes via une simple recherche.

Dans ce cas, vous auriez besoin d’une table SpaceQuadrant avec tous les attributs généraux (valeur unique) décrivant ou caractérisant un quadrant spatial. La table SpaceQuadrant aurait une clé primaire, éventuellement un identifiant généré, éventuellement une valeur naturelle. La table de hachage consisterait alors en un tableau avec la valeur de clé primaire pour le renvoi croisé du SpaceQuadrant, avec la position (un SpaceCoordinate) et les attributs du quadrant et des coordonnées.

Maintenant, si vous avez un SGBD extensible, vous pouvez définir un type défini par l'utilisateur pour le SpaceCoordinate; à défaut, vous pouvez utiliser un trio de colonnes - x, y, z ou r, thêta, rho, par exemple - pour représenter la position (SpaceCoordinate).

De manière générale, la structure que je décris est assez similaire à celle de Bill Karwin; La différence entre la clé (jeu de mots non prévu avant et après la relecture du message) réside dans le fait qu'il est parfaitement acceptable dans mon livre de placer le poste dans la clé primaire de la table des sub-ordonnées si vous êtes sûr que c'est la meilleure façon de s'organiser. il. Vous pouvez également avoir une colonne ID d'objet qui est une clé candidate alternative. Si les objets ont une existence indépendante du quadrant spatial dans laquelle ils se trouvent (ou peuvent exister à plusieurs endroits - car ils ne sont pas des points mais sont des stations spatiales ou quelque chose de ce genre), alors vous pourriez avoir l'objet SpaceObject dans une table séparée. Le meilleur dépend des informations dont nous ne disposons pas.

Vous devez être conscient des limites d'utilisation d'un SpaceCoordinate dans la clé primaire:

• aucun objet ne peut occuper la même position (c'est ce que l'on appelle une collision dans une table de hachage, ainsi que dans un espace 3D),
• si la position change, vous devez alors mettre à jour les données de clé, ce qui coûte plus cher qu'une mise à jour de données non clés,
• les recherches de proximité seront difficiles - les recherches exactes sont assez faciles.

Il en va de même pour votre dictionnaire en mémoire; si vous modifiez les coordonnées, vous devez supprimer la fiche de l'ancien emplacement et la placer dans le nouvel emplacement du dictionnaire (ou la langue doit le faire pour vous dans les coulisses).

Answer 4

Un dictionnaire est une table. Le hash est une question de quel type d'index est utilisé. La plupart des SGBDR supposent que les tables sont grandes et densément remplies, ce qui rend un index haché inadapté.

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
}

Vos objets Space ont des références FK au quadrant dans lequel ils se trouvent.

En fonction de votre SGBDR, vous pourrez peut-être trouver un index basé sur un hachage qui vous donnera les performances que vous espérez. Par exemple, MySQL, l’utilisation du moteur de stockage HEAP prend en charge les index HASH.