Je suis intéressé à apprendre comment fonctionne un moteur de base de données (c'est-à-dire les composants internes de celui-ci). Je connais la plupart des structures de données de base enseignées dans CS (arbres, tables de hachage, listes, etc.) ainsi qu'une assez bonne compréhension de la théorie du compilateur (et j'ai implémenté un interpréteur très simple) mais je ne comprends pas comment y aller sur l'écriture d'un moteur de base de données. J'ai recherché des tutoriels sur le sujet et je n'en ai trouvé aucun, j'espère donc que quelqu'un d'autre pourra me diriger dans la bonne direction. En gros, je voudrais des informations sur les points suivants:
- Comment les données sont stockées en interne (c'est-à-dire comment les tables sont représentées, etc.)
- Comment le moteur trouve les données dont il a besoin (par exemple, exécuter une requête SELECT)
- Comment les données sont insérées de manière rapide et efficace
Et tout autre sujet qui pourrait être pertinent à ce sujet. Il n'est pas nécessaire que ce soit une base de données sur disque - même une base de données en mémoire est très bien (si c'est plus facile) parce que je veux juste apprendre les principes derrière cela.
Merci beaucoup pour votre aide.
La réponse à cette question est énorme. attendez-vous à ce qu'une thèse de doctorat y réponde à 100%;) mais nous pouvons penser aux problèmes un par un:
Comment stocker les données en interne: vous devriez avoir un fichier de données contenant vos objets de base de données et un mécanisme de mise en cache pour charger les données en focus et certaines données autour de lui dans la RAM en supposant que vous avez une table, avec quelques données, nous créerions un format de données pour convertir cette table en un fichier binaire, en s'accordant sur la définition d'un délimiteur de colonne et d'un délimiteur de ligne et assurez-vous qu'un tel modèle de délimiteur n'est jamais utilisé dans vos données elles-mêmes. c'est-à-dire que si vous avez sélectionné <*> par exemple pour séparer les colonnes, vous devez valider les données que vous placez dans ce tableau pour ne pas contenir ce modèle. vous pouvez également utiliser un en-tête de ligne et un en-tête de colonne en spécifiant la taille de la ligne et un certain numéro d'indexation interne pour accélérer votre recherche, et au début de chaque colonne pour avoir la longueur de cette colonne comme "Adam", 1, 11.1, "
Comment trouver rapidement des éléments Essayez d'utiliser le hachage et l'indexation pour pointer sur les données stockées et mises en cache en fonction de différents critères en prenant le même exemple ci-dessus, vous pouvez trier la valeur de la première colonne et la stocker dans un objet séparé pointant sur l'ID de ligne des éléments triés par ordre alphabétique , etc
Comment accélérer l'insertion de données que je connais d'Oracle, c'est qu'ils insèrent des données dans un endroit temporaire à la fois dans la RAM et sur le disque et font du ménage régulièrement, le moteur de base de données est occupé tout le temps à optimiser sa structure mais dans le même temps nous ne le faisons pas veulent perdre des données en cas de panne de courant de quelque chose comme ça. alors essayez de conserver les données dans cet endroit temporaire sans tri, ajoutez votre stockage d'origine, et plus tard, lorsque le système est libre, utilisez vos index et effacez la zone temporaire lorsque vous avez terminé
bonne chance, super projet.
la source
SQLite a déjà été mentionné, mais je veux ajouter quelque chose.
J'ai personnellement beaucoup appris en étudiant SQlite. Ce qui est intéressant, c'est que je ne suis pas allé au code source (même si je viens de jeter un coup d'œil). J'ai beaucoup appris en lisant le matériel technique et en regardant particulièrement les commandes internes qu'il génère. Il a son propre interpréteur basé sur la pile à l'intérieur et vous pouvez lire le P-Code qu'il génère en interne simplement en utilisant expl. Ainsi, vous pouvez voir comment diverses constructions sont traduites dans le moteur de bas niveau (c'est étonnamment simple - mais c'est aussi le secret de sa stabilité et de son efficacité).
la source
Il existe des livres sur le sujet, un bon point de départ serait Database Systems: The Complete Book de Garcia-Molina, Ullman et Widom
la source
D'accord, j'ai trouvé un site qui contient des informations sur SQL et l'implémentation - il est un peu difficile de créer un lien vers la page qui répertorie tous les tutoriels, donc je vais les lier un par un:
la source
Je suggérerais de me concentrer sur www.sqlite.org
C'est récent, petit (code source 1 Mo), open source (vous pouvez donc le découvrir par vous-même) ...
Des livres ont été écrits sur la façon dont il est mis en œuvre:
http://www.sqlite.org/books.html
Il fonctionne sur une variété de systèmes d'exploitation pour les ordinateurs de bureau et les téléphones mobiles, il est donc facile d'expérimenter et d'en apprendre davantage à ce sujet sera utile maintenant et à l'avenir.
Il a même une communauté décente ici: /programming/tagged/sqlite
la source
peut-être que vous pouvez apprendre de HSQLDB . Je pense qu'ils offrent une base de données petite et simple pour l'apprentissage. vous pouvez regarder les codes car il est open source.
la source
Je ne sais pas si cela répondrait à vos besoins, mais j'avais implémenté une base de données simple orientée fichier avec prise en charge de simple (
SELECT, INSERT , UPDATE) en utilisant perl.Ce que j'ai fait, c'est que j'ai stocké chaque table sous forme de fichier sur le disque et les entrées avec un modèle bien défini et j'ai manipulé les données en utilisant des outils Linux intégrés comme awk et sed. pour améliorer l'efficacité, les données fréquemment consultées ont été mises en cache.
la source
Si MySQL vous intéresse, je vous suggère également cette page wiki , qui contient des informations sur le fonctionnement de MySQL. Vous voudrez peut-être également jeter un œil à Comprendre les composants internes de MySQL .
Vous pouvez également envisager de rechercher une interface non SQL pour votre moteur de base de données. Veuillez jeter un œil à Apache CouchDB . C'est ce que vous appelleriez, un système de base de données orienté document.
Bonne chance!
la source