Stocker une liste réorganisable dans une base de données

Je travaille sur un système de liste de souhaits, dans lequel les utilisateurs peuvent ajouter des éléments à leurs différentes listes de souhaits, et je prévois de permettre aux utilisateurs de commander à nouveau les éléments ultérieurement. Je ne suis pas vraiment sûr de la meilleure façon de stocker cela dans une base de données tout en restant rapide et en évitant les dégâts (cette application sera utilisée par une assez grande base d'utilisateurs, donc je ne veux pas qu'elle tombe en panne nettoyer des choses).

J'ai d'abord essayé une positioncolonne, mais il me semble que ce serait assez inefficace de devoir changer la valeur de position de chaque autre élément lorsque vous les déplacez.

J'ai vu des personnes utiliser une référence propre pour faire référence à la valeur précédente (ou suivante), mais encore une fois, il semble que vous deviez mettre à jour de nombreux autres éléments de la liste.

Une autre solution que j’ai déjà vue consiste à utiliser des nombres décimaux et à ne coller que des éléments entre les espaces, ce qui semble être la meilleure solution jusqu’à présent, mais je suis sûr qu’il doit exister un meilleur moyen.

Je dirais qu'une liste typique contiendrait environ 20 articles environ, et je vais probablement la limiter à 50. La réorganisation se ferait par glisser-déposer et serait probablement effectuée par lots pour éviter les conditions de compétition et autres. demandes ajax. J'utilise postgres (sur heroku) si c'est important.

Quelqu'un a-t-il une idée?

Vive toute aide!

Premièrement, n'essayez pas de faire quelque chose d'intelligent avec les nombres décimaux, car ils vous contrarieront. REALet DOUBLE PRECISIONsont inexacts et peuvent ne pas représenter correctement ce que vous y mettez. NUMERICC’est exact, mais la bonne séquence de mouvements vous fera perdre de la précision et votre mise en œuvre se déroulera mal.

Limiter les mouvements à des hauts et des bas rend l'opération très facile. Pour obtenir une liste d'éléments numérotés séquentiellement, vous pouvez déplacer un élément vers le haut en décrémentant sa position et en incrémentant son numéro, quelle que soit la décrémentation précédente. (En d’autres termes, l’objet 5deviendrait, 4et l’ objet deviendrait ce qu’il 4deviendrait 5, un échange tel que décrit par Morons dans sa réponse.) Le déplacer vers le bas serait l’inverse. Indexez votre table par tout ce qui identifie de manière unique une liste et une position et vous pouvez le faire avec deux UPDATEsecondes dans une transaction qui s'exécutera très rapidement. À moins que vos utilisateurs ne réarrangent leurs listes à une vitesse surhumaine, cela ne causera pas beaucoup de charge.

Les déplacements par glisser-déplacer (par exemple, déplacer un élément 6pour s'asseoir entre eux 9et 10) sont un peu plus compliqués et doivent être effectués différemment selon que la nouvelle position est au-dessus ou au-dessous de l'ancienne. Dans l'exemple ci-dessus, vous devez ouvrir un trou en incrémentant toutes les positions supérieures à 9, en mettant à jour 6la position de l' élément pour qu'elle devienne la nouvelle 10, puis en décrémentant la position de tout élément supérieur à celui 6de combler le vide. Avec la même indexation que j'ai décrite précédemment, ce sera rapide. Vous pouvez en fait accélérer le processus en réduisant le nombre de lignes touchées par la transaction, mais il s'agit d'une microoptimisation dont vous n'avez pas besoin jusqu'à ce que vous puissiez prouver qu'il existe un goulot d'étranglement.

Quoi qu'il en soit, essayer de surpasser la base de données avec une solution maison-trop intelligente-par-moitié ne conduit généralement pas au succès. Les bases de données dignes de ce nom ont été soigneusement rédigées pour effectuer ces opérations très, très rapidement, par des personnes très, très expérimentées dans ce domaine.

Même réponse à partir d'ici https://stackoverflow.com/a/49956113/10608

Solution: créer indexune chaîne (car les chaînes ont essentiellement une "précision arbitraire" infinie). Ou si vous utilisez un int, incrémentez indexde 100 au lieu de 1.

Le problème de performances est le suivant: il n’existe pas de valeur "intermédiaire" entre deux éléments triés.

item      index
-----------------
gizmo     1
              <<------ Oh no! no room between 1 and 2.
                       This requires incrementing _every_ item after it
gadget    2
gear      3
toolkit   4
box       5

Au lieu de cela, faites comme ceci (meilleure solution ci-dessous):

item      index
-----------------
gizmo     100
              <<------ Sweet :). I can re-order 99 (!) items here
                       without having to change anything else
gadget    200
gear      300
toolkit   400
box       500

Encore mieux: voici comment Jira résout ce problème. Leur "rang" (ce que vous appelez index) est une valeur de chaîne qui laisse une tonne de marge de manœuvre entre les éléments classés.

Voici un exemple réel de base de données jira avec laquelle je travaille

   id    | jira_rank
---------+------------
 AP-2405 | 0|hzztxk:
 ES-213  | 0|hzztxs:
 AP-2660 | 0|hzztzc:
 AP-2688 | 0|hzztzk:
 AP-2643 | 0|hzztzs:
 AP-2208 | 0|hzztzw:
 AP-2700 | 0|hzztzy:
 AP-2702 | 0|hzztzz:
 AP-2411 | 0|hzztzz:i
 AP-2440 | 0|hzztzz:r

Remarquez cet exemple hzztzz:i. L'avantage d'un rang de chaîne est que vous manquez de place entre deux éléments, vous n'avez toujours pas à re-classer quoi que ce soit d'autre. Vous commencez simplement à ajouter plus de caractères à la chaîne pour limiter la mise au point.

J'ai vu des personnes utiliser une référence propre pour faire référence à la valeur précédente (ou suivante), mais encore une fois, il semble que vous deviez mettre à jour de nombreux autres éléments de la liste.

Pourquoi? Supposons que vous adoptiez une approche de table par liste liée avec des colonnes (listID, itemID, nextItemID).

L'insertion d'un nouvel élément dans une liste coûte une insertion et une ligne modifiée.

Le repositionnement d'un élément coûte trois modifications de ligne (l'élément en cours de déplacement, l'élément qui le précède et l'élément qui se trouve avant son nouvel emplacement).

Supprimer un élément coûte une suppression et une ligne modifiée.

Ces coûts restent les mêmes, que la liste comporte 10 éléments ou 10 000 éléments. Dans les trois cas, il y a une modification de moins si la ligne cible est le premier élément de la liste. Si vous utilisez plus souvent le dernier élément de la liste, il peut être avantageux de stocker prevItemID plutôt que le suivant.

"mais il semble que cela serait assez inefficace"

Avez-vous mesuré cela? Ou est-ce juste une supposition? Ne faites pas de telles suppositions sans aucune preuve.

"20 à 50 éléments par liste"

Honnêtement, ce n'est pas "beaucoup d'articles", cela ne me semble pas très nombreux.

Je vous suggère de vous en tenir à la "colonne de position" (si c'est la mise en œuvre la plus simple pour vous). Pour de si petites listes, ne commencez pas l'optimisation inutile avant de rencontrer de réels problèmes de performances.

C'est vraiment une question d'échelle et de cas d'utilisation.

Combien d'éléments attendez-vous dans une liste? Si des millions, je pense que la voie décimale est la plus évidente.

Si 6, alors la renumérotation des nombres entiers est le choix évident. s La question est également de savoir comment les listes sont réorganisées. Si vous utilisez des flèches vers le haut et vers le bas (augmentant ou diminuant d'un créneau à la fois), l'i utilise des entiers puis échange avec le précédent (ou le suivant) en mouvement.

Aussi, combien de fois commettez-vous, si l'utilisateur peut effectuer 250 modifications, puis commettez en même temps, que je dis entiers avec renumérotation à nouveau ...

tl; dr: Besoin de plus d’informations.

Edit: "Listes de souhaits" sonne comme beaucoup de petites listes (hypothèse, cela peut être faux) .. Je dis donc Integer avec renumérotation. (Chaque liste contient sa propre position)

Si l'objectif est de minimiser le nombre d'opérations de base de données par opération de réorganisation:

En admettant que

• Tous les articles peuvent être énumérés avec des entiers 32 bits.
• Il existe une limite de taille maximale pour la liste de souhaits d'un utilisateur. (J'ai vu certains sites Web populaires utiliser 20 à 40 éléments comme limite)

Stockez la liste de souhaits triée de l'utilisateur sous la forme d'une séquence compacte d'entiers (tableaux de nombres entiers) dans une colonne. Chaque fois que la liste de souhaits est réorganisée, l'ensemble du tableau (une seule ligne; une seule colonne) est mis à jour - ce qui doit être effectué avec une seule mise à jour SQL.

https://www.postgresql.org/docs/current/static/arrays.html

Si l'objectif est différent, restez fidèle à l'approche "colonne de position".

En ce qui concerne la "vitesse", assurez-vous de comparer l'approche de procédure stockée. Bien que la publication de plus de 20 mises à jour distinctes pour un mélange aléatoire d'une liste de souhaits puisse être lente, il peut y avoir un moyen rapide d'utiliser une procédure stockée.

OK, je suis confronté à ce problème épineux récemment, et toutes les réponses de ce message de questions-réponses ont été inspirantes. Selon moi, chaque solution a ses avantages et ses inconvénients.

• Si le positionchamp doit être séquentiel sans espace, vous devrez alors réorganiser la liste complète. Ceci est une opération O (N). L'avantage est que le côté client n'aurait besoin d'aucune logique particulière pour obtenir la commande.

• Si nous voulons éviter le fonctionnement O (N) MAIS ENCORE maintenir une séquence précise, l’une des méthodes consiste à utiliser "référence à soi pour faire référence à la valeur précédente (ou suivante)". Ceci est un scénario de liste chaînée. De par sa conception, il ne générera PAS "beaucoup d'autres éléments de la liste". Toutefois, cela nécessite que le côté client (un service Web ou peut-être une application mobile) implémente la logique de gestion des déplacements de la liste liée pour dériver la commande.

• Certaines variantes n'utilisent pas de référence, c'est-à-dire une liste chaînée. Ils choisissent de représenter la totalité de la commande en tant que blob autonome, tel qu'un tableau JSON-array-in-a-string [5,2,1,3,...]; cet ordre sera alors stocké dans un endroit séparé. Cette approche a également pour effet secondaire d'exiger que le code côté client maintienne ce blob d'ordre séparé.

• Dans de nombreux cas, nous n'avons pas vraiment besoin de stocker l'ordre exact, nous devons simplement conserver un rang relatif parmi chaque enregistrement. Par conséquent, nous pouvons permettre des écarts entre les enregistrements séquentiels. Les variations comprennent: (1) l’utilisation d’un nombre entier avec des espaces tels que 100, 200, 300 ... mais vous manquerez rapidement d’espaces libres et aurez ensuite besoin du processus de restauration; (2) en utilisant une décimale qui vient avec des espaces naturels, mais vous devrez décider si vous pouvez vivre avec la limitation éventuelle de la précision; (3) en utilisant un classement basé sur une chaîne comme décrit dans cette réponse, mais faites attention aux pièges de mise en œuvre délicats .

• La vraie réponse peut être "ça dépend". Revisitez vos besoins métier. Par exemple, s’il s’agit d’un système de listes de souhaits, j’utiliserais volontiers un système organisé en quelques rangs: "indispensable", "bon à avoir", "peut-être plus tard", puis présenterait des éléments sans ordre dans chaque rang. S'il s'agit d'un système de livraison, vous pouvez très bien utiliser le délai de livraison comme un classement approximatif qui vient avec un fossé naturel (et une prévention des conflits naturels car aucune livraison ne se produirait en même temps). Votre kilométrage peut varier.

Utilisez un nombre à virgule flottante pour la colonne de position.

Vous pouvez ensuite réorganiser la liste en ne modifiant que la colonne de position dans la ligne "déplacée".

Fondamentalement, si votre utilisateur veut positionner "rouge" après "bleu" mais avant "jaune"

Ensuite, il vous suffit de calculer

red.position = ((yellow.position - blue.position) / 2) + blue.position

Après quelques millions de repositionnements, vous obtiendrez peut-être des nombres en virgule flottante si petits qu'il n'y aura pas d '"entre", mais cela est aussi probable que d'observer une licorne.

Vous pouvez implémenter cela en utilisant un champ entier avec un écart initial de 1000. Ainsi, votre ligne initiale serait 1000-> bleu, 2000-> Jaune, 3000-> Rouge. Après avoir "bougé" rouge après bleu, vous auriez 1000-> bleu, 1500-> rouge, 2000-> jaune.

Le problème, c’est qu’avec un écart initial apparemment important de 1 000 à 10 déménagements, vous vous retrouverez dans une situation telle que 1000-> bleu, 1001-puce, 1004-> biege ...... où vous ne pourrez plus insérer quoi que ce soit après "bleu" sans renuméroter toute la liste. En utilisant des nombres à virgule flottante, il y aura toujours un point "à mi-chemin" entre les deux positions.

Bien que le PO ait brièvement évoqué la possibilité d’utiliser une liste liée pour stocker un ordre de tri, il présente de nombreux avantages pour les cas où les articles seront fréquemment réorganisés.

J'ai vu des personnes utiliser une référence propre pour faire référence à la valeur précédente (ou suivante), mais encore une fois, il semble que vous deviez mettre à jour de nombreux autres éléments de la liste.

La chose est - vous ne faites pas ! Lorsque vous utilisez une liste chaînée, l'insertion, la suppression et la réorganisation sont des O(1)opérations. L'intégrité référentielle imposée par la base de données garantit l'absence de références cassées, d'enregistrements orphelins ou de boucles.

Voici un exemple:

CREATE TABLE Wishlists (
  WishlistId int           NOT NULL IDENTITY(1,1) PRIMARY KEY,
  [Name]     nvarchar(200) NOT NULL
);

CREATE TABLE WishlistItems (
  ItemId     int           NOT NULL IDENTITY(1,1),
  WishlistId int           NOT NULL,
  Text       nvarchar(200) NOT NULL,
  SortAfter  int               NULL,

  CONSTRAINT PK_WishlistItem PRIMARY KEY ( ItemId, WishlistId ),
  CONSTRAINT FK_Wishlist_WishlistItem FOREIGN KEY ( WishlistId ) REFERENCES Wishlists ( WishlistId ),
  CONSTRAINT FK_Sorting FOREIGN KEY ( SortAfter, WishlistId ) REFERENCES WishlistItems ( ItemId, WishlistId )
);

CREATE UNIQUE INDEX UX_Sorting ON WishlistItems ( SortAfter, WishlistId );

 -----

SET IDENTITY_INSERT Wishlists ON;

INSERT INTO Wishlists ( WishlistId, [Name] ) VALUES
  ( 1, 'Wishlist 1' ),
  ( 2, 'Wishlist 2' );

SET IDENTITY_INSERT Wishlists OFF;

SET IDENTITY_INSERT WishlistItems ON;

INSERT INTO WishlistItems ( ItemId, WishlistId, [Text], SortAfter ) VALUES
( 1, 1, 'One', NULL ),
( 2, 1, 'Two', 1 ),
( 3, 1, 'Three', 2 ),
( 4, 1, 'Four', 3 ),
( 5, 1, 'Five', 4 ),
( 6, 1, 'Six', 5 ),
( 7, 1, 'Seven', 6 ),
( 8, 1, 'Eight', 7 );

SET IDENTITY_INSERT WishlistItems OFF;

Notez les points suivants:

• Utilisation d'une clé primaire composite et d'une clé étrangère FK_Sortingpour éviter que les éléments ne se réfèrent accidentellement au mauvais élément parent.
• Le UNIQUE INDEX UX_Sortingremplit deux rôles:
  • Comme cela permet une seule NULLvaleur, chaque liste ne peut avoir qu'un seul "élément".
  • Il empêche deux ou plusieurs éléments de prétendre se trouver au même endroit de tri (en évitant les doublons SortAfter).

Les principaux avantages de cette approche:

• Jamais ne nécessite de rééquilibrage ou de maintenance - comme les ordres de tri basés sur intou realbasés sur le disque qui finissent par manquer d’espace entre les éléments après des réorganisations fréquentes.
• Seuls les articles réorganisés (et leurs frères et sœurs) doivent être mis à jour.

Cette approche présente toutefois des inconvénients:

• Vous pouvez uniquement trier cette liste en SQL à l'aide d'un CTE récursif, car vous ne pouvez pas le faire directement ORDER BY.
  • Pour contourner le problème, vous pouvez créer un wrapper VIEWou un fichier TVF utilisant un CTE pour ajouter un dérivé contenant un ordre de tri incrémenté, mais son utilisation serait coûteuse dans les grandes opérations.
• Vous devez charger la liste complète dans votre programme pour pouvoir l'afficher. Vous ne pouvez pas utiliser un sous-ensemble de lignes car la SortAftercolonne fera alors référence aux éléments qui ne sont pas chargés dans votre programme.
  • Cependant, le chargement de tous les éléments d’une liste est facile grâce à la clé primaire composite (c’est-à-dire qu’il suffit de le faire SELECT * FROM WishlistItems WHERE WishlistId = @wishlistToLoad).
• L'exécution de toute opération pendant qu'elle UX_Sortingest activée nécessite la prise en charge par le SGBD des contraintes différées.
  • C'est-à - dire que l'implémentation idéale de cette approche ne fonctionnera pas dans SQL Server jusqu'à ce qu'ils ajoutent une prise en charge des contraintes et index pouvant être différés.
  • Une solution de contournement consiste à transformer l'index unique en un index filtré qui autorise plusieurs NULLvaleurs dans la colonne, ce qui signifie malheureusement qu'une liste peut comporter plusieurs éléments HEAD.
    • Une solution de contournement pour cette solution consiste à ajouter une troisième colonne Statequi est un simple indicateur permettant de déclarer si un élément de la liste est "actif" ou non - et l'index unique ignore les éléments inactifs.
  • C’est quelque chose que SQL Server avait l'habitude de supporter dans les années 90, puis ils ont inexplicablement supprimé le support.

Solution 1: vous devez être capable d'effectuer une tâche triviale ORDER BY.

Voici une vue utilisant un CTE récursif qui ajoute une SortOrdercolonne:

CREATE VIEW OrderableWishlistItems AS 

    WITH c ( ItemId, WishlistId, [Text], SortAfter, SortOrder )
    AS
    (
        SELECT
              ItemId, WishlistId, [Text], SortAfter, 1 AS SortOrder
        FROM
              WishlistItems
        WHERE
              SortAfter IS NULL

        UNION ALL

        SELECT
              i.ItemId, i.WishlistId, i.[Text], i.SortAfter, c.SortOrder + 1
        FROM
              WishlistItems AS i
              INNER JOIN c ON
                  i.WishlistId = c.WishlistId
                  AND
                  i.SortAfter = c.ItemId
    )
    SELECT
        ItemId, WishlistId, [Text], SortAfter, SortOrder
    FROM
        c;

Vous pouvez utiliser cette vue dans d'autres requêtes où vous devez trier les valeurs à l'aide de ORDER BY:

Query:

    SELECT * FROM OrderableWishlistItems

Results:

    ItemId  WishlistId  Text        SortAfter   SortOrder
    1       1           One         (null)      1
    2       1           Two             1       2
    3       1           Three           2       3
    4       1           Four            3       4
    5       1           Five            4       5
    6       1           Six             5       6
    7       1           Seven           6       7
    8       1           Eight           7       8

Solution 2: prévention UNIQUE INDEXdes contraintes de violation lors de l'exécution d'opérations:

Ajouter une Statecolonne à la WishlistItemstable. La colonne est marquée comme HIDDENsi la plupart des outils ORM (comme Entity Framework) ne l'incluraient pas lors de la génération de modèles, par exemple.

CREATE TABLE WishlistItems (
  ItemId     int           NOT NULL IDENTITY(1,1),
  WishlistId int           NOT NULL,
  Text       nvarchar(200) NOT NULL,
  SortAfter  int               NULL,
  [State]    bit           NOT NULL HIDDEN,

  CONSTRAINT PK_WishlistItem PRIMARY KEY ( ItemId, WishlistId ),
  CONSTRAINT FK_Wishlist_WishlistItem FOREIGN KEY ( WishlistId ) REFERENCES Wishlists ( WishlistId ),
  CONSTRAINT FK_Sorting FOREIGN KEY ( SortAfter, WishlistId ) REFERENCES WishlistItems ( ItemId, WishlistId )
);

CREATE UNIQUE INDEX UX_Sorting ON WishlistItems ( SortAfter, WishlistId ) WHERE [State] = 1;

Opérations:

Ajouter un nouvel élément à la fin de la liste:

1. Chargez d'abord la liste pour déterminer le ItemIddernier élément actuel de la liste et la stocker @tailItemIdou l'utiliser SELECT MAX( SortOrder ) FROM OrderableWishlistItems WHERE WishlistId = @listId.
2. INSERT INTO WishlistItems ( WishlistId, [Text], SortAfter ) VALUES ( @listId, @text, @tailItemId ).

Remettre en ordre le point 4 en dessous du point 7

BEGIN TRANSACTION

    DECLARE @itemIdToMove int = 4
    DECLARE @itemIdToMoveAfter int = 7

    DECLARE @prev int = ( SELECT SortAfter FROM WishlistItems WHERE ItemId = @itemIdToMove )

    UPDATE WishlistItems SET [State] = 0 WHERE ItemId IN ( @itemIdToMove , @itemIdToMoveAfter )

    UPDATE WishlistItems SET [SortAfter] = @itemIdToMove WHERE ItemId = @itemIdToMoveAfter 

    UPDATE WishlistItems SET [SortAfter] = @prev WHERE SortAfter = @itemIdToMove 

    UPDATE WishlistItems SET [State] = 1 WHERE ItemId IN ( @itemIdToMove, @itemIdToMoveAfter )

COMMIT;

Enlever l'item 4 du milieu de la liste:

Si un élément se trouve à la fin de la liste (c.-à-d. Où NOT EXISTS ( SELECT 1 FROM WishlistItems WHERE SortAfter = @itemId )), vous pouvez en faire un seul DELETE.

Si un élément est trié après un élément, vous procédez de la même manière que pour réorganiser un élément, sauf que vous le DELETEmodifiez par la suite State = 1;.

BEGIN TRANSACTION

    DECLARE @itemIdToRemove int = 4

    DECLARE @prev int = ( SELECT SortAfter FROM WishlistItems WHERE ItemId = @itemIdToRemove )

    UPDATE WishlistItems SET [State] = 0 WHERE ItemId = @itemIdToRemove

    UPDATE WishlistItems SET [SortAfter] = @prev WHERE SortAfter = @itemIdToRemove

    DELETE FROM WishlistItems WHERE ItemId = @itemIdToRemove

COMMIT;