SQLite - есть ли альтернативы rtree для индексации строк на оси?

Question

Я пытаюсь создать базу данных позиций со стартом и стопом: в основном это линии на 1D оси.Я хочу эффективно запросить все позиции, которые перекрывают данный интервал.В традиционной таблице для запроса потребуются два неравенства, поэтому он не может быть проиндексирован.Вы также можете использовать индекс 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-дерево будет работать так:

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-деревья не идеальны для нашей реализации, поэтому мне интересно, есть ли альтернативы ...

Answer 1

Прежде всего, несмотря на то, что вы не можете полностью проиндексировать его, вы можете индексировать только по интервалу запуска.Если у 90% интервалов есть начало = остановка, это должно значительно улучшить ситуацию.Единственное замедление будет с очень длинными интервалами.