Was ist ein B-Baum (ausgeglichener Baum)?

B-Tree (Ausgewogenes Baum) - ist eine Datenstruktur, die in Datenbanken für schnelle Suche, Einfügung und Löschung von Datensätzen verwendet wird. Sie ist in Form eines Baumes organisiert, wobei jeder Knoten Schlüssel und Verweise auf untergeordnete Knoten enthält. Alle Schlüssel in einem Knoten sind sortiert, während andere Knoten die eigentlichen Daten oder Verweise auf Zeilen der Tabelle enthalten. Der Hauptvorteil des B-Tree ist das Gleichgewicht: Die Höhe des Baumes bleibt minimal, was eine Suche in logarithmischer Zeit ermöglicht.

Indizes in Datenbanken basieren genau auf B-Tree (in PostgreSQL und MySQL standardmäßig). Wenn Sie einen Index auf eine Spalte erstellen, baut die Datenbank einen Baum basierend auf den Werten dieser Spalte. Dies ermöglicht es, die benötigten Datensätze schnell zu finden, ohne die gesamte Tabelle scannen zu müssen. Zum Beispiel verwendet die Abfrage WHERE email = '[email protected]' den Index, um sofort zum Knoten mit der benötigten E-Mail zu gelangen, anstatt alle Zeilen zu überprüfen.

In Rails werden Indizes über Migrationen erstellt. Zum Beispiel in PostgreSQL:

class AddIndexToUsersEmail < ActiveRecord::Migration[7.0]
  def change
    add_index :users, :email, unique: true
  end
end

Dieser Index ermöglicht eine schnelle Suche nach Benutzern anhand der E-Mail und garantiert die Eindeutigkeit der Werte. In MySQL ist die Syntax der Migration dieselbe, da Rails das spezifische DBMS abstrahiert.

Intern baut die Datenbank einen B-Tree basierend auf den Werten der Spalte email, und jede Suche über diesen Index erfolgt über die Knoten des Baumes, nicht über die gesamte Tabelle. Dies erhöht die Geschwindigkeit der Abfragen erheblich, insbesondere bei großen Tabellen.

Kurz gesagt - ja. Aber es gibt einen Haken. Indizes in der Datenbank sind sichtbar, obwohl sie nicht als separate Tabellen im herkömmlichen Sinne gespeichert werden. Jedes DBMS bietet Möglichkeiten, um zu sehen, welche Indizes auf einer Tabelle existieren und deren Eigenschaften.

In PostgreSQL können Sie die Indizes mit dem Befehl ansehen:

\d users

oder über die Systemkataloge:

SELECT indexname, indexdef
FROM pg_indexes
WHERE tablename = 'users';

Dies zeigt die Namen der Indizes, die Spalten, auf denen sie erstellt wurden, und den Typ des Index (B-Tree standardmäßig).

In MySQL können die Indizes so angesehen werden:

SHOW INDEX FROM users;

Hier wird eine Liste aller Indizes der Tabelle users angezeigt, die Spalten, den Typ des Index (BTREE oder einen anderen), die Eindeutigkeit und die Sortierreihenfolge.

In Rails können die Indizes über die Konsole angesehen werden:

ActiveRecord::Base.connection.indexes(:users)

Die Ausgabe zeigt ein Array von Objekten mit Informationen zu jedem Index: Name, Spalten, Eindeutigkeit.

Das heißt, Indizes existieren tatsächlich in der Datenbank, und sie können angesprochen und ihre Struktur analysiert werden, auch wenn sie nicht als gewöhnliche Tabelle angezeigt werden.