Liste liée en SQL

Question

Quel est le meilleur moyen de stocker une liste chaînée dans une base de données mysql afin que les insertions soient simples (c'est-à-dire que vous n'ayez pas à réindexer un tas de choses à chaque fois) et que la liste puisse être facilement extraite dans l'ordre.

Answer 1

Stockez une colonne entière dans votre tableau appelée "position". Enregistrez un 0 pour le premier élément de votre liste, un 1 pour le deuxième, etc. Indexez cette colonne dans votre base de données et, lorsque vous souhaitez extraire vos valeurs, triez-le en fonction de cette colonne.

 alter table linked_list add column position integer not null default 0;
 alter table linked_list add index position_index (position);
 select * from linked_list order by position;

Pour insérer une valeur à l'index 3, modifiez les positions des lignes 3 et supérieures, puis insérez:

 update linked_list set position = position + 1 where position >= 3;
 insert into linked_list (my_value, position) values ("new value", 3); 

Answer 2

En utilisant la solution d'Adrian, mais au lieu d'incrémenter de 1, incrémentez de 10 voire 100. Ensuite, les insertions peuvent être calculées à la moitié de la différence de ce que vous insérez sans avoir à tout mettre à jour en dessous de l'insertion. Choisissez un nombre suffisamment important pour gérer le nombre moyen d'insertions. S'il est trop petit, vous devrez alors mettre à jour toutes les lignes avec une position plus haute lors d'une insertion.

Answer 3

créez une table avec deux colonnes auto-référencées PreviousID et NextID. Si l'élément est la première chose dans la liste PreviousID sera null, si c'est le dernier, NextID sera null. Le code SQL ressemblera à quelque chose comme ceci:

create table tblDummy
{
     PKColumn     int     not null, 
     PreviousID     int     null, 
     DataColumn1     varchar(50)     not null, 
     DataColumn2     varchar(50)     not null,  
     DataColumn3     varchar(50)     not null, 
     DataColumn4     varchar(50)     not null, 
     DataColumn5     varchar(50)     not null, 
     DataColumn6     varchar(50)     not null, 
     DataColumn7     varchar(50)     not null, 
     NextID     int     null
}

Answer 4

Une liste chaînée peut être stockée en utilisant des pointeurs récursifs dans la table. C’est à peu près les mêmes hiérarchies que Sql qui utilisent le modèle d’association récursif.

Pour en savoir plus à ce sujet, ici .

J'espère que cela vous aidera.

Answer 5

L'option la plus simple serait de créer une table avec une ligne par élément de liste, une colonne pour la position de l'élément et des colonnes pour les autres données de l'élément. Ensuite, vous pouvez utiliser ORDER BY sur la colonne de position pour récupérer dans l'ordre souhaité.

create table linked_list
(   list_id   integer not null
,   position  integer not null 
,   data      varchar(100) not null
);
alter table linked_list add primary key ( list_id, position );

Pour manipuler la liste, mettez à jour la position, puis insérez / supprimez les enregistrements selon vos besoins. Donc, pour insérer un élément dans la liste 1 à l'index 3:

begin transaction;

update linked_list set position = position + 1 where position >= 3 and list_id = 1;

insert into linked_list (list_id, position, data)
values (1, 3, "some data");

commit;

Etant donné que les opérations de la liste peuvent nécessiter plusieurs commandes (par exemple, une insertion nécessite un INSERT et une UPDATE), veillez à toujours exécuter les commandes dans une transaction.

Une variante de cette option simple consiste à incrémenter la position d’un facteur à l’autre, par exemple de 100. Ainsi, lorsque vous effectuez une opération INSERT, vous n’avez pas toujours besoin de renuméroter la position des éléments suivants. Cependant, cela nécessite un peu plus d'effort pour savoir quand incrémenter les éléments suivants. Vous perdrez donc en simplicité, mais vous gagnerez en performance si vous avez plusieurs inserts.

En fonction de vos besoins, d'autres options pourraient vous intéresser, telles que:

• Si vous souhaitez effectuer de nombreuses manipulations sur la liste et peu d'extraits, vous préférerez peut-être une colonne ID pointant vers l'élément suivant de la liste, au lieu d'utiliser une colonne de position. Ensuite, vous devez utiliser une logique itérative lors de l'extraction de la liste afin de mettre les éléments en ordre. Cela peut être mis en œuvre relativement facilement dans un processus stocké.

• Si vous avez plusieurs listes, un moyen rapide de sérialiser et de désérialiser votre liste en texte / binaire et si vous souhaitez uniquement stocker et récupérer la liste complète, stockez ensuite la liste entière sous forme de valeur unique dans un fichier. seule colonne. Ce n’est probablement pas ce que vous demandez ici.

Answer 6

Cet article est vieux mais il va quand même donner mon 0,02 $. Mettre à jour tous les enregistrements d'une table ou d'un ensemble d'enregistrements semble insensé pour résoudre un ordre. le montant de l'indexation est également fou, mais il semble que la plupart l'ont accepté.

La solution folle que j'ai proposée pour réduire les mises à jour et l'indexation consiste à créer deux tables (et dans la plupart des cas d'utilisation, vous ne triez pas tous les enregistrements dans une seule table). La table A contient les enregistrements de la liste en cours de tri et la table B, le groupe et un enregistrement de la commande sous forme de chaîne. la chaîne de commande représente un tableau pouvant être utilisé pour classer les enregistrements sélectionnés sur le serveur Web ou la couche de navigateur d'une application de page Web.

Create Table A{
Id int primary key identity(1,1),
Data varchar(10) not null
B_Id int
}

Create Table B{
Id int primary key Identity(1,1),
GroupName varchat(10) not null,
Order varchar(max) null
}

Le format de la commande doit être id, position et un séparateur pour diviser () votre chaîne. Dans le cas de l'interface utilisateur jQuery, la fonction .sortable ('serialize') génère pour vous une chaîne de commande compatible POST, qui comprend l'identifiant et la position de chaque enregistrement de la liste.

La vraie magie réside dans la façon dont vous choisissez de réorganiser la liste sélectionnée à l'aide de la chaîne de commande enregistrée. cela dépendra de l'application que vous construisez. Voici à nouveau un exemple de jQuery permettant de réorganiser la liste des éléments: http://ovisdevelopment.com/oramincite/ ? p = 155

Answer 7

https://dba.stackexchange.com/questions/46238/linked -list-in-sql-and-trees suggère une astuce consistant à utiliser une colonne de position à virgule flottante pour les insertions et les commandes rapides.

Il mentionne également la fonctionnalité spécialisée hierarchyid de SQL Server 2014. <

Answer 8

Il y a quelques approches auxquelles je peux penser dès le départ, chacune avec différents niveaux de complexité et de flexibilité. Je suppose que votre objectif est de conserver un ordre lors de l'extraction, plutôt que d'exiger le stockage en tant que liste chaînée.

La méthode la plus simple consisterait à attribuer une valeur ordinale à chaque enregistrement de la table (par exemple 1, 2, 3, ...). Ensuite, lorsque vous récupérez les enregistrements, spécifiez un ordre de tri dans la colonne ordinale pour les remettre en ordre.

Cette approche vous permet également de récupérer les enregistrements sans tenir compte de l'appartenance à une liste, mais autorise l'appartenance à une seule liste et peut nécessiter un "identifiant de liste" supplémentaire. colonne pour indiquer à quelle liste appartient l’enregistrement.

Une approche légèrement plus élaborée, mais également plus flexible, consisterait à stocker des informations sur l'appartenance à une liste ou à des listes dans un tableau séparé. La table aurait besoin de 3 colonnes: l'id de la liste, la valeur ordinale et un pointeur de clé étrangère vers l'enregistrement de données. Selon cette approche, les données sous-jacentes ne savent rien de leur appartenance à des listes et peuvent facilement être incluses dans plusieurs listes.

Answer 9

Je pense que c'est beaucoup plus simple d'ajouter une colonne créée de type Datetime et une colonne de position de int , afin que vous puissiez maintenant avoir des positions en double, utilisez l'instruction ordre par position, option desc créée et votre liste sera récupérée dans l’ordre.

Answer 10

C’est quelque chose que je cherche à comprendre moi-même depuis un moment. Jusqu'à présent, la meilleure solution consiste à créer une seule table pour la liste liée en utilisant le format suivant (pseudo-code):

LinkedList (

• touche1,
• informations,
• clé2

)

key1 est le point de départ. Key2 est une clé étrangère qui se lie à elle-même dans la colonne suivante. Donc, vos colonnes vont lier quelque chose lien quelque chose comme ça

col1

• key1 = 0,
• information = 'bonjour'
• clé2 = 1

Key1 est la clé primaire de col1. key2 est une clé étrangère menant à la clé1 de col2

col2

• key1 = 1,
• information = 'wassup'
• key2 = null

key2 de col2 est défini sur null car il ne pointe vers rien

Lorsque vous entrez pour la première fois une colonne dans la table, vous devez vous assurer que key2 est défini sur null ou vous obtiendrez une erreur. Après avoir entré la deuxième colonne, vous pouvez revenir en arrière et définir la clé2 de la première colonne sur la clé primaire de la deuxième colonne.

Ceci est la meilleure méthode pour entrer plusieurs entrées à la fois, puis revenez en arrière et définissez les clés étrangères en conséquence (ou créez une interface graphique qui le fait juste pour vous)

Voici le code que j'ai préparé (tout le code a fonctionné avec MSSQL. Vous pouvez effectuer des recherches sur la version de SQL que vous utilisez!):

createtable.sql

create table linkedlist00 (

key1 int primary key not null identity(1,1),

info varchar(10),

key2 int

)

register_foreign_key.sql

alter table dbo.linkedlist00

add foreign key (key2) references dbo.linkedlist00(key1)

* Je les ai mis dans deux fichiers séparés, car cela doit se faire en deux étapes. MSSQL ne vous laissera pas le faire en une seule étape, car la table n’existe pas encore pour la clé étrangère à référencer.

La

liste chaînée est particulièrement puissante dans les relations un-à-plusieurs . Donc, si vous avez déjà voulu faire un tableau de clés étrangères? C'est une façon de le faire! Vous pouvez créer une table primaire qui pointe vers la première colonne de la table de liste liée, puis au lieu de "informations". Dans ce champ, vous pouvez utiliser une clé étrangère pour la table d’informations souhaitée.

Exemple:

Supposons que vous avez une bureaucratie qui conserve les formulaires.

Disons qu'ils ont une table appelée classeur

FileCabinet (

• Identifiant du cabinet (pk)
• ID de fichier (fk) )

chaque colonne contient une clé primaire pour le cabinet et une clé étrangère pour les fichiers. Ces fichiers peuvent être des formulaires fiscaux, des papiers d’assurance maladie, des feuillets d’autorisation de sorties, etc.

Fichiers (

• ID de fichiers (pk)

• ID de fichier (fk)

• ID de fichier suivant (fk)

)

cela sert de conteneur pour les fichiers

Fichier (

• ID de fichier (pk)

• Informations sur le fichier

)

c'est le fichier spécifique

Il existe peut-être de meilleures façons de le faire et il y en a, en fonction de vos besoins spécifiques. L'exemple illustre simplement une utilisation possible.

Answer 11

Une liste peut être stockée en ayant une colonne contenant le décalage (position d'index de la liste) - une insertion au milieu incrémente alors tout ce qui se trouve au-dessus du nouveau parent, puis effectue une insertion.

Answer 12

Incrémentez le 'index' SERIAL de 100, mais ajoutez manuellement des valeurs intermédiaires avec un 'index' égal à Prev + Next / 2. Si vous avez déjà saturé les 100 lignes, réorganisez l'index à 100.

Ceci devrait maintenir la séquence avec l'index primaire.