XBtree vs Btree

本期播客

XBtree vs 传统 B-tree

XBtree vs Btree 核心差异概览

数据结构设计差异

传统B-tree结构

传统B-tree使用标准的索引元组格式，依赖PostgreSQL的MVCC机制进行版本管理  。

Xbtree扩展结构

Xbtree在传统索引元组基础上扩展了事务和Undo信息：

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

同时定义了索引项状态管理：

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

更新机制对比

传统B-tree更新流程

1. 插入新版本索引项
2. 旧版本标记为dead
3. 等待VACUUM清理dead版本
4. 空间回收依赖后台进程

Xbtree原位更新流程

Xbtree通过原位更新机制实现高效的空间管理：

// 删除操作 - 原位标记  
staticvoid _xbt_deleteonpage(Relation rel, Buffer buf, OffsetNumber offset, bool is_dead)  
{  
// 准备Undo记录  
    urec_ptr = _xbt_prepare_undo_delete(...);  

// 原位更新状态  
    xbt_tuple->modified_xid = xid;  
    xbt_tuple->urec = urec_ptr;  
    IndexItemIdSetDeleted(item);  

// 更新活跃计数  
    opaque->active_count--;  
}  

可见性判断机制

版本选择器设计

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

性能和运维优势

空间效率提升

Xbtree通过原位更新技术解决了传统索引的空间膨胀问题，不需要依赖垃圾回收机制  。

性能稳定性

消除了垃圾回收导致的性能波动，提供更稳定可预测的性能表现  。

运维简化

无需手动维护索引和调优autovacuum参数，显著降低运维复杂性  。

适用场景对比

传统B-tree适用场景

• 读多写少的负载
• 对空间膨胀不敏感的场景
• 运维资源充足的環境

Xbtree适用场景

• 高并发OLTP场景
• 写密集型应用
• 要求性能稳定的业务系统
• 运维资源有限的环境

Xbtree 是 XStore存储引擎的核心创新，通过重新设计索引的数据结构和更新机制，在保持B-tree高效查询特性的同时，解决了传统索引的空间膨胀和性能波动问题。这种设计特别适合现代高并发OLTP应用场景，为数据库提供了更稳定和可预测的性能表现。

虽然PG 设计了HOT来避免传统btree膨胀, 但这些情况没用

为什么有HOT，B-tree索引还是会膨胀？

核心原因

HOT（Heap Only Tuples）机制虽然能显著减少索引膨胀，但并不能完全解决索引膨胀问题，主要原因如下：

1. HOT的适用条件限制

HOT只在满足严格条件时才能生效  ：

• 不修改索引列：更新不能修改任何被索引引用的列
• 页面空间充足：原页面必须有足够空间存放新版本

// HOT更新条件检查  
if (use_hot_update)  
{  
/* Mark the old tuple as HOT-updated */
    HeapTupleSetHotUpdated(&oldtup);  
/* And mark the new tuple as heap-only */
    HeapTupleSetHeapOnly(heaptup);  
}  

HOT无法触发的情况

主要限制条件

HOT（Heap Only Tuples）优化在以下情况下无法触发：

1. 更新索引列时

当更新任何被非汇总索引引用的列时，HOT优化完全不适用  ：

If any columns that are included by non-summarizing indexes are updated,  
the HOT optimization is not applied, and the new tuple is inserted into  
all indexes of the table.  

这意味着即使只更新一个索引列，也会导致所有索引都需要创建新条目。

2. 页面空间不足时

当原页面没有足够空间存放新版本元组时，无法进行HOT更新  ：

• 新元组必须能放入包含旧元组的同一页面
• 如果空间不足，新元组会被放置到其他页面
• 跨页面的更新会破坏HOT链

3. 汇总索引的特殊情况

对于汇总索引（如BRIN），虽然允许HOT继续，但仍需要更新索引本身  ：

• 汇总索引不包含单个元组的引用
• 但仍需要通知索引新的列数据
• 这是一种部分HOT优化

实现层面的检查

在heapam.c中的实际检查逻辑  ：

if (!bms_overlap(modified_attrs, hot_attrs))  
{  
    use_hot_update = true;  

// 检查是否需要更新汇总索引  
if (bms_overlap(modified_attrs, sum_attrs))  
        summarized_update = true;  
}  

HOT链断裂的情况

1. 跨页面更新

当HOT更新链需要跨越页面时，链会断裂  ：

• HOT链被限制在单个页面内
• 跨页面更新会创建新的索引条目
• 后续更新无法利用HOT优化

2. 索引列更新

一旦更新了索引列，HOT链就会结束  ：

• 最后一个成员有常规的t_ctid链接
• 不标记为HEAP_HOT_UPDATED
• 后续更新可能成为新HOT链的根

实际影响

1. 索引膨胀

更新索引列会导致所有索引膨胀  ：

• 每次更新都会为每个索引创建新条目
• 包括未被"逻辑修改"的索引
• 旧条目需要等待VACUUM清理

2. 性能影响

HOT失效会导致：

• 索引大小增长
• 查询性能下降
• VACUUM负担增加

HOT机制虽然有效，但有严格的适用条件。在高并发OLTP场景中，频繁更新索引列是常见模式，这限制了HOT的效果。XStore的xbtree通过原位更新机制从根本上解决了这个问题，不受这些条件限制。

2. 索引列更新导致膨胀

当更新涉及索引列时，HOT机制完全不适用  ：

If any columns that are included by non-summarizing indexes are updated,  
the HOT optimization is not applied, and the new tuple is inserted into  
all indexes of the table.  

这意味着：

• 每次更新索引列都会为所有索引创建新条目
• 即使某个索引的列没有被修改，也需要创建新条目
• 旧索引条目只能等待VACUUM清理

3. B-tree索引删除机制的限制

B-tree索引的bottom-up删除机制有局限性  ：

• 触发条件限制：只在预期页面分裂时触发
• 删除效率有限：可能无法识别和删除垃圾索引元组
• 依赖启发式算法：某些情况下可能失效

A bottom-up index deletion pass targets suspected  
garbage tuples in a single leaf page based on  
qualitative distinctions involving logical  
rows and versions.  

4. 页面空间利用率问题

即使使用HOT，B-tree索引仍可能因页面空间利用率低而膨胀  ：

if all but a few index keys on a page have  
been deleted, the page remains allocated. Therefore, a usage  
pattern in which most, but not all, keys in each range are eventually  
deleted will see poor use of space.  

具体膨胀场景

1. 频繁更新索引列

-- 假设表有多个索引  
CREATETABLE t (idint, col1 int, col2 int, col3 int);  
CREATEINDEX idx1 ON t(col1);  
CREATEINDEX idx2 ON t(col2);  
CREATEINDEX idx3 ON t(col3);  

-- 更新col1会影响所有索引，即使只修改了col1  
UPDATE t SET col1 = col1 + 1WHEREid = 1;  

2. 部分删除模式

当删除模式导致页面只剩少量索引条目时，页面空间利用率低，但页面不会被释放  。

3. HOT链断裂

当HOT更新链跨页面或更新索引列时，HOT链断裂，后续更新无法利用HOT优化  。

解决方案

1. 优化更新模式

• 尽量批量更新非索引列
• 避免频繁更新索引列
• 合理设计索引策略

2. 定期维护

• 定期执行REINDEX重建索引
• 调整autovacuum参数
• 监控索引大小增长

3. 使用XStore

XStore的xbtree通过原位更新机制从根本上解决了索引膨胀问题  。

HOT机制是PostgreSQL的重要优化，但它有严格的适用条件。在实际应用中，特别是高并发OLTP场景，索引膨胀仍然是需要关注的问题。XStore通过重新设计索引更新机制，提供了更根本的解决方案。