深入理解cstack/db_tutorial项目：内存中的简易数据库实现

项目概述

cstack/db_tutorial项目是一个教学性质的数据库实现教程，旨在帮助开发者理解数据库系统的基本原理。在第三部分中，项目实现了一个简单的内存数据库，支持基本的插入和查询操作。

核心数据结构设计

行(Row)结构

数据库的核心是数据存储，本项目定义了一个简单的行结构：

typedef struct {
  uint32_t id;
  char username[COLUMN_USERNAME_SIZE];  // 32字节
  char email[COLUMN_EMAIL_SIZE];       // 255字节
} Row;

这种设计包含了三种数据类型：

• 整型的id字段
• 固定长度的用户名(32字节)
• 固定长度的邮箱(255字节)

序列化与反序列化

为了高效存储，行数据需要序列化为紧凑的二进制格式：

void serialize_row(Row* source, void* destination) {
  memcpy(destination + ID_OFFSET, &(source->id), ID_SIZE);
  memcpy(destination + USERNAME_OFFSET, &(source->username), USERNAME_SIZE);
  memcpy(destination + EMAIL_OFFSET, &(source->email), EMAIL_SIZE);
}

反序列化过程则相反：

void deserialize_row(void* source, Row* destination) {
  memcpy(&(destination->id), source + ID_OFFSET, ID_SIZE);
  memcpy(&(destination->username), source + USERNAME_OFFSET, USERNAME_SIZE);
  memcpy(&(destination->email), source + EMAIL_OFFSET, EMAIL_SIZE);
}

存储引擎实现

分页设计

数据库采用了分页存储策略，这是大多数数据库系统的常见做法：

• 每页大小设为4KB，与操作系统虚拟内存页大小一致
• 每页可存储约14行数据(291字节/行)
• 最大支持100页，即约1400行数据

const uint32_t PAGE_SIZE = 4096;
#define TABLE_MAX_PAGES 100
const uint32_t ROWS_PER_PAGE = PAGE_SIZE / ROW_SIZE;
const uint32_t TABLE_MAX_ROWS = ROWS_PER_PAGES * TABLE_MAX_PAGES;

表(Table)结构

表结构管理所有页面和行数信息：

typedef struct {
  uint32_t num_rows;
  void* pages[TABLE_MAX_PAGES];  // 页面指针数组
} Table;

这种设计实现了惰性内存分配——只有在访问某页时才分配内存：

void* row_slot(Table* table, uint32_t row_num) {
  uint32_t page_num = row_num / ROWS_PER_PAGE;
  void* page = table->pages[page_num];
  if (page == NULL) {
    page = table->pages[page_num] = malloc(PAGE_SIZE);
  }
  // 计算行在页内的偏移量
  uint32_t row_offset = row_num % ROWS_PER_PAGE;
  uint32_t byte_offset = row_offset * ROW_SIZE;
  return page + byte_offset;
}

命令执行流程

语句准备(Prepare)

系统首先解析用户输入，准备执行语句：

PrepareResult prepare_statement(InputBuffer* input_buffer, Statement* statement) {
  if (strncmp(input_buffer->buffer, "insert", 6) == 0) {
    statement->type = STATEMENT_INSERT;
    // 解析插入参数
    int args_assigned = sscanf(input_buffer->buffer, "insert %d %s %s", 
                              &(statement->row_to_insert.id),
                              statement->row_to_insert.username,
                              statement->row_to_insert.email);
    if (args_assigned < 3) {
      return PREPARE_SYNTAX_ERROR;
    }
    return PREPARE_SUCCESS;
  }
  // ...处理SELECT语句
}

语句执行(Execute)

对于INSERT语句：

ExecuteResult execute_insert(Statement* statement, Table* table) {
  if (table->num_rows >= TABLE_MAX_ROWS) {
    return EXECUTE_TABLE_FULL;
  }
  
  Row* row_to_insert = &(statement->row_to_insert);
  serialize_row(row_to_insert, row_slot(table, table->num_rows));
  table->num_rows += 1;
  
  return EXECUTE_SUCCESS;
}

对于SELECT语句：

ExecuteResult execute_select(Statement* statement, Table* table) {
  Row row;
  for (uint32_t i = 0; i < table->num_rows; i++) {
    deserialize_row(row_slot(table, i), &row);
    print_row(&row);
  }
  return EXECUTE_SUCCESS;
}

项目特点与局限

当前实现特点

1. 纯内存数据库，无持久化功能
2. 仅支持单表固定结构
3. 简单的分页存储策略
4. 支持两种操作：插入行和查询所有行

已知局限性

1. 无持久化存储，程序退出后数据丢失
2. 表结构硬编码，无法动态修改
3. 查询功能简单，仅支持全表扫描
4. 无索引支持，查询效率低
5. 最大行数限制较严格

总结与展望

本部分实现了一个基础的内存数据库核心功能，展示了数据库系统的基本组成部分：数据存储结构、命令解析和执行引擎。虽然功能简单，但已经具备了数据库系统的雏形。

后续开发可以考虑：

1. 增加持久化存储功能
2. 实现更高效的数据结构(如B树)
3. 支持动态表结构
4. 增加事务支持
5. 实现更复杂的查询功能

这个简单的实现为理解更复杂的数据库系统打下了坚实基础，后续的优化和扩展将在此基础上进行。