Модуль R*Tree для SQLite
Содержание
1. Обзор
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*Деревьями», описанная Норбертом Беккманом, Хансом-Петером Кригелем, Ральфом Шнайдером, Бернхардом Зигером: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331.
2. Компиляция модуля R*Tree
Исходный код модуля R*Tree SQLite включён в сборку. Однако в зависимости от параметров конфигурации и конкретной версии SQLite он может быть или не быть включён по умолчанию. Чтобы убедиться, что модуль R*Tree включён, просто скомпилируйте его с определённым макросом препроцессора C SQLITE_ENABLE_RTREE. В большинстве компиляторов это делается путём добавления опции "-DSQLITE_ENABLE_RTREE=1" в командную строку компилятора.
3. Использование модуля R*Tree
Модуль R*Tree SQLite реализован как виртуальная таблица. Каждый индекс R*Tree — это виртуальная таблица с нечётным числом столбцов от 3 до 11. Первый столбец всегда является целочисленным первичным ключом 64-разрядной длины. Остальные столбцы — это пары, одна пара на измерение, содержащая минимальное и максимальное значения для этого измерения соответственно. R*Дерево 1 измерения имеет 3 столбца. R*Дерево 2 измерения имеет 5 столбцов. R*Дерево 3 измерения имеет 7 столбцов. R*Дерево 4 измерения имеет 9 столбцов. А R*Дерево 5 измерения имеет 11 столбцов. Реализация R*Tree SQLite не поддерживает R*Деревья с более чем 5 измерениями.
Первый столбец R*Tree SQLite аналогичен столбцу целочисленного первичного ключа обычной таблицы SQLite. Он может хранить только 64-разрядное целое число со знаком. Вставка NULL в этот столбец заставляет SQLite автоматически сгенерировать новое уникальное значение первичного ключа. Если попытаться вставить в этот столбец любое другое значение, не являющееся целым числом, модуль r-tree тихо преобразует его в целое число перед записью в базу данных.
Столбцы пар мин/макс хранятся как 32-разрядные значения с плавающей запятой для виртуальных таблиц "rtree" или как 32-разрядные целые числа со знаком в виртуальных таблицах "rtree_i32". В отличие от обычных таблиц SQLite, которые могут хранить данные в различных типах и форматах, R*Деревья жёстко навязывают эти типы хранения. Если в такой столбец вставляется любой другой тип значения, модуль 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. Вы можете запросить их напрямую, хотя вряд ли это даст что-то особенно полезное. Вы можете обновить, удалить, вставить или даже удалить тенирующие таблицы, но это повредит индекс 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 также будет эффективно обрабатывать запрос к целочисленному первичному ключу, поэтому предыдущий пример не принципиален. Главная причина использования 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. Одновременное чтение и запись
Алгоритм Guttman R-Tree таков, что любая запись может радикально перестроить дерево, изменив при этом порядок сканирования узлов. По этой причине обычно невозможно изменить R-Tree посреди запроса к нему. Попытки сделать это приведут к ошибке SQLITE_LOCKED «база данных заблокирована».
Например, предположим, что приложение выполняет один запрос к R-Tree так:
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-Tree. Поэтому обновление R-Tree недопустимо, так как это нарушит сканирование.
Это ограничение только для расширения R-Tree. Обычные таблицы в SQLite могут читать и записывать одновременно. Другие виртуальные таблицы могут (или не могут) иметь эту способность. И R-Tree может казаться способным читать и записывать одновременно в некоторых обстоятельствах, если он сможет выяснить, как надёжно выполнить запрос до начала обновления. Но не стоит полагаться на это для каждого запроса. Как правило, лучше избегать одновременного выполнения запросов и обновлений для одного и того же R-Tree.
Если вам действительно необходимо обновить R-Tree на основе сложных запросов к тому же R-Tree, лучше сначала выполнить сложные запросы и сохранить результаты во временной таблице, а затем обновить R-Tree на основе значений, сохранённых во временной таблице.
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, если 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. Использование R*Tree в предпоследнем запросе уменьшает количество вызовов функции contained_in() до небольшого подмножества всей таблицы. Индекс R*Tree не нашёл точного ответа сам по себе, он просто ограничил пространство поиска.
4.1. Вспомогательные столбцы
Начиная с версии SQLite 3.24.0 (2018-06-04), таблицы r-tree могут иметь вспомогательные столбцы, которые хранят произвольные данные. Вспомогательные столбцы могут использоваться вместо вторичных таблиц, таких как «demo_data».
Вспомогательные столбцы отмечаются символом «+» перед именем столбца. Вспомогательные столбцы должны располагаться после всех столбцов границ координат. Таблица RTREE может иметь не более 100 столбцов в общей сложности. Другими словами, количество столбцов, включая столбец первичного ключа, столбцы границ координат и все вспомогательные столбцы, должно быть 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-Trees
По умолчанию виртуальная таблица («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-Tree
Используя стандартные выражения 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, которые перекрываются кругом с центром в 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-функции. Однако новые обратные вызовы на основе запросов предоставляют приложению больший контроль над тем, как происходит запрос.
6.1. Обратный вызов xGeom
Обратный вызов xGeom вызывается с четырьмя аргументами. Первый аргумент — указатель на структуру sqlite3_rtree_geometry, которая предоставляет информацию о том, как была вызвана SQL-функция. Второй аргумент — количество координат в каждой записи r-tree, и оно всегда одинаково для любого данного R*Tree. Количество координат равно 2 для одномерного R-Tree, 4 для двумерного R-Tree, 6 для трёхмерного R-Tree и так далее. Третий аргумент, aCoord[], представляет собой массив nCoord координат, определяющих прямоугольник, который необходимо проверить. Последний аргумент — указатель, в который должен быть записан результат обратного вызова. Результат равен 0, если прямоугольник, определённый aCoord[], полностью находится за пределами области, определённой обратным вызовом xGeom, и результат не равен 0, если прямоугольник находится внутри или перекрывается с областью 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; /* 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 установлена в значение отличное от NULL, то после завершения запроса SQLite автоматически вызывает её со значением переменной pUser в качестве единственного аргумента. Другими словами, xDelUser может быть установлен на функцию-деструктор для значения pUser.
Обратный вызов xGeom всегда выполняет поиск в глубину по дереву r-tree.
6.2. Новый обратный вызов xQueryFunc
Обратный вызов xQueryFunc при каждом вызове получает больше информации от движка запросов r-дерева и отправляет больше информации обратно движку запросов перед возвратом. Для удобства интерфейса обратный вызов 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 имеет целочисленную «глубину» (level). У листьев глубина равна 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 может быть организовано таким образом, чтобы сначала возвращались самые большие или наиболее важные записи, что позволит приложению быстро отобразить наиболее важную информацию и заполнить меньшие и менее важные детали по мере их появления.
Другие поля структуры sqlite3_rtree_query_info доступны для использования обратным вызовом xQueryFunc, если это необходимо. Поле 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):
для каждого измерения (coord1 <= coord2).
если ячейка не является корневым узлом, то ячейка ограничена родительской ячейкой в родительском узле.
для листовых узлов, что существует запись в таблице %_rowid, соответствующая значению rowid ячейки, которая указывает на правильный узел.
для ячеек в узлах, не являющихся листовыми, что существует запись в таблице %_parent, которая сопоставляет дочерний узел ячейки с узлом, в котором она находится.
Что количество записей в таблице %_rowid равно количеству листовых ячеек в структуре r-дерева и что каждой записи в таблице %_rowid соответствует листовая ячейка.
Что количество записей в таблице %_parent равно количеству ячеек, не являющихся листовыми, в структуре r-дерева, и что каждой записи в таблице %_parent соответствует ячейка, не являющаяся листовой.
Эта страница была в последний раз изменена 2023-02-20 00:00:42 по UTC
SQLite is in the Public Domain.
https://sqlite.org/rtree.html
