Модуль R-Tree в SQLite: полное руководство по пространственным индексам

Что такое R-Tree и зачем он нужен

R-Tree — это индекс, который эффективно выполняет диапазонные запросы. Он широко используется в геопространственных системах, где записи представлены в виде прямоугольников с заданными минимальными и максимальными координатами по осям X и Y. С помощью R-Tree можно быстро находить все записи, расположенные внутри или пересекающиеся с указанным прямоугольником

Модуль R-Tree можно адаптировать для работы в трехмерной среде, что делает его полезным для компьютерного проектирования (CAD). Он также подходит для диапазонного поиска во временной области. Например, если база данных содержит информацию о времени начала и окончания событий, R-Tree позволяет быстро находить все события, которые проходят в заданном временном интервале, или события, которые начались в течение этого интервала

Концепция R-Tree берёт начало в работе Тони Гуттмана: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. 47-57

Реализация, используемая в SQLite, является усовершенствованием оригинальной идеи Гуттмана, широко известным как «RTrees», описанным Нобертом Бекманном, Хансом-Петером Кригелем, Ральфом Шнайдером и Бернхардом Зегером: The R-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331

По этой теме полезно отдельно посмотреть EXPLAIN QUERY PLAN: план выполнения SQL-запроса в SQLite, чтобы расширить контекст и сравнить подходы

По этой теме полезно отдельно посмотреть Создание Flutter-приложения с SQLite, BLoC и Streams, чтобы расширить контекст и сравнить подходы

Компиляция модуля R*Tree

Исходный код модуля RTree для SQLite включён в состав амальгамы (amalgamation). Однако в зависимости от параметров конфигурации и конкретной версии SQLite он может быть включён или не включён по умолчанию. Чтобы гарантировать включение модуля RTree, достаточно выполнить компиляцию с определённым макросом препроцессора C — SQLITE_ENABLE_RTREE

Во многих компиляторах это достигается добавлением опции -DSQLITE_ENABLE_RTREE=1 в командную строку компилятора

Использование модуля R*Tree

Модуль RTree в SQLite реализован в виде виртуальной таблицы (virtual table). Каждый индекс RTree представляет собой виртуальную таблицу с нечётным числом столбцов от 3 до 11. Первый столбец всегда является 64-битным знаковым целочисленным первичным ключом. Остальные столбцы образуют пары — по одной паре на каждое измерение, — содержащие соответственно минимальное и максимальное значения для этого измерения

Для RTree количество столбцов в виртуальной таблице всегда нечётное и варьируется от 3 до 11: одномерный RTree имеет 3 столбца, двумерный — 5, трёхмерный — 7, четырёхмерный — 9, пятимерный — 11

Реализация RTree в SQLite не поддерживает RTree с размерностью более 5

Первый столбец R*Tree в SQLite аналогичен столбцу целочисленного первичного ключа в обычной таблице SQLite. В нём может храниться только 64-битное знаковое целое число. Вставка значения NULL в этот столбец заставляет SQLite автоматически генерировать новое уникальное значение первичного ключа

Если предпринимается попытка вставить в этот столбец любое другое нецелочисленное значение, модуль r-tree молча преобразует его в целое число перед записью в базу данных

Пары столбцов минимальных и максимальных значений хранятся как 32-битные значения с плавающей точкой в виртуальных таблицах rtree или как 32-битные целые числа в таблицах rtree_i32. В отличие от обычных таблиц SQLite, R-Tree строго соблюдает указанные типы данных. Если в любой из этих столбцов попытаются вставить значение другого типа, модуль r-tree автоматически преобразует его в нужный тип перед сохранением новой записи

Создание индекса R*Tree

Новый индекс R*Tree создаётся следующим образом:

CREATE VIRTUAL TABLE <name> USING rtree( <column-names> );

Здесь <name> — это имя, которое ваше приложение выбирает для индекса R*Tree, а <column-names> — разделённый запятыми список от 3 до 11 столбцов. Виртуальная таблица <name> создаёт три теневые таблицы (shadow tables) для фактического хранения своего содержимого. Имена этих теневых таблиц:

<name>_node
<name>_rowid
<name>_parent

Теневые таблицы являются обычными таблицами данных SQLite. При желании вы можете напрямую делать к ним запросы, хотя это вряд ли откроет что-либо особенно полезное. Вы также можете выполнять UPDATE, DELETE, INSERT или даже DROP для теневых таблиц, однако это приведёт к повреждению вашего индекса RTree. Поэтому лучше просто игнорировать теневые таблицы. Достаточно знать, что в них хранится информация вашего индекса RTree, и оставить всё как есть

В качестве примера рассмотрим создание двумерного индекса R*Tree для использования в пространственных запросах:

CREATE VIRTUAL TABLE demo_index USING rtree( id, -- Целочисленный первичный ключ minX, maxX, -- Минимальная и максимальная координата X minY, maxY -- Минимальная и максимальная координата Y
);

#### Подробности об именовании столбцов

В аргументах rtree в операторе CREATE VIRTUAL TABLE имена столбцов берутся из первого токена каждого аргумента. Все последующие токены в каждом аргументе молча игнорируются

Это означает, например, что если вы попытаетесь задать столбцу сродство типа (type affinity) или добавить ограничение, такое как UNIQUE, NOT NULL или DEFAULT, эти дополнительные токены принимаются как допустимые, но не изменяют поведение rtree. В виртуальной таблице RTREE первый столбец всегда имеет сродство типа INTEGER, а все остальные столбцы данных имеют сродство типа REAL. В виртуальной таблице RTREE_I32 все столбцы имеют сродство типа INTEGER

Рекомендуемая практика — опускать любые дополнительные токены в спецификации rtree. Пусть каждый аргумент rtree представляет собой единственную обычную метку, являющуюся именем соответствующего столбца, а все остальные токены из списка аргументов опускаются

Заполнение индекса R*Tree

Обычные команды INSERT, UPDATE и DELETE работают с индексом RTree точно так же, как и с обычными таблицами. Поэтому, чтобы вставить некоторые данные в наш образцовый индекс RTree, можно сделать следующее:

INSERT INTO demo_index VALUES
(28215, -80.781227, -80.604706, 35.208813, 35.297367),
(28216, -80.957283, -80.840599, 35.235920, 35.367825),
(28217, -80.960869, -80.869431, 35.133682, 35.208233),
(28226, -80.878983, -80.778275, 35.060287, 35.154446),
(28227, -80.745544, -80.555382, 35.130215, 35.236916),
(28244, -80.844208, -80.841988, 35.223728, 35.225471),
(28262, -80.809074, -80.682938, 35.276207, 35.377747),
(28269, -80.851471, -80.735718, 35.272560, 35.407925),
(28270, -80.794983, -80.728966, 35.059872, 35.161823),
(28273, -80.994766, -80.875259, 35.074734, 35.172836),
(28277, -80.876793, -80.767586, 35.001709, 35.101063),
(28278, -81.058029, -80.956375, 35.044701, 35.223812),
(28280, -80.844208, -80.841972, 35.225468, 35.227203),
(28282, -80.846382, -80.844193, 35.223972, 35.225655);

Приведённые выше записи представляют собой ограничивающие прямоугольники (bounding boxes) — долготу и широту — для 14 почтовых индексов вблизи Шарлотт, Северная Каролина. В реальной базе данных таких записей могут быть тысячи, миллионы или миллиарды, но этой небольшой выборки из 14 строк достаточно для иллюстрации идей

Запросы к индексу R*Tree

Любой допустимый запрос будет работать с индексом RTree. Реализация RTree просто делает некоторые виды запросов особенно эффективными. Запросы по первичному ключу выполняются эффективно:

SELECT * FROM demo_index WHERE id=28269;

Конечно, обычная таблица SQLite также эффективно выполняет запрос по целочисленному первичному ключу, поэтому предыдущий пример не является показательным. Главная причина использования R*Tree заключается в том, что он позволяет эффективно выполнять диапазонные запросы по диапазонам координат. Например, главный офис проекта SQLite расположен по координатам 35.37785, -80.77470. Чтобы найти, какие почтовые индексы могут обслуживать этот офис, можно написать:

SELECT id FROM demo_index WHERE minX<=-80.77470 AND maxX>=-80.77470 AND minY<=35.37785 AND maxY>=35.37785;

Приведённый выше запрос быстро найдёт все почтовые индексы, содержащие главный офис SQLite в своём ограничивающем прямоугольнике, даже если RTree содержит множество записей. Предыдущий пример — это запрос типа «содержится внутри» (contained-within). RTree также поддерживает запросы типа «пересечение» (overlap). Например, чтобы найти все ограничивающие прямоугольники почтовых индексов, пересекающихся с почтовым индексом 28269:

SELECT A.id FROM demo_index AS A, demo_index AS B WHERE A.maxX>=B.minX AND A.minX<=B.maxX AND A.maxY>=B.minY AND A.minY<=B.maxY AND B.id=28269;

Этот второй запрос найдёт как запись 28269 (поскольку каждый ограничивающий прямоугольник пересекается сам с собой), так и любые другие почтовые индексы, достаточно близкие к 28269, чтобы их ограничивающие прямоугольники пересекались

Обратите внимание, что для эффективного поиска по индексу вовсе не обязательно ограничивать все координаты в индексе R*Tree. Например, может потребоваться запросить все объекты, пересекающиеся с 35-й параллелью:

SELECT id FROM demo_index WHERE maxY>=35.0 AND minY<=35.0;

Но, вообще говоря, чем больше ограничений задано для модуля R*Tree и чем меньше ограничивающий прямоугольник, тем быстрее будут возвращены результаты

Ошибка округления и точность координат

По умолчанию координаты хранятся в R*Tree с использованием 32-битных значений с плавающей точкой. Когда координата не может быть точно представлена 32-битным числом с плавающей точкой, координаты нижней границы округляются вниз, а координаты верхней границы — вверх. Таким образом, ограничивающие прямоугольники могут быть немного больше указанных, но никогда не будут меньше

Это именно то, что требуется для более распространённых запросов типа «пересечение», когда приложение хочет найти каждую запись в R*Tree, пересекающуюся с запрашиваемым ограничивающим прямоугольником

Округление ограничивающих прямоугольников записей наружу может привести к появлению нескольких лишних записей в запросе на пересечение, если край ограничивающего прямоугольника записи совпадает с краем запрашиваемого ограничивающего прямоугольника. Но запрос на пересечение никогда не пропустит допустимую запись таблицы

Однако для запроса типа «содержится внутри» округление ограничивающих прямоугольников наружу может привести к исключению некоторых записей из результирующего набора, если край ограничивающего прямоугольника записи совпадает с краем запрашиваемого ограничивающего прямоугольника. Чтобы защититься от этого, приложения должны немного расширять свои запрашиваемые прямоугольники типа «содержится внутри» (на 0.000012%), округляя нижние координаты вниз, а верхние координаты вверх по каждому измерению

Одновременное чтение и запись

По природе алгоритма Гуттмана R-Tree любая запись может кардинально реструктурировать дерево и в процессе изменить порядок обхода узлов. По этой причине, как правило, невозможно изменять R-Tree в середине выполнения запроса к нему. Попытки сделать это завершатся ошибкой SQLITE_LOCKED «database table is locked»

Так, например, предположим, что приложение выполняет один запрос к R-Tree следующего вида:

Затем для каждого возвращённого значения id предположим, что приложение создаёт оператор UPDATE следующего вида и привязывает возвращённое значение id к параметру ?1:

UPDATE demo_index SET maxY=maxY+0.5 WHERE id=?1;

В таком случае UPDATE может завершиться ошибкой SQLITE_LOCKED. Причина в том, что начальный запрос не завершил выполнение. Он запоминает своё место в середине обхода R-Tree. Поэтому обновление R-Tree недопустимо, поскольку это нарушило бы обход

Это ограничение касается только расширения R-Tree. Обычные таблицы в SQLite способны одновременно читать и записывать данные. Другие виртуальные таблицы могут (или не могут) также обладать этой возможностью. И R-Tree может в некоторых обстоятельствах выглядеть так, будто читает и записывает одновременно, если ему удаётся надёжно завершить запрос до начала обновления

Но не стоит рассчитывать на это для каждого запроса. Вообще говоря, лучше всего избегать одновременного выполнения запросов и обновлений одного и того же R-Tree

Если действительно необходимо обновить R-Tree на основе сложных запросов к тому же R-Tree, лучше всего сначала выполнить сложные запросы и сохранить результаты во временной таблице, а затем обновить R-Tree на основе значений, сохранённых во временной таблице

Эффективное использование R*Tree

Для версий SQLite до 3.24.0 (2018-06-04) единственная информация, которую индекс RTree хранит об объекте, — это его целочисленный идентификатор и ограничивающий прямоугольник. Дополнительная информация должна храниться в отдельных таблицах и связываться с индексом RTree через первичный ключ. Для приведённого выше примера можно создать вспомогательную таблицу следующим образом:

CREATE TABLE demo_data( id INTEGER PRIMARY KEY, -- первичный ключ objname TEXT, -- имя объекта objtype TEXT, -- тип объекта boundary BLOB -- подробная граница объекта
);

В этом примере поле demo_data.boundary предназначено для хранения некоего двоичного представления точных границ объекта. Индекс RTree хранит только выровненный по осям прямоугольный контур объекта. Граница RTree — это лишь приближение истинной границы объекта

Поэтому обычно происходит следующее: индекс R*Tree используется для сужения поиска до списка объектов-кандидатов, после чего для каждого кандидата выполняются более детальные и ресурсоёмкие вычисления, чтобы определить, действительно ли кандидат соответствует критериям поиска

Ключевой момент: индекс R*Tree обычно не даёт точного ответа, а лишь сокращает множество потенциальных ответов с миллионов до десятков

Предположим, что поле demo_data.boundary хранит некое проприетарное описание сложной двумерной границы почтового индекса, и предположим, что приложение использовало интерфейс sqlite3_create_function() для создания определяемой приложением функции contained_in(boundary, lat, long), которая принимает объект demo_data.boundary, широту и долготу и возвращает true или false в зависимости от того, находится ли точка lat/long внутри границы

Можно считать, что contained_in() — относительно медленная функция, которую нежелательно вызывать слишком часто. Тогда эффективный способ найти конкретный почтовый индекс для главного офиса SQLite — выполнить запрос следующего вида:

SELECT objname FROM demo_data, demo_index WHERE demo_data.id=demo_index.id AND contained_in(demo_data.boundary, 35.37785, -80.77470) AND minX<=-80.77470 AND maxX>=-80.77470 AND minY<=35.37785 AND maxY>=35.37785;

Обратите внимание на то, как работает приведённый выше запрос: индекс R*Tree выполняется во внешнем цикле для поиска записей, чей ограничивающий прямоугольник содержит главный офис SQLite. Для каждой найденной строки SQLite ищет соответствующую запись в таблице demo_data

Затем он использует поле boundary из таблицы demo_data в качестве параметра функции contained_in(), и если эта функция возвращает true, то мы знаем, что искомая координата находится в границах данного почтового индекса

Тот же результат можно получить без использования индекса R*Tree с помощью следующего более простого запроса:

SELECT objname FROM demo_data WHERE contained_in(demo_data.boundary, 35.37785, -80.77470);

Проблема этого последнего запроса в том, что он должен применять функцию contained_in() ко всем записям в таблице demo_data. Использование RTree в предпоследнем запросе сокращает количество вызовов функции contained_in() до небольшого подмножества всей таблицы. Индекс RTree сам по себе не нашёл точного ответа — он лишь ограничил пространство поиска

Вспомогательные столбцы

Начиная с версии SQLite 3.24.0 (2018-06-04), таблицы r-tree могут иметь вспомогательные столбцы (auxiliary columns), хранящие произвольные данные. Вспомогательные столбцы можно использовать вместо вторичных таблиц, таких как demo_data

Вспомогательные столбцы помечаются символом + перед именем столбца. Вспомогательные столбцы должны располагаться после всех столбцов координатных границ. Таблица RTREE может иметь не более 100 столбцов в общей сложности. Иными словами, количество столбцов, включая столбец целочисленного первичного ключа, столбцы координатных границ и все вспомогательные столбцы, должно быть не более 100

Следующий пример демонстрирует таблицу r-tree со вспомогательными столбцами, эквивалентную двум таблицам demo_index и demo_data выше:

CREATE VIRTUAL TABLE demo_index2 USING rtree( id, -- Целочисленный первичный ключ minX, maxX, -- Минимальная и максимальная координата X minY, maxY, -- Минимальная и максимальная координата Y +objname TEXT, -- имя объекта +objtype TEXT, -- тип объекта +boundary BLOB -- подробная граница объекта
);

Объединяя данные о местоположении и связанную информацию в одной таблице, вспомогательные столбцы могут обеспечить более чистую модель и снизить необходимость в объединениях (joins). Например, более раннее объединение между demo_index и demo_data теперь можно записать в виде простого запроса к одной таблице

#### Ограничения вспомогательных столбцов

Для вспомогательных столбцов имеет значение только имя столбца. Тип данных игнорируется. Ограничения, такие как NOT NULL, UNIQUE, REFERENCES или CHECK, также игнорируются. Однако будущие версии SQLite могут начать учитывать тип данных и ограничения, поэтому пользователям вспомогательных столбцов рекомендуется оставлять и то, и другое пустым, чтобы избежать проблем с совместимостью в будущем

R-Tree с целочисленными значениями

Виртуальная таблица по умолчанию (rtree) хранит координаты в виде чисел с плавающей точкой одинарной точности (4 байта). Если требуются целочисленные координаты, объявите таблицу с использованием rtree_i32 вместо этого:

CREATE VIRTUAL TABLE intrtree USING rtree_i32(id,x0,x1,y0,y1,z0,z1);

Таблица rtree_i32 хранит координаты в виде 32-битных знаковых целых чисел. Несмотря на то что значения хранятся в виде целых чисел, виртуальная таблица rtree_i32 всё равно использует вычисления с плавающей точкой внутри как часть алгоритма r-tree

Пользовательские запросы R-Tree

Используя стандартные SQL-выражения в предложении WHERE запроса SELECT, программист может запрашивать все записи R*Tree, которые пересекаются с определённым ограничивающим прямоугольником или содержатся внутри него

Пользовательские запросы RTree, использующие оператор MATCH в предложении WHERE запроса SELECT, позволяют программисту запрашивать набор записей RTree, пересекающихся с произвольной областью или фигурой, а не только с прямоугольником. Эта возможность полезна, например, при вычислении подмножества объектов в R*Tree, видимых из камеры, расположенной в трёхмерном пространстве

Области для пользовательских запросов RTree определяются геометрическими обратными вызовами (geometry callbacks) RTree, реализованными приложением и зарегистрированными в SQLite посредством вызова одного из следующих двух API:

int sqlite3_rtree_query_callback( sqlite3 *db, const char *zQueryFunc, int (*xQueryFunc)(sqlite3_rtree_query_info*), void *pContext, void (*xDestructor)(void*)
);
int sqlite3_rtree_geometry_callback( sqlite3 *db, const char *zGeom, int (*xGeom)(sqlite3_rtree_geometry *, int nCoord, double *aCoord, int *pRes), void *pContext
);

Функция sqlite3_rtree_query_callback() стала доступна начиная с версии SQLite 3.8.5 (2014-06-04) и является предпочтительным интерфейсом. Функция sqlite3_rtree_geometry_callback() — более старый и менее гибкий интерфейс, поддерживаемый для обратной совместимости

Вызов одного из указанных выше API создаёт новую SQL-функцию, имя которой задаётся вторым параметром (zQueryFunc или zGeom). Когда эта SQL-функция появляется в правой части оператора MATCH, а в левой части оператора MATCH находится любой столбец виртуальной таблицы R*Tree, для определения того, пересекается ли конкретный объект или поддерево с нужной областью, вызывается обратный вызов, определённый третьим аргументом (xQueryFunc или xGeom)

Например, следующий запрос может использоваться для поиска всех записей R*Tree, перекрывающихся с окружностью с центром в точке 45.3, 22.9 и радиусом 5.0:

SELECT id FROM demo_index WHERE id MATCH circle(45.3, 22.9, 5.0)

Синтаксис SQL для пользовательских запросов одинаков независимо от того, какой интерфейс — sqlite3_rtree_geometry_callback() или sqlite3_rtree_query_callback() — используется для регистрации SQL-функции. Однако обратные вызовы нового стиля запросов предоставляют приложению больший контроль над ходом выполнения запроса

Устаревший обратный вызов xGeom

Устаревший обратный вызов xGeom вызывается с четырьмя аргументами. Первый аргумент — указатель на структуру sqlite3_rtree_geometry, которая предоставляет информацию о том, как была вызвана SQL-функция. Второй аргумент — количество координат в каждой записи r-tree; оно всегда одинаково для любого конкретного R*Tree

Количество координат равно 2 для одномерного RTree, 4 для двумерного RTree, 6 для трёхмерного R*Tree и так далее. Третий аргумент, aCoord[], — массив из nCoord координат, определяющий ограничивающий прямоугольник для проверки. Последний аргумент — указатель, в который должен быть записан результат обратного вызова

Результат равен нулю, если ограничивающий прямоугольник, определённый aCoord[], полностью находится за пределами области, определённой обратным вызовом xGeom, и ненулевой, если ограничивающий прямоугольник находится внутри области xGeom или перекрывается с ней. Обратный вызов xGeom в норме должен возвращать SQLITE_OK

Если xGeom возвращает что-либо, отличное от SQLITE_OK, запрос r-tree будет прерван с ошибкой

Структура sqlite3_rtree_geometry, на которую указывает первый аргумент обратного вызова xGeom, имеет следующий вид. Одна и та же структура sqlite3_rtree_geometry используется для каждого обратного вызова одного и того же оператора MATCH в одном и том же запросе. Содержимое структуры sqlite3_rtree_geometry инициализируется SQLite и впоследствии не изменяется

Обратный вызов может вносить изменения в элементы pUser и xDelUser структуры по своему усмотрению

typedef struct sqlite3_rtree_geometry sqlite3_rtree_geometry;
struct sqlite3_rtree_geometry { void *pContext; /* Копия pContext, переданного в s_r_g_c() */ int nParam; /* Размер массива aParam */ double *aParam; /* Параметры, переданные SQL-функции геометрии */ void *pUser; /* Пользовательские данные реализации обратного вызова */ void (*xDelUser)(void *);/* Вызывается SQLite для очистки pUser */
};

Член pContext структуры sqlite3_rtree_geometry всегда устанавливается в копию аргумента pContext, переданного в sqlite3_rtree_geometry_callback() при регистрации обратного вызова. Массив aParam[] (размером nParam) содержит значения параметров, переданных SQL-функции в правой части оператора MATCH. В приведённом выше примере запроса circle значение nParam было бы равно 3, а массив aParam[] содержал бы три значения: 45.3, 22.9 и 5.0

Члены pUser и xDelUser структуры sqlite3_rtree_geometry изначально устанавливаются в NULL. Переменная pUser может быть установлена реализацией обратного вызова в любое произвольное значение, которое может оказаться полезным для последующих вызовов обратного вызова в рамках того же запроса (например, указатель на сложную структуру данных, используемую для проверки пересечения областей)

Если переменная xDelUser установлена в ненулевое значение, то после завершения выполнения запроса SQLite автоматически вызывает её, передавая значение переменной pUser в качестве единственного аргумента. Иными словами, xDelUser может быть установлен в функцию-деструктор для значения pUser

Обратный вызов xGeom всегда выполняет поиск в глубину (depth-first search) по r-tree

Новый обратный вызов xQueryFunc

Новый обратный вызов xQueryFunc получает от движка запросов r-tree больше информации при каждом вызове и перед возвратом отправляет движку запросов больше информации обратно. Чтобы интерфейс оставался управляемым, обратный вызов xQueryFunc обменивается информацией с движком запросов через поля структуры sqlite3_rtree_query_info:

struct sqlite3_rtree_query_info { void *pContext; /* pContext из момента регистрации функции */ int nParam; /* Количество параметров функции */ sqlite3_rtree_dbl *aParam; /* Значения параметров функции */ void *pUser; /* Обратный вызов может использовать это по желанию */ void (*xDelUser)(void*); /* Функция для освобождения pUser */ sqlite3_rtree_dbl *aCoord; /* Координаты узла или записи для проверки */ unsigned int *anQueue; /* Количество ожидающих записей в очереди */ int nCoord; /* Количество координат */ int iLevel; /* Уровень текущего узла или записи */ int mxLevel; /* Наибольшее значение iLevel в дереве */ sqlite3_int64 iRowid; /* Rowid для текущей записи */ sqlite3_rtree_dbl rParentScore;/* Оценка родительского узла */ int eParentWithin; /* Видимость родительского узла */ int eWithin; /* OUT: Видимость */ sqlite3_rtree_dbl rScore; /* OUT: Записать оценку сюда */ /* Следующие поля доступны только в версии 3.8.11 и выше */ sqlite3_value **apSqlParam; /* Исходные SQL-значения параметров */
};

Первые пять полей структуры sqlite3_rtree_query_info идентичны структуре sqlite3_rtree_geometry и имеют точно такое же значение. Структура sqlite3_rtree_query_info также содержит поля nCoord и aCoord, которые имеют то же значение, что и одноимённые параметры в обратном вызове xGeom

Обратный вызов xQueryFunc должен установить поле eWithin структуры sqlite3_rtree_query_info в одно из значений NOT_WITHIN, PARTLY_WITHIN или FULLY_WITHIN в зависимости от того, находится ли ограничивающий прямоугольник, определённый массивом aCoord[], полностью за пределами региона, перекрывает регион или полностью находится внутри региона соответственно

Кроме того, xQueryFunc должен установить поле rScore в неотрицательное значение, указывающее порядок, в котором должны анализироваться и возвращаться поддеревья и записи запроса. Элементы с меньшими оценками обрабатываются первыми

Как следует из названия, RTree организован в виде дерева. Каждый узел дерева представляет собой ограничивающий прямоугольник. Корень дерева — это ограничивающий прямоугольник, охватывающий все элементы дерева. Под корнем находится ряд поддеревьев (как правило, 20 и более), каждое со своим меньшим ограничивающим прямоугольником и содержащее некоторое подмножество записей RTree

Поддеревья могут иметь под-поддеревья и так далее, пока наконец не будут достигнуты листья дерева, которые и являются фактическими записями R*Tree

Запрос к RTree инициализируется путём помещения корневого узла в качестве единственного элемента в очередь с приоритетом (priority queue), отсортированную по rScore. Запрос выполняется путём извлечения из очереди с приоритетом элемента с наименьшей оценкой. Если этот элемент является листом (то есть фактической записью RTree, а не поддеревом), он возвращается как одна строка результата запроса

Если извлечённый элемент очереди с приоритетом является узлом (поддеревом), следующий дочерний элемент этого узла передаётся обратному вызову xQueryFunc. Если у узла есть ещё дочерние элементы, он возвращается в очередь с приоритетом. В противном случае он отбрасывается

Те подэлементы, для которых обратный вызов xQueryFunc устанавливает eWithin в PARTLY_WITHIN или FULLY_WITHIN, добавляются в очередь с приоритетом с оценкой, предоставленной обратным вызовом. Подэлементы, возвращающие NOT_WITHIN, отбрасываются. Запрос выполняется до тех пор, пока очередь с приоритетом не опустеет

Каждая листовая запись и каждый узел (поддерево) внутри RTree имеют целочисленный «уровень» (level). Листья имеют уровень 0. Первое содержащее поддерево листьев имеет уровень 1. Корень RTree имеет наибольшее значение уровня. Поле mxLevel в структуре sqlite3_rtree_query_info — это значение уровня для корня R*Tree. Поле iLevel в sqlite3_rtree_query_info задаёт уровень для проверяемого объекта

Большинство запросов к R*Tree используют поиск в глубину. Это достигается установкой rScore равным iLevel. Поиск в глубину обычно предпочтителен, поскольку минимизирует количество элементов в очереди с приоритетом, что снижает требования к памяти и ускоряет обработку. Однако некоторые приложения могут предпочесть поиск в ширину (breadth-first search), который достигается установкой rScore в mxLevel-iLevel

Создавая более сложные формулы для rScore, приложения могут осуществлять детальный контроль над порядком, в котором выполняется поиск по поддеревьям и возвращаются листовые записи R*Tree

Например, в приложении с многими миллионами записей R*Tree значение rScore можно организовать таким образом, чтобы сначала возвращались наибольшие или наиболее значимые записи, что позволяет приложению быстро отображать наиболее важную информацию и заполнять более мелкие и менее важные детали по мере их появления

Другие информационные поля структуры sqlite3_rtree_query_info доступны для использования обратным вызовом xQueryFunc по желанию. Поле iRowid — это rowid (первый из 3–11 столбцов в R*Tree) для рассматриваемого элемента. iRowid действителен только для листьев. Значения eParentWithin и rParentScore являются копиями значений eWithin и rScore из содержащего поддерева текущей строки

Поле anQueue — это массив из mxLevel+1 беззнаковых целых чисел, указывающих текущее количество элементов в очереди с приоритетом на каждом уровне

Дополнительные соображения для пользовательских запросов

Оператор MATCH пользовательской функции запроса RTree должен быть термом верхнего уровня, соединённым через AND в предложении WHERE, иначе он не сможет использоваться оптимизатором запросов RTree и запрос не будет выполнимым. Если оператор MATCH соединён с другими термами предложения WHERE через оператор OR, например, запрос завершится ошибкой

В одном предложении WHERE допускается два и более операторов MATCH при условии, что они соединены операторами AND. Однако движок запросов R*Tree содержит только одну очередь с приоритетом. Приоритет, назначаемый каждому узлу при поиске, является наименьшим приоритетом, возвращённым любым из операторов MATCH

Детали реализации и теневые таблицы

Содержимое индекса RTree фактически хранится в трёх обычных таблицах SQLite, имена которых производятся от имени RTree. Эти три таблицы называются «теневыми таблицами». Вот их схема:

CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data)
CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode)
CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno)

Символ % в имени каждой теневой таблицы заменяется именем виртуальной таблицы RTree. Так, если имя таблицы RTree — xyz, то три теневые таблицы будут называться xyz_node, xyz_parent и xyz_rowid

В таблице %_node есть по одной записи для каждого узла RTree. Узел RTree состоит из одной или нескольких записей, расположенных близко друг к другу. Узлы RTree образуют дерево. Все узлы, кроме корневого, имеют запись в теневой таблице %_parent, которая идентифицирует родительский узел. Каждая запись в RTree имеет rowid. Теневая таблица %_rowid сопоставляет rowid записей с узлом, содержащим эту запись

Дополнительные столбцы, добавленные в таблицу %_rowid, хранят содержимое вспомогательных столбцов. Имена этих дополнительных столбцов %_rowid, вероятно, не совпадают с фактическими именами вспомогательных столбцов

Я рекомендую периодически запускать проверку целостности индекса, особенно после нештатных завершений работы приложения

Проверка целостности с помощью rtreecheck()

Скалярная SQL-функция rtreecheck(R) или rtreecheck(S,R) выполняет проверку целостности таблицы rtree с именем R, находящейся в базе данных S. Функция возвращает описание обнаруженных проблем на человекочитаемом языке или строку 'ok', если всё в порядке. Запуск rtreecheck() на виртуальной таблице R*Tree аналогичен запуску PRAGMA integrity_check на базе данных

Пример: чтобы убедиться, что R*Tree с именем demo_index корректно сформирован и внутренне согласован, выполните:

SELECT rtreecheck('demo_index');

Функция rtreecheck() выполняет следующие проверки:

• Для каждой ячейки в структуре r-tree (таблица %_node): для каждого измерения выполняется условие coord1 <= coord2.
• Если ячейка не находится в корневом узле, она ограничена родительской ячейкой в родительском узле.
• Для листовых узлов: в таблице %_rowid существует запись, соответствующая значению rowid ячейки и указывающая на правильный узел.
• Для ячеек в нелистовых узлах: в таблице %_parent существует запись, сопоставляющая дочерний узел ячейки с узлом, в котором она находится.
• Количество записей в таблице %_rowid совпадает с количеством листовых ячеек в структуре r-tree, и для каждой записи в таблице %_rowid существует соответствующая листовая ячейка.
• Количество записей в таблице %_parent совпадает с количеством нелистовых ячеек в структуре r-tree, и для каждой записи в таблице %_parent существует соответствующая нелистовая ячейка.

Типичные ошибки при работе с R*Tree

Работая с R*Tree на практике, я замечаю несколько ошибок, которые встречаются особенно часто

Попытка одновременно читать и обновлять RTree в одном цикле

Это приводит к ошибке SQLITE_LOCKED. Решение — сначала собрать все нужные id во временную таблицу, а затем выполнять обновления по ней

Использование запроса типа «содержится внутри» без учёта округления. Из-за того что координаты хранятся как 32-битные числа с плавающей точкой, граничные случаи могут давать неожиданные пропуски. Расширяйте запрашиваемый прямоугольник на 0.000012% по каждому измерению

Ожидание точного ответа от RTree

Индекс возвращает кандидатов, а не финальный результат. Для точной фильтрации всегда нужен второй шаг — проверка через более детальную функцию или геометрию

Использование оператора MATCH внутри условия OR. Такой запрос завершится ошибкой. Оператор MATCH должен быть термом верхнего уровня, соединённым только через AND

Попытка задать ограничения NOT NULL, UNIQUE или DEFAULT для столбцов RTree

Эти ограничения молча игнорируются. Не стоит рассчитывать на их соблюдение

Что ещё изучить по теме

Можно ли хранить в RTree произвольные данные, а не только координаты?

Начиная с SQLite 3.24.0, да — через вспомогательные столбцы, помеченные символом +. До этой версии дополнительные данные нужно хранить в отдельной таблице и связывать через первичный ключ

Почему запрос к RTree возвращает лишние записи, которые не попадают в нужную область?

R*Tree работает с ограничивающими прямоугольниками, а не с точными границами объектов. Индекс сужает список кандидатов, но финальную фильтрацию по точной геометрии нужно выполнять отдельно — например, через пользовательскую функцию

Что произойдёт, если вставить в столбец координат строковое значение?

Модуль r-tree молча преобразует его в требуемый тип (число с плавающей точкой или целое число) перед записью. Никакой ошибки не возникнет, но результат может быть неожиданным

Как убедиться, что индекс RTree не повреждён?

Выполните SELECT rtreecheck('имя_таблицы');. Функция вернёт строку 'ok' при отсутствии проблем или текстовое описание найденных несоответствий

Чем отличается rtree от rtree_i32?

rtree хранит координаты как 32-битные числа с плавающей точкой одинарной точности. rtree_i32 хранит координаты как 32-битные знаковые целые числа. Оба варианта используют вычисления с плавающей точкой внутри алгоритма r-tree, но rtree_i32 подходит для задач, где координаты заведомо целочисленные и округление недопустимо