LinkedList oder Position speichern

shft

Hallo an alle,

folgendes Problem: Es soll eine Tabelle gespeichert werden, wo die Reihenfolge der Einträge entscheidend ist (auch nachträglich noch geändert werden kann (auch Erweiterungen und Löschungen sind nicht ausgeschlossen), aber nicht durch logisches Sortieren (z.B. lexikographisch - Zeichenketten) bestimmbar ist.

Einfache Beispieltabelle:

CREATE TABLE foo( id INTEGER PRIMARY KEY , something TEXT );

Meine erste Idee war nun zu jeder Spalte eine Eintrag hinzuzufügen, welcher die Position des Eintrages speichert.

CREATE TABLE foo( id INTEGER PRIMARY KEY , something TEXT , pos INTEGER );

Der Vorteil ist, dass ich sehr einfach alle Einträge (in gewünschter Reihenfolge) abfragen kann;

SELECT * FROM foo ORDER BY pos

jedoch ist das Einfügen doch relativ teuer (uU/iA muss jeder Eintrag aktualisiert werden!)

Meine zweite Idee war also eine LinkedList abzuspeichern, d.h. jeder Eintrag speichert sich die ID seines Vorgängers.

CREATE TABLE foo( id INTEGER PRIMARY KEY , something TEXT , prev INTEGER , FOREIGN KEY (prev) REFERENCES foo(id) );

Die Frage ist nun, ist der zweite Ansatz wirklich schneller beim Einfügen/Löschen usw.? Oder täusche ich mich? Die zweite Frage ist, wie kann ich mit dem LinkedList-Ansatz alle Einträge in gewünschter Reihenfolge ausgeben?

Danke und MfG

shft

tenim

also die abfrage für die linked list sieht dann so aus
(habs mal schnell probiert, ist hier t-sql -aber trotzdem standard sql code):

du hast eine tabelle "test" mit den spalten "id" und "vor". id enthält deinen wert, vor die "id" des vorgängers. der erste datensatz hat bei "vor" NULL, da er keinen vorgänger haben kann.

WITH tempTbl AS
(
select id,vor,1 as sort from data.test where vor is null
UNION all
select b.id,b.vor,a.sort+1
from tempTbl a
inner join data.test b on b.vor=a.id
)
SELECT *
FROM tempTbl
order by sort

das sortieren mit sort brauchst du tehoretisch nicht, da die rekursive abfrage die werte in der korrekten reihenfolge zurückgegben müsste. "data." ist das schema in dem die tabelle auf dem server liegt.

wegen der geschwindigkeit bei der linkedlist variante:
du musst alt vor jedem einfügen erstmal den datensatz ermitteln der keinen nachfolger mehr hat um ihn mit dem neuen zu verketten. beim der pos-variante brauchst du nur max(pos)+1. ist aber in jedem fall eine abfrage nötig.

beim löschen ist es bei der linkedlist variante so, das du
a) die vorgänger-nr des zu löschenden ds ermitteln musst und dann
b) den ds, dessen vorgänger die id des zu löschenden ds ist
um dann
c) den ds zu löschen und
d) den passenden bestehenden ds anzupassen (dessen vorgänger bekommt die id des gelöschten ds)

insgesamt also 4 abfragen. bei der pos-variante brauchst du halt
anzahl zu updatende ds = anz ds mit pos nr > als zu löschende pos-nr.

wenn ich mich nicht vertan habe.

p.s.

hier ein paar links zu dem thema cte-tabellen und rekursion in sql99:

https://technet.microsoft.com/de-de/library/ms186243(v=sql.105).aspx
https://en.wikipedia.org/wiki/Hierarchical_and_recursive_queries_in_SQL