Comment les données sont-elles organisées dans le fichier de données d'une base de données

Question

En tant qu'exercice d'apprentissage, j'essaie d'écrire une base de données intégrée simple en C#. Tout se passe bien, mais je suis vraiment coincé quand il s'agit de sauvegarder les données sur le disque.

Comme exemple de l'un de mes problèmes. Il se peut que je doive "insérer" des données au milieu du fichier de données. Ceci n'est clairement pas possible avec un accès séquentiel au fichier. Réécrire toute la dernière moitié du fichier chaque fois qu'il y a un insert n'est pas une option pour des raisons évidentes de performance.

La seule solution que je peux imaginer est d'écrire chaque table suivie par un espace vide dans le fichier. L'espace vide sera utilisé pour écrire de nouvelles données, et le fichier devra être restructuré/développé chaque fois qu'une table utilise son espace disponible. Je suppose que mes questions sont .. exactement ce que les données "ressemblent" dans le fichier de données d'une DB typique? Comment/où les nouvelles données sont-elles écrites dans le fichier?

Answer 1

Généralement, les bases de données utiliseront un arbre B pour stocker à la fois les données (où la clé sera la clé primaire de la ligne, et la valeur sera le contenu de la ligne) et les index. De cette façon, vous pouvez insérer des lignes dans des emplacements arbitraires en O(log n) heure. Ex, voir le file format for SQLite databases, qui décrit comment SQLite utilise un arbre B où les nœuds internes ne stockent que des pointeurs et les nœuds feuilles ne stockent que des données. Voir également: http://en.wikipedia.org/wiki/B-tree#Insertions_and_deletions_cause_trouble, qui semble résoudre le problème que vous rencontrez.

Answer 2

La réponse de David Wolever est erronée. Les données d'une base de données ne sont pas stockées dans B-trees. Les arbres B (habituellement B + -trees) stockent uniquement les clés et les pointeurs enfants dans les nœuds internes et les clés et les pointeurs de données dans les nœuds feuilles. Les arbres B + ne stockent généralement pas de données (ils peuvent le faire pour les tables de relations). Les données d'une base de données sont stockées dans ses fichiers de données qui sont organisés en blocs.