Wie sind Datenbanken effizient?

Question

Wenn Datenbanken bis zu Millionen von Datensätzen unterstützen können, wie werden all diese Daten so organisiert, dass Abfragen in einer angemessenen Zeit ausgeführt werden können?

Answer 1

Indizes!

Wikipedia link to a full discussion on Indexes

Answer 2

Ich mag This Erklärung (einschließlich Grafiken;)

Dies ist artcicle Fazit:

Fazit

Index example http://mattfleming.com/files/images/example.gif

B-Baum-Indizes werden erstellt, um die Anzahl der erforderlichen E/A zu finden und eine Reihe von Daten zu laden. Ein hochselektiver Index verwendet die geringste Menge an I/O notwendig, schlecht selektive Indizes sind nicht viel besser als ein Table Scan.

Answer 3

Eine vollständige Antwort ist das Thema zahlreicher Bücher und Dissertationen ;-)

Allerdings ist die grundlegende Antwort, dass alle modernen RDBMS ein paar Eigenschaften haben: Erstens haben sie eine Abfrage-Optimierer, die ist sehr effektiv. Dies findet einen guten (nicht immer den besten) Pfad, um die gestellte Anfrage zu beantworten. Natürlich kann dies mehr tun, um komplizierte Fragen zu beantworten als einfache.

Zweitens speichern sie die Daten in einem strukturierten Format, das einfach zu suchen ist. Daten ohne einen gruppierten Index werden als Heap bezeichnet, und dies ist in der Regel weniger effektiv für die Suche, es handelt sich jedoch weiterhin um strukturierte Daten. Die Daten enthalten im Allgemeinen einen Clustered-Index, der die Daten logisch anordnet. (Einige Leute glauben, dass es die Daten physisch bestellt. Es gibt etwas Wahrheit, aber es ist nicht absolut wahr. Itzik Ben Gan unter anderen hat einen ausgezeichneten Artikel, der diesen Glauben entlarvt).

Zusätzlich zum gruppierten Index werden im Allgemeinen nicht gruppierte Indizes verwendet. Diese sind wie Indizes in einem Buch, die dem Abfrageoptimierer dabei helfen können, nach den angeforderten Daten zu suchen, oder in bestimmten Fällen kann der Index selbst alle erforderlichen Daten enthalten.

Dies ist natürlich eine grobe und schreckliche Vereinfachung. Wenn Sie ein tiefes Niveau verstehen wollen, seien Sie bereit, einen PHD in der Datenbank-Theorie zu verfolgen. Für ein allgemeines Verständnis können Sie Bücher über Datenbank-Interna betrachten. Insbesondere für SQL Server enthält SQL Server 2008 Internals viele Informationen zu diesem Thema.