sql - SQLite - 是否有 rtree 的替代品来索引轴上的线？

Question

我正在尝试创建一个带有开始和停止的位置数据库：基本上是一维轴上的线。我想有效地查询与给定间隔重叠的所有位置。在传统的表中，查询需要两个不等式，因此不能被索引。您也可以使用 R-Tree 索引，但它们似乎是为多维范围查询而设计的。有没有更有效的方法在轴上存储线？

如果有人好奇，该数据库将存储基因组间隔。这是一个示例表：

CREATE TABLE lines (id INTEGER PRIMARY KEY, start INTEGER, stop INTEGER);

这样做的基本方法是：

SELECT * FROM lines WHERE start <= <end of interval> AND stop >= <start of interval>;

同样，这真的很慢并且无法被索引。R-Tree 的工作方式如下：

CREATE VIRTUAL TABLE lines_index USING RTREE (id, start, stop);
SELECT * from lines_index WHERE start <= <end of interval> AND stop >= <start of interval>;

R-Trees 并不适合我们的实现，所以我想知道是否有任何替代方案......

Answer 1

首先，尽管您不能完全索引它，但您可以仅按开始间隔进行索引。如果 90% 的间隔都有 start=stop，那应该会有很大的改进。唯一的放缓将是非常长的间隔。