Zum Inhalt springen

Indizierung mit RDM - Wann soll welche Indizierungsmethode verwendet werden?

Derzeit unterstützt RDM 4 verschiedene Arten von Indizes, die der Benutzer für seine Datenbank verwenden kann. Diese Typen sind: B-Tree, R-Tree, Hash und AVL. Jeder hat seine eigenen idealen Anwendungsfälle und sie werden unten detailliert beschrieben, aber der Benutzer kann jeden Typ in seiner eigenen Datenbank ausprobieren und die ideale Leistung finden. 

B-Baum  

Die Standardindizierungsmethode für RDM ist der B-Baum. Ein B-Baum ist eine selbstausgleichende Baumstruktur, bei der die Daten geordnet bleiben, um sowohl die Suche als auch den sequentiellen Zugriff zu ermöglichen. Einfügungen, Löschungen, Aktualisierungen und Suchvorgänge können in einer logarithmischen Skala erfolgen. Ein B-Baum ist eine gute Lösung für On-Disk-Datenbanken, da die Breite der B-Baum-Knoten die Tiefe des Knotenbaums kleiner halten kann als ein selbstausgleichender Binärbaum. Dies führt dazu, dass weniger Datenträgerzugriff für die Suche und Aktualisierung des Baums erforderlich ist.  

Die RDM-B-Tree-Implementierung ist ein nicht gruppierter externer Baum, der nach den in der Indexdefinition angegebenen Spaltenwerten sortiert ist. Es gibt einen Eintrag in einem B-Tree-Knoten für jede Zeile in der Tabelle, von der der Index abgeleitet ist. Knoten werden durch ihre Objekt-ID identifiziert, die als Knoten-ID für Knotenobjekte bezeichnet wird. Dies ermöglicht eine effiziente Implementierung für Datenbanken, die entweder die On-Disk- oder die In-Memory-Engine verwenden. In beiden Engines werden Verweise auf eine Knoten-ID über den ID-Index für die Schublade nachgeschlagen, in der der B-Baum gespeichert ist. In der On-Disk-Engine enthält der ID-Index einen Offset und eine Größe des Knotens in der Pack-Datei. In der In-Memory-Engine enthält der ID-Index einen Zeiger auf den Knoten. Die RDM-B-Tree-Implementierung verwendet eine Knotengröße von 32 Elementen. Auf dem Transaktionsdateiserver werden jedoch nur die verwendeten Elemente gespeichert. RDM-B-Tree-Knoten werden niemals aktualisiert. Stattdessen wird ein neuer Knoten erstellt und der ID-Index wird aktualisiert, um auf den Speicherort des neuen Knotens zu verweisen. Der alte Knoten kann in späteren Transaktionen wiederverwendet werden.  

Raima-On-Disk-Storage-Datenbank

R-Tree (räumliche Indizierung)

RDM 14.1 hat einen Indexalgorithmus hinzugefügt, der speziell für Geodaten entwickelt wurde und als R-Tree bezeichnet wird. Es handelt sich um einen ausgewogenen Suchbaum, der seine Daten in Seiten organisiert und Objekte in der Nähe gruppiert und diese dann in der nächsten Ebene des Baums darstellt. Dies ist der ideale Indextyp, wenn Benutzer mehrdimensionale Daten innerhalb eines Begrenzungsrahmens schnell abrufen müssen.  Eine übliche reale Verwendung für einen R-Baum könnte darin bestehen, räumliche Objekte wie Restaurantstandorte oder die Polygone zu speichern, aus denen typische Karten bestehen: Straßen, Gebäude, Umrisse von Seen, Küsten usw., und dann schnell Antworten auf Fragen zu finden B. "Alle Museen innerhalb von 2 km von meinem aktuellen Standort finden", "Alle Straßensegmente innerhalb von 2 km von meinem Standort abrufen" (um sie in einem Navigationssystem anzuzeigen) oder "Die nächste Tankstelle finden" (obwohl keine Straßen aufgenommen werden) Konto)

R-Tree-Index Raima Database Manager

Hash  

Die Hash-Implementierung in RDM 14.1 verwendet einen erweiterbaren Hashing-Algorithmus. Der erweiterbare Hashing-Algorithmus erfordert nicht, dass der Entwickler die Kardinalität eines Index während der Entwurfszeit errät. Dies ist wichtig für die In-Memory-Speicher-Engine, da kein Speicher für eine Reihe von Buckets reserviert werden muss, die möglicherweise nie verwendet werden. Stattdessen nimmt die Verzeichnisgröße mit zunehmender Anzahl von Buckets im Hash zu. Die aktuelle Implementierung erlaubt nur eindeutige Schlüssel und ordnet Daten basierend auf den Schlüsselspalten (Daten werden basierend auf dem Hash dieser Spalten organisiert). Dies bedeutet, dass ein Hash für Suchvorgänge verwendet werden kann, jedoch nicht für sequentiellen Zugriff oder Bereiche.

Screenshot 2019-01-17 um 15.37.26

AVL  

RDM 14.1 hat außerdem einen Indexalgorithmus hinzugefügt, der speziell für die Verwendung in der speicherinternen Speicher-Engine verwendet wird und als AVL-Baum bezeichnet wird. Eine AVL ist ein selbstausgleichender Binärbaum, der in RDM nicht extern, sondern intern in einer Zeile implementiert wird. In der AVL gibt es keine Datenverdoppelung, da im Gegensatz zu einem B-Baum externe Knoten, die Kopien indizierter Spalten enthalten, nicht verwaltet werden. Eine AVL ist ein Binärbaum, dh die Tiefe des Baums ist viel größer als die eines B-Baums. Aus diesem Grund ist der AVL-Index für die In-Memory-Speicher-Engine mit dem erweiterten Zeilenformat besser geeignet als für die auf der Festplatte basierende Engine mit dem gepackten Zeilenformat. Das gepackte Zeilenformat enthält zwar eine Implementierung für den AVL-Index, diese ist jedoch hauptsächlich zum Speichern eines speicherinternen Images auf der Festplatte enthalten und nicht für die allgemeine Verwendung in festplattenbasierten Tabellen vorgesehen.  

Eine AVL kann für alle Operationen verwendet werden, für die ein B-Tree-Index verwendet werden würde. Die AVL unterstützt Suchvorgänge, Bereiche, Scannen und sowohl doppelte als auch eindeutige Einschränkungen. Das SQL-Optimierungsprogramm verwendet eine AVL auf die gleiche Weise wie ein B-Baum, verwendet jedoch ein geringfügig anderes Gewicht, basierend auf den Implementierungsunterschieden zwischen einem B-Baum und einer AVL.  

Curcuit Board

Probieren Sie jetzt RDM mit den verschiedenen Indizierungsmethoden aus