Plus grandes que les structures de données de la mémoire et la façon dont ils sont généralement traités

Question

Dire que j'ai une structure de données à base de fichiers comme un arbre B +. Je crois comprendre que les données devraient être stockées sur le disque, mais l'index est généralement chargé en mémoire. Que faire si vous avez un tel fichier que même son index ne rentre pas dans la mémoire? Comment est-ce généralement traitée? En second lieu, puisque l'indice est un arbre, pas un ensemble linéaire de données, comment est-il mis habituellement sur le disque?

Je suis fondamentalement curieux de savoir comment cela se fait dans des projets réels (tels que Berkeley DB). De toute évidence, je suis intéressé à grands traits. J'espère avoir une idée j'ai donc un contexte quand je creuse dans la section B-Tree de mon livre de base de données (ou faire du jogging ma mémoire de CS XYZ il y a des années)

Answer 1

B-arbres sont destinés à des systèmes de page, où un noeud donné s'insère dans une page. Pour trouver une entrée dans un B-arbre, il est seulement nécessaire de charger à la fois dans une page, afin que vous puissiez le faire.

Même les mettre à jour ne nécessite pas un grand nombre de pages en mémoire en même temps - j'imagine est une suppression lorsque les nœuds l'opération la plus difficile sont réorganisées, mais si elle est mise en œuvre avec soin même qui pourrait être fait avec relativement quelques pages en mémoire.

Answer 2

Vous pouvez jeter un oeil à SQLite. la base du code est beaucoup plus petit que Berkeley DB, il est domaine public, il est très clairement organisé et commenté, et le hors source de documentation est excellente. M'a appris beaucoup de choses sur le monde dans un arbre binaire réel

Answer 3

Pour répondre à votre première question, une structure de données qui est trop grand pour tenir dans la mémoire est généralement divisée en « pages », généralement toutes les pages sont de la même taille et chaque page contient une partie de la structure de données, d'utiliser les données pages de chargement et de déchargement.

Une autre option commune (qui n'est pas couramment utilisé dans SGBDR mais est commun avec des choses comme des fichiers XML et des médias) est le streaming, où vous traitez les données afin en chargeant la section suivante et jeter le précédent.

Et cela répond aussi à votre deuxième question, si vous utilisez la pagination que la structure du fichier est une séquence de pages de la même taille, si vous utilisez le streaming que les données doivent être disposées dans l'ordre que vous allez utiliser (dans le cas d'un arbre, il va probablement être soit DFS ou l'ordre BFS, en fonction de l'application).