Bustub重点解析

mvcc解析

主流程

task1: watermark

Watermark::AddTxn 事务开启的时候，记录读时间戳
Watermark::RemoveTxn 事件提交或者回滚的时候，更新watermark

task2: 重建元组和扫描算子

重建元组

示例 1：正常更新链

初始版本 (t=0): {id:1, name:"Alice", age:25}
更新 (t=1): 修改 name → "Bob"    (undo_log[1])
更新 (t=2): 修改 age → 30        (undo_log[0])
当前版本: {id:1, name:"Bob", age:30}

执行 ReconstructTuple 回退到 t=0:

values = {1, "Bob", 30}, is_deleted = false

应用 undo_log[0] (age 修改):
  modified_fields_: [false, false, true]
  tuple_: [30]
  → values = {1, "Bob", 30}  (age 改回 30？不对！)

等等，这里要注意顺序：undo_logs 是从新到旧
undo_logs[0] 是 t=2 的修改 (age: 25 → 30)
undo_logs[1] 是 t=1 的修改 (name: Alice → Bob)

应用 undo_log[0] (回退 age):
  values = {1, "Bob", 25}
应用 undo_log[1] (回退 name):
  values = {1, "Alice", 25}
结果: {id:1, name:"Alice", age:25} ✅

示例 2：删除与恢复

t=0: 插入 {id:1, name:"Alice", age:25}
t=1: 删除该行															(undo_log[1])
t=2: 重新插入 {id:1, name:"Alice", age:25}(undo_log[0])
当前版本: {id:1, name:"Alice", age:25}

执行 ReconstructTuple 回退到 t=1 (已删除):

values = {1, "Alice", 25}, is_deleted = false

应用 undo_log[0] (t=2 的插入):
  undo_log.is_deleted_ = false
  modified_fields_: [true, true, true] (完整元组)
  → 不做特殊处理，因为 values 非空
  → values = {1, "Alice", 25}

应用 undo_log[1] (t=1 的删除):
  undo_log.is_deleted_ = true
  → is_deleted = true
  → values.clear()

循环结束，is_deleted = true
返回 std::nullopt ✅

UndoLink结构体解析

当前元组 (最新版本)
    │
    │  UndoLink
    ↓
Txn 100, undo_logs_[3]  ← 上一个版本
    │
    │  UndoLink (在 UndoLog 内部)
    ↓
Txn 99, undo_logs_[7]   ← 更早版本
    │
    │  UndoLink
    ↓
Txn 98, undo_logs_[1]   ← 最老版本
    │
    │  UndoLink (IsValid() == false)
    ↓
  NULL (没有更早版本)

扫描算子

1、获取 tuple
2、获取当前行的undo log版本链
3、根据版本链获取应该显示的tuple
4、扫描的谓词过滤

task3: 增删改算子

insert

路径 1: UPDATE 路径 (`rid_opt.has_value() == true`)

当检测到主键冲突且需要更新时，执行以下步骤：

获取旧元组信息

auto tuple_link_info = GetTupleAndUndoLink(txn_mgr, table_info->table_.get(), rid_opt.value());
auto &tuple_meta = std::get<0>(tuple_link_info);  // 元组元数据
auto &old_tuple = std::get<1>(tuple_link_info);   // 旧元组数据
auto cur_ts = tuple_meta.ts_;                     // 当前版本的时间戳

写-写冲突检测

if (IsWriteWriteConflict(txn, cur_ts)) {
    txn->SetTainted();
    throw ExecutionException("w-w conflict");
}

检查当前事务是否与持有该元组的事务存在写-写冲突
如果冲突，标记事务为脏并抛出异常

处理已删除元组

auto tuple_ptr = &old_tuple;
if (tuple_meta.is_deleted_) {
    tuple_ptr = nullptr;  // 元组已被删除，视为空
}

生成或查找 Undo Link

auto target_undo_link = GenerateOrFindUndoLink(
    &table_info->schema_, txn_mgr, txn, 
    tuple_ptr,           // 旧元组（可能为空）
    tuple_meta.ts_,      // 旧时间戳
    new_tuple,           // 新元组
    std::get<2>(tuple_link_info)  // 原来的 undo link
);

这是 MVCC 的核心：创建 undo 记录以便回滚
保存旧版本信息，允许事务回滚时恢复

更新元组

auto check = [cur_ts](const TupleMeta &meta, const Tuple &tuple, RID rid, std::optional<UndoLink> undo_link) {
    return meta.ts_ == cur_ts;  // 乐观锁检查：确保元组未被其他事务修改
};
tuple_meta.is_deleted_ = false;  // 标记为未删除
tuple_meta.ts_ = txn->GetTransactionTempTs();  // 更新时间戳为当前事务的临时时间戳
auto updated = UpdateTupleAndUndoLink(txn_mgr, rid_opt.value(), target_undo_link, 
                                       table_info->table_.get(), txn,
                                       tuple_meta, *new_tuple, check);
if (!updated) {
    txn->SetTainted();
    throw ExecutionException("Update failed");
}

使用乐观锁检查，确保更新是原子的
如果更新失败（元组被其他事务修改），抛出异常

路径 2: INSERT 路径 (`rid_opt.has_value() == false`)

纯插入操作：

插入元组到表

1 2	auto tuple_meta = TupleMeta{txn->GetTransactionTempTs(), false}; rid_opt = table_info->table_->InsertTuple(tuple_meta, *new_tuple, lock_mgr, txn, table_info->oid_);

创建新的元组元数据（时间戳 = 事务临时时间戳，未删除）
调用表的 InsertTuple 方法分配新的 RID
使用锁管理器确保并发安全

更新索引（只更新主键索引）

for (const auto &index : indexes) {
    if (!index->is_primary_key_) {
        continue;  // 只处理主键索引
    }
    auto inserted = index->index_->InsertEntry(
        new_tuple->KeyFromTuple(table_info->schema_, index->key_schema_, index->index_->GetKeyAttrs()),
        rid_opt.value(), 
        txn
    );
    if (!inserted) {
        txn->SetTainted();
        throw ExecutionException("Duplicate key");
    }
}

提取元组的主键值
插入到 B+ 树索引中
如果插入失败（重复键），抛出异常

GenerateNewUndoLog and GenerateUpdatedUndoLog

GenerateNewUndoLog

INSERT 操作：base_tuple == nullptr

1
2
3

if (base_tuple == nullptr) {
    return UndoLog{true, {}, {}, ts, prev_version};
}

场景：插入新元组

base_tuple 为空 → 修改前没有数据
返回的Undo日志：is_deleted_ = true（回滚时删除该元组）
modified_fields_ 和 tuple_ 为空（不需要保存旧值）

示例：

1	INSERT INTO users (id, name) VALUES (1, 'Alice');

Undo Log：{is_deleted: true, modified: [], tuple: []}
回滚时：删除RID对应的元组

DELETE 操作：target_tuple == nullptr

if (target_tuple == nullptr) {
    std::vector<bool> modified_fields;
    modified_fields.resize(schema->GetColumnCount(), true);  // 所有字段都修改
    auto original_tuple = *base_tuple;  // 保存完整的旧元组
    return UndoLog{false, modified_fields, original_tuple, ts, prev_version};
}

场景：删除已有元组

target_tuple 为空 → 修改后数据消失
标记所有字段为已修改（modified_fields 全为true）
保存完整的原始元组（original_tuple）
is_deleted_ = false（回滚时恢复元组，不是删除）

示例：

1	DELETE FROM users WHERE id = 1;

Undo Log：{is_deleted: false, modified: [true,true,…], tuple: (1, ‘Alice’, 25)}
回滚时：在RID位置插入保存的完整元组

UPDATE 操作：两者都不为空

std::vector<bool> modified_fields;
modified_fields.resize(schema->GetColumnCount(), false);
std::vector<Column> modified_columns;
std::vector<Value> modified_values;

for (uint32_t i = 0; i < schema->GetColumnCount(); i++) {
    // 比较每个字段的值是否变化
    if (base_tuple->GetValue(schema, i).CompareExactlyEquals(target_tuple->GetValue(schema, i))) {
        continue;  // 字段未变化，跳过
    }
    modified_fields[i] = true;
    modified_columns.push_back(schema->GetColumn(i));
    modified_values.push_back(base_tuple->GetValue(schema, i));  // 保存旧值
}

场景：更新已有元组的部分字段

逐字段比较 base_tuple 和 target_tuple
只记录发生变化的字段
节省存储空间（只保存修改字段的旧值）

示例：

1 2	-- 假设原数据: (1, 'Alice', 25) UPDATE users SET name = 'Bob', age = 26 WHERE id = 1;

比较结果：

id: 1 vs 1 → 未变化，跳过
name: ‘Alice’ vs ‘Bob’ → 变化，记录旧值 ‘Alice’
age: 25 vs 26 → 变化，记录旧值 25

Undo Log：{is_deleted: false, modified: [false, true, true], tuple: (1, ‘Alice’, 25)}

创建部分Schema

1
2
3

Schema modified_schema(modified_columns);  // 只包含被修改的列
Tuple tuple(modified_values, &modified_schema);  // 只保存被修改字段的值
return UndoLog{false, modified_fields, std::move(tuple), ts, prev_version};

4.执行流程图

GenerateNewUndoLog()
    ↓
base_tuple == nullptr? → 是 → INSERT: {is_deleted: true}
    ↓ 否
target_tuple == nullptr? → 是 → DELETE: {modified: 全true, tuple: 完整旧值}
    ↓ 否
UPDATE: 逐字段比较
    ↓
记录变化的字段和旧值
    ↓
返回: {modified: 仅变化字段, tuple: 仅旧值}

GenerateUpdatedUndoLog

第一部分：核心逻辑

处理已删除的元组

1
2
3

if (log.is_deleted_) {
    return log;  // 如果元组已被删除，不需要合并，直接返回
}

没有base_tuple的情况

1
2
3

if (base_tuple == nullptr) {
    return GenerateNewUndoLog(schema, &log.tuple_, target_tuple, log.ts_, log.prev_version_);
}

场景：元组之前不存在，这是第一次插入
行为：生成新的Undo日志，记录从”空”到”新元组”的变化
回滚时，将元组删除即可

有base_tuple的情况（完整合并）

Step 1: 重建原始元组

1 2	auto original_tuple = ReconstructTuple(schema, *base_tuple, {0, false}, {log}); BUSTUB_ASSERT(original_tuple.has_value(), "Reconstructed tuple should have a value");

使用当前的base_tuple和Undo log，重建修改前的原始元组
这是通过应用Undo log中的修改字段来实现的

Step 2: 生成当前的变更日志

1	auto cur_log = GenerateNewUndoLog(schema, base_tuple, target_tuple, log.ts_, log.prev_version_);

记录从base_tuple到target_tuple的变更
即当前事务这次修改了哪些字段

Step 3: 合并两个Undo日志

UndoLog combined_log;
combined_log.is_deleted_ = log.is_deleted_;
combined_log.modified_fields_.resize(schema->GetColumnCount(), false);
combined_log.ts_ = log.ts_;
combined_log.prev_version_ = log.prev_version_;

创建合并后的日志
继承旧日志的元数据（时间戳、上一版本等）

Step 4: 合并修改字段

std::vector<Value> values;
for (size_t i = 0; i < schema->GetColumnCount(); i++) {
    if (cur_log.modified_fields_[i] || log.modified_fields_[i]) {
        combined_log.modified_fields_[i] = true;  // 标记该字段被修改
        values.push_back(original_tuple->GetValue(schema, i));  // 保存原始值
    }
}

如果该字段在当前修改或历史修改中被修改过，标记为已修改
保存该字段的原始值（用于回滚）

Step 5: 构造合并后的元组

1 2	auto temp_schema = GetUndoLogSchema(schema, combined_log); combined_log.tuple_ = Tuple(values, &temp_schema);

创建一个只包含修改字段的临时schema
用保存的原始值构造元组

第二部分：可视化示例

假设表有3个字段：(id, name, age)

场景：事务T1连续修改同一个元组

初始状态: (1, "Alice", 25)

操作1: UPDATE SET name = "Bob"
  → 修改字段: [name]
  → Undo Log 1: {modified: [name], tuple: (Alice)}

操作2: UPDATE SET age = 30  
  → 修改字段: [age]
  → Undo Log 2: {modified: [age], tuple: (25)}

合并过程

base_tuple = 当前数据库值 (1, "Bob", 30)
target_tuple = (1, "Bob", 30)  // 已经是最终状态
log = Undo Log 2

Step 1: 重建原始元组
  original_tuple = (1, "Alice", 25)  // 从base_tuple应用Undo Log 2回退

Step 2: 生成cur_log
  cur_log = 从base_tuple到target_tuple的变更
  由于已经是相同值，cur_log.modified_fields = [所有字段为false]

Step 3: 合并
  检查字段:
  - id: 未修改 → 不标记
  - name: log.modified_fields[name]=true → 标记，保存原始值 "Alice"
  - age: log.modified_fields[age]=true → 标记，保存原始值 25

合并后的Undo Log:
  {modified: [name, age], tuple: (1, "Alice", 25)}

update and detelte

delete_executor

执行删除

阶段一：收集待删除元组并检测冲突

std::vector<Tuple> tuples;
while (child_executor_->Next(tuple, rid)) {
    auto tuple_meta = table_info_->table_->GetTupleMeta(*rid);
    if (IsWriteWriteConflict(exec_ctx_->GetTransaction(), tuple_meta.ts_)) {
        exec_ctx_->GetTransaction()->SetTainted();
        throw ExecutionException("w-w conflict with other committed txn");
    }
    tuples.emplace_back(*tuple);
}

关键点：

从子执行器（通常是 SeqScan/IndexScan）逐行读取要删除的元组
对每个元组检查 写-写冲突（Write-Write Conflict）
将所有待删除元组暂存到 tuples 向量中

为什么要暂存？ 为了符合 MVCC 的”先收集后操作”模式，避免在遍历过程中因为删除操作影响扫描结果。

阶段二：逐个执行删除

for (auto &tuple : tuples) {
    // 1. 获取元组的 UndoLink 信息
    auto tuple_link_info = GetTupleAndUndoLink(exec_ctx_->GetTransactionManager(), 
                                                table_info_->table_.get(), 
                                                tuple.GetRid());
    auto tuple_meta = std::get<0>(tuple_link_info);
    
    // 2. 再次检查冲突
    if (IsWriteWriteConflict(exec_ctx_->GetTransaction(), tuple_meta.ts_)) {
        exec_ctx_->GetTransaction()->SetTainted();
        throw ExecutionException("w-w conflict with other committed txn");
    }
    
    // 3. 生成或查找 Undo Link
    auto target_undo_link = GenerateOrFindUndoLink(
        &table_info_->schema_, 
        exec_ctx_->GetTransactionManager(), 
        exec_ctx_->GetTransaction(),
        &tuple,           // base_tuple（旧版本）
        tuple_meta.ts_,   // 当前版本时间戳
        nullptr,          // target_tuple = nullptr 表示删除操作
        std::get<2>(tuple_link_info)  // prev_version
    );
    
    // 4. 更新元数据（标记为已删除）
    tuple_meta.ts_ = exec_ctx_->GetTransaction()->GetTransactionTempTs();
    tuple_meta.is_deleted_ = true;
    
    // 5. 更新元组和 Undo Link
    auto updated = UpdateTupleAndUndoLink(exec_ctx_->GetTransactionManager(), 
                                          tuple.GetRid(), 
                                          target_undo_link,
                                          table_info_->table_.get(), 
                                          exec_ctx_->GetTransaction(), 
                                          tuple_meta, 
                                          tuple, 
                                          check);
    
    // 6. 记录写集（用于提交时验证）
    exec_ctx_->GetTransaction()->AppendWriteSet(table_info_->oid_, tuple.GetRid());
}

流程图

开始
  │
  ├─ 初始化子执行器
  │
  ├─ 循环扫描待删除元组
  │   ├─ 检查写-写冲突
  │   └─ 暂存到 vector
  │
  ├─ 遍历每个待删除元组
  │   ├─ 获取 UndoLink 信息
  │   ├─ 生成 Undo Log（保存完整元组）
  │   ├─ 更新元数据（is_deleted_ = true, ts = temp_ts）
  │   ├─ 乐观锁更新
  │   └─ 记录事务写集
  │
  ├─ 返回删除行数
  │
  └─ 结束

删除示例

事务 T1（txn_id = 200）执行删除：

1	DELETE FROM users WHERE id = 1;

执行流程：

1. 扫描找到 RID=101 的元组
   ├─ tuple_meta.ts_ = 100, is_deleted_ = false
   ├─ 检查写-写冲突（无冲突）
   └─ 暂存到 tuples 列表

2. 生成 Undo Log
   ├─ base_tuple = {id:1, name:"Alice", age:25}
   ├─ target_tuple = nullptr (删除操作)
   └─ UndoLog {is_deleted_: false, modified_fields: [true,true,true], 
               tuple: {id:1, name:"Alice", age:25}, 
               ts: 100, prev_version: null}

3. 更新元组元数据
   ├─ tuple_meta.ts_ = 200 (临时时间戳)
   └─ tuple_meta.is_deleted_ = true

4. 写入写集
   └─ AppendWriteSet(table_oid, RID=101)

update_executor

核心设计思想

更新操作分为两种类型：

更新类型	处理方式	说明
主键不变	原地更新（In-place Update）	直接修改元组数据，生成 Undo Log 保存旧版本
主键变更	删除 + 插入（Delete + Insert）	先逻辑删除旧元组，再插入新元组

阶段一：收集待更新的元组

std::vector<RID> tuple_rids;
std::vector<Tuple> new_tuples;

while (child_executor_->Next(tuple, rid)) {
    // 1. 检查写-写冲突
    auto tuple_meta = table_info_->table_->GetTupleMeta(*rid);
    if (IsWriteWriteConflict(exec_ctx_->GetTransaction(), tuple_meta.ts_)) {
        exec_ctx_->GetTransaction()->SetTainted();
        throw ExecutionException("w-w conflict with other txn");
    }
    
    // 2. 保存旧元组的 RID
    tuple_rids.emplace_back(*rid);
    
    // 3. 计算新元组的值（通过目标表达式）
    std::vector<Value> values;
    for (auto &expr : plan_->target_expressions_) {
        values.emplace_back(expr->Evaluate(tuple, table_info_->schema_));
    }
    new_tuples.emplace_back(Tuple(values, &table_info_->schema_));
}

关键点：

先扫描所有待更新元组，暂存到 vector 中（避免遍历时数据变化影响结果）
对每个元组计算新值（target_expressions_ 对应 SET 子句）
检查写-写冲突

阶段二：判断主键是否变更

bool primary_key_equal = true;
for (auto &index : indexes) {
    if (!index->is_primary_key_) {
        continue;  // 只考虑主键索引
    }
    auto old_key = old_tuple.KeyFromTuple(table_info_->schema_, index->key_schema_, index->index_->GetKeyAttrs());
    auto new_key = new_tuple.KeyFromTuple(table_info_->schema_, index->key_schema_, index->index_->GetKeyAttrs());
    
    // 逐个字段比较
    for (size_t i = 0; i < index->key_schema_.GetColumnCount(); i++) {
        if (!old_key.GetValue(&index->key_schema_, i).CompareExactlyEquals(new_key.GetValue(&index->key_schema_, i))) {
            primary_key_equal = false;
            break;
        }
    }
}

示例：

sql

-- 主键不变（原地更新）
UPDATE users SET age = 26 WHERE id = 1;   -- id=1 不变 ✅

-- 主键变更（删除+插入）
UPDATE users SET id = 10 WHERE id = 1;    -- id 从 1 变为 10 ❌

分支一：主键不变 → 原地更新

if (primary_key_equal) {
    // 生成 Undo Log（保存旧版本数据）
    auto new_undo_link = GenerateOrFindUndoLink(
        &table_info_->schema_, 
        exec_ctx_->GetTransactionManager(), 
        exec_ctx_->GetTransaction(),
        &old_tuple,      // base_tuple = 旧元组
        tuple_meta.ts_,  // 旧版本时间戳
        &new_tuple,      // target_tuple = 新元组（更新操作）
        std::get<2>(tuple_link_info)  // prev_version
    );
    
    // 更新元组数据
    tuple_meta.ts_ = exec_ctx_->GetTransaction()->GetTransactionTempTs();
    auto is_updated = UpdateTupleAndUndoLink(
        exec_ctx_->GetTransactionManager(), 
        old_tuple.GetRid(), 
        new_undo_link,
        table_info_->table_.get(), 
        exec_ctx_->GetTransaction(), 
        tuple_meta, 
        new_tuple,  // 新数据写入
        check
    );
    
    // 记录写集
    exec_ctx_->GetTransaction()->AppendWriteSet(table_info_->oid_, tuple_rids[i]);
    updated[i] = true;
    continue;
}

Undo Log 生成：

// GenerateNewUndoLog 中的更新路径
if (base_tuple != nullptr && target_tuple != nullptr) {
    // 只记录修改的字段
    for (uint32_t i = 0; i < schema->GetColumnCount(); i++) {
        if (base_tuple->GetValue(schema, i).CompareExactlyEquals(target_tuple->GetValue(schema, i))) {
            continue;  // 未修改的字段不记录
        }
        modified_fields[i] = true;
        modified_columns.push_back(schema->GetColumn(i));
        modified_values.push_back(base_tuple->GetValue(schema, i));  // 保存旧值
    }
    return UndoLog{false, modified_fields, modified_tuple, ts, prev_version};
}

示例数据：

操作前	操作后	Undo Log 内容
`{id:1, name:"Alice", age:25}`	`{id:1, name:"Alice", age:26}`	`modified_fields: [F,F,T]`, `{age:25}`

分支二：主键变更 → 删除 + 插入

步骤 1：逻辑删除旧元组

// 生成 Undo Log（删除操作，保存完整旧元组）
auto new_undo_link = GenerateOrFindUndoLink(
    &table_info_->schema_, 
    exec_ctx_->GetTransactionManager(), 
    exec_ctx_->GetTransaction(),
    &old_tuple,      // base_tuple = 旧元组
    tuple_meta.ts_,  
    nullptr,         // target_tuple = nullptr（删除操作）
    std::get<2>(tuple_link_info)
);

// 标记为已删除
tuple_meta.ts_ = exec_ctx_->GetTransaction()->GetTransactionTempTs();
tuple_meta.is_deleted_ = true;
auto is_deleted = UpdateTupleAndUndoLink(..., tuple_meta, old_tuple, check);

步骤 2：检查新主键是否冲突

bool key_exist = false;
std::optional<RID> rid_opt = std::nullopt;

for (auto &index : indexes) {
    if (!index->is_primary_key_) {
        continue;
    }
    auto ret = CheckKeyIfExistInIndex(&table_info_->schema_, &new_tuples[i], index.get(), 
                                       exec_ctx_->GetTransaction(), table_info_);
    if (ret.first) {
        key_exist = true;  // 新主键已被其他事务占用
        break;
    }
    if (ret.second.GetPageId() != INVALID_PAGE_ID) {
        rid_opt = ret.second;  // 找到可复用的 RID（被删除标记的元组）
    }
}

if (key_exist) {
    continue;  // 冲突则跳过，稍后重试
}

CheckKeyIfExistInIndex 的返回值：

ret.first = true：键冲突（已被其他事务使用）
ret.second：可复用的 RID（被删除标记的旧元组位置）

步骤 3：插入新元组

InsertTupleAndIndexKey(&new_tuples[i], 
                       exec_ctx_->GetTransactionManager(), 
                       exec_ctx_->GetTransaction(), 
                       table_info_,
                       rid_opt,  // 如果有可复用的 RID，直接使用
                       exec_ctx_->GetLockManager(), 
                       indexes);

InsertTupleAndIndexKey 的逻辑（你之前看过的）：

如果 rid_opt.has_value() == true：复用被删除标记的位置（更新模式）
如果 rid_opt.has_value() == false：插入到新位置（插入模式）

阶段三：处理第一次失败的插入

// 4. try to insert for previous not updated
for (size_t i = 0; i < tuple_rids.size(); i++) {
    if (!updated[i]) {
        // 重新检查键冲突
        auto ret = CheckKeyIfExistInIndex(...);
        if (ret.first) {
            exec_ctx_->GetTransaction()->SetTainted();
            throw ExecutionException("key conflict");  // 真的冲突了
        }
        if (ret.second.GetPageId() != INVALID_PAGE_ID) {
            rid_opt = ret.second;
        }
        
        // 执行插入
        InsertTupleAndIndexKey(&new_tuples[i], ..., rid_opt, ...);
        updated[i] = true;
    }
}

为什么需要重试？

第一次循环中可能遇到键冲突（key_exist = true），跳过该元组
第二次循环时，其他元组的插入可能已经完成，冲突可能已解决
如果仍然冲突，则抛出异常

完整执行流程图

开始
  │
  ├─ 阶段一：收集待更新元组
  │   ├─ 扫描子执行器
  │   ├─ 检查写-写冲突
  │   └─ 计算新元组值
  │
  ├─ 阶段二：逐个处理
  │   ├─ 判断主键是否变更？
  │   │
  │   ├─ 【主键不变】原地更新
  │   │   ├─ 生成 Undo Log（保存修改的字段）
  │   │   ├─ 更新元组数据
  │   │   └─ 记录写集
  │   │
  │   └─ 【主键变更】删除 + 插入
  │       ├─ 逻辑删除旧元组
  │       │   ├─ 生成 Undo Log（保存完整元组）
  │       │   └─ is_deleted_ = true
  │       ├─ 检查新主键是否冲突
  │       ├─ 如果冲突 → 跳过，稍后重试
  │       └─ 如果不冲突 → 插入新元组
  │
  ├─ 阶段三：重试失败的插入
  │   ├─ 重新检查键冲突
  │   ├─ 如果仍然冲突 → 抛出异常
  │   └─ 否则执行插入
  │
  └─ 返回更新行数

示例数据演示

-- 初始数据
INSERT INTO users VALUES (1, 'Alice', 25);
INSERT INTO users VALUES (2, 'Bob', 30);

-- 场景1：主键不变
UPDATE users SET age = 26 WHERE id = 1;
→ 原地更新，Undo Log 记录 {age: 25}

-- 场景2：主键变更
UPDATE users SET id = 3 WHERE id = 2;
→ 删除 id=2（is_deleted_=true），插入 id=3
→ 删除的 Undo Log 保存完整 {id:2, name:'Bob', age:30}

这种设计完美地平衡了性能（原地更新）和灵活性（主键变更），同时通过 MVCC 保证了读一致性和事务回滚能力。

垃圾回收

整体架构

GarbageCollection()
    ├── 阶段一：收集所有事务的写集（RID 列表）
    ├── 阶段二：标记不可见的页面版本（Page Versions）
    ├── 阶段三：统计不可见的 Undo Log
    └── 阶段四：清理已完成的事务

阶段一：收集所有事务的写集

auto water_mark = running_txns_.GetWatermark();
std::unordered_map<txn_id_t, size_t> invisible_undo_logs_cnt;
std::vector<std::pair<table_oid_t, RID>> tuple_infos;
std::unordered_set<RID> invisible_page_versions;

{
    std::unique_lock<std::shared_mutex> lck(txn_map_mutex_);
    for (auto &it : txn_map_) {
        auto &txn = it.second;
        std::unique_lock<std::mutex> txn_lck(txn->latch_);
        for (auto &w : txn->write_set_) {
            for (auto &rid : w.second) {
                tuple_infos.emplace_back(w.first, rid);
            }
        }
    }
}

关键点：

变量	含义
`water_mark`	水位线：当前所有活跃事务中最小的读时间戳。任何 `ts <= water_mark` 的版本都对所有活跃事务不可见。
`tuple_infos`	所有已提交/中止事务修改过的 RID 列表（从写集中收集）
`txn_map_`	存储所有事务（包括活跃和已完成的）

为什么需要停止世界（Stop-the-World）？

需要获取所有事务的快照（water_mark）
在 GC 期间，不能有新事务开始或旧事务提交，否则水位线会变化
这就是为什么注释说 “Will be called only when all transactions are not accessing the table heap”

阶段二：标记不可见的页面版本

{
    for (auto &info : tuple_infos) {
        auto table = catalog_->GetTable(info.first);
        auto page_read_guard = table->table_->AcquireTablePageReadLock(info.second);
        auto page = page_read_guard.As<TablePage>();
        auto [meta, tuple] = page->GetTuple(info.second);
        
        if (meta.ts_ <= water_mark) {
            invisible_page_versions.insert(info.second);  // 标记为不可见
        }
    }
}

判断逻辑：

1
2
3

如果 meta.ts_ <= water_mark
    → 该元组的最新版本对所有活跃事务都不可见
    → 可以安全回收其旧版本（Undo Log）

示例：

时间戳场景	water_mark	meta.ts_	是否不可见
活跃事务最小 ts=100	100	50	✅ 不可见（旧版本）
活跃事务最小 ts=100	100	150	❌ 仍可见（新版本）
活跃事务最小 ts=100	100	100	✅ 不可见（边界值）

阶段三：统计不可见的 Undo Log

这是最复杂的部分，需要遍历每个 RID 的 Undo Log 链：

{
    std::unique_lock<std::shared_mutex> lck(version_info_mutex_);
    for (auto &it : version_info_) {
        auto &page_version_info = it.second;
        std::unique_lock<std::shared_mutex> page_lck(page_version_info->mutex_);
        
        for (auto &vit : page_version_info->prev_link_) {
            RID rid{it.first, static_cast<uint32_t>(vit.first)};
            auto meet_first = invisible_page_versions.find(rid) != invisible_page_versions.end();
            auto link = vit.second;
            std::optional<UndoLog> log = std::nullopt;
            
            for (; link.IsValid(); link = log.value().prev_version_) {
                log = GetUndoLogOptional(link);
                if (!log.has_value()) {
                    break;
                }
                
                if (meet_first) {
                    // 已经遇到第一个不可见的版本，后续都不可见
                    invisible_undo_logs_cnt[link.prev_txn_]++;
                    continue;
                }
                
                if (log.value().ts_ <= water_mark) {
                    meet_first = true;  // 找到第一个不可见的版本
                    continue;
                }
            }
        }
    }
}

核心算法解析

数据结构：

version_info_[page_id]：每个页面的版本信息
prev_link_[slot_num]：每个槽位的 Undo Log 链表头
Undo Log 通过 prev_version_ 链接成链表（从新到旧）

遍历逻辑：

Undo Log 链表示例（从新到旧）：
  [版本5: ts=200] → [版本4: ts=180] → [版本3: ts=150] → [版本2: ts=120] → [版本1: ts=80]
                                                                              ↑
                                                                         water_mark = 100

遍历过程：
1. 版本5 ts=200 > 100 → 可见，继续
2. 版本4 ts=180 > 100 → 可见，继续
3. 版本3 ts=150 > 100 → 可见，继续
4. 版本2 ts=120 > 100 → 可见，继续
5. 版本1 ts=80 <= 100 → 不可见，标记 meet_first = true

结果：只有版本1被标记为不可见（版本2-5仍可能被某些事务看到）

两种情况：

情况	`meet_first` 初始值	行为
最新版本已被删除	`true`（RID 在 `invisible_page_versions` 中）	所有 Undo Log 都标记为不可见
最新版本仍可见	`false`	只标记 `ts <= water_mark` 的旧版本

阶段四：清理已完成的事务

std::unique_lock<std::shared_mutex> lck(txn_map_mutex_);
for (auto it = txn_map_.begin(); it != txn_map_.end();) {
    auto &txn = it->second;
    std::unique_lock<std::mutex> txn_lck(txn->latch_);
    auto state = txn->state_.load();
    auto is_complete = state == TransactionState::COMMITTED || state == TransactionState::ABORTED;
    
    if (!is_complete) {
        it++;  // 活跃事务，保留
        continue;
    }
    
    // 检查该事务的所有 Undo Log 是否都已被回收
    if (txn->undo_logs_.empty() || invisible_undo_logs_cnt[txn->GetTransactionId()] == txn->undo_logs_.size()) {
        it = txn_map_.erase(it);  // 所有 Undo Log 已回收，删除事务对象
    } else {
        it++;  // 仍有 Undo Log 被其他事务引用，保留
    }
}

清理条件：

条件1：事务已完成（COMMITTED 或 ABORTED）
条件2：该事务的所有 Undo Log 都已不可见
    → txn->undo_logs_.empty()（没有 Undo Log）
    → 或 invisible_undo_logs_cnt[txn_id] == txn->undo_logs_.size()（全部不可见）

满足以上条件 → 从 txn_map_ 中删除事务对象

完整执行示例

场景设置

时间线：
  ts=100: T1 插入 Alice (id=1, name='Alice', age=25)
  ts=200: T2 将 Alice 更新为 Alice2（生成 UndoLog1）(name='Alice2', age=26)
  ts=300: T3 将 Alice2 更新为 Alice3（生成 UndoLog2）(name='Alice3', age=27)
  ts=400: T4 删除 Alice3（生成 UndoLog3）
  
Undo Log 链结构
text
数据页中的最新版本（已删除）
    ts = 400
    is_deleted_ = true
    roll_ptr ↓
         ↓
    UndoLog3 (T4 的删除操作)
    ├── is_deleted_: false
    ├── modified_fields: [T, T, T]
    ├── tuple: {id:1, name:'Alice3', age:27}
    ├── ts_: 300
    └── prev_version_ ↓
              ↓
    UndoLog2 (T3 的更新操作)
    ├── is_deleted_: false
    ├── modified_fields: [F, T, T]
    ├── tuple: {name:'Alice2', age:26}
    ├── ts_: 200
    └── prev_version_ ↓
              ↓
    UndoLog1 (T2 的更新操作)
    ├── is_deleted_: false
    ├── modified_fields: [F, T, T]
    ├── tuple: {name:'Alice', age:25}
    ├── ts_: 100
    └── prev_version_: null

当前活跃事务：T5（ts=250）
water_mark = 250（最小活跃事务时间戳）

数据状态

版本	内容	ts	prev_version
最新（元组）	已删除	400	→ UndoLog3
UndoLog3	Alice3	300	→ UndoLog2
UndoLog2	Alice2	200	→ UndoLog1
UndoLog1	Alice	100	null

GC 执行

// 阶段一：收集 RID
tuple_infos = [RID_Alice]

// 阶段二：检查最新版本
meta.ts_ = 400 > water_mark(250)
→ invisible_page_versions = {} (空，因为最新版本仍可见)

// 阶段三：遍历 Undo Log 链
meet_first = false

遍历 UndoLog3: ts=300 > 250 → 可见，继续
遍历 UndoLog2: ts=200 <= 250 → 不可见，标记 meet_first = true
遍历 UndoLog1: meet_first = true → 标记为不可见

结果：
  invisible_undo_logs_cnt[T2] = 1  (UndoLog1)
  invisible_undo_logs_cnt[T3] = 1  (UndoLog2)
  invisible_undo_logs_cnt[T4] = 0  (UndoLog3 仍可见)

// 阶段四：清理事务
T1: 无 Undo Log → 可清理
T2: 所有 Undo Log (1个) 已不可见 → 可清理
T3: 所有 Undo Log (1个) 已不可见 → 可清理
T4: UndoLog3 仍被 T5 需要 → 保留

清理结果

事务	Undo Log	是否可见	是否清理
T1	无	N/A	✅ 清理
T2	UndoLog1	❌ 不可见	✅ 清理
T3	UndoLog2	❌ 不可见	✅ 清理
T4	UndoLog3	✅ 可见（T5需要）	❌ 保留
T5	无	N/A	❌ 活跃事务

task4: 索引扫描

Init() 方法解析

Init() 负责初始化扫描状态，根据 plan_->filter_predicate_（过滤谓词）决定扫描策略：

无过滤条件（全索引扫描）

if (plan_->filter_predicate_ == nullptr) {
    index_iterator_ = index_->GetBeginIterator();
    return;
}

从索引的起始位置开始遍历所有记录

点查找（Point Lookup） - 两种场景

场景 A：通过析取条件匹配

1	if (FindDisjunctiveIndexConditions(plan_->filter_predicate_, index_info.get(), point_lookups))

将谓词拆解为多个析取子句（OR 连接）
每个子句作为一次独立的等值查询

场景 B：索引前缀完全匹配

1	if (match_result.equality_condition_count_ == index_info->index_->GetKeyAttrs().size())

所有索引列都有等值条件
执行精确查找

范围查找（Range Scan）

1 2	// 匹配索引前缀条件 MatchIndexWithPreds(predicates, index_info.get(), match_result);

提取索引前缀的等值和范围条件
构建起始键（start_partial_tuple_）
使用 GetBeginIterator(start_key) 定位起始位置
处理 > 和 >= 的边界情况（跳过等于起始键的记录）

全表/全索引扫描

如果没有匹配任何优化路径，退化为全索引扫描
所有过滤条件转为 remaining_conds_ 在 Next() 中逐条检查

Next() 方法解析

Next() 负责获取下一条满足条件的记录，返回 (tuple, rid)：

点查找分支

if (is_point_lookup_) {
    for (auto &cur_tuple : point_lookup_partial_tuples_) {
        index_->ScanKey(cur_tuple, &rid_ret, ...);
        // 通过 rid 从表中读取完整数据
    }
}

遍历所有点查找键
使用 ScanKey 获取 RID
MVCC 处理：通过 GetTupleAndUndoLink + CollectUndoLogs + ReconstructTuple 获取当前事务可见的版本

范围/全扫描分支

while (!index_iterator_.IsEnd()) {
    auto [cur_key, cur_rid] = *index_iterator_;
    // MVCC 重建元组
    // 应用 prefix_preds_ 和 remaining_conds_ 过滤
    ++index_iterator_;
}

迭代索引条目（(key, rid)）
对每个 RID 重建可见元组
依次应用前缀条件和剩余条件
前缀条件失败时提前终止（利用索引有序性）

示例数据

假设有一个学生表 student：

CREATE TABLE student (
    id INT PRIMARY KEY,      -- 索引列0
    name VARCHAR(20),        -- 索引列1
    age INT,                 -- 索引列2
    score INT
);

-- 创建复合索引 (id, name, age)
CREATE INDEX idx_student ON student(id, name, age);

表数据：

(1, 'Alice', 20, 90)   RID=100
(2, 'Bob',   22, 85)   RID=101
(3, 'Charlie', 21, 88) RID=102
(4, 'David',  23, 92)  RID=103
(5, 'Eve',    20, 95)  RID=104

索引结构（B+树）：

键值: (1,'Alice',20) -> RID=100
(2,'Bob',22)    -> RID=101
(3,'Charlie',21) -> RID=102
(4,'David',23)   -> RID=103
(5,'Eve',20)    -> RID=104

示例1：无过滤条件（全索引扫描）

SQL

1	SELECT * FROM student;

执行流程

Init() 阶段：

1 2	// plan_->filter_predicate_ == nullptr index_iterator_ = index_->GetBeginIterator(); // 指向 (1,'Alice',20)

Next() 阶段：

// 第1次调用 Next()
auto [cur_key, cur_rid] = *index_iterator_;  // cur_rid=100
// 读取 RID=100 的完整元组
// 没有过滤条件，直接返回
return (1,'Alice',20,90), RID=100
index_iterator_++  // 指向 (2,'Bob',22)

// 第2次调用 Next()
返回 (2,'Bob',22,85), RID=101
// ...
// 第5次调用 Next()
返回 (5,'Eve',20,95), RID=104
index_iterator_++  // 指向 End()

// 第6次调用 Next()
index_iterator_.IsEnd() == true
return false

输出顺序：按索引键排序，即 (1,2,3,4,5)

示例2：点查找（完整索引匹配）

SQL

1	SELECT * FROM student WHERE id = 3 AND name = 'Charlie' AND age = 21;

Init() 阶段

步骤1：分解谓词

1
2
3

// plan_->filter_predicate_ = (id=3) AND (name='Charlie') AND (age=21)
DecomposeConjunction(plan_->filter_predicate_, predicates);
// predicates = [id=3, name='Charlie', age=21]

步骤2：匹配索引

MatchIndexWithPreds(predicates, index_info.get(), match_result);
// match_result:
//   equality_condition_count_ = 3  (三个都是等值)
//   index_conditions_ = [
//       {column: id, constant_value: 3, type: EQ},
//       {column: name, constant_value: 'Charlie', type: EQ},
//       {column: age, constant_value: 21, type: EQ}
//   ]
//   remaining_conditions_ = []  (无剩余条件)

步骤3：构建查找键

if (match_result.equality_condition_count_ == index_info->index_->GetKeyAttrs().size()) {
    // 3 == 3, 是点查找
    is_point_lookup_ = true;
    for (auto &cond : match_result.index_conditions_) {
        // 构建查询元组 (3, 'Charlie', 21)
        BuildTupleFromIndexPrefixExprs(&tuple, {cond.constant_value_}, index_info);
        point_lookup_partial_tuples_.emplace_back(tuple);
    }
}

结合后面的分析,这里的代码是错的。

Next() 阶段

// 第1次调用 Next()
auto &cur_tuple = point_lookup_partial_tuples_[0];  // (3, 'Charlie', 21)
index_->ScanKey(cur_tuple, &rid_ret, ...);
// B+树查找，返回 rid_ret=[102]

// 通过 RID=102 从表中读取完整元组
auto rebuild_tuple = ReconstructTuple(...);  // (3, 'Charlie', 21, 88)
select_func(rebuild_tuple, remaining_conds_)  // true (无剩余条件)
*tuple = (3, 'Charlie', 21, 88)
*rid = 102
return true

// 第2次调用 Next()
point_lookup_idx_ = 1 >= point_lookup_partial_tuples_.size()  // 1 >= 1
return false

示例3：点查找（析取条件 OR）

SQL

1	SELECT * FROM student WHERE (id = 1 AND name = 'Alice') OR (id = 5 AND name = 'Eve');

Init() 阶段

FindDisjunctiveIndexConditions(plan_->filter_predicate_, index_info.get(), point_lookups);
// 找到两个析取条件：
// point_lookups = [
//     [id=1, name='Alice'],
//     [id=5, name='Eve']
// ]

is_point_lookup_ = true;
// 构建两个查询键：
point_lookup_partial_tuples_ = [
    (1, 'Alice'),  // 缺少 age，填充最小值
    (5, 'Eve')
];

Next() 阶段

// 第1次 Next()
cur_tuple = (1, 'Alice')
index_->ScanKey(cur_tuple, &rid_ret, ...);  // rid_ret=[100]
// 返回 Alice 的记录

// 第2次 Next()
cur_tuple = (5, 'Eve')
index_->ScanKey(cur_tuple, &rid_ret, ...);  // rid_ret=[104]
// 返回 Eve 的记录

// 第3次 Next()
返回 false

关键点：即使没有 age 条件，仍能利用索引前缀进行查找

示例4：范围查找

SQL

1	SELECT * FROM student WHERE id >= 2 AND id < 4;

Init() 阶段

步骤1：匹配索引

MatchIndexWithPreds(predicates, index_info.get(), match_result);
// match_result:
//   equality_condition_count_ = 0
//   index_conditions_ = [
//       {column: id, constant_value: 2, type: GreaterThanOrEqual},
//       {column: id, constant_value: 4, type: LessThan}
//   ]
//   remaining_conditions_ = []  (无条件)

步骤2：构建范围

// start_key_exprs = [2]
BuildTupleFromIndexPrefixExprs(&start_partial_tuple_, start_key_exprs, index_info);
// start_partial_tuple_ = (2, 最小值, 最小值)

IntegerKeyType_BTree start_key;
start_key.SetFromKey(start_partial_tuple_);  // 构建 B+树查找键
index_iterator_ = index_->GetBeginIterator(start_key);  // 指向第一个 >= (2,min,min) 的键

Next() 阶段

// 第1次 Next()
auto [cur_key, cur_rid] = *index_iterator_;  // (2,'Bob',22), RID=101
// 读取并返回 Bob 的记录
index_iterator_++  // 指向 (3,'Charlie',21)

// 第2次 Next()
auto [cur_key, cur_rid] = *index_iterator_;  // (3,'Charlie',21), RID=102
// 返回 Charlie 的记录
index_iterator_++  // 指向 (4,'David',23)

// 第3次 Next()
// 检查条件 id < 4
select_func(rebuild_tuple, prefix_preds_)
// 前缀条件：id >= 2 AND id < 4
// (4,'David',23) 不满足 id < 4
index_iterator_ = index_->GetEndIterator();  // 提前终止
return false

性能优势：不需要扫描 id=4 和 id=5 的记录

示例5：前缀匹配 + 剩余条件

SQL

1	SELECT * FROM student WHERE id = 2 AND score > 80;

Init() 阶段

MatchIndexWithPreds(predicates, index_info.get(), match_result);
// match_result:
//   equality_condition_count_ = 1
//   index_conditions_ = [{column: id, constant_value: 2, type: EQ}]
//   remaining_conditions_ = [score > 80]  // score不是索引列，剩余处理

// 不是完整索引匹配（只有1个等值，索引有3列）
// is_point_lookup_ = false
// prefix_preds_ = [id=2]
// 构建 start_partial_tuple_ = (2, min, min)
// index_iterator_ = 指向第一个 >= (2,min,min) 的键

Next() 阶段

// 第1次 Next()
auto [cur_key, cur_rid] = *index_iterator_;  // (2,'Bob',22), RID=101
// 1. 应用 prefix_preds_：id=2 ✓
// 2. 读取完整元组：Bob的记录
// 3. 应用 remaining_conds_：score > 80 ✓ (85>80)
返回 Bob

// 第2次 Next()
auto [cur_key, cur_rid] = *index_iterator_;  // (3,'Charlie',21), RID=102
// 1. 应用 prefix_preds_：id=3 != 2 ✗
// 触发提前终止
index_iterator_ = index_->GetEndIterator();
return false

关键点：即使 id=2 后面还有记录（如 (2,'Charlie',20)），但我们的前缀条件是 id=2，如果遇到 id=3，说明 id=2 的所有记录都已遍历完，可以提前终止。

示例6：MVCC 可见性处理

场景

事务 T1 将 id=3 的 score 从 88 改为 90（未提交）

SQL

1	SELECT * FROM student WHERE id = 3;

Next() 执行过程

// 1. 索引查找得到 RID=102
index_->ScanKey((3,min,min), &rid_ret, ...);  // rid_ret=[102]

// 2. 获取当前版本
auto [tuple_meta, tuple_, undo_link] = GetTupleAndUndoLink(..., RID=102);
// tuple_meta.is_deleted_ = false
// tuple_ = (3, 'Charlie', 21, 90)  // T1 修改后的值
// undo_link 指向 T1 的 undo 日志

// 3. 收集 undo 日志
auto undo_logs = CollectUndoLogs(RID=102, tuple_meta, tuple_, undo_link, T2);
// T2 当前事务需要应用 T1 的 undo 日志才能看到旧版本
// undo_logs = [T1的undo: (score: 88)]

// 4. 重建元组
auto rebuild_tuple = ReconstructTuple(&GetOutputSchema(), tuple_, tuple_meta, undo_logs);
// rebuild_tuple = (3, 'Charlie', 21, 88)  // 回退到 T1 修改前的值

// 5. 返回 T2 可见的版本
*tuple = (3, 'Charlie', 21, 88);
return true;

没有剩余条件的点查找（即索引点查）-Init()函数

核心函数 FindDisjunctiveIndexConditions

这个函数的作用是从过滤谓词中提取可以用于点查找的析取条件。

处理逻辑：

场景 A：简单点查找

-- SQL
SELECT * FROM student WHERE id = 3 AND name = 'Charlie' AND age = 21;

-- 过滤谓词结构
plan_->filter_predicate_ = (id=3) AND (name='Charlie') AND (age=21)

-- FindDisjunctiveIndexConditions 处理：
-- 1. 识别这是一个 AND 连接
-- 2. 检查每个子条件是否都在索引列上
-- 3. 返回 point_lookups = [[id=3, name='Charlie', age=21]]
-- 4. 返回 true

场景 B：OR 条件（析取）

-- SQL
SELECT * FROM student 
WHERE (id = 1 AND name = 'Alice') 
   OR (id = 5 AND name = 'Eve');

-- 过滤谓词结构（简化为抽象语法树）
plan_->filter_predicate_ = OR(
    AND(id=1, name='Alice'),
    AND(id=5, name='Eve')
)

-- FindDisjunctiveIndexConditions 处理：
-- 1. 识别顶层是 OR
-- 2. 对每个 OR 分支递归处理
-- 3. 返回 point_lookups = [
--       [id=1, name='Alice'],  // 分支1
--       [id=5, name='Eve']     // 分支2
--    ]
-- 4. 返回 true

场景 C：部分索引前缀

-- SQL
SELECT * FROM student WHERE id = 3;  -- 只有第一个索引列

-- 返回 point_lookups = [[id=3]]  // 虽然不完整，但可以用索引前缀

场景 D：无法使用索引

-- SQL
SELECT * FROM student WHERE score > 80;  -- score 不是索引列

-- FindDisjunctiveIndexConditions 处理：
-- 1. 检查 score > 80 无法匹配任何索引列
-- 2. 返回 false

1	is_point_lookup_ = true;

设置执行模式

标记当前为点查找模式
在 Next() 方法中会走点查找分支

1	point_lookup_partial_tuples_.reserve(point_lookups.size());

预分配内存

reserve() 预先分配容量，避免动态扩容
优化性能，减少内存分配次数

for (auto &constant_exprs : point_lookups) {
    Tuple tuple;
    BuildTupleFromIndexPrefixExprs(&tuple, constant_exprs, index_info);
    point_lookup_partial_tuples_.emplace_back(tuple);
}

构建查找键

BuildTupleFromIndexPrefixExprs 函数解析：

void BuildTupleFromIndexPrefixExprs(Tuple *tuple, 
                                    const std::vector<AbstractExpressionRef> &exprs,
                                    const std::shared_ptr<IndexInfo> &index_info) {
    std::vector<Value> values;
    for (size_t i = 0; i < index_info->key_schema_.GetColumns().size(); i++) {
        if (i < exprs.size()) {
            // 有对应的常量值，直接使用
            values.push_back(exprs[i]->Evaluate(nullptr, index_info->key_schema_));
            continue;
        }
        // 缺少的列填充最小值
        values.push_back(Type::GetMinValue(index_info->key_schema_.GetColumn(i).GetType()));
    }
    *tuple = Tuple{values, &index_info->key_schema_};
}

示例：

// 索引有3列：(id, name, age)
// constant_exprs = [id=3, name='Charlie']  // 只提供了前2列

// BuildTupleFromIndexPrefixExprs 构建：
// 第0列(id)：使用 constant_exprs[0] = 3
// 第1列(name)：使用 constant_exprs[1] = 'Charlie'
// 第2列(age)：没有提供，填充最小值

// 最终 tuple = (3, 'Charlie', MIN_VALUE)

完整的执行流程示例

示例1：单值点查找

1	SELECT * FROM student WHERE id = 3;

代码执行：*

// 1. FindDisjunctiveIndexConditions 解析
point_lookups = [[id=3]]  // 返回 true

// 2. 设置模式
is_point_lookup_ = true

// 3. 构建查找键
tuple = (3, MIN_VALUE, MIN_VALUE)  // 索引有3列，只提供了1个值
point_lookup_partial_tuples_ = [(3, MIN_VALUE, MIN_VALUE)]

// 4. 在 Next() 中
index_->ScanKey((3, MIN_VALUE, MIN_VALUE), &rid_ret, ...)
// B+树会找到所有键以 (3, *, *) 开头的记录

示例2：OR 条件

1	SELECT * FROM student WHERE id = 3 OR id = 5;

代码执行：

// 1. FindDisjunctiveIndexConditions 解析
point_lookups = [[id=3], [id=5]]  // 返回 true

// 2. 设置模式
is_point_lookup_ = true

// 3. 构建两个查找键
point_lookup_partial_tuples_ = [
    (3, MIN_VALUE, MIN_VALUE),
    (5, MIN_VALUE, MIN_VALUE)
]

// 4. 在 Next() 中
// 第1次调用：查找 id=3
// 第2次调用：查找 id=5
// 第3次调用：返回 false

示例3：多列 OR

1
2
3

SELECT * FROM student 
WHERE (id = 1 AND name = 'Alice') 
   OR (id = 2 AND name = 'Bob');

代码执行：

// 1. FindDisjunctiveIndexConditions 解析
point_lookups = [
    [id=1, name='Alice'],
    [id=2, name='Bob']
]  // 返回 true

// 2. 构建两个查找键
point_lookup_partial_tuples_ = [
    (1, 'Alice', MIN_VALUE),  // 索引有3列，填充第3列
    (2, 'Bob', MIN_VALUE)
]

// 3. 在 Next() 中顺序执行两个点查找

示例4：复杂条件（函数返回 false）

1
2
3

SELECT * FROM student 
WHERE (id = 1 AND name = 'Alice') 
   OR score > 80;  -- score 不是索引列

代码执行：

// FindDisjunctiveIndexConditions 解析：
// 1. 顶层是 OR
// 2. 检查第一个分支：id=1 AND name='Alice' ✓ 可以用索引
// 3. 检查第二个分支：score > 80 ✗ 不能用索引
// 4. 因为有一个分支不能用索引，返回 false

// 结果：不走点查找优化，退化为全索引扫描 + 过滤

带剩余条件的点查找-Init()函数

分解合取条件

1
2
3

// 3. point lookup with remaining conditions / range lookup with specific prefix
std::vector<AbstractExpressionRef> predicates;
DecomposeConjunction(plan_->filter_predicate_, predicates);

DecomposeConjunction 函数： 将 AND 连接的条件拆分成独立的谓词列表。

示例：

-- SQL
SELECT * FROM student 
WHERE id = 3 
  AND name = 'Charlie' 
  AND age > 20 
  AND score > 80;

-- 分解后
predicates = [
    id = 3,
    name = 'Charlie',
    age > 20,
    score > 80
]

匹配索引条件

1 2	IndexMatchResult match_result; MatchIndexWithPreds(predicates, index_info.get(), match_result);

MatchIndexWithPreds 函数： 分析哪些谓词可以用索引处理。

数据结构：

struct IndexMatchResult {
    bool is_valid_;                          // 是否能利用索引
    int equality_condition_count_;          // 等值条件的数量
    std::vector<IndexCondition> index_conditions_;   // 可用索引的条件
    std::vector<AbstractExpressionRef> remaining_conditions_; // 剩余条件
};

struct IndexCondition {
    AbstractExpressionRef column_;          // 列表达式
    AbstractExpressionRef constant_value_;  // 常量值
    ComparisonType type_;                   // EQ, GT, GE, LT, LE
};

处理逻辑示例：

-- 索引列: (id, name, age)
-- predicates = [id=3, name='Charlie', age>20, score>80]

MatchIndexWithPreds 处理：
├── id=3          → index_conditions_[0] = {id, 3, EQ}, equality_count=1
├── name='Charlie'→ index_conditions_[1] = {name, 'Charlie', EQ}, equality_count=2
├── age>20        → index_conditions_[2] = {age, 20, GT}, equality_count=2 (保持)
└── score>80      → remaining_conditions_[0] = score>80 (非索引列)

关键规则：

等值条件：必须按索引列顺序出现
范围条件：只能有一个（且必须在最后一个等值条件之后）
不等值/非索引列：全部放入 `remaining_conditions_

保存剩余条件

if (match_result.is_valid_) {
    for (auto &cond : match_result.remaining_conditions_) {
        remaining_conds_.push_back(cond);
    }
}

将非索引列的条件保存下来，在 Next() 中回表后过滤。

判断是否为点查找

1 2	// 3.1 point lookup if (match_result.equality_condition_count_ == index_info->index_->GetKeyAttrs().size()) {

条件： 等值条件的数量 == 索引列的总数

含义： 索引的每一列都有一个等值匹配，可以精确定位到唯一/少数记录。

示例对比：

-- 索引: (id, name, age)

-- ✅ 点查找
WHERE id = 3 AND name = 'Charlie' AND age = 21
-- equality_count = 3, 索引列数 = 3 → 是点查找

-- ❌ 不是点查找（范围查找）
WHERE id = 3 AND name = 'Charlie' AND age > 21
-- equality_count = 2, 索引列数 = 3 → 范围查找

-- ❌ 不是点查找（缺少列）
WHERE id = 3 AND name = 'Charlie'
-- equality_count = 2, 索引列数 = 3 → 前缀查找

构建点查找键

is_point_lookup_ = true;
point_lookup_partial_tuples_.reserve(match_result.index_conditions_.size());
for (auto &cond : match_result.index_conditions_) {
    Tuple tuple;
    BuildTupleFromIndexPrefixExprs(&tuple, {cond.constant_value_}, index_info);
    point_lookup_partial_tuples_.emplace_back(tuple);
}
return;

注意： 这里有个看似奇怪的地方：

1	BuildTupleFromIndexPrefixExprs(&tuple, {cond.constant_value_}, index_info);

为什么只传 {cond.constant_value_} 而不是所有 index_conditions_？

原因分析：

match_result.index_conditions_ 中存储的是所有索引条件，但 BuildTupleFromIndexPrefixExprs 期望的是按顺序的常量表达式列表。

问题出在哪里？

// 假设 match_result.index_conditions_ = [
//     {column: id, constant: 3, type: EQ},
//     {column: name, constant: 'Charlie', type: EQ},
//     {column: age, constant: 21, type: EQ}
// ]

// 但循环中只取了 cond.constant_value_
// 第1次循环: cond = {id, 3} → tuple = (3, MIN, MIN)
// 第2次循环: cond = {name, 'Charlie'} → tuple = ('Charlie', MIN, MIN)
// 第3次循环: cond = {age, 21} → tuple = (21, MIN, MIN)

这是代码的 BUG 还是设计？

实际上，这是一个索引扫描的范围查找优化：

深入理解：这不是真正的点查找！

// 正确的点查找应该用 ScanKey 精确匹配所有列
// 但这里用的是 GetBeginIterator + 前缀过滤

// 实际上这段代码执行的是：
// 1. 对每个索引条件，构建一个"前缀键"
// 2. 用这个前缀键作为范围扫描的起点
// 3. 在 Next() 中通过 prefix_preds_ 过滤

// 例如：WHERE id=3 AND name='Charlie' AND age=21
// 会构建三个范围扫描：
//   - 扫描 id=3 的所有记录
//   - 扫描 name='Charlie' 的所有记录  
//   - 扫描 age=21 的所有记录
// 然后通过 prefix_preds_ 精确过滤

完整执行流程示例

示例1：点查找（所有列等值）

SELECT * FROM student 
WHERE id = 3 
  AND name = 'Charlie' 
  AND age = 21 
  AND score > 80;  -- score 是非索引列（剩余条件）

执行过程：

// 1. 分解条件
predicates = [id=3, name='Charlie', age=21, score>80]

// 2. 匹配索引
match_result = {
    is_valid_: true,
    equality_condition_count_: 3,  // 三个等值
    index_conditions_: [
        {id, 3, EQ},
        {name, 'Charlie', EQ},
        {age, 21, EQ}
    ],
    remaining_conditions_: [score>80]
}

// 3. 保存剩余条件
remaining_conds_ = [score>80]

// 4. 点查找分支
is_point_lookup_ = true
point_lookup_partial_tuples_ = [
    (3, MIN, MIN),      // 基于 id=3
    ('Charlie', MIN, MIN), // 基于 name='Charlie'（实际会替换上一轮）
    (21, MIN, MIN)      // 基于 age=21（实际会替换上一轮）
]

// 问题：最后只保留 (21, MIN, MIN)
// 这会导致范围扫描从 age=21 开始，而不是精确匹配所有列

实际执行（Next()）：

// 点查找循环
cur_tuple = (21, MIN, MIN)  // 最后一个条件
index_->ScanKey((21, MIN, MIN), &rid_ret, ...)
// 扫描所有 age=21 的记录（可能有多条）

// 对每条记录应用 remaining_conds_
// 检查 score>80

// 但忽略了 id=3 和 name='Charlie' 的条件！

这里存在严重的逻辑错误！ 🐛

// 正确的点查找键构建
if (match_result.equality_condition_count_ == index_info->index_->GetKeyAttrs().size()) {
    is_point_lookup_ = true;
    std::vector<AbstractExpressionRef> constants;
    for (auto &cond : match_result.index_conditions_) {
        constants.push_back(cond.constant_value_);
    }
    Tuple tuple;
    BuildTupleFromIndexPrefixExprs(&tuple, constants, index_info);
    point_lookup_partial_tuples_.push_back(tuple);
    return;
}

范围查找-Init()函数

代码整体结构

这段代码处理的是：利用索引前缀进行范围查找，例如 WHERE id = 3 AND name = 'Charlie' AND age > 20。

逐行详细解析

变量声明

1
2
3

// 3.2 range lookup with specific prefix
std::vector<AbstractExpressionRef> start_key_exprs;
ComparisonType last_comparison_type;

start_key_exprs：存储构建起始键的常量表达式列表
last_comparison_type：记录最后一个比较操作的类型（用于边界处理）

构建前缀条件和起始键

for (auto &cond : match_result.index_conditions_) {
    last_comparison_type = cond.type_;
    prefix_preds_.push_back(std::make_shared<ComparisonExpression>(cond.column_, cond.constant_value_, cond.type_));
    start_key_exprs.push_back(cond.constant_value_);
}

循环处理每个索引条件：

步骤	操作	说明
1	更新 `last_comparison_type`	记录最后一个条件类型
2	加入 `prefix_preds_`	保存为过滤条件（在 `Next()` 中检查）
3	加入 `start_key_exprs`	构建起始键的常量值

示例：

// 索引条件: [id=3(EQ), name='Charlie'(EQ), age>20(GT)]

// 循环处理：
// 第1次: cond={id, 3, EQ}
//   last_comparison_type = EQ
//   prefix_preds_ = [id=3]
//   start_key_exprs = [3]

// 第2次: cond={name, 'Charlie', EQ}
//   last_comparison_type = EQ
//   prefix_preds_ = [id=3, name='Charlie']
//   start_key_exprs = [3, 'Charlie']

// 第3次: cond={age, 20, GT}
//   last_comparison_type = GT  ← 最后是 GT
//   prefix_preds_ = [id=3, name='Charlie', age>20]
//   start_key_exprs = [3, 'Charlie', 20]

构建起始元组

1	BuildTupleFromIndexPrefixExprs(&start_partial_tuple_, start_key_exprs, index_info);

BuildTupleFromIndexPrefixExprs 的作用：

// 索引列: (id, name, age)
// start_key_exprs = [3, 'Charlie', 20]

// 构建结果:
// start_partial_tuple_ = (3, 'Charlie', 20)
// 所有列都有值，因为提供了3个常量

如果有缺失列：

// 索引列: (id, name, age)
// start_key_exprs = [3, 'Charlie']  // 只有2个条件

// 构建结果:
// start_partial_tuple_ = (3, 'Charlie', MIN_VALUE)  // 第3列填充最小值

定位到起始位置

1
2
3

IntegerKeyType_BTree start_key;
start_key.SetFromKey(start_partial_tuple_);
index_iterator_ = index_->GetBeginIterator(start_key);

GetBeginIterator(start_key) 的作用：

返回第一个 >= start_key 的索引条目
对于 B+树，这是范围扫描的起点

示例：

// start_key = (3, 'Charlie', 20)
// B+树数据:
// (1, 'Alice', 20)   ← 跳过
// (2, 'Bob', 22)     ← 跳过
// (3, 'Alice', 21)   ← 跳过 (虽然id=3，但name='Alice' < 'Charlie')
// (3, 'Charlie', 20) ← 起点 ✓ (正好等于)
// (3, 'Charlie', 21) ← 包含
// (3, 'Charlie', 22) ← 包含
// (3, 'David', 20)   ← 包含 (id=3, name='David' > 'Charlie')
// (4, 'Eve', 20)     ← 停止 (id > 3)

index_iterator_ 指向 (3, 'Charlie', 20)

边界处理：跳过起始键（重要！）

// skip the included start key if the last comparison is greater than
if (!index_iterator_.IsEnd() && last_comparison_type == ComparisonType::GreaterThan) {
    auto [cur_key, _] = *index_iterator_;
    std::vector<uint32_t> attrs;
    for (size_t i = 0; i < start_key_exprs.size(); i++) {
        attrs.push_back(index_->GetKeyAttrs()[i]);
    }
    auto key_schema = Schema::CopySchema(&table_schema, attrs);
    IntegerComparatorType_BTree comparator(&key_schema);
    if (comparator(start_key, cur_key) == 0) {
        ++index_iterator_;
    }
}

问题： 当最后一个条件是 >（大于）而不是 >=（大于等于）时，需要跳过等于起始键的记录。

为什么需要这个处理？

-- SQL
SELECT * FROM student WHERE id = 3 AND age > 20;

-- 索引查找
start_key = (3, 20)  -- 使用 >= 定位
GetBeginIterator(start_key) 返回第一个 >= (3,20) 的记录

-- 但 age > 20 要求排除 age = 20 的记录
-- 所以需要检查并跳过等于 start_key 的记录

详细处理流程：

步骤1：检查条件

1	if (!index_iterator_.IsEnd() && last_comparison_type == ComparisonType::GreaterThan)

迭代器有效（不是结束）
最后一个比较是 >（而不是 >=）

步骤2：获取当前键

1 2	auto [cur_key, _] = *index_iterator_; // cur_key = (3, 'Charlie', 20) // 当前指向的键

步骤3：构建比较模式

std::vector<uint32_t> attrs;
for (size_t i = 0; i < start_key_exprs.size(); i++) {
    attrs.push_back(index_->GetKeyAttrs()[i]);
}
auto key_schema = Schema::CopySchema(&table_schema, attrs);

// 示例：
// start_key_exprs.size() = 3
// attrs = [0, 1, 2]  // 索引的前3列
// key_schema 只包含这3列，用于比较

步骤4：比较键值

IntegerComparatorType_BTree comparator(&key_schema);
if (comparator(start_key, cur_key) == 0) {  // 如果相等
    ++index_iterator_;  // 跳过当前记录
}

完整的执行示例

示例1：> 条件（需要跳过）

SELECT * FROM student 
WHERE id = 3 
  AND name = 'Charlie' 
  AND age > 20;

数据：

索引键值:
(3, 'Charlie', 20) → RID=100  ← 不符合 age>20
(3, 'Charlie', 21) → RID=101  ← 符合
(3, 'Charlie', 22) → RID=102  ← 符合

执行过程：

// 1. 构建起始键
start_key = (3, 'Charlie', 20)
last_comparison_type = GT

// 2. 定位
index_iterator_ = GetBeginIterator((3, 'Charlie', 20))
// 指向 (3, 'Charlie', 20)

// 3. 跳过处理
// last_comparison_type == GT
// cur_key = (3, 'Charlie', 20)
// comparator(start_key, cur_key) == 0  → 相等
// ++index_iterator_  // 跳过 (3, 'Charlie', 20)

// 4. 现在指向 (3, 'Charlie', 21)
// Next() 返回符合 age>20 的记录

示例2：>= 条件（不需要跳过）

SELECT * FROM student 
WHERE id = 3 
  AND name = 'Charlie' 
  AND age >= 20;

执行过程：

// 1. 构建起始键
start_key = (3, 'Charlie', 20)
last_comparison_type = GE  // 大于等于

// 2. 定位
index_iterator_ = GetBeginIterator((3, 'Charlie', 20))
// 指向 (3, 'Charlie', 20)

// 3. 跳过处理
// last_comparison_type == GE，不是 GT
// 不跳过，包含 (3, 'Charlie', 20) ✅

// Next() 返回所有 >= (3,'Charlie',20) 的记录

示例3：前缀不足（缺失列）

1
2
3

SELECT * FROM student 
WHERE id = 3 
  AND name > 'Charlie';

执行过程：

// 1. 匹配索引
index_conditions = [
    {id, 3, EQ},
    {name, 'Charlie', GT}
]
// start_key_exprs = [3, 'Charlie']
// last_comparison_type = GT

// 2. 构建起始键
// 索引有3列：(id, name, age)
// 但只提供了2个条件
start_partial_tuple_ = (3, 'Charlie', MIN_VALUE)
start_key = (3, 'Charlie', -∞)

// 3. 定位
index_iterator_ = GetBeginIterator((3, 'Charlie', -∞))
// 指向第一个 id=3 且 name>='Charlie' 的记录

// 4. 跳过处理
// last_comparison_type == GT
// 检查当前键是否等于 (3, 'Charlie', -∞)
// 由于有 MIN_VALUE，不可能有记录正好等于
// 所以不跳过

// Next() 扫描所有 id=3 且 name>'Charlie' 的记录
// 包括 (3, 'David', 20), (3, 'Eve', 21) 等

示例4：复杂条件组合

SELECT * FROM student 
WHERE id >= 3 
  AND id < 5 
  AND age > 20;

执行过程：

// 1. 匹配索引
index_conditions = [
    {id, 3, GE},  // >=
    {id, 5, LT}   // <
]
// start_key_exprs = [3]
// last_comparison_type = GE

// 2. 构建起始键
start_partial_tuple_ = (3, MIN_VALUE, MIN_VALUE)

// 3. 定位
index_iterator_ = GetBeginIterator((3, MIN, MIN))
// 指向第一个 id>=3 的记录

// 4. 跳过处理
// last_comparison_type == GE，不跳过

// 5. Next() 中
// prefix_preds_ = [id>=3, id<5]
// 扫描并过滤，遇到 id>=5 时提前终止

点查找 - Next函数

代码整体结构

这段代码处理两种扫描模式：

点查找模式 (is_point_lookup_ == true)
范围扫描模式（后续代码，这里暂不解析）
快速失败检查

1
2
3

if (IsPredicateFalse(plan_->filter_predicate_)) {
    return false;
}

IsPredicateFalse 函数： 检查谓词是否恒为 FALSE。

// 示例：
// WHERE 1 = 0  → 恒为 FALSE
// WHERE NULL   → 恒为 FALSE
// WHERE id = id → 恒为 TRUE（不返回 false）

if (IsPredicateFalse(...)) {
    return false;  // 直接返回，不需要扫描
}

优化目的： 避免执行无意义查询。

过滤函数定义

auto select_func = [this](const Tuple &cur_tuple, const std::vector<AbstractExpressionRef> &preds) {
    for (auto &pred : preds) {
        auto value = pred->Evaluate(&cur_tuple, plan_->OutputSchema());
        if (value.IsNull() || !value.GetAs<bool>()) {
            return false;
        }
    }
    return true;
};

select_func Lambda： 检查元组是否满足所有谓词条件。

执行逻辑：

for (auto &pred : preds) {
    // 1. 计算谓词结果
    auto value = pred->Evaluate(&cur_tuple, plan_->OutputSchema());
    
    // 2. 检查是否为 NULL 或 FALSE
    if (value.IsNull() || !value.GetAs<bool>()) {
        return false;  // 不满足条件
    }
}
return true;  // 所有条件都满足

示例：

// remaining_conds_ = [score > 80]
// cur_tuple = (3, 'Charlie', 21, 88)

// 计算 score > 80 → TRUE
// value.IsNull() = false
// value.GetAs<bool>() = true
// 返回 true ✓

// cur_tuple = (3, 'Charlie', 21, 75)
// 计算 score > 80 → FALSE
// 返回 false ✗

注意： 这里使用 plan_->OutputSchema() 作为求值上下文，而不是表 schema。这意味着输出列可能被重命名或投影。

点查找主循环

1
2
3

// 1. point lookup
if (is_point_lookup_) {
    while (true) {

无限循环，直到找到一条满足条件的记录或遍历完所有查找键。

检查是否还有查找键

1
2
3

if (point_lookup_idx_ >= point_lookup_partial_tuples_.size()) {
    return false;
}

point_lookup_idx_： 当前处理的查找键索引
point_lookup_partial_tuples_： 所有查找键列表

// 示例：
// point_lookup_partial_tuples_ = [(3,'Charlie',21), (5,'Eve',20)]
// point_lookup_idx_ = 0

// 第1次 Next(): idx=0 < 2，继续
// 第2次 Next(): idx=1 < 2，继续
// 第3次 Next(): idx=2 >= 2，返回 false

执行索引查找

1
2
3

auto &cur_tuple = point_lookup_partial_tuples_[point_lookup_idx_++];
std::vector<RID> rid_ret;
index_->ScanKey(cur_tuple, &rid_ret, exec_ctx_->GetTransaction());

ScanKey 函数： 在 B+树中查找匹配的键，返回所有对应的 RID。

// 示例：
// cur_tuple = (3, 'Charlie', 21)
// index_->ScanKey(...) 在 B+树中查找
// 如果存在，rid_ret = [RID=102]
// 如果不存在，rid_ret = []

为什么用 std::vector？

虽然点查找通常返回唯一记录，但索引可能不唯一
也可能存在重复键（B+树支持重复键）

获取元组和 Undo 链接

1
2
3

if (!rid_ret.empty()) {
    auto [tuple_meta_, tuple_, undo_link] =
        GetTupleAndUndoLink(exec_ctx_->GetTransactionManager(), table_info_->table_.get(), rid_ret[0]);

GetTupleAndUndoLink 函数： 从表中读取指定 RID 的元组及其版本链信息。

返回三元组：

tuple_meta_：元组元数据（is_deleted, timestamp 等）
tuple_：当前版本的元组数据
undo_link：指向 undo 日志的链接（用于 MVCC）

MVCC 背景：

表存储:
RID=102 → 当前版本: (3, 'Charlie', 21, 90) [由 T1 修改]
         → undo_link → T1 的 undo 日志
                       → 旧版本: (3, 'Charlie', 21, 88)

收集 Undo 日志

auto undo_logs = CollectUndoLogs(rid_ret[0], tuple_meta_, tuple_, undo_link, 
                                  exec_ctx_->GetTransaction(),
                                  exec_ctx_->GetTransactionManager());
if (!undo_logs.has_value()) {
    // means tuple is not exist at that time
    continue;
}

CollectUndoLogs 函数： 收集当前事务需要应用的 undo 日志列表。

判断逻辑：

// 当前事务 T2
// 读取 RID=102 的记录

// 情况1：记录在 T2 之前已删除
// undo_logs 返回 nullopt → 记录不存在

// 情况2：记录被 T1 修改（未提交）
// undo_logs 包含 T1 的 undo 日志 → 需要回退

// 情况3：记录没有被其他事务修改
// undo_logs 为空 → 直接读取当前版本

为什么 continue？

如果记录在当前事务看来不存在（已删除）
跳过这条记录，尝试下一个查找键

重建可见元组

auto rebuild_tuple = ReconstructTuple(&GetOutputSchema(), tuple_, tuple_meta_, undo_logs.value());
if (!rebuild_tuple.has_value()) {
    // means tuple is deleted
    continue;
}

ReconstructTuple 函数： 应用 undo 日志，重建当前事务可见的元组版本。

重建过程：

// 原始 tuple_ = (3, 'Charlie', 21, 90)  // T1 修改后
// undo_logs = [T1: score 90→88]
// 重建后 = (3, 'Charlie', 21, 88)  // T2 可见的旧版本

// 如果 tuple_meta_.is_deleted_ == true
// 且 undo_logs 显示记录在 T2 开始前已存在
// 则重建后元组存在

// 如果重建失败（记录确实已删除）
// rebuild_tuple 为 nullopt → continue

应用剩余条件并返回

if (select_func(rebuild_tuple.value(), remaining_conds_)) {
    rebuild_tuple->SetRid(rid_ret[0]);
    *tuple = rebuild_tuple.value();
    *rid = rid_ret[0];
    return true;
}

执行步骤：

应用剩余条件：

1
2
3

// remaining_conds_ = [score > 80]
// rebuild_tuple = (3, 'Charlie', 21, 88)
// select_func 检查：88 > 80 → true

设置 RID：

1	rebuild_tuple->SetRid(rid_ret[0]); // 设置 RID=102

返回结果：

1
2
3

*tuple = rebuild_tuple.value();  // 输出元组
*rid = rid_ret[0];               // 输出 RID
return true;                     // 找到一条记录

循环控制

1
2
3

}
// 如果 rid_ret 为空，继续下一个查找键
return false;

如果当前查找键没有匹配：

rid_ret 为空 → 继续 while 循环
尝试下一个查找键

如果所有查找键都处理完：

point_lookup_idx_ 超出范围 → 返回 false

完整的执行流程图

开始 Next()
    ↓
检查谓词是否恒为 FALSE → 是 → 返回 false
    ↓
定义 select_func 过滤函数
    ↓
is_point_lookup_ == true?
    ↓ 是
进入点查找循环
    ↓
还有查找键？ → 否 → 返回 false
    ↓ 是
取下一个查找键 cur_tuple
    ↓
在索引中查找 cur_tuple → rid_ret
    ↓
rid_ret 为空？ → 是 → 继续循环
    ↓ 否
取第一个 RID
    ↓
读取元组和 undo 链接
    ↓
收集 undo 日志
    ↓
undo_logs 为空？ → 是 → 继续循环（记录不存在）
    ↓ 否
重建可见元组
    ↓
重建失败？ → 是 → 继续循环（记录已删除）
    ↓ 否
应用剩余条件
    ↓
不满足？ → 是 → 继续循环
    ↓ 否
设置 RID，返回元组
    ↓
返回 true

综合示例

场景：点查找 + 剩余条件

初始状态：

-- 表 student(id, name, age, score)
-- 索引 (id, name, age)

-- 数据：
RID=100: (1, 'Alice', 20, 90)
RID=101: (2, 'Bob', 22, 85)
RID=102: (3, 'Charlie', 21, 88)  [T1 修改为 score=90，未提交]

-- 当前事务 T2

SQL：

SELECT * FROM student 
WHERE id = 3 
  AND name = 'Charlie' 
  AND age = 21 
  AND score > 80;

执行过程：

cpp

// Init() 阶段：
// is_point_lookup_ = true
// point_lookup_partial_tuples_ = [(3, 'Charlie', 21)]
// remaining_conds_ = [score > 80]

// ===== 第1次 Next() =====

// 1. 取查找键
cur_tuple = (3, 'Charlie', 21)

// 2. 索引查找
index_->ScanKey((3,'Charlie',21), &rid_ret, ...)
rid_ret = [102]

// 3. 读取元组
tuple_meta_ = {is_deleted: false}
tuple_ = (3, 'Charlie', 21, 90)  // T1 修改后的值
undo_link = → T1_undo

// 4. 收集 undo 日志
undo_logs = [T1_undo: (score: 90→88)]

// 5. 重建元组
rebuild_tuple = (3, 'Charlie', 21, 88)  // T2 可见版本

// 6. 应用剩余条件
select_func(rebuild_tuple, [score > 80])
score=88 > 80 → true ✓

// 7. 返回结果
*tuple = (3, 'Charlie', 21, 88)
*rid = 102
return true

// ===== 第2次 Next() =====

// 1. 检查索引
point_lookup_idx_ = 1 >= point_lookup_partial_tuples_.size() (1>=1)
return false  // 没有更多记录

范围查找-Next函数

代码整体结构

这段代码处理的是：从索引的某个起始位置开始，顺序扫描直到满足条件或到达末尾。

检查迭代器状态

// 2. range lookup
if (index_iterator_.IsEnd()) {
    return false;
}

index_iterator_：指向当前要扫描的索引条目

// 如果迭代器已经到达末尾
if (index_iterator_.IsEnd()) {
    return false;  // 没有更多记录
}

// 示例：
// index_iterator_ 指向 (3, 'Charlie', 21) → 继续
// index_iterator_ 指向 End() → 返回 false

获取输出模式

1	auto schema = plan_->OutputSchema();

注意： 这里声明了 schema 但实际上没有使用！

1	auto schema = plan_->OutputSchema(); // 未使用，可能是冗余代码

这可能是遗留代码或准备用于未来扩展。

主循环

while (true) {
    if (index_iterator_.IsEnd()) {
        return false;
    }

无限循环，直到找到一条满足条件的记录或到达索引末尾。

获取当前索引条目

1	auto [cur_key, cur_rid] = *index_iterator_;

解引用迭代器返回：

// B+树迭代器返回 pair<KeyType, RID>
auto [cur_key, cur_rid] = *index_iterator_;

// 示例：
// cur_key = (3, 'Charlie', 21)  // 索引键
// cur_rid = RID=102              // 对应的行ID

读取元组和 Undo 链接

1 2	auto [tuple_meta, tuple_, undo_link] = GetTupleAndUndoLink(exec_ctx_->GetTransactionManager(), table_info_->table_.get(), cur_rid);

与点查找相同的 MVCC 处理：

// 从表中读取 RID=102 的记录
tuple_meta = {is_deleted: false, timestamp: 100}
tuple_ = (3, 'Charlie', 21, 90)  // 当前版本
undo_link = → 指向 undo 日志链

收集 Undo 日志

auto undo_logs = CollectUndoLogs(cur_rid, tuple_meta, tuple_, undo_link, 
                                  exec_ctx_->GetTransaction(),
                                  exec_ctx_->GetTransactionManager());
// 如果记录在当前事务看来不存在
if (!undo_logs.has_value()) {
    ++index_iterator_;  // 移动到下一条索引记录
    continue;           // 跳过当前记录
}

示例场景：

// 记录被其他事务删除且已提交
// 或者记录在当前事务开始前已删除
// undo_logs 返回 nullopt
// 跳过这条记录，继续扫描下一条

重建可见元组

auto rebuild_tuple = ReconstructTuple(&GetOutputSchema(), tuple_, tuple_meta, undo_logs.value());
if (!rebuild_tuple.has_value()) {
    ++index_iterator_;
    continue;
}

示例:

// 应用 undo 日志，得到当前事务可见的版本
rebuild_tuple = (3, 'Charlie', 21, 88)  // T2 可见版本

// 如果重建失败（记录已删除）
if (!rebuild_tuple.has_value()) {
    ++index_iterator_;  // 跳过
    continue;
}

应用前缀条件（关键！）

if (!select_func(rebuild_tuple.value(), prefix_preds_)) {
    index_iterator_ = index_->GetEndIterator();
    return false;
}

prefix_preds_：从 Init() 中保存的索引前缀条件

// 示例：
// prefix_preds_ = [id=3, name='Charlie', age>20]
// rebuild_tuple = (3, 'Charlie', 21, 88)

// select_func 检查：
// id=3 → true
// name='Charlie' → true  
// age>20 → 21>20 → true
// 所有条件满足 → 继续

// 如果 rebuild_tuple = (4, 'David', 23, 92)
// id=4 → false
// select_func 返回 false
// 执行：index_iterator_ = GetEndIterator()
// 返回 false → 提前终止扫描！

为什么提前终止？

因为索引是有序的，prefix_preds_ 是连续的前缀条件：

// 索引顺序：(id, name, age)
// prefix_preds_ = [id=3, name='Charlie']

// 扫描顺序：
// (3, 'Alice', 20)  ← id=3, name='Alice' < 'Charlie' → 继续扫描
// (3, 'Charlie', 20) ← id=3, name='Charlie' ✓ → 处理
// (3, 'Charlie', 21) ← id=3, name='Charlie' ✓ → 处理
// (3, 'David', 20)   ← id=3, name='David' > 'Charlie' → 前缀条件失败！
//                      → 后面所有记录都 > 'Charlie'
//                      → 可以提前终止！🚀

这是一个重要的性能优化！

应用剩余条件

if (!select_func(rebuild_tuple.value(), remaining_conds_)) {
    ++index_iterator_;
    continue;
}

remaining_conds_：非索引列的条件（如 score > 80）

// remaining_conds_ = [score > 80]
// rebuild_tuple = (3, 'Charlie', 21, 88)

// select_func 检查：
// score > 80 → 88>80 → true ✓
// 继续返回

// 如果 rebuild_tuple = (3, 'Charlie', 21, 75)
// score > 80 → 75>80 → false ✗
// 跳过当前记录，继续扫描下一条
// 注意：这里不能提前终止！因为后面可能有满足条件的记录

为什么不能提前终止？

// 索引顺序：(id, name, age)
// remaining_conds_ 不是索引列，与顺序无关
// 后面可能有 score > 80 的记录
// 必须继续扫描

返回结果

rebuild_tuple->SetRid(cur_rid);
*tuple = rebuild_tuple.value();
*rid = cur_rid;
++index_iterator_;
break;

找到一条满足所有条件的记录：

// 1. 设置 RID
rebuild_tuple->SetRid(cur_rid);  // RID=102

// 2. 输出元组
*tuple = rebuild_tuple.value();  // (3, 'Charlie', 21, 88)

// 3. 输出 RID
*rid = cur_rid;  // 102

// 4. 移动迭代器到下一个位置
++index_iterator_;  // 下次 Next() 从下一条开始

// 5. 跳出循环
break;

返回成功

1	return true;

表示找到了一条记录，调用者可以继续调用 Next() 获取更多记录。

完整的执行流程图

开始 Next()
    ↓
迭代器到达末尾？ → 是 → 返回 false
    ↓ 否
进入主循环
    ↓
迭代器到达末尾？ → 是 → 返回 false
    ↓ 否
取当前索引条目 (key, rid)
    ↓
读取元组和 undo 链接
    ↓
收集 undo 日志
    ↓
undo_logs 为空？ → 是 → 移动到下一条，继续循环
    ↓ 否
重建可见元组
    ↓
重建失败？ → 是 → 移动到下一条，继续循环
    ↓ 否
应用前缀条件
    ↓
不满足？ → 是 → 提前终止，返回 false
    ↓ 满足
应用剩余条件
    ↓
不满足？ → 是 → 移动到下一条，继续循环
    ↓ 满足
设置 RID，返回元组
    ↓
移动迭代器到下一个位置
    ↓
返回 true

综合示例

场景：范围查找 + 前缀条件 + 剩余条件

初始状态：

sql

-- 表 student(id, name, age, score)
-- 索引 (id, name, age)
-- 数据：
RID=100: (1, 'Alice', 20, 90)
RID=101: (2, 'Bob', 22, 85)
RID=102: (3, 'Charlie', 21, 88)
RID=103: (3, 'David', 23, 70)   -- score < 80
RID=104: (4, 'Eve', 20, 95)
RID=105: (5, 'Frank', 25, 78)

SQL：

SELECT * FROM student 
WHERE id = 3 
  AND name >= 'Charlie' 
  AND score > 80;

Init() 阶段：

// 匹配索引：
prefix_preds_ = [id=3, name>='Charlie']
remaining_conds_ = [score > 80]

// 起始键：
start_key = (3, 'Charlie', MIN_VALUE)
index_iterator_ = GetBeginIterator(start_key)
// 指向第一个 >= (3, 'Charlie', MIN_VALUE) 的记录
// 即 (3, 'Charlie', 21)

Next() 执行过程：

// ===== 第1次 Next() =====

// 1. 当前迭代器指向 (3, 'Charlie', 21), RID=102
// 2. 读取元组：(3, 'Charlie', 21, 88)
// 3. 应用前缀条件：
//    id=3 ✓, name>='Charlie' ✓
// 4. 应用剩余条件：
//    score > 80 → 88>80 ✓
// 5. 返回 RID=102
// 6. 迭代器移动到 (3, 'David', 23)

// ===== 第2次 Next() =====

// 1. 当前迭代器指向 (3, 'David', 23), RID=103
// 2. 读取元组：(3, 'David', 23, 70)
// 3. 应用前缀条件：
//    id=3 ✓, name>='Charlie' ✓ (David > Charlie)
// 4. 应用剩余条件：
//    score > 80 → 70>80 ✗ 不满足
// 5. 跳过当前记录，迭代器移动到 (4, 'Eve', 20)

// ===== 第3次 Next() =====

// 1. 当前迭代器指向 (4, 'Eve', 20), RID=104
// 2. 读取元组：(4, 'Eve', 20, 95)
// 3. 应用前缀条件：
//    id=4 ✗ 不满足！
// 4. 执行：index_iterator_ = GetEndIterator()
//    return false  // 提前终止！

关键点： 当遇到 id=4 时，由于索引有序，后面所有记录的 id 都 > 3，所以 id=3 的条件永远不会再满足，可以安全地提前终止！

b+树解析

Insert

我来逐行解析这段 B+树插入 的代码。这是 BusTub 数据库系统中 B+树索引的核心插入逻辑。

整体结构

这段代码包含两个函数：

Insert - 对外的公开接口（处理事务参数）
InsertHelper - 内部的核心插入逻辑（支持两种锁模式）

一、Insert 函数解析

1	auto BPLUSTREE_TYPE::Insert(const KeyType &key, const ValueType &value, Transaction *transaction) -> bool {

公开的插入接口，返回 bool 表示插入是否成功
参数：要插入的键值对 (key, value)，以及当前事务

bool dummy_used = false;
if (transaction == nullptr) {
    // for consistency, make sure there is always a non-empty transaction passed in
    transaction = new Transaction(0);
    dummy_used = true;
}

事务兼容性处理：如果外部没有传入事务（nullptr），创建一个虚拟事务对象
dummy_used 标记这个事务是临时创建的，后面需要释放

1	bool success = InsertHelper(key, value, transaction, LatchMode::OPTIMIZE);

调用核心插入函数，初始使用 OPTIMIZE 模式
OPTIMIZE 模式是乐观锁模式（性能更好，但可能在页面满时失败）

if (dummy_used) {
    delete transaction;
}
return success;

如果是临时创建的事务，释放内存
返回插入结果

二、InsertHelper 函数解析

1
2
3

auto BPlusTree<KeyType, ValueType, KeyComparator>::InsertHelper(const KeyType &key, const ValueType &value,
                                                                Transaction *transaction, BPlusTree::LatchMode mode)
    -> bool {

内部核心插入函数
多了一个 mode 参数：OPTIMIZE（乐观）或 INSERT（保守/悲观）

第一阶段：初始化变量和加根页锁

1 2	int dirty_height = 0; // 记录脏页高度（用于释放锁时判断哪些页被修改了） LatchRootPageId(transaction, mode); // 对根页面加锁

if (IsEmpty()) {  // B+树为空
    if (mode == LatchMode::OPTIMIZE) {
        // OPTIMIZE mode fails
        ReleaseAllLatches(transaction, mode, dirty_height);
        return InsertHelper(key, value, transaction, LatchMode::INSERT);
    }
    // 初始化B+树
    InitBPlusTree(key, value);
    ReleaseAllLatches(transaction, mode, dirty_height);
    return true;
}

逻辑说明：

树为空时，插入操作将创建第一个节点
如果是 OPTIMIZE 模式：释放锁，改用 INSERT 模式重新调用（悲观模式下做更多准备工作）
如果是 INSERT 模式：直接调用 InitBPlusTree() 初始化树，释放锁，返回 true

第二阶段：查找叶子节点

1	auto [raw_leaf_page, leaf_page] = FindLeafPage(key, transaction, mode);

从根节点开始查找，定位到应该插入的叶子节点
FindLeafPage 会沿途加锁（根据 mode 决定加锁策略）
返回叶子页面的原始指针和包装对象

if ((1 + leaf_page->GetSize()) == leaf_page->GetMaxSize() && mode == LatchMode::OPTIMIZE) {
    // OPTIMIZE mode fails
    ReleaseAllLatches(transaction, mode, dirty_height);
    return InsertHelper(key, value, transaction, LatchMode::INSERT);
}

乐观锁失败条件：如果叶子节点已满（插入后需要分裂），且当前是 OPTIMIZE 模式
因为乐观模式下没有对父节点加锁，无法安全地处理分裂
所以：释放所有锁，改用 INSERT 模式重新调用

第三阶段：插入键值对

bool no_duplicate = leaf_page->Insert(key, value, comparator_);
if (!no_duplicate) {
    // 有重复
    ReleaseAllLatches(transaction, mode, dirty_height);
    return false;
}

尝试在叶子节点中插入 (key, value)
如果返回 false，说明键已存在（B+树不允许重复键）
释放锁，返回 false

1 2	// 没有重复 dirty_height += 1; // 叶子页被修改了，标记脏页高度为1

第四阶段：处理分裂

if (leaf_page->GetSize() == leaf_page->GetMaxSize()) {
    // overflow, need split
    auto leaf_page_prime = CreateLeafPage();  // 创建新的叶子页面
    leaf_page->MoveLatterHalfTo(leaf_page_prime);  // 把后半部分数据移到新页面
    leaf_page_prime->SetParentPageId(leaf_page->GetParentPageId());  // 设置父节点
    const auto key_upward = leaf_page_prime->KeyAt(0);  // 获取新页面的最小键（向上传递）
    InsertInParent(leaf_page, leaf_page_prime, key_upward);  // 在父节点中插入新键
    buffer_pool_manager_->UnpinPage(leaf_page_prime->GetPageId(), true);  // 释放新页面
}

如果叶子节点满了，执行分裂操作：
1. 创建新的叶子页面
2. 将原叶子页面的后半部分移动到新页面
3. 新页面的父节点与原页面相同
4. 取新页面的第一个键作为向上的键
5. 调用 InsertInParent() 在父节点中插入该键（可能递归分裂）
6. UnpinPage 释放新页面（true 表示页面已修改，需要刷盘）

第五阶段：清理并返回

1 2	ReleaseAllLatches(transaction, mode, dirty_height); return true;

释放所有持有的锁
返回 true 表示插入成功

三、两种锁模式对比

模式	说明	使用场景
OPTIMIZE（乐观）	只对路径上的页面加读锁，效率高	树结构变化可能性小时使用
INSERT（悲观/保守）	对路径上的页面加写锁，允许安全修改	OPTIMIZE 失败后回退使用

设计思想：

先用乐观模式尝试，如果发现需要分裂（结构会变化），则释放锁，改用悲观模式重新执行
这样在大多数情况下（叶子节点未满），性能最优

四、关键辅助函数

函数	作用
`LatchRootPageId()`	对根页面加锁
`FindLeafPage()`	查找键应该落入的叶子节点
`ReleaseAllLatches()`	释放当前事务持有的所有页面锁
`InitBPlusTree()`	初始化一棵只有根节点的B+树
`InsertInParent()`	在父节点中插入键，必要时递归分裂

五、执行流程图

Insert(key, value)
    ↓
InsertHelper(OPTIMIZE模式)
    ↓
加锁根页
    ↓
树为空？─────YES─────→ 乐观？ ──YES──→ 失败，重试INSERT模式
    │                    │                 │
    NO                   NO                ↓
    ↓                    ↓            InitBPlusTree()
FindLeafPage()      InitBPlusTree()
    ↓
叶子已满 且 乐观？ ──YES──→ 释放锁，重试INSERT模式
    │
    NO
    ↓
叶子插入键值对
    ↓
有重复？ ──YES──→ 释放锁，返回false
    │
    NO
    ↓
标记脏页
    ↓
叶子满了？ ──YES──→ 分裂 + InsertInParent()
    │
    NO
    ↓
释放锁，返回true

Search

我来逐行解析这段 B+树查询（GetValue） 的代码。这是 BusTub 数据库系统中 B+树索引的查找操作。

整体功能

这段代码实现了 B+树的 键值查找 功能：给定一个键 key，在 B+树中查找所有匹配的值，并将结果存入 result 向量中。

逐行解析

第一部分：事务处理

1	auto BPLUSTREE_TYPE::GetValue(const KeyType &key, std::vector<ValueType> result, Transaction transaction) -> bool {

函数签名：B+树的查询接口
参数：
- key：要查找的键
- result：输出参数，存储查找到的所有值
- transaction：当前事务
返回值：bool，表示是否找到至少一个匹配的值

bool dummy_used = false;
if (transaction == nullptr) {
    // for consistency, make sure there is always a non-empty transaction passed in
    transaction = new Transaction(0);
    dummy_used = true;
}

事务兼容处理：如果没有传入事务，创建一个临时虚拟事务
dummy_used 标记是否需要释放这个临时事务

第二部分：根页面加锁与空树检查

1	LatchRootPageId(transaction, LatchMode::READ);

对根页面加读锁（READ 模式）
因为这是查询操作，不会修改树结构，所以只需要共享锁（读锁）
多个读操作可以并发执行

if (IsEmpty()) {
    ReleaseAllLatches(transaction, LatchMode::READ);
    if (dummy_used) {
        delete transaction;
    }
    return false;
}

空树检查：如果 B+树为空（没有根节点）
释放所有锁，清理临时事务，返回 false（未找到）

第三部分：查找叶子节点

1 2	bool found = false; auto [raw_leaf_page, leaf_page] = FindLeafPage(key, transaction, LatchMode::READ);

定位叶子节点：从根节点开始，根据键值查找应该存储该键的叶子节点
FindLeafPage 会沿着路径逐层加读锁
使用 C++17 的结构化绑定，返回两个对象：
- raw_leaf_page：原始页面指针
- leaf_page：包装后的叶子页面对象

第四部分：在叶子节点中进行二分查找

1 2	auto left = 0; auto right = leaf_page->GetSize() - 1;

初始化二分查找边界
GetSize() 返回叶子节点中键值对的数量
left 指向第一个元素，right 指向最后一个元素

1
2
3

while (left <= right) {
    // binary search
    auto mid = left + (right - left) / 2;

二分查找循环，条件是 left <= right
mid 计算中间位置（避免整数溢出）

1	auto comp_result = comparator_(key, leaf_page->KeyAt(mid));

比较键值：将目标键与叶子节点中 mid 位置的键进行比较
comparator_ 是键的比较器（通常是 std::less 或自定义比较函数）
返回值：
- 0：相等
- < 0：目标键小于中间键
- > 0：目标键大于中间键

if (comp_result == 0) {
    result->push_back(leaf_page->ValueAt(mid));
    found = true;
    break;
}

找到匹配：如果键相等
将对应的值（ValueAt(mid)）添加到结果向量中
标记 found = true，跳出循环

if (comp_result < 0) {
    right = mid - 1;
} else {
    left = mid + 1;
}

二分查找的常规移动：
- 如果目标键小于中间键，在左半部分继续查找（right = mid - 1）
- 如果目标键大于中间键，在右半部分继续查找（left = mid + 1）

第五部分：清理并返回

1 2	// clear up all the latches held in this transaction ReleaseAllLatches(transaction, LatchMode::READ);

释放所有锁：释放当前事务持有的所有页面读锁
包括根页面和路径上所有页面的锁

if (dummy_used) {
    delete transaction;
}
return found;

如果是临时事务，释放内存
返回查找结果（true 表示找到，false 表示未找到）

关键设计思想

读锁（共享锁）机制

1 2	LatchRootPageId(transaction, LatchMode::READ); FindLeafPage(key, transaction, LatchMode::READ);

查询操作只加读锁，不阻塞其他读操作
多个查询可以并发执行，提高并发性能
与插入操作的写锁（OPTIMIZE/INSERT）互斥

二分查找优化

叶子节点内部使用二分查找，时间复杂度 O(log N)
比线性扫描更高效，特别是叶子节点包含大量键时

事务一致性

即使没有外部事务，也会创建临时事务来管理锁
确保所有操作都在事务上下文中，便于统一管理锁的获取和释放

与插入操作的对比

特性	`GetValue`（查询）	`Insert`（插入）
锁模式	`READ`（读锁/共享锁）	`OPTIMIZE` / `INSERT`（写锁/排他锁）
锁粒度	路径上的页面都加读锁	路径上的页面加写锁
是否修改树	否（只读）	是（可能分裂）
并发性	高（多读并发）	低（互斥）
二分查找	在叶子节点中进行	插入前需要先定位位置

执行流程图

GetValue(key, result, transaction)
    ↓
创建临时事务（如果需要）
    ↓
加根页面读锁
    ↓
树为空？ ──YES──→ 释放锁，返回 false
    │
    NO
    ↓
FindLeafPage(key, READ)   ← 沿路径加读锁
    ↓
获取叶子节点的 key-value 列表
    ↓
二分查找 key
    ↓
找到？ ──YES──→ 将 value 加入 result，标记 found=true
    │                  │
    NO                 │
    │                  ↓
    ↓             释放所有锁
继续二分查找
    ↓
释放所有锁
    ↓
清理临时事务
    ↓
返回 found

Delete

整体功能

这段代码实现了 B+树的 键值删除 功能：给定一个键 key，从 B+树中删除对应的键值对。与插入操作类似，也采用了 乐观/悲观 双模式策略。

一、Remove 函数解析

1 2	INDEX_TEMPLATE_ARGUMENTS void BPLUSTREE_TYPE::Remove(const KeyType &key, Transaction *transaction) {

公开的删除接口，无返回值（void）
参数：要删除的键 key，以及当前事务

bool dummy_used = false;
if (transaction == nullptr) {
    // for consistency, make sure there is always a non-empty transaction passed in
    transaction = new Transaction(0);
    dummy_used = true;
}

事务兼容处理：与插入/查询一样，如果没有事务则创建临时事务
dummy_used 标记临时事务

1	RemoveHelper(key, transaction, LatchMode::OPTIMIZE);

调用核心删除函数，初始使用 OPTIMIZE 模式（乐观锁）
乐观模式性能更好，但可能在需要合并/重分配时失败

1
2
3

if (dummy_used) {
    delete transaction;
}

释放临时事务

二、RemoveHelper 函数解析

第一部分：初始化与空树检查

INDEX_TEMPLATE_ARGUMENTS
void BPlusTree<KeyType, ValueType, KeyComparator>::RemoveHelper(const KeyType &key, Transaction *transaction,
                                                                BPlusTree::LatchMode mode) {
  int dirty_height = 0;

内部核心删除函数
dirty_height：记录脏页高度，用于释放锁时判断哪些页被修改了
mode：OPTIMIZE（乐观）或 DELETE（悲观/保守）

1	LatchRootPageId(transaction, mode);

对根页面加锁：根据 mode 决定加读锁还是写锁

if (IsEmpty()) {
    ReleaseAllLatches(transaction, mode, dirty_height);
    return;
}

空树检查：如果树为空，释放锁后直接返回（无需删除）

第二部分：定位叶子节点

1	auto [raw_leaf_page, leaf_page] = FindLeafPage(key, transaction, mode);

查找包含该键的叶子节点
沿着路径逐层加锁，返回叶子页面

第三部分：乐观模式失败条件检查

1	if ((leaf_page->GetSize() - 1) < leaf_page->GetMinSize() && mode == LatchMode::OPTIMIZE) {

核心判断：如果删除后叶子节点的大小小于最小容量，且当前是乐观模式
leaf_page->GetSize() - 1：删除后的预期大小
leaf_page->GetMinSize()：叶子节点的最小容量（通常是 max_size / 2）

这意味着删除后叶子节点会下溢出（Underflow），需要通过合并（Merge）或重分配（Redistribute）来修复

1
2
3

auto is_root = leaf_page->IsRootPage();
auto is_leaf = leaf_page->IsLeafPage();
auto is_internal = leaf_page->IsInternalPage();

获取当前页面的属性：是否为根节点、是否为叶子节点、是否为内部节点

1
2
3

auto fail_condition1 = !is_root;
auto fail_condition2 = is_root && is_leaf && (leaf_page->GetSize() - 1) == 0;
auto fail_condition3 = is_root && is_internal && (leaf_page->GetSize() - 1) == 1;

三个失败条件（任何一条满足，乐观模式都会失败）：

条件	说明	为什么需要特殊处理
`fail_condition1`	不是根节点	删除后需要从兄弟节点借元素或合并，需要修改父节点，乐观模式下父节点可能没有写锁
`fail_condition2`	是叶子根节点，且删除后大小为0	树可能变为空树，需要特殊处理
`fail_condition3`	是内部根节点，且删除后大小为1	根节点可能只需要一个键，需要特殊处理

cpp

if (fail_condition1 || fail_condition2 || fail_condition3) {
    ReleaseAllLatches(transaction, mode);
    return RemoveHelper(key, transaction, LatchMode::DELETE);
}

如果满足任一失败条件：释放所有锁，使用 DELETE 模式（悲观模式）重新调用
悲观模式下会对路径上的页面加写锁，允许安全地修改父节点

第四部分：执行删除

1	RemoveEntry(leaf_page, key, dirty_height);

实际执行删除操作：在叶子节点中移除键值对
dirty_height 会递增，标记页面已被修改

1	ReleaseAllLatches(transaction, mode, dirty_height);

释放所有持有的锁（包括页面锁）

三、乐观 vs 悲观模式对比

乐观模式 (OPTIMIZE)

加锁方式：沿路径加读锁
适用场景：删除后叶子节点大小 >= 最小容量（不会下溢出）
优点：并发性能好，多个删除/查询可以并发
缺点：如果叶子节点下溢出，无法安全处理（需要修改父节点）

悲观模式 (DELETE)

加锁方式：沿路径加写锁（排他锁）
适用场景：删除后叶子节点下溢出，需要合并或重分配
优点：可以安全地修改树结构
缺点：并发性能差，阻塞其他操作

四、B+树删除的核心概念

下溢出（Underflow）

定义：叶子节点删除后，键值对数量小于 GetMinSize()
最小容量：通常是 GetMaxSize() / 2（根节点除外）
修复方式：
1. 重分配（Redistribute）：从兄弟节点借一个元素
2. 合并（Merge）：将当前节点与兄弟节点合并

根节点特殊规则

根节点没有最小容量限制（可以为空）
如果根节点变成空，需要：
- 如果是叶子根节点，树变为空树
- 如果是内部根节点，树高度降低

五、执行流程图

Remove(key, transaction)
    ↓
RemoveHelper(OPTIMIZE模式)
    ↓
加锁根页
    ↓
树为空？ ──YES──→ 释放锁，返回
    │
    NO
    ↓
FindLeafPage(key, READ/OPTIMIZE)
    ↓
删除后 < 最小容量？ ──NO──→ RemoveEntry() 删除，释放锁，返回
    │                      ↓
    YES                   完成
    ↓
检查失败条件：
  - 非根节点？
  - 根+叶子+大小为0？
  - 根+内部+大小为1？
    ↓
任一满足？ ──YES──→ 释放锁，用 DELETE 模式重试
    │
    NO           RemoveEntry() 删除（乐观模式可处理）
    ↓
释放锁，完成

RemoveEntry

我来逐行解析这段 B+树删除操作的完整实现，包括删除条目、重分配、合并等核心逻辑。

整体架构

这段代码实现了 B+树删除的四个核心函数：

RemoveEntry - 删除入口，处理下溢出
RemoveDependingOnType - 根据页面类型执行删除
TryRedistribute - 尝试从兄弟节点借元素
TryMerge - 尝试与兄弟节点合并
Redistribute - 实际执行重分配
Merge - 实际执行合并
RefreshParentPointer/RefreshAllParentPointer - 更新父指针

执行流程图

RemoveHelper (悲观模式)
    ↓
RemoveEntry(叶子页面)
    ↓
RemoveDependingOnType()
    ↓
删除键值对
    ↓
dirty_height++
    ↓
是否需要修复下溢出？
    ↓
是根节点？
    ├─ YES ─→ 特殊处理（降低树高度或置空）
    └─ NO  ─→ 尝试修复
              ↓
          TryRedistribute()
          ├─ 从右兄弟借 → 成功？
          ├─ 从左兄弟借 → 成功？
          └─ 都失败 → TryMerge()
                      ├─ 与右兄弟合并
                      └─ 与左兄弟合并

一、示例 B+树结构

假设我们有一个阶数（Order）为 3 的 B+树（每个节点最多 3 个键，最少 1 个键），当前状态如下：

                 [4, 7]  ← 根节点（内部节点）
                /   |   \
               /    |    \
 [1, 2, 3]  [4, 5, 6]  [7, 8, 9]
  ↑           ↑           ↑
叶子A       叶子B       叶子C

根节点：内部节点，存储键 [4, 7]，有 3 个子节点指针
叶子 A：存储 [1, 2, 3]
叶子 B：存储 [4, 5, 6]
叶子 C：存储 [7, 8, 9]

二、`RemoveEntry` - 删除入口函数

1 2	void BPlusTree<KeyType, ValueType, KeyComparator>::RemoveEntry(BPlusTreePage *base_page, const KeyType &key, int &dirty_height) {

场景：删除键 1

base_page → 叶子 A（[1, 2, 3]）
key → 1
dirty_height → 初始为 0

auto delete_success = RemoveDependingOnType(base_page, key);
if (!delete_success) {
    // no modification made on this page
    return;
}
dirty_height++;

步骤 1：调用 RemoveDependingOnType 在叶子 A 中删除键 1

1
2
3

叶子 A：[1, 2, 3] → 删除 1 → [2, 3]
delete_success = true
dirty_height = 1  （标记页面被修改）

1	if (base_page->GetSize() < base_page->GetMinSize()) {

步骤 2：检查是否下溢出

1
2
3

叶子 A 当前大小 = 2
最小容量 = 1
2 < 1 ? → false ✅ 没有下溢出

跳过修复逻辑，函数返回

✅ 删除完成，树结构保持不变：

                [4, 7]
               /   |   \
              /    |    \
[2, 3]      [4, 5, 6]  [7, 8, 9]

三、继续删除键 `2`

场景：删除键 2

1 2	叶子 A：[2, 3] → 删除 2 → [3] dirty_height = 1

检查下溢出：

1
2
3

叶子 A 大小 = 1
最小容量 = 1
1 < 1 ? → false ✅ 刚好满足，无需修复

四、继续删除键 `3` - 触发修复

场景：删除键 3

1 2	叶子 A：[3] → 删除 3 → [] （空！） dirty_height = 1

检查下溢出：

1
2
3

叶子 A 大小 = 0
最小容量 = 1
0 < 1 ? → true ⚠️ 下溢出！需要修复

根节点判断

1	if (base_page->IsRootPage())

1	叶子 A 是根节点吗？→ false（根节点是内部节点）

进入非根节点修复分支：

执行修复

auto redistribute_success = TryRedistribute(base_page, key);
if (!redistribute_success) {
    auto merge_success = TryMerge(base_page, key, dirty_height);
    BUSTUB_ASSERT(redistribute_success || merge_success, "redistribute_success || merge_success");
}

当前树结构：

                  [4, 7]  ← 根节点
                 /   |   \
                /    |    \
 [] (underfull) [4,5,6]  [7,8,9]
  ↑              ↑        ↑
叶子A         叶子B     叶子C
(下溢出)      (右兄弟)

五、`TryRedistribute` - 尝试重分配

1
2
3

auto BPlusTree<KeyType, ValueType, KeyComparator>::TryRedistribute(BPlusTreePage *base_page, const KeyType &key)
    -> bool {
  BUSTUB_ASSERT(!base_page->IsRootPage(), "!base_page->IsRootPage()");

断言：base_page 不是根节点 ✅

1
2
3

auto parent_page_id = base_page->GetParentPageId();
auto [raw_parent_page, base_parent_page] = FetchBPlusTreePage(parent_page_id);
auto parent_page = ReinterpretAsInternalPage(base_parent_page);

步骤 1：获取父节点

1
2
3

叶子 A 的父节点 → 根节点 [4, 7]
parent_page_id = 根节点ID
parent_page = 内部节点 [4, 7]

1	auto underfull_index = parent_page->SearchJumpIdx(key, comparator_);

步骤 2：找到 base_page 在父节点中的索引

在父节点 [4, 7] 中查找键 3
SearchJumpIdx 返回：0
（键 3 在键 4 的左侧，对应第 0 个子节点指针）

underfull_index = 0

父节点结构：

1
2
3

索引:    0       1       2
指针:  [叶子A]  [叶子B]  [叶子C]
键:      4       7

尝试从右兄弟借

1 2	if (underfull_index < parent_page->GetSize() - 1) { // has right sibling

1
2
3

parent_page->GetSize() = 2（键的数量）
underfull_index = 0
0 < 1 ? → true ✅ 存在右兄弟

1 2	auto [sibling_raw_page, sibling_page] = FetchBPlusTreePage(parent_page->ValueAt(underfull_index + 1)); sibling_raw_page->WLatch(); // lock sibling

步骤 3：获取右兄弟

underfull_index + 1 = 1
parent_page->ValueAt(1) = 叶子B
右兄弟 = 叶子B [4, 5, 6]
加写锁（并发控制）

if ((sibling_page->GetSize() - 1) >= sibling_page->GetMinSize()) {
    // stealing not leading to sibling underfull
    Redistribute(base_page, sibling_page, parent_page, underfull_index, false);
    redistribute_success = true;
}

步骤 4：检查右兄弟借出后是否下溢出

右兄弟大小 = 3
右兄弟借出1个后 = 2
最小容量 = 1
2 >= 1 ? → true ✅ 可以借

执行重分配：调用 Redistribute

1 2	sibling_raw_page->WUnlatch(); buffer_pool_manager_->UnpinPage(sibling_page->GetPageId(), redistribute_success);

解锁并释放右兄弟页面

1
2
3

if (!redistribute_success && underfull_index > 0) {
    // 尝试从左兄弟借（本例中 underfull_index = 0，没有左兄弟）
}

跳过（没有左兄弟）

1 2	buffer_pool_manager_->UnpinPage(parent_page->GetPageId(), redistribute_success); return redistribute_success;

释放父节点，返回 true（重分配成功）

六、`Redistribute` - 实际执行重分配

1
2
3

void BPlusTree<KeyType, ValueType, KeyComparator>::Redistribute(
    BPlusTreePage *base, BPlusTreePage *sibling, BPlusTreeInternalPage<KeyType, page_id_t, KeyComparator> *parent,
    int base_index, bool sibling_on_left) {

参数：

base = 叶子A（下溢出，空）
sibling = 叶子B（[4, 5, 6]）
parent = 根节点（[4, 7]）
base_index = 0
sibling_on_left = false（右兄弟）

1	if (base->IsLeafPage()) {

判断：base 是叶子节点 ✅

if (sibling_on_left) {
    // 左兄弟分支（不执行）
} else {
    // sibling on the right
    sibling_leaf->MoveFirstToEndOf(base_leaf);
    parent->SetKeyAt(base_index + 1, sibling_leaf->KeyAt(0));
}

执行右兄弟重分配：

步骤 1：将右兄弟的第一个元素移到 base

1 2	叶子B：[4, 5, 6] → 移除第一个元素 4 → [5, 6] 叶子A：[] → 将 4 移到末尾 → [4]

步骤 2：更新父节点的分隔键

原来的分隔键在索引 1（KeyAt(1)）= 4
现在右兄弟的第一个键变为 5
父节点->SetKeyAt(1, 5)

父节点：[4, 7] → [5, 7]

删除完成

                 [5, 7]  ← 根节点更新
                /   |   \
               /    |    \
 [4]         [5, 6]     [7, 8, 9]
  ↑           ↑          ↑
叶子A       叶子B      叶子C

✅ 通过重分配修复完成

七、继续删除键 `4` - 触发合并

场景：删除键 `4`

1 2	叶子A：[4] → 删除 4 → [] （空！） dirty_height = 1

检查下溢出：0 < 1 ⚠️

进入 TryRedistribute

`TryRedistribute` - 重分配失败

当前树结构：

                  [5, 7]
                 /   |   \
                /    |    \
 [] (underfull) [5,6]    [7,8,9]
  ↑              ↑        ↑
叶子A         叶子B     叶子C

尝试从右兄弟借：

右兄弟 = 叶子B [5, 6]
右兄弟大小 = 2
借出1个后 = 1
最小容量 = 1
1 >= 1 ? → true ✅ 可以借！

执行重分配：

1
2
3

叶子B → [5, 6] 移除第一个元素 5 → [6]
叶子A → [5]
父节点：[5, 7] → [6, 7]

删除完成

                [6, 7]
               /   |   \
              /    |    \
[5]         [6]      [7, 8, 9]

八、继续删除键 `5` - 合并

场景：删除键 `5`

1	叶子A：[5] → 删除 5 → [] （空！）

TryRedistribute：

当前树结构：

                 [6, 7]
                /   |   \
               /    |    \
[] (underfull) [6]     [7,8,9]

尝试从右兄弟借：

右兄弟 = 叶子B [6]
右兄弟大小 = 1
借出1个后 = 0
最小容量 = 1
0 >= 1 ? → false ⚠️ 不能借，会下溢出

尝试从左兄弟借：不存在

redistribute_success = false

进入 `TryMerge`

auto TryMerge(...) -> bool {
    BUSTUB_ASSERT(!base_page->IsRootPage(), "!base_page->IsRootPage()");
    auto parent_page_id = base_page->GetParentPageId();
    auto [raw_parent_page, base_parent_page] = FetchBPlusTreePage(parent_page_id);
    auto parent_page = ReinterpretAsInternalPage(base_parent_page);
    auto underfull_index = parent_page->SearchJumpIdx(key, comparator_);
    auto merge_success = false;

获取父节点和索引：

1 2	父节点 = [6, 7] underfull_index = 0（叶子A在父节点中的位置）

if (underfull_index < parent_page->GetSize() - 1) {
    // has right sibling, definitely can merge in our logic flow
    auto [sibling_raw_page, sibling_page] = FetchBPlusTreePage(parent_page->ValueAt(underfull_index + 1));
    sibling_raw_page->WLatch();  // lock sibling
    Merge(base_page, sibling_page, parent_page, underfull_index, false, dirty_height);
    sibling_raw_page->WUnlatch();
    merge_success = true;
    buffer_pool_manager_->UnpinPage(sibling_page->GetPageId(), merge_success);
}

与右兄弟合并：

1 2	右兄弟 = 叶子B [6] 调用 Merge(叶子A, 叶子B, 父节点, 0, false, dirty_height)

九、`Merge` - 实际执行合并

1
2
3

void BPlusTree<KeyType, ValueType, KeyComparator>::Merge(
    BPlusTreePage *base, BPlusTreePage *sibling, BPlusTreeInternalPage<KeyType, page_id_t, KeyComparator> *parent,
    int base_index, bool sibling_on_left, int &dirty_height) {

参数：

base = 叶子A（空）
sibling = 叶子B（[6]）
parent = 根节点（[6, 7]）
base_index = 0
sibling_on_left = false（右兄弟）

if (base->IsLeafPage()) {
    auto base_leaf = ReinterpretAsLeafPage(base);
    auto sibling_leaf = ReinterpretAsLeafPage(sibling);
    if (sibling_on_left) {
        // 左兄弟分支（不执行）
    } else {
        // sibling on the right
        auto key_in_between = parent->KeyAt(base_index + 1);
        sibling_leaf->MoveAllTo(base_leaf);
        base_leaf->SetNextPageId(sibling_leaf->GetNextPageId());
        sibling_leaf->SetParentPageId(INVALID_PAGE_ID);
        RemoveEntry(parent, key_in_between, dirty_height);
    }
}

执行合并：

步骤 1：获取分隔键

1 2	parent->KeyAt(base_index + 1) = parent->KeyAt(1) = 6 key_in_between = 6

步骤 2：将右兄弟所有元素移到 base

1 2	叶子B：[6] → 移动到叶子A 叶子A：[] → [6]

步骤 3：更新叶子节点链表

1 2	叶子A 原来 → 叶子B（next）叶子A 现在 → 叶子B 原来的 next（叶子C）

步骤 4：标记叶子B为无效

1	叶子B->SetParentPageId(INVALID_PAGE_ID)

步骤 5：从父节点删除分隔键

1	RemoveEntry(父节点, 6, dirty_height)

十、递归调用 `RemoveEntry` 删除父节点中的键

场景：从父节点删除键 `6`

1	RemoveEntry(parent, key_in_between, dirty_height)

步骤 1：在父节点中删除键

1
2
3

父节点 = [6, 7]
删除键 6 → [7]
dirty_height++ =

步骤 2：检查父节点是否下溢出

1
2
3

父节点大小 = 1
内部节点最小容量 = 1
1 < 1 ? → false ✅ 没有下溢出

父节点保留为 [7]

合并完成

                 [7]  ← 根节点（只有1个键）
                /   \
               /     \
 [6]                [7, 8, 9]
  ↑                  ↑
叶子A              叶子C
(合并后)

十一、继续删除键 `6` - 树高度降低

场景：删除键 `6`

1	叶子A：[6] → 删除 6 → []

TryRedistribute：

右兄弟 = 叶子C [7, 8, 9]
右兄弟大小 = 3
借出1个后 = 2 ≥ 1 ✅ 可以借
→ 重分配成功！

执行重分配：

1
2
3

叶子C 移除第一个元素 7 → [8, 9]
叶子A → [7]
父节点：[7] → [8]

最终状态

                [8]  ← 根节点
               /   \
              /     \
[7]                [8, 9]

十二、总结：删除操作的核心逻辑

函数	职责	关键操作
`RemoveEntry`	删除入口	删除键 → 检查下溢出 → 调用修复
`TryRedistribute`	尝试重分配	从右→左尝试借元素
`TryMerge`	尝试合并	从右→左尝试合并
`Redistribute`	执行重分配	移动 1 个元素，更新分隔键
`Merge`	执行合并	移动所有元素，递归删除父节点键

Bustub重点解析

mvcc解析

主流程

task1: watermark

task2: 重建元组 和 扫描算子

task3: 增删改算子

insert

路径 1: UPDATE 路径 (rid_opt.has_value() == true)

路径 2: INSERT 路径 (rid_opt.has_value() == false)

GenerateNewUndoLog and GenerateUpdatedUndoLog

GenerateNewUndoLog

GenerateUpdatedUndoLog

update and detelte

delete_executor

update_executor

垃圾回收

task4: 索引扫描

Init() 方法解析

Next() 方法解析

示例数据

没有剩余条件的点查找（即索引点查）-Init()函数

带剩余条件的点查找-Init()函数

范围查找-Init()函数

点查找 - Next函数

范围查找-Next函数

b+树解析

Insert

Search

Delete

RemoveEntry

一、示例 B+树结构

二、RemoveEntry - 删除入口函数

三、继续删除键 2

四、继续删除键 3 - 触发修复

根节点判断

执行修复

五、TryRedistribute - 尝试重分配

尝试从右兄弟借

六、Redistribute - 实际执行重分配

删除完成

七、继续删除键 4 - 触发合并

场景：删除键 4

TryRedistribute - 重分配失败

删除完成

八、继续删除键 5 - 合并

场景：删除键 5

进入 TryMerge

九、Merge - 实际执行合并

十、递归调用 RemoveEntry 删除父节点中的键

场景：从父节点删除键 6

合并完成

十一、继续删除键 6 - 树高度降低

场景：删除键 6

最终状态

十二、总结：删除操作的核心逻辑

task2: 重建元组和扫描算子

路径 1: UPDATE 路径 (`rid_opt.has_value() == true`)

路径 2: INSERT 路径 (`rid_opt.has_value() == false`)

二、`RemoveEntry` - 删除入口函数

三、继续删除键 `2`

四、继续删除键 `3` - 触发修复

五、`TryRedistribute` - 尝试重分配

六、`Redistribute` - 实际执行重分配

七、继续删除键 `4` - 触发合并

场景：删除键 `4`

`TryRedistribute` - 重分配失败

八、继续删除键 `5` - 合并

场景：删除键 `5`

进入 `TryMerge`

九、`Merge` - 实际执行合并

十、递归调用 `RemoveEntry` 删除父节点中的键

场景：从父节点删除键 `6`

十一、继续删除键 `6` - 树高度降低

场景：删除键 `6`