De nombreuses applications de bases de données (peut-être la plupart?) Utilisent aujourd'hui des arborescences B et des variantes pour stocker des données, car cette structure de données optimise les opérations de lecture, d'écriture et de recherche sur un disque dur (et ces opérations jouent à leur tour un rôle important dans l'efficacité globale de les bases de données).
Les disques SSD devraient-ils complètement remplacer les disques durs traditionnels (HDD), cependant, pourrait-on dire que les arbres B et les variantes deviendront obsolètes, laissant la place à des structures de données plus efficaces fonctionnant sur la mémoire à accès direct? Si oui, quelles seront ces structures? (par exemple, tables de hachage, arbres AVL)
database
data-structures
Daniel Scocco
la source
la source
Réponses:
Les B-Trees sont le plus souvent utilisés pour les index de base de données sur le disque dur, mais ils présentent des avantages même en tant que structure de données en mémoire, compte tenu de l'hérarchie de la mémoire moderne avec plusieurs couches de cache et de mémoire virtuelle. Même si la mémoire virtuelle est sur un SSD, cela ne changera pas.
J'utilise une bibliothèque d'arborescence multi-voies de style B + en mémoire que j'ai beaucoup écrite en C ++. Il peut avoir des avantages en termes de performances - la raison pour laquelle il a été écrit à l'origine était d'essayer de mieux utiliser le cache - mais je dois admettre qu'il ne fonctionne pas souvent de cette façon. Le problème est le compromis qui signifie que les éléments doivent se déplacer dans les nœuds lors des insertions et des suppressions, ce qui ne se produit pas pour les arbres binaires. En outre, certains des hacks de codage de bas niveau que j'ai utilisés pour l'optimiser - eh bien, ils confondent et défont probablement l'optimiseur, a dit la vérité.
Quoi qu'il en soit, même si vos bases de données sont stockées sur un SSD, il s'agit toujours d' un périphérique de stockage orienté bloc, et il y a toujours un avantage à utiliser les arborescences B et d'autres arborescences multivoies.
MAIS il y a une dizaine d'années, des algorithmes et des structures de données sans cache ont été inventés. Ceux-ci sont inconscients de la taille et de la structure des caches, etc. - ils font (asymptotiquement) la meilleure utilisation possible de toute hiérarchie de la mémoire. Les B-Trees doivent être "accordés" à une hiérarchie de mémoire particulière pour en faire le meilleur usage (bien qu'ils fonctionnent assez bien pour un éventail assez large de variations).
Les structures de données inconscientes du cache ne sont pas encore souvent vues dans la nature, voire pas du tout, mais il est temps qu'elles rendent les arbres binaires en mémoire obsolètes. Et ils peuvent également s'avérer utiles pour les disques durs et les SSD, car ils ne se soucient pas de la taille de la page de la taille du cluster ou du cache du disque dur.
La disposition de Van Emde Boas est très importante dans les structures de données sans cache.
Le cours sur les algorithmes MIT OpenCourseware comprend une certaine couverture des structures de données inconscientes du cache.
la source
A priori, oui, la plupart des moteurs de base de données devront être réécrits car le B-Tree ne sera plus la structure de données la plus efficace pour stocker les données, étant donné que la localité est très importante dans un disque dur où le disque se déplace lentement et les données sont récupérées en blocs, ce qui signifie que toute modification des données doit:
C'est 10 + 3 + 3 + 10 + 3 + 3 = 34 ms
En moyenne, faire la même chose sur un SSD n'est que de 1 ms, quelle que soit la position sur le disque.
Et comme une table de hachage est beaucoup plus rapide, nous pourrions penser qu'une table de hachage serait un meilleur remplacement.
Le seul problème est que les tables de hachage ne préservent pas l'ordre et qu'il n'est donc pas possible de trouver le suivant et le précédent comme le fait Van Emde Boas.
Voir:
Pourquoi trouver le suivant et le précédent est important? Imaginez que tous les éléments soient supérieurs à x et inférieurs à z, vous devez utiliser des index avec find previous et find next.
Eh bien, le seul problème est que nous n'avons pas trouvé de tables de hachage avec des capacités de conservation de l'ordre. Peut-être que la taille du compartiment dans l'arborescence B sera importante, mais cela est résolu avec des algorithmes de cache inconscients.
Je dirais donc que c'est un problème ouvert.
la source