Datenstruktur zum Speichern von Milliarden von Ganzzahlen

Question

Welche Datenstruktur ist am besten, um die Millionen/Milliarden von Datensätzen (vorausgesetzt ein Datensatz enthält einen Namen und eine Ganzzahl) im Arbeitsspeicher (RAM) zu speichern? Beste in Bezug auf - minimale Suchzeit (1. Priorität) und Speicher effizient (2. Priorität)? Ist es Patricia Baum? Irgendein anderes besser als das?

Der Suchschlüssel ist eine Ganzzahl (z. B. eine 32-Bit-Zufallszahl). Und alle Datensätze sind im RAM (vorausgesetzt, dass genügend RAM verfügbar ist).

In C-Plattform Linux ..

Grundsätzlich Mein Server-Programm weist einen 32-Bit-zufälligen Schlüssel für den Benutzer, und ich mag den entsprechenden Benutzerdatensatz speichern, so dass ich den Rekord in effizienter Weise suchen/löschen. Es kann davon ausgegangen werden, dass die Datenstruktur gut gefüllt sein wird.

Answer 1

Hängt davon ab.

Möchten Sie nach einem Namen oder einer Ganzzahl suchen?

Sind die Namen ungefähr gleich groß?

Sind alle Ganzzahlen 32 Bits, oder einige große Zahl Dings?

Sind Sie sicher, dass alles in den Speicher passt? Wenn nicht, dann sind Sie wahrscheinlich durch Festplatten-I/O eingeschränkt und Speicher (oder Festplattennutzung) ist überhaupt kein Problem mehr.

Hat der Index (Name oder Integer) gemeinsame Präfixe oder sind sie einheitlich verteilt? Nur wenn sie gemeinsame Präfixe haben, ist ein Patricia-Baum nützlich.

Suchen Sie Indizes in der Reihenfolge (Bandensuche) oder zufällig? Wenn alles einheitlich, zufällig und keine gemeinsamen Präfixe ist, ist ein Hash bereits so gut wie er ist (was schlecht ist).

Wenn der Index die Ganzzahl ist, bei der die Suche nach Gruppen verwendet wird, könnten Sie in Radix-Bäume schauen.

Answer 2

meine fundierte Vermutung ist ein B-Tree (aber ich könnte falsch sein ...):

B-Bäume haben wesentliche Vorteile über alternative Implementierungen, wenn Knoten Zugriffszeiten weit Zugang Zeiten innerhalb Knoten überschreiten. Dies geschieht normalerweise tritt auf, wenn die meisten Knoten in sekundären Speicher wie Festplatten sind. Durch Maximierung der Anzahl der untergeordneten Knoten innerhalb jedes internen Knotens verringert sich die Höhe des Baums , wird weniger häufig ausgeglichen, und Effizienz steigt. Normalerweise wird dieser Wert so eingestellt, dass jeder Knoten einen vollen Plattenblock oder eine analoge Größe im Sekundärspeicher aufnimmt. Während 2-3 B-Bäume in Haupt Speicher nützlich sein können, und sicherlich einfacher sind zu erklären, wenn die Knotengrößen auf die Größe eines Plattenblocks abgestimmt sind, könnte das Ergebnis ein 257-513 B- sein. Baum (wo die Größen zu größeren Potenzen von 2 beziehen).

Answer 3

Anstelle eines Hash können Sie zumindest einen Radix verwenden, um loszulegen.

Für jedes spezifische Problem können Sie viel besser als ein btree, eine Hash-Tabelle oder ein Patricia Trie. Beschreibe das Problem ein wenig besser, und wir können vorschlagen, was könnte funktionieren

Answer 4

Wenn Sie nur durch einen Ganzzahlschlüssel abrufen möchten, dann ist eine einfache Hash-Tabelle am schnellsten. Wenn die Ganzzahlen aufeinanderfolgend (oder fast aufeinanderfolgend) und eindeutig sind, ist ein einfaches Array (mit Zeigern auf Datensätze) noch schneller.

Wenn Sie eine Hashtabelle verwenden, möchten Sie die Hashtabelle für die erwartete endgültige Größe vorab zuweisen, damit sie nicht erneut aufgeräumt wird.