Comment concevoir une base de données pour stocker une liste triée?

Je cherche à stocker une liste triée dans une base de données. Je souhaite effectuer efficacement les opérations suivantes.

1. Insert (x) - Insère l'enregistrement x dans la table
2. Supprimer (x) - Supprimer l'enregistrement x de la table
3. Before (x, n) - Renvoie les enregistrements 'n' précédant l'enregistrement x dans la liste triée.
4. After (x, n) - Renvoie les enregistrements 'n' qui succèdent à l'enregistrement x dans la liste triée.
5. Premier (n) - Renvoie les premiers n enregistrements de la liste triée.
6. Dernier (n) - Renvoie les derniers n enregistrements de la liste triée.
7. Comparer (x, y) - Deux enregistrements x et y de la table, trouver si x> y.

La méthode simple à laquelle je pouvais penser est de stocker une sorte d'attribut 'rang' dans la table et d'interroger en triant sur cet attribut. Mais dans cette méthode, insérer / modifier un enregistrement avec un rang devient une opération coûteuse. Y a-t-il une meilleure méthode?

Plus précisément, je cherche à implémenter la table en utilisant SimpleDB d'Amazon. Mais une réponse générale à une base de données relationnelle devrait également être utile.

Mise à jour sur le profil de charge:

Comme je prévois cela pour une application Web, cela dépend du nombre d'utilisateurs qui l'utilisent.

S'il y a 100 000 utilisateurs actifs (super optimisme: P), alors mon estimation très approximative par jour serait

500 000 sélections, 100 000 insertions et suppressions, 500 000 mises à jour

Je m'attendrais à ce que la table atteigne 500k au total.

Je cherche à optimiser les opérations de mise à jour, d’insertion et de comparaison. Le classement des objets changera constamment et je dois tenir le tableau à jour.

Si le classement n'est pas complètement arbitraire, mais qu'il peut être déduit d'une autre propriété (par exemple, nom, score du joueur, etc.), examinez attentivement la réponse de Joel .

S'il s'agit d' une propriété arbitraire de vos données, elle doit être stockée sous forme de colonne dans votre table d'enregistrements. En supposant que SimpleDB d'Amazon soit similaire au SGBDR classique, vous pouvez alors indexer cette colonne et satisfaire rapidement toutes vos requêtes ci-dessus avec la stratégie d'indexation appropriée. Ceci est normal pour un SGBDR.

Étant donné que vous vous attendez à une activité d'insertion et de mise à jour élevée, mais également à une activité de lecture relativement élevée, je vous recommande de procéder comme suit:

• Cluster la table sur le rang, surtout si la grande majorité de vos requêtes sont contre rang. Si ce n'est pas le cas, ou si le choix d'une clé de cluster n'est pas disponible dans SimpleDB, créez simplement un index avec rang comme colonne de tête. Cela satisferait les requêtes 3 à 6.
• Un index sur l’enregistrement d’abord, puis un rang (ou, dans le monde SQL Server, un INCLUDErang et un rang, ou simplement un enregistrement si vous avez mis en cluster sur un rang) satisferaient la requête 7.
• Les opérations 1 et 2 peuvent être optimisées en espaçant vos données de manière appropriée (c.-à-d. En définissant le FILLFACTORdans SQL Server). Ceci est particulièrement important si vous vous regroupez sur un rang.
• Au fur et à mesure que vous insérez ou mettez à jour des rangs, maintenez le plus possible l’écart entre les numéros de rangs afin de minimiser la possibilité que vous deviez reclasser un enregistrement existant pour permettre l’insertion ou la mise à jour de rangs. Par exemple, si vous classez vos enregistrements par pas de 1 000, vous laissez assez de place pour environ la moitié du nombre de modifications et d'insertions avec un minimum de chance, vous devrez redéfinir le classement d'un enregistrement qui n'est pas directement impliqué dans ces modifications.
• Chaque nuit, re-classer tous les enregistrements pour réinitialiser les écarts de classement entre eux.
• Vous pouvez ajuster la fréquence des reclassements en masse ainsi que la taille de l'écart entre les classements afin de l'adapter au nombre d'insertions ou de mises à jour prévu par rapport au nombre d'enregistrements existants. Donc, si vous avez 100 000 enregistrements et que vos insertions et mises à jour représentent 10% de ce total, laissez assez de place pour 10 000 nouveaux rangs et procédez à un nouveau classement tous les soirs.
• Ré-classer 500 000 enregistrements est une opération coûteuse, mais une fois par jour ou par semaine en dehors des heures de bureau devrait convenir à une base de données comme celle-là. Ce reclassement de masse en dehors des heures de travail pour maintenir les écarts de classement vous évite de devoir reclasser de nombreux enregistrements pour chaque mise à jour ou insertion de classement pendant vos heures normales et de pointe.

Si vous vous attendez à plus de 100 000 lectures sur une table de taille supérieure à 100 000, je vous déconseille d'utiliser la méthode de la liste chaînée. Il ne sera pas adapté à ces tailles.

J'utilise généralement la méthode "rang" que vous décrivez. Plutôt que de perdre du temps avec la mise à jour des lignes lorsque des éléments devaient être réorganisés, j'ai souvent réussi à supprimer tous les enregistrements de la liste et à réinsérer de nouveaux éléments dans le bon ordre. Cette méthode est clairement optimisée pour la récupération.

Une autre approche consisterait à modéliser les enregistrements sous forme de liste chaînée en utilisant une colonne de clé étrangère réflexive "prédécesseur" sur la table:

ID   setID   item       predecessor
---  ------  ------     ------------
1    1       Apple      null
2    1       Orange     1
3    2       Cucumber   null
4    1       Pear       2
5    1       Grape      4
6    2       Carrot     3

Vous pouvez facilement récupérer une liste et ajouter et supprimer des éléments avec un léger surcoût, mais il sera difficile de sortir les enregistrements dans le bon ordre. Peut-être y a-t-il une façon intelligente de le faire en une seule requête, probablement avec beaucoup de jointures de table avec alias.

J'utilise souvent cette dernière approche lorsque je modélise une relation en arborescence (catégories, dossiers, ensembles et sous-ensembles). J'ai généralement eu une fonction récursive pour reconstruire l'arborescence complète dans mon application.

Je pense que la chose à faire est de stocker la ou les propriétés qui sont utilisées pour calculer le rang , puis de construire un index sur elles. Plutôt que d'essayer de forcer la base de données à stocker physiquement les données dans un ordre hiérarchisé ou à l'aide d'une liste chaînée gérée manuellement, pourquoi ne pas laisser le moteur de base de données faire ce pour quoi il a été conçu?

Ce sont les limitations d'un système non-SGBDR tel que simpleDB. Les fonctionnalités dont vous avez besoin ne peuvent pas être implémentées du côté de la base de données dans simpleDB, elles doivent être implémentées du côté de la programmation / de l'application.

Pour un SGBDR SQL server, les fonctionnalités dont vous avez besoin sont rudimentaires pour l’index clusterisé.

• Insérer (x) - Insérer l'enregistrement x dans le tableau> Insertion simple.
• Supprimer (x) - Supprimer l'enregistrement x de la table> Suppression simple.

• Before (x, n) - Renvoie les enregistrements 'n' précédant l'enregistrement x dans la liste triée. > Sélectionnez les n premiers résultats où x est inférieur à valeur et commande par clause.

• After (x, n) - Renvoie les enregistrements 'n' qui succèdent à l'enregistrement x dans la liste triée. > Sélectionnez les n premiers résultats où x est supérieur à valeur et commande par clause.

• Premier (n) - Renvoie les premiers n enregistrements de la liste triée. > Sélectionnez les n premiers résultats.

• Dernier (n) - Renvoie les derniers n enregistrements de la liste triée. > Sélectionnez les n premiers résultats après ordre en desc.

• Comparer (x, y) - Deux enregistrements x et y de la table, trouver si x> y. > Instruction TSQL IF.

Voici ce que j'avais l'habitude de re-classer ma table Postgres après chaque insertion:

CREATE OR REPLACE FUNCTION re_rank_list() RETURNS trigger AS $re_rank_list$
DECLARE
    temprow record;
    row_idx integer := 1;    
BEGIN
    FOR temprow IN
    SELECT * FROM your_schema.your_list WHERE list_id = NEW.list_id ORDER BY rank ASC
    LOOP
        UPDATE your_schema.your_list SET rank = row_idx * 100 WHERE id = temprow.id;
        row_idx := row_idx + 1;
    END LOOP;
    RETURN NEW;
END;
$re_rank_list$ LANGUAGE plpgsql;


CREATE TRIGGER re_rank_list AFTER UPDATE ON your_schema.your_list_value
    FOR EACH ROW 
    WHEN (pg_trigger_depth() = 0)
    EXECUTE PROCEDURE re_rank_list();

Pour mon cas d'utilisation, la performance n'est pas une préoccupation, mais il est important de pouvoir compter sur sa capacité à ne jamais casser ou à agir bizarrement.