Wie funktioniert die Datenbankindizierung? [geschlossen]

Kann jemand erklären, wie die Indizierung auf datenbankunabhängiger Ebene funktioniert, da die Indizierung mit zunehmender Größe Ihres Datensatzes so wichtig ist?

Weitere Informationen zum Abfragen Index ein Feld, überprüfen Wie kann ich Index eine Datenbankspalte .

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 zur atomaren Plattenzugriffsoperation macht. Plattenblöcke sind ähnlich wie verknüpfte Listen aufgebaut. Beide enthalten einen Datenabschnitt, einen Zeiger auf die Position des nächsten Knotens (oder Blocks), und beide müssen nicht zusammenhängend gespeichert werden.

Aufgrund der Tatsache, dass eine Anzahl von Datensätzen nur nach einem Feld sortiert werden kann, können wir angeben, dass für die Suche in einem nicht sortierten Feld eine lineare Suche erforderlich ist N/2, für die (im Durchschnitt) Blockzugriffe erforderlich sind. Dabei Nist die Anzahl der Blöcke angegeben Der Tisch überspannt. Wenn dieses Feld ein Nicht-Schlüsselfeld ist (dh keine eindeutigen Einträge enthält), muss der gesamte Tabellenbereich bei NBlockzugriffen durchsucht werden .

Während bei einem sortierten Feld eine binäre Suche verwendet werden kann, die log2 NBlockzugriffe hat. Da die Daten nach einem Nicht-Schlüsselfeld sortiert sind, muss der Rest der Tabelle nicht nach doppelten Werten durchsucht werden, sobald ein höherer Wert gefunden wurde. Somit ist die Leistungssteigerung erheblich.

Was ist Indizierung?

Durch die Indizierung können mehrere Datensätze nach mehreren Feldern sortiert werden. Durch das Erstellen eines Index für ein Feld in einer Tabelle wird eine andere 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 daran 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 in derselben Tabelle indiziert werden .

Wie funktioniert es?

Lassen Sie uns zunächst ein Beispiel für ein Datenbanktabellenschema skizzieren.

Feldname Datentyp Größe auf der Festplatte
id (Primärschlüssel) INT 4 Bytes ohne Vorzeichen
Vorname Char (50) 50 Bytes
lastName Char (50) 50 Bytes
emailAddress Char (100) 100 Bytes

Hinweis : 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. Die Leistung mehrerer Abfragen wird nun analysiert. Hierbei handelt es sich um eine Abfrage unter Verwendung der ID (ein sortiertes Schlüsselfeld) und eine Abfrage unter Verwendung des Vornamens (ein nicht sortiertes unsortiertes Schlüsselfeld).

Beispiel 1 - sortierte vs unsortierte Felder

Ausgehend von unserer Beispieldatenbank mit r = 5,000,000Datensätzen fester Größe mit einer Datensatzlänge von R = 204Bytes werden diese mithilfe der MyISAM-Engine, die die Standardbytes für Blockgrößen verwendet, in einer Tabelle gespeichert B = 1,024. Der Blockierungsfaktor der Tabelle wären bfr = (B/R) = 1024/204 = 5Datensätze pro Plattenblock. Die Gesamtzahl der Blöcke, die zum Halten der Tabelle erforderlich sind, beträgt N = (r/bfr) = 5000000/5 = 1,000,000Blöcke.

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

Jetzt ist das Feld firstName weder sortiert noch ein Schlüsselfeld, sodass eine binäre Suche nicht möglich ist und die Werte nicht eindeutig sind. Daher muss die Tabelle bis zum Ende nach genauen N = 1,000,000Blockzugriffen gesucht werden . Diese Situation soll durch die Indizierung 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 Mehrfelddatensatz, auf den er zeigt. Der Index selbst erfordert also weniger Plattenblöcke als die ursprüngliche Tabelle, weshalb weniger Blockzugriffe zum Durchlaufen erforderlich sind. Das Schema für einen Index für das Feld firstName ist unten aufgeführt.

Feldname Datentyp Größe auf der Festplatte
Vorname Char (50) 50 Bytes
(Datensatzzeiger) Spezielle 4 Bytes

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

Beispiel 2 - Indizierung

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

Jetzt kann eine Suche mit dem Feld firstName den Index verwenden, um die Leistung zu steigern. Dies ermöglicht eine binäre Suche des Index mit einem Durchschnitt von log2 277778 = 18.08 = 19Blockzugriffen. Um die Adresse des tatsächlichen Datensatzes zu finden, für dessen Lesen ein weiterer Blockzugriff erforderlich ist, um die Gesamtzahl der 19 + 1 = 20Blockzugriffe zu ermitteln, ist dies weit entfernt von den 1.000.000 Blockzugriffen, die erforderlich sind, um eine Übereinstimmung mit dem Vornamen in der nicht indizierten Tabelle zu finden.

Wann sollte es verwendet werden?

Angesichts der Tatsache, dass das Erstellen eines Index zusätzlichen Speicherplatz erfordert (277.778 zusätzliche Blöcke aus dem obigen Beispiel, eine Erhöhung um ~ 28%) und dass zu viele Indizes Probleme verursachen können, die sich aus den Größenbeschränkungen des Dateisystems ergeben, muss sorgfältig überlegt werden, um den richtigen auszuwählen zu indizierende Felder.

Da Indizes nur verwendet werden, um die Suche nach einem übereinstimmenden Feld in den Datensätzen zu beschleunigen, ist es naheliegend, dass Indizierungsfelder, die nur für die Ausgabe verwendet werden, lediglich eine Verschwendung von Speicherplatz und Verarbeitungszeit beim Einfügen oder Löschen darstellen sollte vermieden werden. Auch angesichts der Art einer binären Suche ist die Kardinalität oder Eindeutigkeit der Daten wichtig. Die Indizierung auf einem Feld mit einer Kardinalität von 2 würde die Daten in zwei Hälften teilen, während eine Kardinalität von 1.000 ungefähr 1.000 Datensätze zurückgeben würde. Bei einer so geringen 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 zu einer Platzverschwendung wird.

Klassisches Beispiel "Index in Büchern"

Stellen Sie sich ein "Buch" mit 1000 Seiten vor, das durch 10 Kapitel unterteilt ist, wobei jeder Abschnitt 100 Seiten umfasst.

Einfach, oder?

Stellen Sie sich vor, Sie möchten ein bestimmtes Kapitel finden, das das Wort " Alchemist " enthält. Ohne Indexseite haben Sie keine andere Möglichkeit, als das gesamte Buch / die Kapitel zu durchsuchen. dh: 1000 Seiten.

Diese Analogie wird in der Datenbankwelt als "Full Table Scan" bezeichnet .

Aber mit einer Indexseite wissen Sie, wohin Sie gehen müssen! Um ein bestimmtes Kapitel nachzuschlagen, müssen Sie lediglich jedes Mal die Indexseite durchsehen. Nachdem Sie den passenden Index gefunden haben, können Sie effizient zu diesem Kapitel springen, indem Sie den Rest überspringen.

Aber zusätzlich zu den tatsächlichen 1000 Seiten benötigen Sie weitere ~ 10 Seiten, um die Indizes anzuzeigen, also insgesamt 1010 Seiten.

Daher ist der Index ein separater Abschnitt, in dem die Werte der indizierten Spalte + des Zeigers auf die indizierte Zeile in einer sortierten Reihenfolge gespeichert werden, um eine effiziente Suche zu ermöglichen.

In Schulen ist es einfach, nicht wahr? : P.

Das erste Mal, als ich das las, war es sehr hilfreich für mich. Vielen Dank.

Seitdem habe ich einige Einblicke in die Nachteile des Erstellens von Indizes erhalten: Wenn Sie in eine Tabelle ( UPDATEoder INSERT) mit einem Index schreiben , haben Sie tatsächlich zwei Schreibvorgänge im Dateisystem. Eine für die Tabellendaten und eine andere für die Indexdaten (und deren Neuausrichtung (und - falls gruppiert - die Neuausrichtung der Tabellendaten)). Wenn sich Tabelle und Index auf derselben Festplatte befinden, kostet dies mehr Zeit. Somit würde eine Tabelle ohne Index (ein Heap) schnellere Schreibvorgänge ermöglichen. (Wenn Sie zwei Indizes hätten, würden Sie am Ende drei Schreibvorgänge haben und so weiter)

Das Definieren von zwei verschiedenen Speicherorten auf zwei verschiedenen Festplatten für Indexdaten und Tabellendaten kann jedoch das Problem der erhöhten Zeitkosten verringern / beseitigen. Dies erfordert die Definition zusätzlicher Dateigruppen mit entsprechenden Dateien auf den gewünschten Festplatten und die Definition des gewünschten Speicherorts für Tabelle / Index.

Ein weiteres Problem bei Indizes ist ihre zeitliche Fragmentierung beim Einfügen von Daten. REORGANIZEhilft, müssen Sie Routinen schreiben, um es zu tun.

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

Beispiel: - Wenn Sie viele konkurrierende Schreibvorgänge haben, aber nur eine Nacht außerhalb der Geschäftszeiten lesen, um Berichte zu erstellen.

Auch eine Unterscheidung zwischen gruppierten und nicht gruppierten Indizes ist ziemlich wichtig.

Hat mir geholfen: - Was bedeuten Clustered- und Non-Clustered-Index eigentlich?

Ein Index ist nur eine Datenstruktur, die die Suche nach einer bestimmten Spalte in einer Datenbank beschleunigt. Diese Struktur ist normalerweise ein B-Baum oder eine Hash-Tabelle, kann aber auch eine andere Logikstruktur sein.

Nehmen wir nun an, wir möchten eine Abfrage ausführen, um alle Details von Mitarbeitern mit dem Namen "Abc" zu ermitteln.

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

Was würde ohne einen Index passieren?

Die Datenbanksoftware müsste buchstäblich jede einzelne Zeile in der Employee-Tabelle überprüfen, um festzustellen, ob der Employee_Name für diese Zeile 'Abc' ist. Und weil wir jede Zeile mit dem Namen 'Abc' wollen, können wir nicht einfach aufhören zu suchen, sobald wir nur eine Zeile mit dem Namen 'Abc' gefunden haben, weil es andere Zeilen mit dem Namen Abc geben könnte . Daher muss jede Zeile bis zur letzten Zeile durchsucht werden. Dies bedeutet, dass Tausende von Zeilen in diesem Szenario von der Datenbank untersucht werden müssen, um die Zeilen mit dem Namen 'Abc' zu finden. Dies wird als vollständiger Tabellenscan bezeichnet

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, im Wesentlichen verringert wird. Ein Index ist eine Datenstruktur (am häufigsten ein B-Baum), in der die Werte für eine bestimmte Spalte in einer Tabelle gespeichert werden.

Wie funktioniert der B-Tree-Index?

Der Grund, warum B-Bäume die beliebteste Datenstruktur für Indizes sind, liegt in der Tatsache, dass sie zeiteffizient sind - da Suchvorgänge, Löschungen und Einfügungen alle in logarithmischer Zeit erfolgen können. Ein weiterer wichtiger Grund, warum B-Bäume häufiger verwendet werden, besteht darin, dass die im B-Baum gespeicherten Daten sortiert werden können. Das RDBMS bestimmt normalerweise, 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 beim Erstellen des Index selbst verwenden soll.

Wie funktioniert ein Hash-Tabellenindex?

Der Grund, warum Hash-Indizes verwendet werden, liegt darin, dass Hash-Tabellen äußerst effizient sind, wenn es nur darum geht, Werte nachzuschlagen. Abfragen, die auf Gleichheit mit einer Zeichenfolge verglichen werden, können daher sehr schnell Werte abrufen, wenn sie einen Hash-Index verwenden.

Beispielsweise könnte die zuvor diskutierte Abfrage von einem Hash-Index profitieren, der in der Spalte Employee_Name erstellt wurde. Ein Hash-Index funktioniert so, dass der Spaltenwert der Schlüssel in der Hash-Tabelle ist und der diesem Schlüssel zugeordnete tatsächliche Wert nur ein Zeiger auf die Zeilendaten in der Tabelle ist. Da eine Hash-Tabelle im Grunde genommen ein assoziatives Array ist, würde ein typischer Eintrag ungefähr wie "Abc => 0x28939" aussehen, wobei 0x28939 eine Referenz 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 herausfinden, die jünger als 40 Jahre sind. Wie können Sie das mit einem Hash-Tabellenindex machen? Dies ist nicht möglich, da eine Hash-Tabelle nur zum Nachschlagen von Schlüsselwertpaaren geeignet ist. Dies bedeutet, dass Abfragen auf Gleichheit prüfen

Was genau befindet sich in einem Datenbankindex? 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 die Werte nicht 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 nur alle anderen Spalten im Index speichern würden, wäre dies wie das Erstellen einer weiteren Kopie der gesamten Tabelle - was viel zu viel Platz beanspruchen und sehr ineffizient wäre.

Woher weiß eine Datenbank, wann ein Index verwendet werden muss? Wenn eine Abfrage wie "SELECT * FROM Employee WHERE Employee_Name = 'Abc'" ausgeführt wird, prüft die Datenbank, ob ein Index für die abgefragten Spalten vorhanden ist. Unter der Annahme, dass in der Spalte Employee_Name ein Index erstellt wurde, muss die Datenbank entscheiden, ob es tatsächlich sinnvoll ist, den Index zum Suchen 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 Ihre Tabelle ist, desto größer ist 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 minutengenauen Daten enthalten muss wie alle Daten in den Tabellenspalten, die der Index abdeckt.

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

Siehe auch

1. Welche Spalten sind im Allgemeinen gute Indizes?
2. Wie funktionieren Datenbankindizes?

Einfache Beschreibung!

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

Beispiel: Wir haben eine Datenbanktabelle genannt haben Usermit drei Spalten - Name, Ageund Address. Angenommen, die UserTabelle enthält Tausende von Zeilen.

Angenommen, wir möchten eine Abfrage ausführen, um alle Details aller Benutzer mit dem Namen "John" zu ermitteln. Wenn wir die folgende Abfrage ausführen:

SELECT * FROM User 
WHERE Name = 'John'

Die Datenbanksoftware müsste buchstäblich jede einzelne Zeile in der UserTabelle überprüfen, um festzustellen, ob die Namefür diese Zeile 'John' ist. Dies wird lange dauern.

Das ist wo index hilft uns: Index wird verwendet, um Suchanfragen zu beschleunigen, indem die Anzahl der Datensätze / Zeilen in einer Tabelle, die untersucht werden muss, im Wesentlichen verringert wird .

So erstellen Sie einen Index:

CREATE INDEX name_index
ON User (Name)

Ein indexbesteht aus Spaltenwerten (zB: John) aus einer Tabelle , und diese Werte werden in einer Datenstruktur gespeichert .

Die Datenbank verwendet nun den Index, um Mitarbeiter mit dem Namen John zu finden, da der Index vermutlich alphabetisch nach dem Benutzernamen sortiert wird. Und weil es sortiert ist, bedeutet dies, dass die Suche nach einem Namen viel schneller ist, da alle Namen, die mit einem „J“ beginnen, im Index direkt nebeneinander stehen!

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

Stellen Sie sich den Datenbankindex als Index eines Buches vor.

Wenn Sie ein Buch über Hunde haben und Informationen über beispielsweise Deutsche Schäferhunde finden möchten, können Sie natürlich alle Seiten des Buches durchblättern und herausfinden, wonach Sie suchen - aber dies ist natürlich zeitaufwändig und nicht sehr schnell.

Eine andere Möglichkeit ist, dass Sie einfach zum Indexabschnitt des Buches gehen und dann finden, wonach Sie suchen, indem Sie den Namen der Entität verwenden, die Sie suchen (in diesem Fall Deutsche Schäferhunde) und auch die Seitenzahl auf Finden Sie schnell, wonach 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 German Shepherd-Analogie könnten wir so etwas haben („German Shepherd“, 0x77129), wo 0x77129sich die Adresse auf der Festplatte befindet, auf der die Zeilendaten für German Shepherd gespeichert sind.

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