深入解析cstack/db_tutorial中的B-Tree叶子节点格式

前言

在数据库系统中，数据存储格式对性能有着决定性影响。本文将深入探讨cstack/db_tutorial项目中从简单数组存储到B-Tree结构的转变，特别是B-Tree叶子节点的格式设计。

存储格式对比

在数据库设计中，我们通常面临几种基本存储格式的选择：

1. 无序数组：

   • 优点：插入速度快(O(1))，空间利用率高
   • 缺点：查找和删除效率低(O(n))

2. 有序数组：

   • 优点：支持二分查找(O(log n))
   • 缺点：插入和删除需要移动大量数据(O(n))

3. B-Tree结构：

   • 优点：查找、插入和删除都是O(log n)
   • 缺点：需要存储元数据，空间利用率稍低

特性	无序数组	有序数组	B-Tree节点
页面内容	纯数据	纯数据	元数据+键+数据
每页行数	多	多	较少
插入复杂度	O(1)	O(n)	O(log n)
删除复杂度	O(n)	O(n)	O(log n)
ID查找复杂度	O(n)	O(log n)	O(log n)

B-Tree节点设计

节点类型定义

首先定义了两种节点类型：

typedef enum { NODE_INTERNAL, NODE_LEAF } NodeType;

公共头部结构

所有节点共享相同的头部结构，包含：

• 节点类型(1字节)
• 是否是根节点标志(1字节)
• 父节点指针(4字节)

const uint32_t NODE_TYPE_SIZE = sizeof(uint8_t);
const uint32_t NODE_TYPE_OFFSET = 0;
const uint32_t IS_ROOT_SIZE = sizeof(uint8_t);
const uint32_t IS_ROOT_OFFSET = NODE_TYPE_SIZE;
const uint32_t PARENT_POINTER_SIZE = sizeof(uint32_t);
const uint32_t PARENT_POINTER_OFFSET = IS_ROOT_OFFSET + IS_ROOT_SIZE;
const uint8_t COMMON_NODE_HEADER_SIZE = NODE_TYPE_SIZE + IS_ROOT_SIZE + PARENT_POINTER_SIZE;

叶子节点特有结构

叶子节点在公共头部基础上增加了：

• 单元格数量(4字节)

const uint32_t LEAF_NODE_NUM_CELLS_SIZE = sizeof(uint32_t);
const uint32_t LEAF_NODE_NUM_CELLS_OFFSET = COMMON_NODE_HEADER_SIZE;
const uint32_t LEAF_NODE_HEADER_SIZE = COMMON_NODE_HEADER_SIZE + LEAF_NODE_NUM_CELLS_SIZE;

单元格结构

每个单元格包含：

• 键(4字节)
• 值(行数据，293字节)

const uint32_t LEAF_NODE_KEY_SIZE = sizeof(uint32_t);
const uint32_t LEAF_NODE_KEY_OFFSET = 0;
const uint32_t LEAF_NODE_VALUE_SIZE = ROW_SIZE;
const uint32_t LEAF_NODE_VALUE_OFFSET = LEAF_NODE_KEY_OFFSET + LEAF_NODE_KEY_SIZE;
const uint32_t LEAF_NODE_CELL_SIZE = LEAF_NODE_KEY_SIZE + LEAF_NODE_VALUE_SIZE;

空间计算

计算每页能存储的最大单元格数：

const uint32_t LEAF_NODE_SPACE_FOR_CELLS = PAGE_SIZE - LEAF_NODE_HEADER_SIZE;
const uint32_t LEAF_NODE_MAX_CELLS = LEAF_NODE_SPACE_FOR_CELLS / LEAF_NODE_CELL_SIZE;

关键实现细节

节点访问方法

提供了一系列辅助函数来访问节点各部分：

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

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

uint32_t* 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;
}

插入操作实现

叶子节点插入逻辑：

void leaf_node_insert(Cursor* cursor, uint32_t key, Row* value) {
  void* node = get_page(cursor->table->pager, cursor->page_num);
  
  uint32_t num_cells = *leaf_node_num_cells(node);
  if (num_cells >= LEAF_NODE_MAX_CELLS) {
    printf("Need to implement splitting a leaf node.\n");
    exit(EXIT_FAILURE);
  }

  if (cursor->cell_num < num_cells) {
    // 为新单元格腾出空间
    for (uint32_t 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));
}

系统调整

Pager和Table对象变更

• 移除了部分页面写入支持，现在每个节点占用完整页面
• 用页面数替代行数作为主要度量
• Table对象现在跟踪根节点页码而非行数

游标对象变更

游标现在通过页码和单元格号定位，而非简单的行号：

typedef struct {
  Table* table;
  uint32_t page_num;
  uint32_t cell_num;
  bool end_of_table;
} Cursor;

调试工具

添加了两个有用的元命令：

1. .constants - 打印关键常量值
2. .btree - 打印B-Tree结构

当前限制

目前实现有以下限制：

1. 仅支持单节点树(最多13行)
2. 数据未排序存储
3. 节点分裂尚未实现

总结

本文详细介绍了cstack/db_tutorial项目中B-Tree叶子节点的格式设计和实现。虽然当前实现还有诸多限制，但已为后续扩展奠定了坚实基础。下一阶段将实现按主键查找和有序存储功能，进一步完善这个教学数据库系统。

通过这种渐进式的实现方式，开发者可以更好地理解数据库底层存储结构的演变过程和设计考量。