cstack/db_tutorial 项目解析：实现二分查找与重复键检测

引言

在数据库系统中，高效的数据检索和唯一性约束是核心功能。本文将深入探讨如何在cstack/db_tutorial项目中实现键的有序存储、二分查找算法以及重复键检测机制。

背景与问题

在之前的实现中，我们的数据库存在两个主要问题：

1. 键(key)以无序方式存储，导致查询效率低下
2. 没有检测重复键的机制，可能导致数据不一致

解决方案概述

我们将通过以下改进来解决这些问题：

1. 将插入操作改为在正确位置插入，而非总是追加到末尾
2. 实现二分查找算法来快速定位键的位置
3. 添加重复键检测功能

核心代码解析

插入操作的改进

ExecuteResult execute_insert(Statement* statement, Table* table) {
    void* node = get_page(table->pager, table->root_page_num);
    uint32_t num_cells = (*leaf_node_num_cells(node));
    if (num_cells >= LEAF_NODE_MAX_CELLS) {
        return EXECUTE_TABLE_FULL;
    }

    Row* row_to_insert = &(statement->row_to_insert);
    uint32_t key_to_insert = row_to_insert->id;
    Cursor* cursor = table_find(table, key_to_insert);

    if (cursor->cell_num < num_cells) {
        uint32_t key_at_index = *leaf_node_key(node, cursor->cell_num);
        if (key_at_index == key_to_insert) {
            return EXECUTE_DUPLICATE_KEY;
        }
    }

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

这段代码的主要改进点：

1. 首先检查节点是否已满
2. 使用table_find查找键应该插入的位置
3. 检查该位置是否已存在相同的键
4. 如果一切正常，执行插入操作

二分查找实现

Cursor* leaf_node_find(Table* table, uint32_t page_num, uint32_t key) {
    void* node = get_page(table->pager, page_num);
    uint32_t num_cells = *leaf_node_num_cells(node);

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

    // 二分查找实现
    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;
        uint32_t key_at_index = *leaf_node_key(node, index);
        if (key == key_at_index) {
            cursor->cell_num = index;
            return cursor;
        }
        if (key < key_at_index) {
            one_past_max_index = index;
        } else {
            min_index = index + 1;
        }
    }

    cursor->cell_num = min_index;
    return cursor;
}

二分查找算法解析：

1. 初始化查找范围为整个节点
2. 每次迭代将范围缩小一半
3. 如果找到匹配的键，返回其位置
4. 如果未找到，返回键应该插入的位置

节点类型处理

为了支持不同类型的节点(叶节点和内部节点)，我们添加了节点类型处理函数：

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

并在初始化叶节点时设置节点类型：

void initialize_leaf_node(void* node) {
    set_node_type(node, NODE_LEAF);
    *leaf_node_num_cells(node) = 0;
}

错误处理增强

我们扩展了执行结果枚举，添加了重复键错误：

enum ExecuteResult_t {
    EXECUTE_SUCCESS,
    EXECUTE_DUPLICATE_KEY,
    EXECUTE_TABLE_FULL
};

并添加了相应的错误处理：

case (EXECUTE_DUPLICATE_KEY):
    printf("Error: Duplicate key.\n");
    break;

测试验证

有序存储验证

修改后的测试验证了键是否按顺序存储：

expect(result).to match_array([
    "db > Executed.",
    "db > Tree:",
    "leaf (size 3)",
    "  - 0 : 1",
    "  - 1 : 2",
    "  - 2 : 3",
    "db > "
])

重复键检测验证

新增测试验证重复键检测功能：

it 'prints an error message if there is a duplicate id' do
    script = [
        "insert 1 user1 person1@example.com",
        "insert 1 user1 person1@example.com",
        "select",
        ".exit",
    ]
    expect(result).to match_array([
        "db > Executed.",
        "db > Error: Duplicate key.",
        "db > (1, user1, person1@example.com)",
        "Executed.",
        "db > ",
    ])
end

性能分析

使用二分查找后，查找操作的时间复杂度从O(n)降低到O(log n)，这对于大型数据库表尤其重要。例如：

• 100条记录：最多7次比较
• 10,000条记录：最多14次比较
• 1,000,000条记录：最多20次比较

总结与展望

通过本次改进，我们实现了：

1. 键的有序存储
2. 高效的二分查找
3. 重复键检测机制

下一步计划是实现叶节点分裂和内部节点的创建，这将使我们的数据库能够处理更多数据并保持高效查询。

这些改进为构建一个功能完整的关系型数据库奠定了基础，展示了即使是简单的数据库实现也需要考虑数据组织、查询效率和完整性约束等核心问题。