在大数据 lakehouse 架构中，数据布局直接影响查询引擎的裁剪效率。传统上，我们依赖单列排序或静态分区来组织数据文件，但这种方法在多维范围过滤场景下往往力不从心。Qbeast 提出的 OTree 有序空间索引提供了一种新的思路：通过递归空间划分将数据映射到多维超立方体中，使物理存储本身就具备空间局部性，从而在不需要查询计划器感知索引的情况下实现更高效的数据裁剪。
OTree 核心算法：递归空间划分
OTree 的设计目标非常明确：一是实现真正的多维索引，二是支持高效的数据采样。与传统 R-tree 在读取时构建索引结构不同，OTree 在写入时就决定了数据的物理布局，整个索引即数据本身。
递归空间划分是 OTree 的基础技术。对于一个使用 n 个列构建索引的数据集，算法会构建一个 n 维向量空间，最初包含所有数据的根立方体（root cube）会递归地划分为 $2^n$ 个等大小的非重叠子空间。每个立方体都有一个预定义的容量阈值（capacity），当立方体中包含的元素数量超过该阈值时，就会触发进一步的划分 —— 在所有维度上同时将空间范围减半，直到所有立方体的大小都不超过预设容量为止。
以两个索引列 x 和 y 为例，假设每个立方体的容量为 2。初始状态下，根立方体包含超过两个元素，因此被划分为四个等大小的子立方体。算法会继续对仍然超标的子立方体进行划分，直到每个叶子立方体都满足容量约束。这种划分方式确保了数据在多维空间中的均匀分布，同时也为后续的范围查询提供了天然的裁剪依据。
多维索引与 Iceberg 查询优化的关联
Iceberg 作为开放表格式，其元数据层维护了数据文件的统计信息（最小值、最大值）用于查询裁剪。然而，传统统计信息仅针对单列设计，当查询涉及多个列的范围过滤时，单列统计往往无法有效裁剪不相关的数据文件。例如，一个查询同时过滤 "country = 'US' AND price BETWEEN 100 AND 200 AND year = 2024"，即使 country 和 year 列的统计信息能够定位到部分文件，price 列的范围过滤仍然需要扫描文件内容才能判断。
OTree 通过多维空间划分解决了这一难题。当数据按照 OTree 布局写入时，物理上相邻的文件对应着多维空间中的相邻区域。这意味着涉及多个列的范围查询可以充分利用空间局部性：查询条件所覆盖的多维空间区域直接对应到需要读取的文件集合，而不需要逐个文件检查其统计信息。
这种优化对查询引擎是透明的。Spark、Flink、Trino 等引擎在读取 Iceberg 表时，仍然使用标准的统计信息和布隆过滤器进行初步裁剪；OTree 布局则在更深层次上提供了更精细的数据局部性。写入端使用 Qbeast 提供的 Spark DataSource 或维护任务来应用 OTree 布局，读取端无需任何修改即可受益。
与 R-tree 的理论对比
R-tree 是最经典的空间索引结构，通过最小外接矩形（MBR）组织数据，支持动态插入和删除。在理论上，R-tree 特别适合点查询和范围查询，其树形结构能够在查询时快速定位相关的叶子节点。然而，R-tree 在大数据 lakehouse 场景下面临几个核心挑战。
首先是写入放大的问题。R-tree 需要在每次写入时更新树结构并维护 MBR 信息，在大规模批量写入场景下会产生显著的计算开销。其次，R-tree 的查询优化依赖于查询计划器在运行时理解索引结构，而 Iceberg 等开放表格式的设计哲学是让读取端保持简单 —— 元数据层只暴露统计信息，不直接暴露索引结构。第三，R-tree 针对几何查询优化，但 lakehouse 中的 "空间" 是多维属性空间，两者的查询模式存在差异。
OTree 的核心优势在于将索引与数据布局合一。写入时通过递归划分确定数据的物理位置，读取时利用文件边界与多维空间的对应关系实现高效裁剪。由于不需要在读取时构建或遍历额外的索引结构，OTree 的查询开销与元数据扫描相当。同时，OTree 的空间划分是确定性的，文件边界直接对应多维空间区域，这使得元数据统计的精度更高。
需要指出的是，目前没有公开的权威基准测试直接对比 OTree 与 R-tree 在真实 lakehouse 工作负载下的性能表现。实际性能取决于数据分布、查询模式、维度选择等多种因素。R-tree 在相对静态的空间数据集上经过多年验证，其实现成熟稳定；而 OTree 作为新兴方案，在动态演化的 lakehouse 数据上更具潜力。
工程实现关键参数
在生产环境中部署 OTree，需要理解几个核心参数的意义和调优策略。
容量参数（desiredCubeSize）控制了每个立方体能够容纳的最大元素数量。较小的容量会产生更深的树形结构和更多的文件数量，从而提供更精细的裁剪粒度，但会增加元数据开销和文件数量；较大的容量则相反。建议根据单文件大小目标来反推该参数，例如目标文件大小为 128MB，假设每行数据 1KB，则 desiredCubeSize 可设置为约 130000。
权重参数（weight）是 OTree 实现高效采样的关键。每个写入的元素都会被分配一个均匀分布的随机整数权重，立方体的 maxWeight 定义了该立方体包含的数据集比例。在读取时，通过设置目标采样比例 f，算法从根节点开始深度优先遍历，遇到 maxWeight 大于 f 的立方体时停止下沉，转而检查同级的兄弟立方体来确定读取范围。这种机制使得采样操作无需扫描全量数据即可获得统计上具有代表性的样本。
维度选择直接影响索引效果。OTree 的多维划分在所有维度上同时进行，因此选择哪些列作为索引列至关重要。最佳实践是选择查询过滤中最频繁参与范围条件的列作为索引列，同时避免选择高基数、低选择性的列。维度数量越多，划分的粒度越细，但树深度也会增加，建议根据实际查询模式选择 2 到 5 个维度。
数据演化是另一个需要关注的因素。OTree 的布局效果依赖于数据在多维空间中的稳定分布。如果底层数据的分布特性发生显著变化（例如新增了大量原本不存在的维度值区间），原有的空间划分可能不再是最优的。此时需要运行维护任务来重新组织数据布局，类似于传统表格式的压缩或重写操作。
实践建议与监控要点
在生产环境中采用 OTree 索引，建议从以下几个方面入手。首先是增量验证：在小规模数据集上验证 OTree 布局对目标查询模式的改善效果，重点观察涉及多列范围过滤的查询的扫描数据量变化。其次是容量规划：根据预期的数据增长速率和查询模式，合理设置 desiredCubeSize 和目标文件大小，确保元数据层的文件数量保持在可管理范围内。第三是监控布局质量：定期检查立方体的深度分布、文件大小分布以及采样操作的精确度，及时发现布局退化的迹象。
OTree 为 lakehouse 场景下的多维查询优化提供了一种新的思路：通过在写入时确定数据的空间布局，使物理存储本身就具备索引能力。虽然目前缺乏大规模生产环境的公开案例，但其核心理念 —— 让数据布局成为索引 —— 值得在特定场景下进行探索和实践。