Comment écrire un moteur de base de données simple

Question

Je souhaite apprendre le fonctionnement d'un moteur de base de données (c'est-à-dire son fonctionnement interne). Je connais la plupart des structures de données de base enseignées en informatique (arbres, tables de hachage, listes, etc.) ainsi qu'une assez bonne compréhension de la théorie des compilateurs (et j'ai implémenté un interpréteur très simple) mais je ne comprends pas comment écrire un moteur de base de données. J'ai cherché des tutoriels sur le sujet et je n'en ai trouvé aucun, alors j'espère que quelqu'un d'autre pourra m'orienter dans la bonne direction. En gros, j'aimerais avoir des informations sur les points suivants :

• La manière dont les données sont stockées en interne (c'est-à-dire la manière dont les tables sont représentées, etc.)
• Comment le moteur trouve les données dont il a besoin (par exemple, en exécutant une requête SELECT).
• Comment les données sont-elles insérées de manière rapide et efficace ?

Et tout autre sujet qui pourrait être pertinent. 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 convient (si c'est plus facile) parce que je veux juste apprendre les principes sous-jacents.

Merci beaucoup pour votre aide.

Answer 1

Si vous êtes doué pour la lecture de code, l'étude de SQLite vous apprendra beaucoup de choses sur la conception des bases de données. Il est petit, donc plus facile à comprendre. Mais il est également écrit par des professionnels.

SQLite 2.5.0 pour la lecture de code

http://sqlite.org/

Answer 2

La réponse à cette question est très vaste. On peut s'attendre à ce qu'une thèse de doctorat y réponde à 100 % ;) mais nous pouvons envisager les problèmes un par un :

• Comment stocker les données en interne : vous devez disposer d'un fichier de données contenant les objets de votre base de données et d'un mécanisme de mise en cache pour charger les données en question et les données environnantes dans la mémoire vive. Supposons que vous ayez un tableau contenant des données. Nous créerons un format de données pour convertir ce tableau en fichier binaire, en nous accordant sur la définition d'un délimiteur de colonne et d'un délimiteur de ligne et en veillant à ce que ce type de délimiteur ne soit jamais utilisé dans les données elles-mêmes. Si vous avez choisi <*> pour séparer les colonnes, par exemple, vous devez valider les données que vous placez dans ce tableau pour qu'elles ne contiennent pas ce motif. 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 numéro d'indexation interne pour accélérer votre recherche, et au début de chaque colonne pour indiquer la longueur de cette colonne. comme "Adam", 1, 11.1, "123 ABC Street POBox 456" vous pouvez l'avoir comme <&RowHeader, 1><&Col1,CHR, 4>Adam<&Col2, num,1,0>1<&Col3, Num,2,1>111<&Col4, CHR, 24>123 ABC Street POBox 456<&RowTrailer>

• Comment trouver rapidement les articles essayez d'utiliser le hachage et l'indexation pour pointer vers les données stockées et mises en cache sur la base de différents critères en reprenant l'exemple ci-dessus, vous pourriez trier la valeur de la première colonne et la stocker dans un objet distinct pointant vers l'identifiant de ligne des éléments triés par ordre alphabétique, et ainsi de suite.

• Comment accélérer l'insertion des données Je sais d'Oracle qu'ils insèrent les données dans un endroit temporaire à la fois dans la RAM et sur le disque et font le ménage périodiquement, le moteur de base de données est occupé tout le temps à optimiser sa structure, mais en même temps nous ne voulons pas perdre les données en cas de panne de courant ou quelque chose comme ça. Essayez donc de conserver les données dans cet emplacement temporaire sans les trier, ajoutez votre stockage d'origine, et plus tard, lorsque le système est libre, recyclez vos index et effacez la zone temporaire une fois que vous avez terminé.

Bonne chance, beau projet.

Answer 3

Il existe des livres sur le sujet, mais un bon point de départ est le suivant Systèmes de base de données : Le livre complet par Garcia-Molina, Ullman et Widom

Answer 4

Je suggère de se concentrer sur www.sqlite.org

Il est récent, petit (code source 1MB), open source (pour que vous puissiez le découvrir par vous-même)...

Des livres ont été écrits sur sa mise 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 portables. Il est donc facile d'expérimenter et d'apprendre à le connaître, ce qui sera utile aujourd'hui et à l'avenir.

Il y a même une communauté décente ici : https://stackoverflow.com/questions/tagged/sqlite

Answer 5

J'ai trouvé un site qui contient des informations sur SQL et son implémentation - il est un peu difficile de faire un lien vers la page qui liste tous les tutoriels, donc je vais les lier un par un :

• http://c2.com/cgi/wiki?CategoryPattern
• http://c2.com/cgi/wiki?SliceResultVertically
• http://c2.com/cgi/wiki?SqlMyopia
• http://c2.com/cgi/wiki?SqlPattern
• http://c2.com/cgi/wiki?StructuredQueryLanguage
• http://c2.com/cgi/wiki?TemplateTables
• http://c2.com/cgi/wiki?ThinkSqlAsConstraintSatisfaction