程序流程图

数据库系统结构

存储结构

叶子节点

（图中少标注了一个next_leaf_pointer）

内部节点

完整代码（待完善）

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <signal.h>
#include <stdbool.h>
#include <sys/stat.h>
#include <fcntl.h>

#define INPUT_BUFFER_SIZE 31
struct {
  char buffer[INPUT_BUFFER_SIZE + 1];
  size_t length;
} input_buffer;

typedef enum {
  INPUT_SUCCESS,
  INPUT_TOO_LONG
} InputResult;

typedef enum {
  EXECUTE_SUCCESS
} ExecuteResult;

typedef enum {
  META_COMMAND_SUCCESS,
  META_COMMAND_UNRECOGNIZED_COMMAND
} MetaCommandResult;

typedef enum {
  PREPARE_SUCCESS,
  PREPARE_NEGATIVE_VALUE,
  PREPARE_STRING_TOO_LONG,
  PREPARE_SYNTAX_ERROR,
  PREPARE_UNRECOGNIZED_STATEMENT,
  PREPARE_EMPTY_STATEMENT
} PrepareResult;

typedef enum {
  STATEMENT_INSERT,
  STATEMENT_SELECT,
  STATEMENT_DELETE
} StatementType;

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

InputResult read_input() {
  /* we read the entire line as the input */
  input_buffer.length = 0;
  while (input_buffer.length <= INPUT_BUFFER_SIZE
    && (input_buffer.buffer[input_buffer.length++] = getchar()) != '\n'
    && input_buffer.buffer[input_buffer.length - 1] != EOF);
  if (input_buffer.buffer[input_buffer.length - 1] == EOF)
    exit(EXIT_SUCCESS);
  input_buffer.length--;
  /* if the last character is not new-line, the input is considered too long,
     the remaining characters are discarded */
  if (input_buffer.length == INPUT_BUFFER_SIZE
    && input_buffer.buffer[input_buffer.length] != '\n') {
    while (getchar() != '\n');
    return INPUT_TOO_LONG;
  }
  input_buffer.buffer[input_buffer.length] = 0;
  return INPUT_SUCCESS;
}

#define COLUMN_B_SIZE 11

typedef struct {
  uint32_t a;
  char b[COLUMN_B_SIZE + 1];
} Row;

struct {
  StatementType type;
  Row row;
  uint8_t flag; /* whether row.a, row.b have valid values */
} statement;

// 定义Row序列化的布局

#define size_of_attribute(Struct, Attribute) sizeof(((Struct*)0)->Attribute)

#define a_SIZE size_of_attribute(Row, a)
#define b_SIZE size_of_attribute(Row, b)
#define a_OFFSET 0
#define b_OFFSET (a_OFFSET + a_SIZE)
#define ROW_SIZE (a_SIZE + b_SIZE)

#define PAGE_SIZE 4096
#define TABLE_MAX_PAGES 100

typedef struct{
  int file_descriptor;
  uint32_t file_length;
  uint32_t num_pages;
  void* pages[TABLE_MAX_PAGES];
}Pager;

struct {
  Pager* pager;
  uint32_t root_page_num;
}table;

typedef struct{
  uint32_t page_num;
  uint32_t cell_num;
  bool end_of_table;
}Cursor;

void print_row(Row* row) {
  printf("(%d, %s)\n", row->a, row->b);
}

/* B-Tree operations */

typedef enum { NODE_INTERNAL, NODE_LEAF } NodeType;

// 节点公共头部布局

#define NODE_TYPE_SIZE sizeof(uint8_t) // 节点类型
#define NODE_TYPE_OFFSET 0

#define IS_ROOT_SIZE sizeof(uint8_t) // 是否为根节点
#define IS_ROOT_OFFSET NODE_TYPE_SIZE

#define PARENT_POINTER_SIZE sizeof(uint32_t) // 父节点的指针
#define PARENT_POINTER_OFFSET (IS_ROOT_OFFSET + IS_ROOT_SIZE)

#define COMMON_NODE_HEADER_SIZE (NODE_TYPE_SIZE + IS_ROOT_SIZE + PARENT_POINTER_SIZE)

// 内部节点头部布局

#define INTERNAL_NODE_NUM_KEYS_SIZE sizeof(uint32_t) //key的数量
#define INTERNAL_NODE_NUM_KEYS_OFFSET COMMON_NODE_HEADER_SIZE

#define INTERNAL_NODE_RIGHT_CHILD_SIZE sizeof(uint32_t) // 最右子节点指针
#define INTERNAL_NODE_RIGHT_CHILD_OFFSET (INTERNAL_NODE_NUM_KEYS_OFFSET + INTERNAL_NODE_NUM_KEYS_SIZE)

#define INTERNAL_NODE_HEADER_SIZE (COMMON_NODE_HEADER_SIZE + INTERNAL_NODE_NUM_KEYS_SIZE + INTERNAL_NODE_RIGHT_CHILD_SIZE)

// 内部节点结构体布局

#define INTERNAL_NODE_KEY_SIZE (sizeof(char)*12) // 关键字
#define INTERNAL_NODE_CHILD_SIZE sizeof(uint32_t) // 关键字对应子节点指针

#define INTERNAL_NODE_CELL_SIZE (INTERNAL_NODE_CHILD_SIZE + INTERNAL_NODE_KEY_SIZE)
#define INTERNAL_NODE_MAX_CELLS 30

// 叶子节点头部定义

#define LEAF_NODE_NUM_CELLS_SIZE sizeof(uint32_t) // cell数量
#define LEAF_NODE_NUM_CELLS_OFFSET COMMON_NODE_HEADER_SIZE

#define LEAF_NODE_NEXT_LEAF_SIZE sizeof(uint32_t) // 下一叶节点指针
#define LEAF_NODE_NEXT_LEAF_OFFSET (LEAF_NODE_NUM_CELLS_OFFSET + LEAF_NODE_NUM_CELLS_SIZE)

#define LEAF_NODE_HEADER_SIZE (COMMON_NODE_HEADER_SIZE + LEAF_NODE_NUM_CELLS_SIZE + LEAF_NODE_NEXT_LEAF_SIZE)

// 叶子节点结构体定义

#define LEAF_NODE_KEY_SIZE (sizeof(char)*12) // 关键字
#define LEAF_NODE_KEY_OFFSET 0

#define LEAF_NODE_VALUE_SIZE ROW_SIZE // 存储的数据(Row)
#define LEAF_NODE_VALUE_OFFSET (LEAF_NODE_KEY_OFFSET + LEAF_NODE_KEY_SIZE)

#define LEAF_NODE_CELL_SIZE (LEAF_NODE_KEY_SIZE + LEAF_NODE_VALUE_SIZE)
#define LEAF_NODE_SPACE_FOR_CELLS (PAGE_SIZE - LEAF_NODE_HEADER_SIZE)
#define LEAF_NODE_MAX_CELLS (LEAF_NODE_SPACE_FOR_CELLS / LEAF_NODE_CELL_SIZE)
#define LEAF_NODE_RIGHT_SPLIT_COUNT ((LEAF_NODE_MAX_CELLS + 1) / 2)
#define LEAF_NODE_LEFT_SPLIT_COUNT ((LEAF_NODE_MAX_CELLS + 1) - LEAF_NODE_RIGHT_SPLIT_COUNT)

// B+树基本功能函数定义

NodeType get_node_type(void* node) {
  uint8_t value = *((uint8_t*)(node + NODE_TYPE_OFFSET));
  return (NodeType)value;
}

void set_node_type(void* node, NodeType type) {
  uint8_t value = type;
  *((uint8_t*)(node + NODE_TYPE_OFFSET)) = value;
}

bool is_node_root(void* node) {
  uint8_t value = *((uint8_t*)(node + IS_ROOT_OFFSET));
  return (bool)value;
}

void set_node_root(void* node, bool is_root) {
  uint8_t value = is_root;
  *((uint8_t*)(node + IS_ROOT_OFFSET)) = value;
}

uint32_t* node_parent(void* node) { return node + PARENT_POINTER_OFFSET; }

uint32_t* internal_node_num_keys(void* node) {
  return node + INTERNAL_NODE_NUM_KEYS_OFFSET;
}

uint32_t* internal_node_right_child(void* node) {
  return node + INTERNAL_NODE_RIGHT_CHILD_OFFSET;
}

uint32_t* internal_node_cell(void* node, uint32_t cell_num) {
  return node + INTERNAL_NODE_HEADER_SIZE + cell_num * INTERNAL_NODE_CELL_SIZE;
}

uint32_t* internal_node_child(void* node, uint32_t child_num) {
  uint32_t num_keys = *internal_node_num_keys(node);
  if (child_num > num_keys) {
    printf("Tried to access child_num %d > num_keys %d\n", child_num, num_keys);
    exit(EXIT_FAILURE);
  } else if (child_num == num_keys) {
    return internal_node_right_child(node);
  } else {
    return internal_node_cell(node, child_num);
  }
}

char* internal_node_key(void* node, uint32_t key_num) {
  return (void*)internal_node_cell(node, key_num) + INTERNAL_NODE_CHILD_SIZE;
}

uint32_t* leaf_node_num_cells(void* node) {
  return node + LEAF_NODE_NUM_CELLS_OFFSET;
}

uint32_t* leaf_node_next_leaf(void* node) {
  return node + LEAF_NODE_NEXT_LEAF_OFFSET;
}

void* leaf_node_cell(void* node, uint32_t cell_num) {
  return node + LEAF_NODE_HEADER_SIZE + cell_num * LEAF_NODE_CELL_SIZE;
}

char* leaf_node_key(void* node, uint32_t cell_num) {
  return leaf_node_cell(node, cell_num);
}

void* leaf_node_value(void* node, uint32_t cell_num) {
  return leaf_node_cell(node, cell_num) + LEAF_NODE_KEY_SIZE;
}

char* get_node_max_key(void* node) {
  switch (get_node_type(node)) {
    case NODE_INTERNAL:
      return &*internal_node_key(node, *internal_node_num_keys(node) - 1);
    case NODE_LEAF:
      return &*leaf_node_key(node, *leaf_node_num_cells(node) - 1);
  }
}

// Pager Cursor

void* get_page(Pager* pager, uint32_t page_num) {
  if (page_num > TABLE_MAX_PAGES) {
    printf("Tried to fetch page number out of bounds. %d > %d\n", page_num,
           TABLE_MAX_PAGES);
    exit(EXIT_FAILURE);
  }

  if (pager->pages[page_num] == NULL) {
    // 缓存为0，从文件中分配内存
    void* page = malloc(PAGE_SIZE);
    uint32_t num_pages = pager->file_length / PAGE_SIZE;

    // 可能在文件末尾保存一个部分页面
    if (pager->file_length % PAGE_SIZE) {
      num_pages += 1;
    }

    if (page_num <= num_pages) {
      lseek(pager->file_descriptor, page_num * PAGE_SIZE, SEEK_SET);
      ssize_t bytes_read = read(pager->file_descriptor, page, PAGE_SIZE);
      if (bytes_read == -1) {
        exit(EXIT_FAILURE);
      }
    }

    pager->pages[page_num] = page;

    if (page_num >= pager->num_pages) {
      pager->num_pages = page_num + 1;
    }
  }

  return pager->pages[page_num];
}

void serialize_row(Row* source, void* destination) {
  memcpy(destination + a_OFFSET, &(source->a), a_SIZE);
  memcpy(destination + b_OFFSET, &(source->b), b_SIZE);
}

void deserialize_row(void* source, Row* destination) {
  memcpy(&(destination->a), source + a_OFFSET, a_SIZE);
  memcpy(&(destination->b), source + b_OFFSET, b_SIZE);
}

void initialize_leaf_node(void* node) {
  set_node_type(node, NODE_LEAF);
  set_node_root(node, false);
  *leaf_node_num_cells(node) = 0;
  *leaf_node_next_leaf(node) = 0;  // 0 represents no sibling
}

void initialize_internal_node(void* node) {
  set_node_type(node, NODE_INTERNAL);
  set_node_root(node, false);
  *internal_node_num_keys(node) = 0;
}

Cursor* leaf_node_find(uint32_t page_num, char* key) {
  void* node = get_page(table.pager, page_num);
  uint32_t num_cells = *leaf_node_num_cells(node);

  Cursor* cursor = malloc(sizeof(Cursor));
  cursor->page_num = page_num;
  cursor->end_of_table = false;

  // Binary search
  uint32_t min_index = 0;
  uint32_t one_past_max_index = num_cells;
  while (one_past_max_index != min_index) {
    uint32_t index = (min_index + one_past_max_index) / 2;
    char* key_at_index = &*leaf_node_key(node, index);
    if (strcmp(key, key_at_index) == 0) {
      cursor->cell_num = index;
      return cursor;
    }
    if (strcmp(key, key_at_index) < 0) {
      one_past_max_index = index;
    } else {
      min_index = index + 1;
    }
  }

  cursor->cell_num = min_index;
  return cursor;
}

uint32_t internal_node_find_child(void* node, char* key) {
  /*
  Return the index of the child which should contain
  the given key.
  */

  uint32_t num_keys = *internal_node_num_keys(node);

  /* Binary search */
  uint32_t min_index = 0;
  uint32_t max_index = num_keys; /* there is one more child than key */

  while (min_index != max_index) {
    uint32_t index = (min_index + max_index) / 2;
    char* key_to_right = &*internal_node_key(node, index);
    if (strcmp(key_to_right, key) >= 0) {
      max_index = index;
    } else {
      min_index = index + 1;
    }
  }

  return min_index;
}

Cursor* internal_node_find(uint32_t page_num, char* key) {
  void* node = get_page(table.pager, page_num);

  uint32_t child_index = internal_node_find_child(node, key);
  uint32_t child_num = *internal_node_child(node, child_index);
  void* child = get_page(table.pager, child_num);
  switch (get_node_type(child)) {
    case NODE_LEAF:
      return leaf_node_find(child_num, key);
    case NODE_INTERNAL:
      return internal_node_find(child_num, key);
  }
}

Cursor* table_find(char* key) {
  uint32_t root_page_num = table.root_page_num;
  void* root_node = get_page(table.pager, root_page_num);

  if (get_node_type(root_node) == NODE_LEAF) {
    return leaf_node_find(root_page_num, key);
  } else {
    return internal_node_find(root_page_num, key);
  }
}

Cursor* table_start() {
  Cursor* cursor = table_find("A");

  void* node = get_page(table.pager, cursor->page_num);
  uint32_t num_cells = *leaf_node_num_cells(node);
  cursor->end_of_table = (num_cells == 0);

  return cursor;
}

void* cursor_value(Cursor* cursor) {
  uint32_t page_num = cursor->page_num;
  void* page = get_page(table.pager, page_num);
  return leaf_node_value(page, cursor->cell_num);
}

void cursor_advance(Cursor* cursor) {
  uint32_t page_num = cursor->page_num;
  void* node = get_page(table.pager, page_num);

  cursor->cell_num += 1;
  if (cursor->cell_num >= (*leaf_node_num_cells(node))) {
    /* Advance to next leaf node */
    uint32_t next_page_num = *leaf_node_next_leaf(node);
    if (next_page_num == 0) {
      /* This was rightmost leaf */
      cursor->end_of_table = true;
    } else {
      cursor->page_num = next_page_num;
      cursor->cell_num = 0;
    }
  }
}



Pager* pager_open(const char* filename) {
  int fd = open(filename,
                O_RDWR |      // 读/写模式
                    O_CREAT,  // 如果文件不存在，则创建该文件
                S_IWUSR |     // 用户写权限
                    S_IRUSR   // 用户读权限
                );

  if (fd == -1) {
    printf("Unable to open file\n");
    exit(EXIT_FAILURE);
  }

  off_t file_length = lseek(fd, 0, SEEK_END);

  Pager* pager = malloc(sizeof(Pager));
  pager->file_descriptor = fd;
  pager->file_length = file_length;
  pager->num_pages = (file_length / PAGE_SIZE);

    if (file_length % PAGE_SIZE != 0) {
        printf("Db file is not a whole number of pages. Corrupt file.\n");
        exit(EXIT_FAILURE);
    }

    for (uint32_t i = 0; i < TABLE_MAX_PAGES; i++) {
        pager->pages[i] = NULL;
    }


  return pager;
}

void open_file(const char* filename) {
	/* open file */
  Pager* pager = pager_open(filename);

  table.pager = pager;
  table.root_page_num = 0;

  if (pager->num_pages == 0) {
    // New database file. Initialize page 0 as leaf node.
    void* root_node = get_page(pager, 0);
    initialize_leaf_node(root_node);
    set_node_root(root_node, true);
  }

}

void pager_flush(Pager* pager, uint32_t page_num) {
  if (pager->pages[page_num] == NULL) {
    printf("Tried to flush null page\n");
    exit(EXIT_FAILURE);
  }

  off_t offset = lseek(pager->file_descriptor, page_num * PAGE_SIZE, SEEK_SET);

  if (offset == -1) {
    exit(EXIT_FAILURE);
  }

  ssize_t bytes_written =
      write(pager->file_descriptor, pager->pages[page_num], PAGE_SIZE);

  if (bytes_written == -1) {
    exit(EXIT_FAILURE);
  }
}

void exit_nicely(int code) {
  /* do clean work */
  Pager* pager = table.pager;

  int i = 0;
  for (i = 0; i < pager->num_pages; i++) {
    if (pager->pages[i] == NULL) {
      continue;
    }
    pager_flush(pager, i);
    free(pager->pages[i]);
    pager->pages[i] = NULL;
  }

  int result = close(pager->file_descriptor);
  if (result == -1) {
    printf("Error closing db file.\n");
    exit(EXIT_FAILURE);
  }
  for (i = 0; i < TABLE_MAX_PAGES; i++) {
    void* page = pager->pages[i];
    if (page) {
      free(page);
      pager->pages[i] = NULL;
    }
  }
  free(pager);
  exit(code);
}

void exit_success() {
  printf("bye~\n");
  exit_nicely(EXIT_SUCCESS);
}

MetaCommandResult do_meta_command() {
  if (strcmp(input_buffer.buffer, ".exit") == 0) {
    exit(EXIT_SUCCESS);
  } else {
    return META_COMMAND_UNRECOGNIZED_COMMAND;
  }
}

PrepareResult prepare_insert() {
  statement.type = STATEMENT_INSERT;

  char* keyword = strtok(input_buffer.buffer, " ");
  char* a = strtok(NULL, " ");
  char* b = strtok(NULL, " ");
  int x;

  if (a == NULL || b == NULL)
    return PREPARE_SYNTAX_ERROR;

  x = atoi(a);
  if (x < 0)
    return PREPARE_NEGATIVE_VALUE;
  if (strlen(b) > COLUMN_B_SIZE)
    return PREPARE_STRING_TOO_LONG;

  statement.row.a = x;
  strcpy(statement.row.b, b);

  return PREPARE_SUCCESS;
}

PrepareResult prepare_condition() {
  statement.flag = 0;

  char* keyword = strtok(input_buffer.buffer, " ");
  char* b = strtok(NULL, " ");
  char* c = strtok(NULL, " ");

  if (b == NULL) return PREPARE_SUCCESS;
  if (c != NULL) return PREPARE_SYNTAX_ERROR;

  if (strlen(b) > COLUMN_B_SIZE)
    return PREPARE_STRING_TOO_LONG;

  strcpy(statement.row.b, b);
  statement.flag |= 2;

  return PREPARE_SUCCESS;
}

PrepareResult prepare_select() {
  statement.type = STATEMENT_SELECT;
  return prepare_condition();
}

PrepareResult prepare_delete() {
  statement.type = STATEMENT_DELETE;
  PrepareResult result = prepare_condition();
  if (result == PREPARE_SUCCESS && statement.flag == 0)
    return PREPARE_SYNTAX_ERROR;
  return result;
}

PrepareResult prepare_statement() {
  if (strlen(input_buffer.buffer) == 0) {
    return PREPARE_EMPTY_STATEMENT;
  } else if (strncmp(input_buffer.buffer, "insert", 6) == 0) {
    return prepare_insert();
  } else if (strncmp(input_buffer.buffer, "select", 6) == 0) {
    return prepare_select();
  } else if (strncmp(input_buffer.buffer, "delete", 6) == 0) {
    return prepare_delete();
  }
  return PREPARE_UNRECOGNIZED_STATEMENT;
}

uint32_t get_unused_page_num(Pager* pager) { return pager->num_pages; }

void create_new_root(uint32_t right_child_page_num) {
  /*
  拆分根的处理。
  旧的根复制到新页面，成为左子。
  确保子结点的地址正确传入。
  重新初始化根页面以确保包含新的根节点。
  新的根节点指向两个子节点。
  */

  void* root = get_page(table.pager, table.root_page_num);
  void* right_child = get_page(table.pager, right_child_page_num);
  uint32_t left_child_page_num = get_unused_page_num(table.pager);
  void* left_child = get_page(table.pager, left_child_page_num);

  /* 左子结点具有从旧根复制的数据 */
  memcpy(left_child, root, PAGE_SIZE);
  set_node_root(left_child, false);

  /* 根节点是一个新的内部节点，有一个关键值和两个子节点 */
  initialize_internal_node(root);
  set_node_root(root, true);
  *internal_node_num_keys(root) = 1;
  *internal_node_child(root, 0) = left_child_page_num;
  char* left_child_max_key = get_node_max_key(left_child);
  *internal_node_key(root, 0) = *left_child_max_key;
  *internal_node_right_child(root) = right_child_page_num;
  *node_parent(left_child) = table.root_page_num;
  *node_parent(right_child) = table.root_page_num;
}

void internal_node_insert(uint32_t parent_page_num,
                          uint32_t child_page_num) {
  /*
  将新的子/关键值（child/key）键值对添加到与子结点对应的父结点
  */

  void* parent = get_page(table.pager, parent_page_num);
  void* child = get_page(table.pager, child_page_num);
  char* child_max_key = get_node_max_key(child);
  uint32_t index = internal_node_find_child(parent, child_max_key);

  uint32_t original_num_keys = *internal_node_num_keys(parent);
  *internal_node_num_keys(parent) = original_num_keys + 1;

  if (original_num_keys >= INTERNAL_NODE_MAX_CELLS) {
    printf("Need to implement splitting internal node\n");
    exit(EXIT_FAILURE);
  }

  uint32_t right_child_page_num = *internal_node_right_child(parent);
  void* right_child = get_page(table.pager, right_child_page_num);

  if ( strcmp(child_max_key, get_node_max_key(right_child) ) > 0 ) {
    /* 替换右子树的结点 */
    *internal_node_child(parent, original_num_keys) = right_child_page_num;
    *internal_node_key(parent, original_num_keys) =
        *get_node_max_key(right_child);
    *internal_node_right_child(parent) = child_page_num;
  } else {
    /* 为新的结点或者说层腾出空间 */
    int i;
    for (i = original_num_keys; i > index; i--) {
      void* destination = internal_node_cell(parent, i);
      void* source = internal_node_cell(parent, i - 1);
      memcpy(destination, source, INTERNAL_NODE_CELL_SIZE);
    }
    *internal_node_child(parent, index) = child_page_num;
    *internal_node_key(parent, index) = *child_max_key;
  }
}

void update_internal_node_key(void* node, char* old_key, const char* new_key) {
  uint32_t old_child_index = internal_node_find_child(node, old_key);
  *internal_node_key(node, old_child_index) = *new_key;
}

void leaf_node_split_and_insert(Cursor* cursor, const char* key, Row* value) {
  /*
  创建一个新节点并移动一半的结点。
  将新值插入两个节点之一。
  更新父结点或创建新父结点。
  */

  void* old_node = get_page(table.pager, cursor->page_num);
  char* old_max = get_node_max_key(old_node);
  uint32_t new_page_num = get_unused_page_num(table.pager);
  void* new_node = get_page(table.pager, new_page_num);
  initialize_leaf_node(new_node);
  *node_parent(new_node) = *node_parent(old_node);
  *leaf_node_next_leaf(new_node) = *leaf_node_next_leaf(old_node);
  *leaf_node_next_leaf(old_node) = new_page_num;

  /*
  在旧的（左）和新（右）结点之间平均分配所有现有密钥和新密钥。
  从右侧开始，将每个键移动到正确的位置。
  */
  int i;
  for (i = LEAF_NODE_MAX_CELLS; i >= 0; i--) {
    void* destination_node;
    if (i >= LEAF_NODE_LEFT_SPLIT_COUNT) {
      destination_node = new_node;
    } else {
      destination_node = old_node;
    }
    uint32_t index_within_node = i % LEAF_NODE_LEFT_SPLIT_COUNT;
    void* destination = leaf_node_cell(destination_node, index_within_node);

    if (i == cursor->cell_num) {
      serialize_row(value,
                    leaf_node_value(destination_node, index_within_node));
      *leaf_node_key(destination_node, index_within_node) = *key;
    } else if (i > cursor->cell_num) {
      memcpy(destination, leaf_node_cell(old_node, i - 1), LEAF_NODE_CELL_SIZE);
    } else {
      memcpy(destination, leaf_node_cell(old_node, i), LEAF_NODE_CELL_SIZE);
    }
  }

  /* 更新两个叶结点上的结构 */
  *(leaf_node_num_cells(old_node)) = LEAF_NODE_LEFT_SPLIT_COUNT;
  *(leaf_node_num_cells(new_node)) = LEAF_NODE_RIGHT_SPLIT_COUNT;

  if (is_node_root(old_node)) {
    return create_new_root(new_page_num);
  } else {
    uint32_t parent_page_num = *node_parent(old_node);
    char* new_max = get_node_max_key(old_node);
    void* parent = get_page(table.pager, parent_page_num);

    update_internal_node_key(parent, old_max, new_max);
    internal_node_insert(parent_page_num, new_page_num);
    return;
  }
}

void leaf_node_insert(Cursor* cursor, char* key, Row* value) {
  void* node = get_page(table.pager, cursor->page_num);

  uint32_t num_cells = *leaf_node_num_cells(node);
  if (num_cells >= LEAF_NODE_MAX_CELLS) {
    // 节点已满
    leaf_node_split_and_insert(cursor, key, value);
    return;
  }

  if (cursor->cell_num < num_cells) {
    // 为新数据腾出空间
    int i;
    for (i = num_cells; i > cursor->cell_num; i--) {
      memcpy(leaf_node_cell(node, i), leaf_node_cell(node, i - 1),
             LEAF_NODE_CELL_SIZE);
    }
  }

  *(leaf_node_num_cells(node)) += 1;
  *(leaf_node_key(node, cursor->cell_num)) = *key;
  serialize_row(value, leaf_node_value(node, cursor->cell_num));
}

ExecuteResult execute_insert() {
  Row* row_to_insert = &(statement.row);
  char* key_to_insert = row_to_insert->b;
  Cursor* cursor = table_find(key_to_insert);

  void* node = get_page(table.pager, cursor->page_num);
  uint32_t num_cells = *leaf_node_num_cells(node);

  leaf_node_insert(cursor, row_to_insert->b, row_to_insert);

  free(cursor);

  return EXECUTE_SUCCESS;
}

ExecuteResult execute_select() {

  Cursor* cursor = table_start();

  Row row;
  bool isFind = false;
  if (statement.flag == 0) {
      while (!(cursor->end_of_table)) {
          deserialize_row(cursor_value(cursor), &row);
          if (row.a != 0) {
              if (!isFind)
              {
                  isFind = true;
                  printf("\n");
              }
              print_row(&row);
          }

          cursor_advance(cursor);
      }
  }
  Row rows[10000];
  int count = 0;
  while (!(cursor->end_of_table)) {
    deserialize_row(cursor_value(cursor), &row);
    if (strcmp(row.b, statement.row.b) == 0 && row.a != 0) {
        if (!isFind)
        {
            isFind = true;
            printf("\n");
            rows[0] = row;
            count = 1;
        }
        else {
            int position = 0;
            while (position <= count) {
                if (row.a > rows[position].a) {
                    break;
                } else {
                    position++;
                }
            }
            count++;
            for (int i = count; i > position; i--) {
                rows[i] = rows[i - 1];
            }
            rows[position] = row;
        }
    }

    cursor_advance(cursor);
  }
  for (int i = 0; i < count; i++) {
      print_row(&rows[i]);
  }

  free(cursor);
  if (!isFind) {
      printf("\n(Empty)");
      printf("\n");
  }

  return EXECUTE_SUCCESS;
}

ExecuteResult execute_delete() {
    Cursor* cursor = table_start();

    Row row;
    while (!(cursor->end_of_table)) {
        deserialize_row(cursor_value(cursor), &row);
        if (strcmp( row.b, statement.row.b) == 0) {
            Row del;
            del.a = 0;
            int i;
            for (i = 0; i < sizeof(del) ; i++) {
                del.b[i] = row.b[i];
            }
            serialize_row(&del, cursor_value(cursor));

        }
        cursor_advance(cursor);
    }

    free(cursor);

    return EXECUTE_SUCCESS;
}

ExecuteResult execute_statement() {
  switch (statement.type) {
    case STATEMENT_INSERT:
      return execute_insert();
    case STATEMENT_SELECT:
      return execute_select();
    case STATEMENT_DELETE:
      return execute_delete();
  }
}

void sigint_handler(int signum) {
  printf("\n");
  exit(EXIT_SUCCESS);
}

int main(int argc, char* argv[]) {
  if (argc < 2) {
    printf("Must supply a database filename.\n");
    exit(EXIT_FAILURE);
  }

  atexit(&exit_success);
  signal(SIGINT, &sigint_handler);

  open_file(argv[1]);

  while (1) {
    print_prompt();
    switch (read_input()) {
      case INPUT_SUCCESS:
        break;
      case INPUT_TOO_LONG:
        printf("Input is too long.\n");
        continue;
    }

    if (input_buffer.buffer[0] == '.') {
      switch (do_meta_command()) {
        case META_COMMAND_SUCCESS:
          continue;
        case META_COMMAND_UNRECOGNIZED_COMMAND:
          printf("Unrecognized command '%s'.\n", input_buffer.buffer);
          continue;
      }
    }

    switch (prepare_statement()) {
      case PREPARE_SUCCESS:
        break;
      case PREPARE_EMPTY_STATEMENT:
        continue;
      case PREPARE_NEGATIVE_VALUE:
        printf("Column `a` must be positive.\n");
        continue;
      case PREPARE_STRING_TOO_LONG:
        printf("String for column `b` is too long.\n");
        continue;
      case PREPARE_SYNTAX_ERROR:
        printf("Syntax error. Could not parse statement.\n");
        continue;
      case PREPARE_UNRECOGNIZED_STATEMENT:
        printf("Unrecognized keyword at start of '%s'.\n",
               input_buffer.buffer);
        continue;
    }

    switch (execute_statement()) {
      case EXECUTE_SUCCESS:
        printf("\nExecuted.\n\n");
        break;
    }
  }
}

参考资料：db_tutorial