Модуль SQLite R*Tree

R-дерево — это специальный индекс, предназначенный для выполнения запросов по диапазонам. Чаще всего R-деревья используются в геопространственных системах, где каждая запись представляет собой прямоугольник с минимальными и максимальными координатами X и Y. Получив прямоугольник запроса, R-дерево может быстро найти все записи, находящиеся внутри него или пересекающие его. Эта идея легко расширяется до трёх измерений для использования в системах автоматизированного проектирования. R-деревья также применяются для поиска диапазонов во временной области. Например, предположим, что база данных хранит время начала и окончания большого числа событий. R-дерево может быстро найти все события, активные в любой момент заданного временного интервала, все события, начавшиеся в заданном интервале, или все события, которые начались и закончились в пределах заданного интервала. И так далее.

Концепция R-дерева была предложена Тони Гуттманом: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data, стр. 47–57. Реализация в SQLite представляет собой усовершенствование исходной идеи Гуттмана, обычно называемое «R*Trees»; она описана Норбертом Бекманном, Хансом-Петером Кригелем, Ральфом Шнайдером и Бернхардом Зегером: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322–331.

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

Исходный код модуля SQLite R*Tree включён в состав амальгамации. Однако, в зависимости от параметров конфигурации и конкретной используемой версии SQLite, модуль может быть включён или выключен по умолчанию. Чтобы убедиться, что модуль R*Tree включён, достаточно выполнить компиляцию с определённым макросом препроцессора C SQLITE_ENABLE_RTREE. Во многих компиляторах для этого нужно добавить параметр "-DSQLITE_ENABLE_RTREE=1" в командную строку компилятора.

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

Модуль SQLite R*Tree реализован как виртуальная таблица. Каждый индекс R*Tree представляет собой виртуальную таблицу с нечётным числом столбцов от 3 до 11. Первый столбец всегда является первичным ключом — 64-разрядным целым числом со знаком. Остальные столбцы образуют пары: по одной паре на каждое измерение, содержащей соответственно минимальное и максимальное значения для этого измерения. Таким образом, одномерное R-дерево содержит 3 столбца, двумерное — 5 столбцов, трёхмерное — 7 столбцов, четырёхмерное — 9 столбцов, а пятимерное — 11 столбцов. Реализация SQLite R*Tree не поддерживает R-деревья размерностью более 5.

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

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

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

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

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

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

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

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

Например, создадим двумерный индекс R*Tree для пространственных запросов:

CREATE VIRTUAL TABLE demo_index USING rtree(
   id,              -- Integer primary key
   minX, maxX,      -- Minimum and maximum X coordinate
   minY, maxY       -- Minimum and maximum Y coordinate
);

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

В аргументах "rtree" в операторе CREATE VIRTUAL TABLE имена столбцов берутся из первого токена каждого аргумента. Все последующие токены внутри каждого аргумента незаметно игнорируются. Это означает, например, что если вы попытаетесь задать столбцу сродство типа или добавить такое ограничение, как UNIQUE, NOT NULL или DEFAULT, эти дополнительные токены будут приняты как допустимые, но не изменят поведение rtree. В виртуальной таблице RTREE первый столбец всегда имеет сродство типа INTEGER, а все остальные столбцы данных — сродство типа REAL. В виртуальной таблице RTREE_I32 все столбцы имеют сродство типа INTEGER.

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

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

Обычные команды INSERT, UPDATE и DELETE работают с индексом R*Tree так же, как и с обычными таблицами. Поэтому для вставки данных в наш пример индекса R*Tree можно выполнить примерно следующее:

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);

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

3.3. Выполнение запросов к индексу R*Tree

Для индекса R*Tree подходят любые допустимые запросы. Реализация R*Tree лишь делает некоторые виды запросов особенно эффективными. Запросы по первичному ключу выполняются эффективно:

SELECT * FROM demo_index WHERE id=28269;

Разумеется, обычная таблица SQLite также эффективно выполняет запросы по первичному ключу типа INTEGER, поэтому предыдущий пример не так важен. Основная причина использовать 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, даже если R*Tree содержит много записей. Это пример запроса на поиск объектов, «содержащихся внутри». R*Tree также поддерживает запросы на поиск «пересекающихся» объектов. Например, чтобы найти все ограничивающие прямоугольники почтовых индексов, пересекающиеся с индексом 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 и чем меньше ограничивающий прямоугольник, тем быстрее будут получены результаты.

3.4. Ошибка округления

По умолчанию координаты в R*Tree хранятся в виде 32-разрядных чисел с плавающей точкой. Если координату невозможно точно представить 32-разрядным числом с плавающей точкой, координаты нижней границы округляются вниз, а координаты верхней границы — вверх. Поэтому ограничивающие прямоугольники могут оказаться немного больше заданных, но никогда не будут меньше. Это именно то, что нужно для наиболее распространённых запросов на поиск «пересекающихся» объектов, когда приложению требуется найти каждую запись R*Tree, пересекающую ограничивающий прямоугольник запроса. Округление ограничивающих прямоугольников записей наружу может привести к появлению нескольких лишних записей в результатах запроса на пересечение, если край ограничивающего прямоугольника записи совпадает с краем ограничивающего прямоугольника запроса. Однако запрос на пересечение никогда не пропустит подходящую запись таблицы.

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

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

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

Например, предположим, что приложение выполняет запрос к R-дереву, подобный этому:

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

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

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

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

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

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

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

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

CREATE TABLE demo_data(
  id INTEGER PRIMARY KEY,  -- primary key
  objname TEXT,            -- name of the object
  objtype TEXT,            -- object type
  boundary BLOB            -- detailed boundary of object
);

В этом примере поле demo_data.boundary предназначено для хранения какого-либо двоичного представления точных границ объекта. Индекс R*Tree хранит только прямоугольную границу объекта, параллельную осям. Граница R*Tree является лишь приближением к истинной границе объекта. Поэтому обычно индекс R*Tree используется для сокращения поиска до списка объектов-кандидатов, после чего для каждого кандидата выполняются более подробные и затратные вычисления, позволяющие выяснить, соответствует ли кандидат критериям поиска.

Важно: Индекс R*Tree обычно не даёт точного ответа, а лишь сокращает множество возможных ответов с миллионов до нескольких десятков.

Предположим, что поле demo_data.boundary содержит некоторое закрытое описание сложной двумерной границы почтового индекса и что приложение использовало интерфейс sqlite3_create_function() для создания функции, определённой приложением, "contained_in(boundary,lat,long)", которая принимает объект demo_data.boundary, широту и долготу и возвращает true или false в зависимости от того, находится ли точка с указанными широтой и долготой внутри границы. Можно считать, что функция "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. Использование R*Tree в предпоследнем запросе позволяет сократить число вызовов функции contained_in() до небольшого подмножества всей таблицы. Индекс R*Tree не нашёл точный ответ самостоятельно, а лишь ограничил область поиска.

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

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

Вспомогательные столбцы обозначаются символом "+" перед именем столбца. Вспомогательные столбцы должны располагаться после всех столбцов с координатами границ. Таблица RTREE может содержать не более 100 столбцов. Иными словами, общее число столбцов, включая столбец первичного ключа типа INTEGER, столбцы с координатами границ и все вспомогательные столбцы, не должно превышать 100. В следующем примере показана таблица r-tree со вспомогательными столбцами, эквивалентная двум приведённым выше таблицам "demo_index" и "demo_data":

CREATE VIRTUAL TABLE demo_index2 USING rtree(
   id,              -- Integer primary key
   minX, maxX,      -- Minimum and maximum X coordinate
   minY, maxY,      -- Minimum and maximum Y coordinate
   +objname TEXT,   -- name of the object
   +objtype TEXT,   -- object type
   +boundary BLOB   -- detailed boundary of object
);

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

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

4.1.1. Ограничения

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

5. R-деревья с целочисленными значениями

Виртуальная таблица по умолчанию ("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.

6. Пользовательские запросы к R-дереву

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

Области для пользовательских запросов к R*Tree задаются обратными вызовами геометрии R*Tree, реализованными приложением и зарегистрированными в 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, пересекающихся с окружностью радиусом 5.0 с центром в точке 45.3,22.9:

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

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

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

Устаревший обратный вызов xGeom вызывается с четырьмя аргументами. Первый аргумент — указатель на структуру sqlite3_rtree_geometry, которая содержит сведения о вызове функции SQL. Второй аргумент — число координат в каждой записи r-tree; оно всегда одинаково для любого заданного R*Tree. Число координат равно 2 для одномерного R*Tree, 4 для двумерного, 6 для трёхмерного и так далее. Третий аргумент, aCoord[], — это массив из nCoord координат, задающий проверяемый ограничивающий прямоугольник. Последний аргумент — указатель, по которому следует записать результат обратного вызова. Результат равен нулю, если ограничивающий прямоугольник, заданный aCoord[], полностью находится за пределами области, определённой обратным вызовом xGeom; результат не равен нулю, если ограничивающий прямоугольник находится внутри области xGeom или пересекается с ней. Обычно обратный вызов xGeom должен возвращать SQLITE_OK. Если xGeom возвращает любое значение, отличное от SQLITE_OK, запрос r-tree прерывается с ошибкой.

Структура sqlite3_rtree_geometry, на которую указывает первый аргумент обратного вызова xGeom, имеет приведённый ниже вид. Для всех обратных вызовов одного и того же оператора MATCH в одном запросе используется одна и та же структура sqlite3_rtree_geometry. SQLite инициализирует содержимое структуры sqlite3_rtree_geometry, но впоследствии не изменяет его. При необходимости обратный вызов может менять элементы pUser и xDelUser структуры.

typedef struct sqlite3_rtree_geometry sqlite3_rtree_geometry;
struct sqlite3_rtree_geometry {
  void *pContext;                 /* Copy of pContext passed to s_r_g_c() */
  int nParam;                     /* Size of array aParam */
  double *aParam;                 /* Parameters passed to SQL geom function */
  void *pUser;                    /* Callback implementation user data */
  void (*xDelUser)(void *);       /* Called by SQLite to clean up 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 всегда выполняет поиск в r-tree в глубину.

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

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

struct sqlite3_rtree_query_info {
  void *pContext;                   /* pContext from when function registered */
  int nParam;                       /* Number of function parameters */
  sqlite3_rtree_dbl *aParam;        /* value of function parameters */
  void *pUser;                      /* callback can use this, if desired */
  void (*xDelUser)(void*);          /* function to free pUser */
  sqlite3_rtree_dbl *aCoord;        /* Coordinates of node or entry to check */
  unsigned int *anQueue;            /* Number of pending entries in the queue */
  int nCoord;                       /* Number of coordinates */
  int iLevel;                       /* Level of current node or entry */
  int mxLevel;                      /* The largest iLevel value in the tree */
  sqlite3_int64 iRowid;             /* Rowid for current entry */
  sqlite3_rtree_dbl rParentScore;   /* Score of parent node */
  int eParentWithin;                /* Visibility of parent node */
  int eWithin;                      /* OUT: Visiblity */
  sqlite3_rtree_dbl rScore;         /* OUT: Write the score here */
  /* The following fields are only available in 3.8.11 and later */
  sqlite3_value **apSqlParam;       /* Original SQL values of parameters */
};

Первые пять полей структуры 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 неотрицательное значение, указывающее порядок анализа и возврата поддеревьев и записей запроса. Сначала обрабатываются значения с меньшим баллом.

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

Запрос к R*Tree начинается с помещения корневого узла в качестве единственного элемента в очередь с приоритетами, отсортированную по rScore. Затем из очереди извлекается элемент с наименьшим баллом. Если этот элемент является листом (то есть реальной записью R*Tree, а не поддеревом), он возвращается как одна строка результата запроса. Если извлечённый из очереди элемент является узлом (поддеревом), следующий дочерний узел передаётся обратному вызову xQueryFunc. Если у узла остались дочерние элементы, он возвращается в очередь с приоритетами; в противном случае он отбрасывается. Подэлементы, для которых обратный вызов xQueryFunc задаёт eWithin равным PARTLY_WITHIN или FULLY_WITHIN, добавляются в очередь с приоритетами с баллом, предоставленным обратным вызовом. Подэлементы, для которых возвращается NOT_WITHIN, отбрасываются. Запрос выполняется, пока очередь с приоритетами не опустеет.

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

В большинстве запросов к R*Tree используется поиск в глубину. Для этого rScore устанавливается равным iLevel. Обычно предпочтителен поиск в глубину, поскольку он сводит к минимуму число элементов в очереди с приоритетами, что уменьшает требования к памяти и ускоряет обработку. Однако некоторым приложениям может быть предпочтителен поиск в ширину; для этого rScore устанавливается равным mxLevel-iLevel. Создавая более сложные формулы для rScore, приложения могут точно управлять порядком поиска поддеревьев и возврата листовых записей R*Tree. Например, в приложении с миллионами записей R*Tree значение rScore можно настроить так, чтобы сначала возвращались самые крупные или значимые записи. Это позволит приложению быстро отобразить наиболее важную информацию, а затем добавить более мелкие и менее важные подробности по мере их получения.

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

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

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

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

7. Детали реализации

В следующих разделах описаны некоторые низкоуровневые особенности реализации R*Tree, которые могут пригодиться при поиске и устранении неполадок или анализе производительности.

7.1. Теневые таблицы

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

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

В имени каждой теневой таблицы символ "%" заменяется именем виртуальной таблицы R*Tree. Поэтому если таблица R*Tree называется "xyz", три теневые таблицы будут называться "xyz_node", "xyz_parent" и "xyz_rowid".

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

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

7.2. Проверка целостности с помощью SQL-функции 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-дерева (таблица %_node):
1. для каждого измерения (coord1 <= coord2).
2. если ячейка не находится в корневом узле, она ограничена родительской ячейкой в родительском узле.
3. для листовых узлов: в таблице %_rowid есть запись, соответствующая значению rowid ячейки и указывающая на правильный узел.
4. для ячеек в нелистовых узлах: в таблице %_parent есть запись, сопоставляющая дочерний узел ячейки с узлом, в котором она находится.
Количество записей в таблице %_rowid совпадает с количеством листовых ячеек в структуре r-дерева, и каждой записи в таблице %_rowid соответствует листовая ячейка.
Количество записей в таблице %_parent совпадает с количеством нелистовых ячеек в структуре r-дерева, и каждой записи в таблице %_parent соответствует нелистовая ячейка.

Последнее обновление этой страницы: 2025-05-31 13:08:22Z

SQLite is in the Public Domain.
https://sqlite.org/rtree.html