Я пытаюсь создать базу данных позиций с началом и остановкой: в основном линии на оси 1D. Я хочу эффективно запросить все позиции, которые перекрывают данный интервал. В традиционной таблице запрос потребует двух неравенств, поэтому он не может быть проиндексирован. Вы также можете использовать индекс R-Tree, но они, похоже, предназначены для запросов многомерного диапазона. Есть ли более эффективный способ хранения строк на оси?SQLite - Существуют ли альтернативы rtree для индексирования строк по оси?
Если кому-то интересно, база данных должна хранить интервалы генома. Вот пример таблицы:
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-дерева не являются идеальными для нашей реализации, так что мне интересно, если есть какая-либо альтернатива ...
Почему вы говорите, что R-деревья не оптимальны для вашей реализации? Хотя они могут обрабатывать многомерные данные, вы можете использовать их и для одномерных данных. – btilly
Извините, должен был быть расширен. Я написал несколько тестов традиционных индексов rtree v, а rtree - плохо. Наш прецедент очень уникален по нескольким причинам: 1) Большинство (~ 90%) вариантов - это одиночные точки - запуск и остановка одинаковы. 2) Таблицы действительно большие - десятки миллионов строк. 3) Позиции являются целыми числами, а не плавают. 4) варианты фактически хранятся по положению хромосомы И, поэтому мы делаем много обработки после запроса. Итак, я искал, есть ли другие варианты, такие как дерево интервалов. –
Я понимаю, что это больше двух лет, но мне было интересно, если вы пробовали вариант rtree_i32 R * Tree в sqlite, который хранит значения как int, а не float. – infogulch