SQL INDEX - wie geht das?

Meine Kenntnisse in Datenbanken und SQL basieren größtenteils auf Universitätsklassen. Jedenfalls habe ich einige Monate (fast ein Jahr) in einer Firma verbracht, in der ich mit Datenbanken gearbeitet habe.

Ich habe einige Bücher gelesen , und ich habe in wenigen Trainings über Datenbanken wie teilgenommen MySQL, PostgreSQL, SQLite, Oracleund auch wenige nonSQL dbs so uns MongoDB, Redis, ElasticSearchusw.

Wie gesagt, ich bin ein Anfänger mit vielen Unkenntnissen, aber heute hat jemand etwas erzählt, was völlig gegen das Wissen meines Anfängers ist.

Lassen Sie mich erklären. Nehmen wir die SQL- Datenbank und erstellen eine einfache Tabelle Personmit wenigen darin enthaltenen Datensätzen:

id | name   | age
-----------------
1  | Alex   | 24
2  | Brad   | 34
3  | Chris  | 29
4  | David  | 28
5  | Eric   | 18
6  | Fred   | 42
7  | Greg   | 65
8  | Hubert | 53
9  | Irvin  | 17
10 | John   | 19
11 | Karl   | 23

Nun, es ist der Teil, auf den ich mich konzentrieren möchte - idist der INDEX.

Bisher dachte ich, dass es so funktioniert: Wenn eine Tabelle erstellt wird, ist die INDEXleer. Wenn ich meinem Tisch einen neuen Datensatz hinzufüge, INDEXwird der anhand einiger Alghortims neu berechnet. Beispielsweise:

Eins nach dem anderen gruppieren:

1    ... N
N+1  ... 2N
     ...
XN+1 ... (X+1)N

Also, für mein Beispiel mit size = 11 elementsund wird N = 3es so sein:

id | name   | age
-----------------
1  | Alex   | 24     // group0
2  | Brad   | 34     // group0
3  | Chris  | 29     // group0
4  | David  | 28     // group1
5  | Eric   | 18     // group1
6  | Fred   | 42     // group1
7  | Greg   | 65     // group2
8  | Hubert | 53     // group2
9  | Irvin  | 17     // group2
10 | John   | 19     // group3
11 | Karl   | 23     // group3

Wenn ich also query verwende SELECT * FROM Person WHERE id = 8, wird eine einfache Berechnung durchgeführt 8 / 3 = 2, daher müssen wir nach diesem Objekt in suchen group2und dann wird diese Zeile zurückgegeben:

8  | Hubert | 53

Dieser Ansatz funktioniert in der Zeit O(k)wo k << size. Ein Alghoritm, Zeilen in Gruppen zu organisieren, ist natürlich viel komplizierter, aber ich denke, dieses einfache Beispiel zeigt meinen Standpunkt.

Deshalb möchte ich jetzt einen anderen Ansatz vorstellen, der mir heute gezeigt wurde.

Nehmen wir noch einmal diese Tabelle:

id | name   | age
-----------------
1  | Alex   | 24
2  | Brad   | 34
3  | Chris  | 29
4  | David  | 28
5  | Eric   | 18
6  | Fred   | 42
7  | Greg   | 65
8  | Hubert | 53
9  | Irvin  | 17
10 | John   | 19
11 | Karl   | 23

Nun sind wir etwas Ähnliches zu schaffen Hashmap(in der Tat wörtlich ist es eine Hash - Map) , die Karten idzu addressdieser Reihen - ID. Sagen wir:

id | addr 
---------
1  | @0001
2  | @0010
3  | @0011
4  | @0100
5  | @0101
6  | @0110
7  | @0111
8  | @1000
9  | @1001
10 | @1010
11 | @1011

Wenn ich jetzt meine Abfrage starte: SELECT * FROM Person WHERE id = 8

Es wird direkt id = 8auf die Adresse im Speicher abgebildet und die Zeile wird zurückgegeben. Natürlich ist die Komplexität davon O(1).

Jetzt habe ich einige Fragen.

1. Was sind die Vor- und Nachteile beider Lösungen?

2. Welches ist in aktuellen Datenbankimplementierungen beliebter? Vielleicht verwenden unterschiedliche DBs unterschiedliche Ansätze?

3. Existiert es in Nicht-SQL-Datenbanken?

Danke im Voraus

VERGLEICH

               |      B-tree     |   Hash Table
----------------------------------------------------
----------------   one element   -------------------
----------------------------------------------------
SEARCHING      |  O(log(N))      | O(1) -> O(N)  
DELETING       |  O(log(N))      | O(1) -> O(N)
INSERTING      |  O(log(N))      | O(1) -> O(N)
SPACE          |  O(N)           | O(N)
----------------------------------------------------
----------------    k elements   -------------------
----------------------------------------------------
SEARCHING      |  k + O(log(N))  | k * O(1) -> k * O(N)
DELETING       |  k + O(log(N))  | k * O(1) -> k * O(N)
INSERTING      |  k + O(log(N))  | k * O(1) -> k * O(N)
SPACE          |  O(N)           | O(N)

N - Anzahl der Datensätze

Habe ich recht? Was ist mit den Kosten für die Neuerstellung von B-Tree und Hash-Tabelle nach jedem Einfügen / Löschen ? Im Falle eines B-Baums müssen wir einige Zeiger ändern, aber im Falle eines ausgeglichenen B-Baums ist mehr Aufwand erforderlich. Auch im Fall einer Hash-Tabelle müssen wir nur wenige Operationen ausführen, insbesondere wenn unsere Operationen Konflikte erzeugen .

Sie beschreiben im Grunde einen B-Tree-Index und einen Hash-Index. Sie haben beide einen Platz, aber beide eignen sich am besten für verschiedene Jobs.

Vorteile und Nachteile

B-Tree- (und B + -Baum-) Indizes sind normalerweise ausgeglichen. Dies bedeutet, dass die Suche nach einem Wert immer dieselbe Zeit in Anspruch nimmt, unabhängig davon, wohin der Baum fällt (O (log n)). Im Allgemeinen ist die Anzahl der Ebenen im Baum begrenzt, sodass die Tendenz besteht, dass der Baum "breiter" und nicht "tiefer" wird. Bei kleinen Datensätzen können die Kosten für die Wartung und Verwendung des B-Baums jedoch mehr sein als nur das Lesen aller Zeilen. B-Tree-Indizes eignen sich für große Datensätze, Datensätze mit geringer Selektivität oder Datensätze, in denen Sie mehrere Objekte auswählen möchten, nicht nur ein Objekt.

Hash-Tabellen eignen sich hervorragend für kleine Datenmengen. Hash-Indizes haben je nach verwendetem Hash-Algorithmus eine vordefinierte Anzahl von Hash-Buckets. Dies liegt daran, dass ein gegebener Hash-Algorithmus nur so viele eindeutige Hashes erzeugen kann, dass er nur "tiefer" und nicht "breiter" wird. Sobald das Datenbankmodul den richtigen Bucket gefunden hat, durchsucht es alle Objekte in diesem Bucket, um den gewünschten zu finden. Bei kleinen, hochselektiven Datensätzen enthält jeder Bucket eine sehr geringe Anzahl von Objekten und wird ziemlich schnell aufgelöst. Bei größeren Datenmengen sind die Eimer viel überfüllt. Befindet sich das von Ihnen benötigte Objekt in einem kleinen Eimer oder in der Nähe des Eimeranfangs, wird es ziemlich schnell zurückgegeben. Wenn es am Ende eines großen Eimers ist, dauert es länger. Der Index ist nicht ausgewogen, sodass die Performance zwischen O (1) und O (n) liegt.

Popularität

Im Allgemeinen bin ich am häufigsten über B-Bäume gelaufen. Bitmap-Indizes sind auch eine weitere Option für Werte mit einer geringen Kardinalität (denken Sie an Boolesche Werte oder vielleicht an das Geschlecht). Dies variiert je nach Datenbankmodul, welche Indextypen verfügbar sind.

NoSQL

NoSQL-Datenbanken unterstützen auf jeden Fall Indizes. Die meisten unterstützen B-Tree oder eine Variation von B-Tree. Die meisten scheinen auch gehashte Indizes zu unterstützen.

Was sind die Vor- und Nachteile beider Lösungen? Die zweite Lösung kann keine Bereichsscans durchführen. Es ist ideal für die Auswahl einer einzelnen ID. Aber was ist, wenn Sie die IDs 3 bis 8 möchten? Es müssen alle Datensätze einzeln abgerufen werden, die in der realen Welt nicht nur aus O (1) * 6 Datensätzen bestehen. In einer großen Produktionsdatenbank mit einem HashMap-Index würden Sie Datensätze auf verschiedenen Seiten erhalten. Dazu müssten Sie auf die Festplatte klicken und sechs verschiedene Seiten in den Speicher einlesen.

In einer B-Tree-Struktur wären die IDs, wie in Ihrer ersten Situation, sequentiell auf der Festplatte, und eine einzelne Seite würde wahrscheinlich die IDs 3 bis 8 enthalten. Wenn Sie die Geschwindigkeit der Bereichsüberprüfungen erhöhen, erhalten Sie individuellen Zugriff. O (log n) .

Welches ist in aktuellen Datenbankimplementierungen beliebter? Vielleicht verwenden unterschiedliche DBs unterschiedliche Ansätze? Ich habe keine große Erfahrung in vielen verschiedenen Datenbanken. Ich weiß, dass SQL Server hauptsächlich B-Trees verwendet, aber SQL 2014 hat einige neue Hash-Indizes, die Sie für bestimmte Tabellen verwenden können. Ich höre viele No-SQL-Datenbanken und Caching-Datenbanken, die auf dem Abrufen einzelner Datensätze basieren, auch Hash-Indizes verwenden. Dies ist für Caches sinnvoll, da Sie den Datensatz für Benutzer A benötigen und keine Bereichsscans benötigen.

Existiert es in Nicht-SQL-Datenbanken? Ja. Ein kurzer Blick auf die Dokumentation zum Erstellen von Indizes für postgressql zeigt, dass sie sowohl Hash- und B-Tree-Indizes als auch einige andere unterstützt.