Conception axée sur la performance d'une base de données basée sur un graphique (clé/valeur)

Question

Je suis dans la phase de préparation de la conception d'une bibliothèque de base de données basée sur un graphique (ou valeur-clé) pour C++ comme http://neo4j.org/.

Puisque c'est une phase très précoce de la conception, mes exigences sont simples, non raffiné et (je l'avoue) sans doute encore un peu naïve:

• Un graphe orienté acyclique
  • A arborescent, comme la structure avec peu de racines et de feuilles
  • Les branches peuvent contenir des références à d'autres branches
  • Mais aucun cycle
  • Le graphique est représenté par paire clé-valeur où les clés et les valeurs sont des types simples (entiers) pour la plupart, mais certains peuvent se référer à des types plus complexes tels que les chaînes
• Requêtes
  • Les requêtes simples renvoient généralement des bords. C'est à dire. Quels arêtes partant de cette racine, correspond à (clé/valeur/valeur-clé tupple)?
  • requêtes en utilisant des chaînes de clés (clé, clé, clé, valeur)
• modèles d'accès et performance
  • lookups rapides doivent être soulignés
  • Ajout d'arêtes
  • Mais pas de suppression des arêtes/nœuds du graphique. C'est à dire. Le graphique va croître mais il ne rétrécira jamais.
  • Optimisations peuvent être effectuées sur le graphique afin d'optimiser la mise en page de mémoire pour l'utilisation du cache
  • Taille du graphique est de l'ordre d'environ 1 Mo - 2 Go et devrait le plus en forme de partie dans la mémoire principale

Compte tenu de ces exigences difficiles comme un défi, quelles seraient vos principales préoccupations est en ce qui concerne:

• stockage de la mémoire: la mise en page, l'allocation
  • E.g. Pool de blocs de taille fixe?
  • Affectation de mémoire par un algorithme de clustering?
• Les requêtes rapides
• réorganisation dynamique
  • Comment gérer plus d'arêtes/nœuds?
  • mises à jour pour l'optimisation (par exemple l'amélioration de la mise en page de mémoire)
• d'accès simultané
  • Par ex Gérer les modifications apportées à la mise en forme de la mémoire par un thread d'optimisation?

Je cherche de bons points de départ à partir duquel travailler, donc je suis plus qu'heureux de recevoir des références aux travaux existants. Le plus important: Qu'est-ce devrait Je pense à ce que je suis pas penser?

Answer 1

Une base de données clé/valeur rapide, vous pourriez être intéressé par titre de référence est tinycdb http://www.corpit.ru/mjt/tinycdb.html

Answer 2

Mais aucun cycle

Ceci est une exigence forte si vous avez besoin bord rapide insère. La vérification qu'un nouveau tronçon n'introduit pas un cycle est O (v + e) ​​dans le pire des cas (où v est le nombre de sommets et e est le nombre d'arêtes). Cela exclut probablement aussi l'insertion simultanée d'arêtes. Pensez à rendre cette exigence facultative.

Une autre option consiste à distinguer deux opérations d'insertion: CheapInsert et ExpensiveInsert. Laissez chaque vertice avoir un entier "rank" et n'autorisez que des insertions bon marché d'arêtes de sommets de rang inférieur à supérieur. L'insertion coûteuse n'aura pas cette contrainte et réécrira automatiquement les rangs si nécessaire. Les clients peuvent inspecter et changer le rang de n'importe quel vertice (tant que la règle de bas à haut n'est pas cassée). De cette façon, ils peuvent implémenter leur propre stratégie d'insertion, éventuellement en exploitant certaines propriétés spécifiques du graphique pour éviter les insertions coûteuses.