La structure de données la plus appropriée pour une liste ordonnée dans un SGBDR?

Question

Je stocke une liste ordonnée de plusieurs millions d'éléments dans une base de données MySQL. Raisonnablement souvent, les éléments doivent être ajoutés ou supprimés de la liste; le plus souvent, la position dans la liste d'un article doit être déterminée. Je dirais que le rapport lecture/écriture est d'environ 50:50. À partir d'un modèle de liste liée, j'ai lu [1] et les différents modèles discutés ici. Pour une liste liée stricte, le modèle de liste d'adjacence fonctionnerait très bien, mais puisque le rapport lecture/écriture est plus ou moins égal, j'ai opté pour une approche diviser pour régner en utilisant des listes contiguës standard:

Diviser la liste entière en «tranches» de longueur approximative (disons ~ 10000), en maintenant un indice de la taille des godets et de leur position relative dans la liste principale. Chaque élément est affecté à un compartiment spécifique et garde la trace de sa position dans ce compartiment.

Avec cette approche, la position d'un article est déterminée en additionnant les tailles des compartiments qui précèdent le compartiment de l'article dans la liste, puis en ajoutant la position de l'article dans son propre compartiment. Pour insérer/supprimer un élément de la liste, le «décalage» des éléments qui en résulte est localisé dans le compartiment dans lequel un élément est ajouté ou supprimé; la taille de ce compartiment doit également être mise à jour en conséquence. Il existe une certaine dénormalisation dans cette approche (les tailles de baquets), et elle n'est pas intrinsèquement thread-safe, même avec des transactions, car lors d'une suppression/insertion, la table des éléments doit être interrogée pour déterminer la position du godet. élément en cours de modification, puis mis à jour pour effectuer le «décalage» sur tous les autres éléments dans le compartiment de cet élément. À moins que ces actions soient atomiques (via une procédure stockée peut-être?), Les threads sont toujours bloqués. Y at-il des approches plus appropriées pour conserver ce type de données dans un SGBDR? Le problème de la sécurité des threads me cause un gros mal de tête et il me semble qu'il devrait y avoir une meilleure façon de résoudre ce problème que de me forcer à utiliser des procédures stockées. Un grand merci, Matt.

[1] Database Structure for Tree Data Structure

Answer 1

Si vous avez besoin d'une liste chaînée (pas une hiérarchie), vous pouvez simplement utiliser l'approche décrite dans cet article dans mon blog:

• Sorting lists

, avec cette requête simple:

SELECT @r AS _parent, 
     @r := (
     SELECT id 
     FROM t_list 
     WHERE parent = _parent 
     ) AS id 
FROM (
     SELECT @r := 0 
     ) vars, 
     t_list 

Assurez-vous que votre id et parent ont des index UNIQUE définis pour que cela soit efficace.

Remplacez @r := 0 par @r := @id_of_record_to_start_with pour commencer à naviguer à partir de id.

Pour connaître la position de l'élément, simplement inverser la requête:

SELECT COUNT(*) 
FROM (
     SELECT @r AS _id, 
       @r := (
       SELECT parent 
       FROM t_list 
       WHERE id = _id 
       ) AS id 
     FROM (
       SELECT @r := @item_id 
       ) vars, 
       t_list 
     ) q