Abrufen von verknüpften Liste in MySQL-Datenbank

Question

Ich habe eine MySQL-Datenbank-Tabelle mit dieser Struktur:

table
    id INT NOT NULL PRIMARY KEY
    data ..
    next_id INT NULL

Ich brauche die Daten in der Reihenfolge der verknüpften Liste zu holen. Zum Beispiel dieser Daten angegeben:

 id | next_id
----+---------
  1 |       2
  2 |       4
  3 |       9
  4 |       3
  9 |    NULL

ich brauche die Zeilen für ID = 1, 2, 4, 3, 9, die in dieser Reihenfolge zu holen. Wie kann ich mit einer Datenbankabfrage dies tun? (Ich kann es auf der Client-Seite tun. Ich bin gespannt, ob diese auf der Datenbank Seite getan werden kann. So sagen es unmöglich ist, ist in Ordnung (bei genügend Beweise)).

Es wäre schön, als auch einen Endpunkt haben (zum Beispiel nach 10 Fetches zu stoppen, oder wenn eine bestimmte Bedingung in der Zeile wahr dreht), aber dies ist nicht erforderlich (kann auf Client-Seite durchgeführt werden). I (Hoffnung I) nicht benötigen für zirkuläre Referenzen zu überprüfen.

Answer 1

Einige Marken von Datenbank (zum Beispiel Oracle, Microsoft SQL Server) unterstützt zusätzliche SQL-Syntax „rekursive Abfragen“ zu laufen, aber MySQL unterstützt keine solche Lösung.

Das Problem, das Sie beschreiben, ist das gleiche wie eine Baumstruktur in einer SQL-Datenbank darstellt. Sie haben nur einen langen, dünnen Baum.

Es gibt mehrere Lösungen für die Speicherung und diese Art von Datenstruktur von einem RDBMS zu holen. Sehen Sie einige der folgenden Fragen:

• " Ist es möglich, eine rekursive SQL-Abfrage zu machen? "

---

Da Sie erwähnen, dass Sie die „Tiefe“ von der Abfrage zurückgegeben begrenzen möchten, können Sie diese während erreichen, um die Liste auf diese Weise die Abfrage:

SELECT * FROM mytable t1
 LEFT JOIN mytable t2 ON (t1.next_id = t2.id)
 LEFT JOIN mytable t3 ON (t2.next_id = t3.id)
 LEFT JOIN mytable t4 ON (t3.next_id = t4.id)
 LEFT JOIN mytable t5 ON (t4.next_id = t5.id)
 LEFT JOIN mytable t6 ON (t5.next_id = t6.id)
 LEFT JOIN mytable t7 ON (t6.next_id = t7.id)
 LEFT JOIN mytable t8 ON (t7.next_id = t8.id)
 LEFT JOIN mytable t9 ON (t8.next_id = t9.id)
 LEFT JOIN mytable t10 ON (t9.next_id = t10.id);

Es wird wie Melasse durchführen, und das Ergebnis wird wieder kommen alle auf einer Zeile (pro verkettete Liste), aber Sie werden das Ergebnis erhalten.

Answer 2

Wenn das, was Sie versuchen, ist zu vermeiden, mehrere Abfragen mit (einer für jeden Knoten), und Sie sind in der Lage Spalten hinzufügen, dann könnten Sie eine neue Spalte, die auf den Wurzelknoten verbindet. So können Sie in allen Daten auf einmal durch die Wurzel-ID ziehen können, aber Sie werden immer noch die Liste (oder Baum) auf der Client-Seite sortieren müssen.

in diesem So ist beispielsweise müßten Sie:

 id | next_id | root_id
----+---------+---------
  1 |       2 |       1
  2 |       4 |       1
  3 |       9 |       1
  4 |       3 |       1
  9 |    NULL |       1

Natürlich ist der Nachteil dieser im Gegensatz zu traditionellen verkettete Listen oder Bäumen ist, dass die Wurzel nicht ohne das Schreiben auf einer Größenordnung von O (n) ändern kann, wobei n die Anzahl der Knoten ist. Dies ist, weil Sie die Wurzel-ID für jeden Knoten würde aktualisieren. Glücklicherweise aber Sie sollten immer in der Lage sein, dies in einer einzigen Update-Abfrage zu tun, wenn Sie eine Liste / Baum in der Mitte geteilt wird.

Answer 3

Dies ist weniger eine Lösung und mehr zu einem Problem zu umgehen, aber für eine lineare Liste (statt dem Baum Bill Karwin erwähnt), es könnte effizienter sein, eine Sortierspalte auf Ihrer Liste zu verwenden. Zum Beispiel:

TABLE `schema`.`my_table` (
    `id` INT NOT NULL PRIMARY KEY,
    `order` INT,
    data ..,
    INDEX `ix_order` (`sort_order` ASC)
);

Dann:

SELECT * FROM `schema`.`my_table` ORDER BY `order`;

Dies hat den Nachteil langsamer Einsätze (Sie haben alle Elemente sortiert vorbei an der Einfügemarke positionieren), aber sollte schnell zum Abruf sein, da die Reihenfolge Spalte indiziert ist.