Ist O (1) Zugriff auf eine Datenbankzeile möglich?

Question

Ich habe eine Tabelle, die ein Auto-Inkrement-Feld (ID) als Primärschlüssel verwenden. Die Tabelle ist nur Anhang und keine Zeile wird gelöscht. Tabelle wurde entworfen, um eine konstante Zeilengröße zu haben.

Daher erwartete ich O (1) Zugriffszeit mit einem beliebigen Wert als ID, da es einfach ist, genaue Position zu ermitteln, in Datei suchen (ID * row_size), leider ist das nicht der Fall.

Ich benutze SQL Server.
Ist es überhaupt möglich?

Dank

Answer 1

Ich denke, das, was dir wichtig ist, ist die Leistung. Datenbanken verwenden Indizes, um auf Datensätze zuzugreifen, die auf dem Datenträger geschrieben sind.

Üblicherweise wird dies mit B + -Baum-Indizes durchgeführt, die log sind _b n wobei B für interne Knoten typischerweise zwischen 100 und 200 ist (optimierte Größe zu blockieren, siehe ref)

Diese noch streng genommen logarithmischer Leistung, aber bei einer anständigen Anzahl von Datensätzen, sagen wir ein paar Millionen, können die Blattknoten in 3 bis 4 Schritten erreicht werden, und das zusammen mit dem Overhead für Abfrageplanung, Sitzungsinitiierung, Sperren usw. (das hätten Sie sowieso) Wenn Sie ein Multiuser-ACID-konformes Datenmanagementsystem benötigen, ist dies aus praktischen Gründen mit der Zeit vergleichbar.

Answer 2

Daher erwartete ich O (1) Zugang Zeit unter Verwendung eines beliebigen Wert als ID haben, da es leicht exakte Position spulen in Datei (ID * row_size) zu berechnen,

Ah. Nein Autoincrement nicht - auch ohne Löschungen - garantieren keine Löcher. Holes = über den Index suchen. Ergo: Deine Annahme ist falsch.

Answer 3

Die gute Nachricht ist, dass ein indizierter Lesevorgang O (log (n)) ist, der für große Werte von n ziemlich nah an O (1) kommt. Das heißt, in diesem Zusammenhang ist die O-Notation nicht sehr nützlich, und die tatsächlichen Zeiten sind viel schlechter.

Answer 4

Auch wenn es möglich wäre, Zeilen direkt zu adressieren, müsste Ihre Abfrage immer noch die Client- und Serverprotokollstacks durchlaufen und verschiedene Suchen und Speicherzuordnungen durchführen, bevor sie das gewünschte Ergebnis liefern könnte. Es scheint, als ob Sie etwas erwarten, das nicht einmal praktisch ist. Was ist das eigentliche Problem hier? Ist SQL Server nicht schnell genug für Sie? Wenn dies der Fall ist, gibt es viele Optionen, die Sie verwenden können, um die Leistung zu verbessern, aber das direkte Suchen einer Adresse in einer Datei ist nicht einer davon.

Answer 5

Nicht möglich. SQL Server organisiert Daten basierend auf Schlüssel- und Indexwerten in einer baumartigen Struktur. Ein "Index" im Sinne von DB ist eher wie der Index eines Referenzbuchs und nicht wie eine indizierte Datenstruktur wie ein Array oder eine Liste. Im besten Fall können Sie logarithmische Leistung erhalten, wenn Sie nach einem indizierten Wert suchen (PKs werden im Allgemeinen als Index behandelt). Worst-Case ist ein Tabellenscan für eine nicht indizierte Spalte, die linear ist. Bis die Datenbank sehr groß wird, wird die Suchzeit einer gut entworfenen Abfrage gegen eine gut entworfene Tabelle im Vergleich zu der Zeit verblassen, die benötigt wird, um sie über das Netzwerk oder sogar eine Named Pipe zu senden.