Structure de données pour stocker des milliards d'entiers

Question

Quelle est la meilleure structure de données pour stocker les millions/milliards d'enregistrements (supposons qu'un enregistrement contienne un nom et un entier) dans la mémoire (RAM). Meilleur en termes de - temps de recherche minimum (priorité 1) et mémoire efficace (2ème priorité)? Est-ce l'arbre patricia? un autre mieux que ça?

La clé de recherche est un entier (disons un entier aléatoire de 32 bits). Et tous les enregistrements sont en RAM (en supposant que suffisamment de RAM est disponible).

En C, la plate-forme Linux ..

En gros Mon programme serveur attribue un 32bit clé aléatoire à l'utilisateur, et je veux stocker l'enregistrement d'utilisateur correspondant afin que je puisse rechercher/supprimer l'enregistrement de manière efficace. On peut supposer que la structure de données sera bien remplie.

Answer 1

Dépend.

Voulez-vous rechercher un nom ou un nombre entier?

Les noms sont-ils tous de la même taille?

Tous les nombres entiers sont-ils de 32 bits, ou quelque chose de grand nombre?

Etes-vous sûr que tout cela tient dans la mémoire? Si ce n'est pas le cas, vous êtes probablement limité par les E/S disque et la mémoire (ou l'utilisation du disque) ne vous préoccupe plus du tout. L'index (nom ou entier) a-t-il des préfixes communs ou est-il distribué uniformément? Seulement s'ils ont des préfixes communs, un arbre patricia est utile.

Cherchez-vous des index dans l'ordre (recherche de gang), ou au hasard? Si tout est uniforme, aléatoire et aucun préfixe commun, un hachage est déjà aussi bon qu'il obtient (ce qui est mauvais).

Si l'index est l'entier où la recherche de groupe est utilisée, vous pouvez vous intéresser aux arbres de base.

Answer 2

ma supposition est un B-Tree (mais je peux me tromper ...):

B-arbres présentent des avantages importants sur des implémentations alternatives lorsque dépassent largement l'accès temps d'accès aux nœuds fois dans les nœuds. Il se produit généralement lorsque la plupart des nœuds sont dans le stockage secondaire tels que les disques durs. En maximisant le nombre d'enfants nœuds dans chaque nœud interne, la hauteur de l'arbre diminue, l'équilibrage se produit moins souvent, et augmente l'efficacité. Habituellement, cette valeur est définie de sorte que chaque nœud prenne jusqu'à un bloc de disque complet ou une taille analogue dans le stockage secondaire. Alors que 2-3 arbres B- pourraient être utiles dans la mémoire principale , et sont certainement plus faciles à expliquer, si les tailles de nœuds sont accordées à la taille d'un bloc de disque, le résultat pourrait être un 257-513 B- arbre (où les tailles sont liées à plus grandes puissances de 2).

Answer 3

Au lieu d'un hachage, vous pouvez au moins utiliser une base pour commencer.

Pour tout problème spécifique, vous pouvez faire beaucoup mieux qu'un btree, une table de hachage, ou un patricia trie. Décrivez le problème un peu mieux, et nous pouvons vous suggérer ce qui pourrait fonctionner

Answer 4

Si vous voulez juste récupérer par une clé entière, alors une table de hachage simple est la plus rapide. Si les entiers sont consécutifs (ou presque consécutifs) et uniques, alors un simple tableau (de pointeurs vers des enregistrements) est encore plus rapide.

Si vous utilisez une table de hachage, vous souhaitez pré-allouer la hachage pour la taille finale attendue afin qu'elle ne ressasse pas.