Wie funktioniert die Datenbankindizierung?[geschlossen]

https://stackoverflow.com/questions/1108

08-06-2019
|

Frage

Kann jemand angesichts der Tatsache, dass die Indizierung mit zunehmender Größe Ihres Datensatzes so wichtig ist, erklären, wie die Indizierung auf einer datenbankunabhängigen Ebene funktioniert?

Informationen zu Abfragen zum Indizieren eines Felds finden Sie unter Wie indiziere ich eine Datenbankspalte?.

Lösung

Warum wird es benötigt?

Wenn Daten auf festplattenbasierten Speichergeräten gespeichert werden, werden sie als Datenblöcke gespeichert.Auf diese Blöcke wird in ihrer Gesamtheit zugegriffen, was sie zum atomaren Plattenzugriffsvorgang macht.Festplattenblöcke sind ähnlich strukturiert wie verknüpfte Listen.beide enthalten einen Abschnitt für Daten, einen Zeiger auf die Position des nächsten Knotens (oder Blocks) und beide müssen nicht zusammenhängend gespeichert werden.

Aufgrund der Tatsache, dass mehrere Datensätze nur nach einem Feld sortiert werden können, können wir sagen, dass die Suche nach einem Feld, das nicht sortiert ist, eine lineare Suche erfordert, die Folgendes erfordert N/2 Blockzugriffe (im Durchschnitt), wo N ist die Anzahl der Blöcke, die die Tabelle umfasst.Wenn es sich bei diesem Feld um ein Nicht-Schlüsselfeld handelt (d. h.enthält keine eindeutigen Einträge), dann muss der gesamte Tablespace durchsucht werden N Zugriffe blockieren.

Bei einem sortierten Feld hingegen kann eine binäre Suche verwendet werden log2 N Zugriffe blockieren.Da die Daten außerdem anhand eines Nicht-Schlüsselfelds sortiert werden, muss der Rest der Tabelle nicht nach doppelten Werten durchsucht werden, sobald ein höherer Wert gefunden wird.Somit ist die Leistungssteigerung erheblich.

Was ist Indizierung?

Die Indizierung ist eine Möglichkeit, eine Reihe von Datensätzen nach mehreren Feldern zu sortieren.Durch das Erstellen eines Index für ein Feld in einer Tabelle wird eine weitere Datenstruktur erstellt, die den Feldwert und einen Zeiger auf den Datensatz enthält, auf den er sich bezieht.Diese Indexstruktur wird dann sortiert, sodass binäre Suchen darauf durchgeführt werden können.

Der Nachteil der Indizierung besteht darin, dass diese Indizes zusätzlichen Speicherplatz auf der Festplatte benötigen, da die Indizes mithilfe der MyISAM-Engine zusammen in einer Tabelle gespeichert werden. Diese Datei kann schnell die Größenbeschränkungen des zugrunde liegenden Dateisystems erreichen, wenn viele Felder innerhalb derselben Tabelle indiziert werden .

Wie funktioniert es?

Lassen Sie uns zunächst ein Beispiel-Datenbanktabellenschema skizzieren.

Field name       Data type      Size on disk
id (Primary key) Unsigned INT   4 bytes
firstName        Char(50)       50 bytes
lastName         Char(50)       50 bytes
emailAddress     Char(100)      100 bytes

Notiz:char wurde anstelle von varchar verwendet, um eine genaue Größe des Festplattenwerts zu ermöglichen.Diese Beispieldatenbank enthält fünf Millionen Zeilen und ist nicht indiziert.Nun wird die Performance mehrerer Abfragen analysiert.Dabei handelt es sich um eine Abfrage mit dem Ausweis (ein sortiertes Schlüsselfeld) und eines mit dem Vorname (ein unsortiertes Feld ohne Schlüssel).

Beispiel 1 - sortierte vs. unsortierte Felder

Angesichts unserer Beispieldatenbank von r = 5,000,000 Datensätze einer festen Größe mit einer Datensatzlänge von R = 204 Bytes und sie werden mithilfe der MyISAM-Engine, die die Standardblockgröße verwendet, in einer Tabelle gespeichert B = 1,024 Bytes.Der Blockierungsfaktor der Tabelle wäre bfr = (B/R) = 1024/204 = 5 Datensätze pro Plattenblock.Die Gesamtzahl der Blöcke, die zum Halten der Tabelle erforderlich sind, beträgt N = (r/bfr) = 5000000/5 = 1,000,000 Blöcke.

Eine lineare Suche im ID-Feld würde einen Durchschnitt von erfordern N/2 = 500,000 Blockieren Sie Zugriffe, um einen Wert zu finden, vorausgesetzt, das ID-Feld ist ein Schlüsselfeld.Da aber auch das ID-Feld sortiert ist, kann eine binäre Suche durchgeführt werden, die einen Durchschnitt von erfordert log2 1000000 = 19.93 = 20 Zugriffe blockieren.Wir können sofort erkennen, dass dies eine drastische Verbesserung ist.

Jetzt die Vorname Das Feld ist weder sortiert noch ein Schlüsselfeld, sodass eine binäre Suche nicht möglich ist. Die Werte sind auch nicht eindeutig, sodass die Tabelle bis zum Ende nach einem genauen Wert durchsucht werden muss N = 1,000,000 Zugriffe blockieren.Genau diese Situation soll durch die Indexierung korrigiert werden.

Da ein Indexdatensatz nur das indizierte Feld und einen Zeiger auf den ursprünglichen Datensatz enthält, liegt es nahe, dass er kleiner ist als der Datensatz mit mehreren Feldern, auf den er verweist.Der Index selbst benötigt also weniger Plattenblöcke als die Originaltabelle, was daher weniger Blockzugriffe zum Durchlaufen erfordert.Das Schema für einen Index für Vorname Feld ist unten beschrieben;

Field name       Data type      Size on disk
firstName        Char(50)       50 bytes
(record pointer) Special        4 bytes

Notiz:Zeiger in MySQL sind je nach Größe der Tabelle 2, 3, 4 oder 5 Byte lang.

Beispiel 2 - Indizierung

Angesichts unserer Beispieldatenbank von r = 5,000,000 Datensätze mit einer Indexsatzlänge von R = 54 Bytes und unter Verwendung der Standardblockgröße B = 1,024 Bytes.Der Sperrfaktor des Index wäre bfr = (B/R) = 1024/54 = 18 Datensätze pro Plattenblock.Die Gesamtzahl der Blöcke, die zum Halten des Index erforderlich sind, beträgt N = (r/bfr) = 5000000/18 = 277,778 Blöcke.

Nun eine Suche mit dem Vorname Das Feld kann den Index nutzen, um die Leistung zu steigern.Dies ermöglicht eine binäre Suche des Index mit einem Durchschnitt von log2 277778 = 18.08 = 19 Zugriffe blockieren.Um die Adresse des tatsächlichen Datensatzes zu finden, ist zum Lesen ein weiterer Blockzugriff erforderlich, um die Gesamtsumme zu ermitteln 19 + 1 = 20 Blockzugriffe, weit entfernt von den 1.000.000 Blockzugriffen, die erforderlich sind, um einen zu finden Vorname Übereinstimmung in der nicht indizierten Tabelle.

Wann sollte es verwendet werden?

Angesichts der Tatsache, dass die Erstellung eines Indexes zusätzlichen Speicherplatz erfordert (277.778 Blöcke mehr als im obigen Beispiel, eine Steigerung von ca. 28 %) und dass zu viele Indizes aufgrund der Größenbeschränkungen des Dateisystems zu Problemen führen können, muss sorgfältig überlegt werden, um den richtigen Index auszuwählen Felder zur Indizierung.

Da Indizes nur dazu dienen, die Suche nach einem passenden Feld innerhalb der Datensätze zu beschleunigen, liegt es auf der Hand, dass die Indizierung von Feldern, die nur für die Ausgabe verwendet werden, einfach eine Verschwendung von Speicherplatz und Verarbeitungszeit wäre, wenn ein Einfüge- oder Löschvorgang ausgeführt wird sollte vermieden werden.Angesichts der Natur einer binären Suche ist auch die Kardinalität oder Eindeutigkeit der Daten wichtig.Die Indizierung eines Feldes mit einer Kardinalität von 2 würde die Daten in zwei Hälften teilen, wohingegen eine Kardinalität von 1.000 etwa 1.000 Datensätze zurückgeben würde.Bei einer so niedrigen Kardinalität wird die Effektivität auf eine lineare Sortierung reduziert, und der Abfrageoptimierer vermeidet die Verwendung des Index, wenn die Kardinalität weniger als 30 % der Datensatznummer beträgt, wodurch der Index effektiv Platz verschwendet.

Andere Tipps

Als ich das zum ersten Mal las, war es für mich sehr hilfreich.Danke schön.

Seitdem habe ich einige Erkenntnisse über die Nachteile der Indexerstellung gewonnen:wenn man in eine Tabelle schreibt (UPDATE oder INSERT) mit einem Index haben Sie tatsächlich zwei Schreibvorgänge im Dateisystem.Eine für die Tabellendaten und eine weitere für die Indexdaten (und deren Umsortierung (und – falls geclustert – die Umsortierung der Tabellendaten)).Liegen Tabelle und Index auf derselben Festplatte, kostet das mehr Zeit.Somit würde eine Tabelle ohne Index (einen Heap) schnellere Schreibvorgänge ermöglichen.(Wenn Sie zwei Indizes hätten, hätten Sie am Ende drei Schreibvorgänge usw.)

Allerdings kann die Definition zweier unterschiedlicher Speicherorte auf zwei unterschiedlichen Festplatten für Indexdaten und Tabellendaten das Problem erhöhter Zeitkosten verringern/eliminieren.Dies erfordert die Definition zusätzlicher Dateigruppen mit entsprechenden Dateien auf den gewünschten Festplatten und die Definition des gewünschten Tabellen-/Indexspeicherorts.

Ein weiteres Problem bei Indizes ist ihre Fragmentierung im Laufe der Zeit, wenn Daten eingefügt werden. REORGANIZE hilft, Sie müssen Routinen schreiben, um es zu erledigen.

In bestimmten Szenarien ist ein Heap hilfreicher als eine Tabelle mit Indizes.

Beispiel: – Wenn Sie viele konkurrierende Schreibvorgänge haben, aber nur eine nächtliche Lektüre außerhalb der Geschäftszeiten zur Berichterstattung durchführen.

Außerdem ist eine Unterscheidung zwischen Clustered- und Non-Clustered-Indizes sehr wichtig.

Half mir:- Was bedeuten eigentlich Clustered- und Non-Clustered-Index?

Ein Index ist lediglich eine Datenstruktur, die die Suche nach einer bestimmten Spalte in einer Datenbank beschleunigt.Diese Struktur ist normalerweise ein B-Baum oder eine Hash-Tabelle, es kann sich jedoch auch um jede andere logische Struktur handeln.

Klassisches Beispiel „Index in Büchern“

Stellen Sie sich ein „Buch“ mit 1000 Seiten vor, unterteilt in 100 Abschnitte, wobei jeder Abschnitt X Seiten hat.

Ganz einfach, oder?

Um nun ohne Indexseite einen bestimmten Abschnitt zu finden, der mit dem Buchstaben „S“ beginnt, bleibt Ihnen keine andere Möglichkeit, als das gesamte Buch zu durchsuchen.d.h.:1000 Seiten

Aber mit einer Indexseite am Anfang sind Sie am Ziel.Und mehr noch: Um einen bestimmten Abschnitt zu lesen, der wichtig ist, müssen Sie nur jedes Mal immer wieder einen Blick auf die Indexseite werfen.Nachdem Sie den passenden Index gefunden haben, können Sie effizient zu dem Abschnitt springen, indem Sie andere Abschnitte überspringen.

Dann benötigen Sie aber zusätzlich zu den 1000 Seiten weitere ca. 10 Seiten, um die Indexseite anzuzeigen, also insgesamt 1010 Seiten.

Somit ist der Index ein separater Abschnitt, der die Werte der indizierten Spalte + Zeiger auf die indizierte Zeile in sortierter Reihenfolge für effiziente Suchvorgänge speichert.

In Schulen sind die Dinge einfach, nicht wahr?:P

Nehmen wir nun an, wir möchten eine Abfrage ausführen, um alle Details aller Mitarbeiter mit dem Namen „Abc“ zu finden?

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

Was würde ohne einen Index passieren?

Datenbanksoftware müsste sich buchstäblich jede einzelne Zeile in der Employee-Tabelle ansehen, um zu sehen, ob der Employee_Name für diese Zeile „Abc“ ist.Und da wir jede Zeile mit dem Namen „Abc“ darin haben wollen, können wir nicht einfach aufhören zu suchen, sobald wir nur eine Zeile mit dem Namen „Abc“ gefunden haben, denn es könnten noch andere Zeilen mit dem Namen vorhanden sein ABC.Daher muss jede Zeile bis zur letzten Zeile durchsucht werden – was bedeutet, dass in diesem Szenario Tausende von Zeilen von der Datenbank untersucht werden müssen, um die Zeilen mit dem Namen „Abc“ zu finden.Das nennt man a Vollständiger Tabellenscan

Wie ein Datenbankindex die Leistung verbessern kann

Der Sinn eines Index besteht darin, Suchanfragen zu beschleunigen, indem die Anzahl der Datensätze/Zeilen in einer Tabelle, die untersucht werden müssen, wesentlich reduziert wird.Ein Index ist eine Datenstruktur (am häufigsten ein B-Baum), die die Werte für eine bestimmte Spalte in einer Tabelle speichert.

Wie funktioniert der B-Trees-Index?

Der Grund dafür, dass B-Bäume die beliebteste Datenstruktur für Indizes sind, liegt darin, dass sie zeiteffizient sind – weil Suchvorgänge, Löschungen und Einfügungen alle in logarithmischer Zeit durchgeführt werden können.Ein weiterer wichtiger Grund dafür, dass B-Bäume häufiger verwendet werden, besteht darin, dass die im B-Baum gespeicherten Daten sortiert werden können.Das RDBMS bestimmt typischerweise, welche Datenstruktur tatsächlich für einen Index verwendet wird.In einigen Szenarien mit bestimmten RDBMS können Sie jedoch tatsächlich angeben, welche Datenstruktur Ihre Datenbank verwenden soll, wenn Sie den Index selbst erstellen.

Wie funktioniert ein Hash-Tabellenindex?

Der Grund für die Verwendung von Hash-Indizes liegt darin, dass Hash-Tabellen äußerst effizient sind, wenn es nur darum geht, Werte nachzuschlagen.Daher können Abfragen, die einen Gleichheitsvergleich mit einer Zeichenfolge durchführen, sehr schnell Werte abrufen, wenn sie einen Hash-Index verwenden.

Beispielsweise könnte die zuvor besprochene Abfrage von einem Hash-Index profitieren, der für die Spalte „Employee_Name“ erstellt wird.Ein Hash-Index funktioniert so, dass der Spaltenwert der Schlüssel zur Hash-Tabelle ist und der tatsächliche Wert, der diesem Schlüssel zugeordnet ist, lediglich ein Zeiger auf die Zeilendaten in der Tabelle ist.Da es sich bei einer Hash-Tabelle grundsätzlich um ein assoziatives Array handelt, würde ein typischer Eintrag etwa so aussehen: „Abc => 0x28939“, wobei 0x28939 ein Verweis auf die Tabellenzeile ist, in der Abc im Speicher gespeichert ist.Das Nachschlagen eines Werts wie „Abc“ in einem Hash-Tabellenindex und das Zurückholen eines Verweises auf die Zeile im Speicher ist offensichtlich viel schneller als das Durchsuchen der Tabelle, um alle Zeilen mit dem Wert „Abc“ in der Spalte „Employee_Name“ zu finden.

Die Nachteile eines Hash-Index

Hash-Tabellen sind keine sortierten Datenstrukturen, und es gibt viele Arten von Abfragen, bei denen Hash-Indizes nicht einmal helfen können.Angenommen, Sie möchten alle Mitarbeiter ermitteln, die jünger als 40 Jahre sind.Wie könnte man das mit einem Hash-Tabellenindex machen?Nun, das ist nicht möglich, da eine Hash-Tabelle nur zum Nachschlagen von Schlüssel-Wert-Paaren geeignet ist – also für Abfragen, die auf Gleichheit prüfen

Was genau ist in einem Datenbankindex enthalten?Jetzt wissen Sie also, dass ein Datenbankindex für eine Spalte in einer Tabelle erstellt wird und dass der Index die Werte in dieser bestimmten Spalte speichert.Es ist jedoch wichtig zu verstehen, dass ein Datenbankindex nicht die Werte in den anderen Spalten derselben Tabelle speichert.Wenn wir beispielsweise einen Index für die Spalte „Employee_Name“ erstellen, bedeutet dies, dass die Spaltenwerte „Employee_Age“ und „Employee_Address“ nicht auch im Index gespeichert werden.Wenn wir einfach alle anderen Spalten im Index speichern würden, wäre das so, als würde man eine weitere Kopie der gesamten Tabelle erstellen – was viel zu viel Platz beanspruchen würde und sehr ineffizient wäre.

Woher weiß eine Datenbank, wann sie einen Index verwenden muss?Wenn eine Abfrage wie „SELECT * FROM Employee WHERE Employee_Name = ‚Abc‘“ ausgeführt wird, prüft die Datenbank, ob für die abgefragten Spalten ein Index vorhanden ist.Unter der Annahme, dass für die Spalte „Employee_Name“ tatsächlich ein Index erstellt wurde, muss die Datenbank entscheiden, ob es tatsächlich sinnvoll ist, den Index zum Auffinden der gesuchten Werte zu verwenden – da es einige Szenarien gibt, in denen die Verwendung des Datenbankindex tatsächlich weniger effizient ist und effizienter, nur um die gesamte Tabelle zu scannen.

Was kostet ein Datenbankindex?

Es nimmt Platz ein – und je größer Ihr Tisch, desto größer Ihr Index.Ein weiterer Leistungseinbruch bei Indizes ist die Tatsache, dass jedes Mal, wenn Sie Zeilen in der entsprechenden Tabelle hinzufügen, löschen oder aktualisieren, dieselben Vorgänge für Ihren Index ausgeführt werden müssen.Denken Sie daran, dass ein Index dieselben aktuellen Daten enthalten muss wie alles, was sich in den Tabellenspalten befindet, die der Index abdeckt.

Als allgemeine Regel gilt, dass ein Index nur dann für eine Tabelle erstellt werden sollte, wenn die Daten in der indizierten Spalte häufig abgefragt werden.

Siehe auch

Einfache Beschreibung!!!!!!!!!!!

Der Index ist nichts anderes als eine Datenstruktur, die die Werte für eine bestimmte Spalte in einer Tabelle speichert.Ein Index wird für eine Spalte einer Tabelle erstellt.

Beispiel: Wir haben eine Datenbanktabelle namens „Benutzer“ mit drei Spalten – Name, Alter und Adresse.Gehen Sie davon aus, dass die Benutzertabelle Tausende von Zeilen enthält.

Nehmen wir nun an, wir möchten eine Abfrage ausführen, um alle Details aller Benutzer mit dem Namen „John“ zu finden.Wenn wir die folgende Abfrage ausführen.

SELECT * FROM User 
WHERE Name = 'John'

Die Datenbanksoftware müsste sich buchstäblich jede einzelne Zeile in der Benutzertabelle ansehen, um festzustellen, ob der Name für diese Zeile „John“ lautet.Das wird lange dauern.
Hier hilft uns der Index: „Der Index wird verwendet, um Suchanfragen zu beschleunigen, indem die Anzahl der Datensätze/Zeilen in einer Tabelle, die untersucht werden müssen, wesentlich reduziert wird.“
So erstellen Sie einen Index

CREATE INDEX name_index
ON User (Name)

Ein Index besteht aus Spaltenwerten (z. B.:John) aus einer Tabelle und dass diese Werte in einer Datenstruktur gespeichert werden.
Daher wird die Datenbank nun den Index verwenden, um Mitarbeiter mit dem Namen John zu finden, da der Index vermutlich alphabetisch nach dem Namen des Benutzers sortiert wird.Und da es sortiert ist, ist die Suche nach einem Namen viel schneller, da alle Namen, die mit einem „J“ beginnen, im Index direkt nebeneinander stehen!

Nur ein kurzer Vorschlag..Da die Indizierung zusätzliche Schreibvorgänge und Speicherplatz kostet, sollten Sie, wenn Ihre Anwendung mehr Einfüge-/Aktualisierungsvorgänge erfordert, möglicherweise Tabellen ohne Indizes verwenden. Wenn jedoch mehr Datenabrufvorgänge erforderlich sind, sollten Sie sich für indizierte Tabellen entscheiden.

Stellen Sie sich den Datenbankindex einfach als den Index eines Buches vor.Wenn Sie ein Buch über Hunde haben und Informationen über, sagen wir, Deutsche Schäferhunde finden möchten, können Sie natürlich alle Seiten des Buches durchblättern und finden, was Sie suchen, aber das ist natürlich zeitaufwändig und nicht sehr schnell.Eine andere Möglichkeit besteht darin, dass Sie einfach zum Indexabschnitt des Buches gehen und dann finden, wonach Sie suchen, indem Sie den Namen der gesuchten Entität (in diesem Fall Deutsche Schäferhunde) und auch die Seitenzahl angeben Finden Sie schnell, was Sie suchen.In der Datenbank wird die Seitenzahl als Zeiger bezeichnet, der die Datenbank auf die Adresse auf der Festplatte leitet, auf der sich die Entität befindet.Mit der gleichen Analogie zum Deutschen Schäferhund könnten wir so etwas haben („Deutscher Schäferhund“, 0x77129), wobei 0x77129 die Adresse auf der Festplatte ist, auf der die Zeilendaten für den Deutschen Schäferhund gespeichert sind.

Kurz gesagt ist ein Index eine Datenstruktur, die die Werte für eine bestimmte Spalte in einer Tabelle speichert, um die Abfragesuche zu beschleunigen.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow