解析电信天翼云OpenTeleDB XBtree索引：原位更新原理与Undo机制

Xbtree是XStore存储引擎的索引组件，专为原位更新设计。它重新设计了传统PostgreSQL的B-tree索引，支持索引项的原位更新，通过Undo机制管理版本信息，解决了传统索引空间膨胀和垃圾回收性能波动问题。

数据结构设计

索引元组格式

Xbtree扩展了传统索引元组，增加了事务和Undo信息：

typedef struct XBTreeIndexTupleData {
    FullTransactionId modified_xid;  // 修改该索引项的事务ID
    UndoRecPtr urec;                 // 指向Undo记录的指针
} XBTreeIndexTupleData;

索引项状态管理

Xbtree定义了索引项的两种状态：

#define LP_INDEX_DELETED 2      // 已删除状态
#define LP_INDEX_INSERTED LP_NORMAL  // 已插入状态

原位更新机制

插入操作

在插入时，Xbtree为索引项预留Undo空间：

bool xbtinsert(Relation rel, Datum *values, bool *isnull, ItemPointer ht_ctid,
               Relation heapRel, IndexUniqueCheck checkUnique, bool indexUnchanged, IndexInfo *indexInfo)
{
    // 生成索引元组
    itup = index_form_tuple(RelationGetDescr(rel), values, isnull);
    itup->t_tid = *ht_ctid;

    // 为xbtree undo预留空间
    newsize = IndexTupleSize(itup) + sizeof(FullTransactionId) + sizeof(UndoRecPtr);
    newsize = MAXALIGN(newsize);
    IndexTupleSetSize(itup, newsize);

    result = _xbt_doinsert(rel, itup, checkUnique, heapRel);
}

你是不是曾好奇为什么xbtree索引会比普通btree索引大一些？看看下面的实际数据对比就清楚了。同样是500万条记录：

postgres=# \di+
                                                              List of relations
 Schema |       Name        | Type  |  Owner   |    Table    | Persistence | Access method |  Size  | Description
--------+-------------------+-------+----------+-------------+-------------+---------------+--------+-------------
 public | tbl_heap_pkey     | index | postgres | tbl_heap    | unlogged    | btree         | 107 MB |
 public | tbl_xstore_pkey   | index | postgres | tbl_xstore  | unlogged    | xbtree        | 194 MB |
(2 rows)

删除操作

删除操作通过标记索引项为删除状态实现原位更新：

bool xbtdelete(Relation rel, Datum *values, bool *isnull, ItemPointer heap_tid, bool is_dead)
{
    IndexTuple itup = index_form_tuple(RelationGetDescr(rel), values, isnull);
    itup->t_tid = *heap_tid;
    ret = _xbt_dodelete(rel, itup, is_dead);
}

可见性判断机制

版本选择器

Xbtree定义了版本选择器枚举：

typedef enum {
    XBTREEVERSION_NONE,      // 无可见版本
    XBTREEVERSION_CURRENT,   // 当前版本可见
    XBTREEVERSION_OLDER,     // 需要检查更旧版本
    XBTREEVERSION_CHECK_CID  // 需要检查命令ID
} XBTreeVersionSelector;

可见性判断流程

bool _xbt_tuple_satisfies(Page page, Snapshot snapshot, BlockNumber blk, OffsetNumber offnum)
{
    // 获取索引项操作类型
    op = xbtree_oper_from_lp(item);
    xbt_tuple = (XBTreeIndexTuple) XbtreeIndexGetTuple(itup);

    // 版本选择
    selector = xbtree_tuple_version_select(op, snapshot, xbt_tuple->modified_xid);

    // 根据选择器结果决定可见性
    if (selector == XBTREEVERSION_OLDER)
        is_visible = xbtree_get_tuple_from_undo(xbt_tuple->urec, xbt_tuple, snapshot, cid);
    else if (selector == XBTREEVERSION_CURRENT)
        is_visible = true;
    else
        is_visible = false;
}

Undo和回滚机制

Undo操作类型

Xbtree支持两种主要的Undo操作：

switch (undotype) {
case UNDO_XBTREE_INSERT:
        undo_res = execute_undo_insert_xbtree(relation, buffer, undorecord, &target_buf, &target_offset);
        break;
case UNDO_XBTREE_DELETE:
        undo_res = execute_undo_delete_xbtree(relation, undorecord, &target_buf, &target_offset);
        break;
}

插入回滚实现

static int execute_undo_insert_xbtree(Relation rel, Buffer buffer, UnpackedUndoRecord *urec,
                                       Buffer* tarBuffer, Offset* tarOffset)
{
    // 从Undo记录恢复原始索引元组
    StringInfoData *index_tuple_data = GetUndoRecordRawdata(urec);
    itup = (IndexTuple) index_tuple_data->data;

    // 搜索并删除对应的索引项
    itupKey = _xbt_mkscankey(rel, itup);
    (void) _xbt_search(rel, itupKey, tarBuffer, BT_WRITE, false);
    *tarOffset = _xbt_binsrch(rel, itupKey, *tarBuffer);
}

WAL日志系统

日志记录类型

Xbtree定义了多种WAL记录类型：

#define XLOG_XBTREE_INSERT_LEAF 0x00    // 叶子页插入
#define XLOG_XBTREE_DELETE 0x10         // 删除操作
#define XLOG_XBTREE_PRUNE_PAGE 0x20     // 页面清理
#define XLOG_XBTREE_UNDO 0x30           // Undo操作

删除日志记录

static void xbtree_xlog_delete(XLogReaderState *record)
{
    // 准备Undo记录
    urecptr = _xbt_redo_undo_delete(record, blkno);

    // 更新索引页
    if (XLogReadBufferForRedo(record, 0, &buffer) == BLK_NEEDS_REDO) {
        IndexItemIdSetDeleted(item);
        uxid->modified_xid = XLogRecGetFullXid(record);
        uxid->urec = urecptr;
        opaque->active_count--;
    }
}

访问方法接口

索引访问方法注册

Xbtree通过 xbthandler 函数注册索引访问方法：

Datum xbthandler(PG_FUNCTION_ARGS)
{
    IndexAmRoutine *amroutine = makeNode(IndexAmRoutine);

    amroutine->amstrategies = BTMaxStrategyNumber;
    amroutine->amsupport = BTNProcs;
    amroutine->amcanunique = true;
    amroutine->amcanmulticol = true;

    // 设置回调函数
    amroutine->ambuild = xbtbuild;
    amroutine->aminsert = xbtinsert;
    amroutine->amdelete = xbtdelete;
    amroutine->ambeginscan = xbtbeginscan;
    amroutine->amgettuple = xbtgettuple;
}

与传统B-tree的区别

特性	传统B-tree	Xbtree
更新方式	创建新版本	原位更新
版本管理	事务ID标记	Undo链管理
空间管理	需要VACUUM清理	自动回收
垃圾回收	周期性扫描	按需清理
性能特征	波动较大	稳定可控

技术优势

1. 空间效率：原位更新避免索引膨胀，空间利用率高。
2. 性能稳定：消除垃圾回收导致的性能波动。
3. 运维简化：无需手动维护索引，自动管理空间。

总结

Xbtree是XStore存储引擎的核心创新之一，通过重新设计索引的数据结构和更新机制，实现了真正的原位更新。其核心思想是将版本从事务ID标记转向Undo链管理，既保持了B-tree的高效查询特性，又解决了传统索引的空间膨胀和性能波动问题。这种设计特别适合高并发OLTP场景，为数据库提供了更稳定和可预测的性能表现。

想了解更多数据库内核技术细节或参与讨论，欢迎访问 云栈社区 的数据库技术板块。