Datenbankindizes

Question

Ich brauche eine „naive“ Implementierung von Datenbankindizes für die Verwendung in einer verteilten Umgebung zu entwickeln. Ich weiß fast nichts über das Thema, und ich bin ein bisschen unter Zeitdruck.

Ich würde gerne einige Meinungen, Beispiele und Algorithmen zum Thema hören. Ich möchte eine mentale Repräsentation dessen haben, was ich implementieren muss.

EDIT: Ich beziehe mich auf Clustered-Indizes

Answer 1

Es gibt grundsätzlich zwei Arten von Indizes:

• Clustered (dh die Daten physisch organisiert ist, und Sie umsortieren es bei jedem Einfügen, wenn erforderlich)

  Typischer anwendungs~~POS=TRUNC: die physische Organisation ist in der Regel das gleiches wie der Auftrag, so dass die Umsortierung Overhead ist kein Problem. Dies ist beispielsweise bei sequenziellen UIDs der Fall (die sogenannten "IDENTITY" -Felder in einem Datenbankkontext)

  Ein offensichtlicher Nachteil der Clustered-Indexierung ist, dass Sie nur einen solchen Index für Ihre Daten haben können.

  Naive Implementierung, wenn der Anzeigenauftrag ist genau die Sortierreihenfolge: eine Liste verwenden.

  1. Insertion O (1): Sie sonst nur die neuen Daten der Liste anhängen
  2. Access ist O (1), wenn die ID des sequentiellen (dh Array-Indizes entspricht exakt UID), O (log)

• ungebündelte (dh Sie halten Zeiger auf den Daten, wie in einem Hashtable)

  Typischer anwendungs~~POS=TRUNC: Die Clustering nicht geeignet ist, weil es zu groß einen Einführungsaufwand hervorrufen würde.

Je nach Bedarf, werden Sie wahrscheinlich auf diese beiden Datenstrukturen am Ende mit

Eine umfangreiche Sammlung von Index-bezogenen Informationen sind verfügbar here

Answer 2

Ein wirklich schnell-and-Easy- implementierende, wirklich naiv Index Implementierung der am besten geeignete für jede Sprache, die eine native associative array Format hat, ist ein Hash, dessen Schlüssel noch vorhandenen Werte für die Spalte Sie indizieren und deren Werte sind Arrays von Zeilen-IDs für die Zeilen mit diesem Wert .