• 实现一个简单的Database1

    “What I cannot create, I do not understand.” – Richard Feynman I’m building a clone of sqlite from scratch in C in order to understand, and I’m going to document my process as I go.

    译注：cstsck在github维护了一个简单的、类似SQLite的数据库实现，通过这个简单的项目，可以很好的理解数据库是如何运行的，实现教程原文是英文，共有13篇，这里翻译过来以飨读者。原文标题：Let's Build a Simple Database，本文是第一篇

    Part 1 介绍&设置REPL

    作为一名开发人员，在工作中我每天都使用关系型数据库。但是对我来说，它们是一个黑盒。我有一些问题：

    • 数据存储使用什么格式？（在内存与磁盘中）

    • 数据什么时候从内存转移到磁盘？

    • 为什么每张表只能有一个主键？

    • 事务回滚是怎么工作的？

    • 索引是什么格式的？

    • 全表扫描时什么时候发生，如何发生的？

    • 预处理语句（prepared statement）是使用什么格式存储的？

    换句话说，数据库是怎么工作的？

    为了弄清楚这些，我从头写了一个数据库。它是模仿SQLite实现的，因为SQLite设计小巧，并且相比于MySQL和PostgreSQL，它的功能相对要少很多，所以我希望能更容易的理解它。在实现上，整个数据库都存储在一个数据文件中。

    SQLite

    在SQLite的网站上，有很多SQLite的内部文档 （https://www.sqlite.org/arch.html） 。另外我还拷贝了文档（SQLite Database System: Design and Implementation.）的一个副本 （https://play.google.com/store/book s/details?id=9Z6IQQnX1JEC）

    SQLite architecture

    (https://www.sqlite.org/zipvfs/doc/trunk/www/howitworks.wiki)

    一个查询通过组件链来获取数据或者修改数据。前端如下组件：

    • 分词器(tokenizer)

    • 解析器（parser）

    • 代码生成器（code generator）

    前端的输入是SQL语句。输出则是SQLite的虚拟机字节码（virtual machine bytecode），本质上是一个可以在数据库运行的编译程序。

    译注：数据库实现查询优化模型分为传统的火山模型（Volcano model）与Code gen模型，本文作者实现的是code gen模型。

    后端包括如下组件：

    • 虚拟机（virtual machine）

    • B-tree

    • 页管理（pager）

    • 系统接口（os interface）

    virtual machine

    虚拟机将前端生成的字节码作为指令。它接下来可以在一个或更多的表、索引上执行操作，表以及索引都是存储在叫B-tree的数据结构中。VM 本质上是字节码指令类型的一个大开关语句 （a big switch statement on the type of bytecode instruction）

    B-tree

    每个B-tree有许多节点。每个节点是一个page的长度。B-tree可以通过执行命令到pager，从磁盘获取一个page或者保存回page到磁盘。

    pager

    pager接收命令来读取或者写入数据的pages。它是负责来读、写数据库文件的适当偏移位置。也负责保持当前访问的pages在内存中，并且决定何时这些pages需要写回磁盘。

    os interface

    系统接口与SQLite根据不同操作系统平台来编译不同，在这个系列教程中，我不准备去支持多平台适配。

    千里之行始于足下，所以我们从一些简单的事开始：REPL

    实现简单的REPL

    译注：REPL，Read - Execute - Print - Loop，即读取 - 执行 - 打印输出 - 循环，这个过程。有时候翻译成交互式解释器

    当你执行命令行命令时，SQLite开始读取-执行-打印循环 ：

    1. sqlite3
    2.     SQLite version 3.16.0 2016-11-04 19:09:39
    3.     Enter ".help" for usage hints.
    4.     Connected to a transient in-memory database.
    5.     Use ".open FILENAME" to reopen on a persistent database.
    6.     sqlite> create table users (id int, username varchar(255), email varchar(255));
    7.     sqlite> .tables
    8.     users
    9.     sqlite> .exit

    为了实现这样的效果，我们的主程序需要有一个无限循环来打印这个提示，获取一行输入，然后处理这行输入：

    1.     int main(int argc, char* argv[]) {
    2.       InputBuffer* input_buffer = new_input_buffer();
    3.       while (true) {
    4.         print_prompt();
    5.         read_input(input_buffer);
    6.     
    7.         if (strcmp(input_buffer->buffer, ".exit") == 0) {
    8.           close_input_buffer(input_buffer);
    9.           exit(EXIT_SUCCESS);
    10.         } else {
    11.           printf("Unrecognized command '%s'.\n", input_buffer->buffer);
    12.         }
    13.       }
    14.     }

    我们定义一个InputBuffer来作为一个封装，封装围绕在我们需要存储的、与 getline()函数 交互的状态（稍后将对此进行详细介绍）

    1. typedef struct {
    2.       char* buffer;
    3.       size_t buffer_length;
    4.       ssize_t input_length;
    5.     } InputBuffer;
    6.     
    7.     InputBuffer* new_input_buffer() {
    8.       InputBuffer* input_buffer = (InputBuffer*)malloc(sizeof(InputBuffer));
    9.       input_buffer->buffer = NULL;
    10.       input_buffer->buffer_length = 0;
    11.       input_buffer->input_length = 0;
    12.     
    13.       return input_buffer;
    14.     }

    接下来， print_prompt()函数 为用户打印出提示。在做这个之前需要读取每一行输入。

     void print_prompt() { printf("db > "); }

    读取命令行输入，需要使用 getline() 函数:

    ssize_t getline(char **lineptr, size_t *n, FILE *stream);

    （以下为getline的函数释义）

    lineptr：

    一个指针指向我们在buffer中包含的，从命令行读取的命令的变量。如果设置为NULL，它由 getline()函数 分配内存。并且后续由用户来释放，即使命令行的命令执行失败也能保证会被释放已分配的内存。

    n：

    一个指针变量，指向已经分配内存的buffer的大小（size）。

    stream：

    读取的输入流，这里是从标准输入读取的。

    return value（返回值，ssize_t类型）: 

    读取的字节数量，可能会比buffer的size小。

    我们告诉 getline()函数 保存读取的命令行到 input_buffer->buffer ，存储buffer的size到 input_buffer->buffer_length ，保存返回值到 input_buffer->input_length

    buffer在初始时是NULL，所以 getline()函数 分配足够的内存来存输入的命令行数据然后让buffer来指向这些数据。

    1. void read_input(InputBuffer* input_buffer) {
    2.       ssize_t bytes_read =
    3.           getline(&(input_buffer->buffer), &(input_buffer->buffer_length), stdin);
    4.     
    5.       if (bytes_read <= 0) {
    6.         printf("Error reading input\n");
    7.         exit(EXIT_FAILURE);
    8.       }
    9.     
    10.       // Ignore trailing newline
    11.       input_buffer->input_length = bytes_read - 1;
    12.       input_buffer->buffer[bytes_read - 1] = 0;
    13.     }

    现在就可以定义一个函数来释放已分配给 InputBuffer 实例和buffer中元素各自的数据结构的内存了（在 read_input()函数 中，调用 getline()函数 为 input_buffer->buffer 分配内存）。

    1.     void close_input_buffer(InputBuffer* input_buffer) {
    2.         free(input_buffer->buffer);
    3.         free(input_buffer);
    4.     }

    在最后，我们解析并执行命令。现在这只是仅有的一个认可的命令：.exit，一个终止程序的命令。除此之外的命令，我们打印一个报错信息然后继续程序的循环。

    1. if (strcmp(input_buffer->buffer, ".exit") == 0) {
    2.       close_input_buffer(input_buffer);
    3.       exit(EXIT_SUCCESS);
    4.     } else {
    5.       printf("Unrecognized command '%s'.\n", input_buffer->buffer);
    6.     }

    让我们来试试吧！

    1. ~ ./db
    2.     db > .tables
    3.     Unrecognized command '.tables'.
    4.     db > .exit
    5.     ~

    好了，我们得到了一个可以工作的REPL。在下一部分，我们将开始开发我们的命令语言。同时，下面是是这部分的全部程序代码：

    1. 1 #include <stdbool.h>
    2. 2 #include <stdio.h>
    3. 3 #include <stdlib.h>
    4. 4 #include <string.h>
    5. 5    
    6. 6    typedef struct {
    7. 7      char* buffer;
    8. 8      size_t buffer_length;
    9. 9      ssize_t input_length;
    10. 10    } InputBuffer;
    11. 11    
    12. 12    InputBuffer* new_input_buffer() {
    13. 13      InputBuffer* input_buffer = malloc(sizeof(InputBuffer));
    14. 14      input_buffer->buffer = NULL;
    15. 15      input_buffer->buffer_length = 0;
    16. 16      input_buffer->input_length = 0;
    17. 17    
    18. 18      return input_buffer;
    19. 19    }
    20. 20    
    21. 21    void print_prompt() { printf("db > "); }
    22. 22    
    23. 23    void read_input(InputBuffer* input_buffer) {
    24. 24      ssize_t bytes_read =
    25. 25               
    26. 26      getline(&(input_buffer->buffer), &(input_buffer->buffer_length), stdi n);
    27. 27    
    28. 28      if (bytes_read <= 0) {
    29. 29        printf("Error reading input\n");
    30. 30        exit(EXIT_FAILURE);
    31. 31      }
    32. 32    
    33. 33      // Ignore trailing newline
    34. 34      input_buffer->input_length = bytes_read - 1;
    35. 35      input_buffer->buffer[bytes_read - 1] = 0;
    36. 36    }
    37. 37    
    38. 38    void close_input_buffer(InputBuffer* input_buffer) {
    39. 39        free(input_buffer->buffer);
    40. 40        free(input_buffer);
    41. 41    }
    42. 42    
    43. 43    int main(int argc, char* argv[]) {
    44. 44      InputBuffer* input_buffer = new_input_buffer();
    45. 45      while (true) {
    46. 46        print_prompt();
    47. 47        read_input(input_buffer);
    48. 48    
    49. 49        if (strcmp(input_buffer->buffer, ".exit") == 0) {
    50. 50          close_input_buffer(input_buffer);
    51. 51          exit(EXIT_SUCCESS);
    52. 52        } else {
    53. 53          printf("Unrecognized command '%s'.\n", input_buffer->buffer);
    54. 54        }
    55. 55      }
    56. 56    }

    En j o y   G r e a t S Q L   : )

    《零基础学习MySQL 》 视 频 课 程

    戳 此 小 程 序 即 可 直 达 B 站

    https://www.bilibili.com/video/BV1Da411W7Va

    G r e a t S Q L 是 由 万 里 数 据 库 维 护 的 M y S Q L 分 支 ， 专 注 于 提 升 M G R 可 靠 性 及 性 能 ， 支 持 I n n o D B 并 行 查 询 特 性 ， 是 适 用 于 金 融 级 应 用 的 M y S Q L 分 支 版 本 。

     

  • 相关阅读:
    六、数组及其操作《2022 solidity8.+ 版本教程到实战》
    挑战杯 基于深度学习的水果识别 设计 开题 技术
    sql语句-如何以一个表中的数据为条件据查询另一个表中的数据
    企业内部通讯，WorkPlus助您打造高效沟通平台
    python中集合简介及使用
    最新WIN10 64位21H2正式版19044.2006
    前端技术koa/egg和es6入门
    深度学习：激活函数曲线总结
    Android音视频——AwesomePlayer到OMX服务过程
    从TCP到Socket，彻底理解网络编程是怎么回事
  • 原文地址：https://blog.csdn.net/m0_73257876/article/details/126927602