Was ist der Vorteil der Verwendung von btree in aerospike für den Primärindex?

Question

Ich ging durch die Dokumentation von Aerospike. und fand heraus, dass Aerospike zum Speichern des Primärschlüssels Hashing verwendet und Hash auf einen BTree verweist und bTree den Zeiger auf den tatsächlichen Datensatz enthält. Soweit ich weiß Redis verwendet nur Hashing (zur Kollisionsauflösung pflegen sie eine Liste für Hash) .und Hash wird auf den tatsächlichen Datensatz gezeigt.

Was ist der Vorteil von Btree aerospike? bedeutet es nicht, dass aerospike für den Zugriff auf einen Datensatz mit seinem Primärschlüssel O (logn) benötigt? während redis würde nur O (1) nehmen.

Ich kann falsch liegen, aber das ist alles, was ich von documentation verstanden habe. Kann jemand bitte mehr Licht auf dieses Thema werfen?

Answer 1

Ich bin der Punkt der Frage nicht sicher, aber hier geht:

Eigentlich Aerospike des primary index ist eine verteilte Hash von red-black trees, zwischen 1 und 4096 sprigs pro Partition (siehe partition-tree-sprigs Config-param).

Es gibt 4096 logische Partitionen, die evenly distributed über die Knoten des Clusters sind. Der Schlüssel, der record identifiziert, ist ein 20-Byte-Digest, der erzeugt wird, indem das 3-Tupel (namespace, set, PK) durch RIPEMD-160 weitergegeben wird (der Client erledigt das automatisch für Sie). Der Datensatz ist konsistent Hash zu einer bestimmten Partition, da Bits in diesem Digest verwendet werden, um die Partitions-ID zu berechnen.

Im Gegensatz zu Redis, das als single-core Single-Thread-Anwendung auf einem einzigen Knoten ausgeführt wurde, wurde Aerospike als verteilte Datenbank erstellt. Es stimmt, dass Benutzer Ad-hoc-Cluster-Redis mit anwendungsseitigen Lösungen oder Middleware verwenden können. Im Fall von Aerospike teilen sich alle Knoten im Cluster und alle Clients partition map. Da der Client die Partitionszuordnung des Clusters kennt, ist er immer einen Sprung von dem Knoten entfernt, auf dem sich die Hauptpartition befindet (oder ein Knoten, der die Replikatpartition enthält - dies wird von replica read policy gesteuert). Also ist es O (1) zum richtigen Knoten im Cluster. Innerhalb dieses Knotens ist es O (1), den rbTree der Partition zu finden, und dann sind alle Operationen O (log n).

Wenn in einer hash table nicht viele Daten vorhanden sind (vorausgesetzt, Sie haben Recht mit der von Redis verwendeten Datenstruktur), sollte das Suchen nach einem Datensatz O (1) sein. Sobald jedoch mehr Elemente als Slots in der Hash-Tabelle vorhanden sind, wird zu einer verketteten Liste gewechselt, die O (n) ist. Für den rbTree ist es O (log n) für den Durchschnitts- und den Worst-Case-Fall. Aerospike soll große Datenmengen mit vorhersagbarer niedriger Latenz behandeln, daher war der rbTree geeigneter. Die Kosten für das Abrufen eines Datensatzes sind unabhängig von der Datenmenge im Cluster gleich.