XBtree 索引原理详解

本期播客

电信天翼云 OpenTeleDB XBtree 索引原理详解

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

数据结构设计

索引元组格式

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

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

索引项状态管理

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

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

原位更新机制

插入操作

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

boolxbtinsert(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万 记录, 对比btree, xbtree  

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)  

删除操作

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

boolxbtdelete(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定义了版本选择器枚举：

typedefenum {  
    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);  
elseif (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;  
}  

插入回滚实现

staticintexecute_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操作  

删除日志记录

staticvoidxbtree_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的区别

技术优势

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

Notes

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