Модуль SQLite R*Tree

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

Понятие R-дерева порождено Toni Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. 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-bit signed integer. Другие колонки это пары, одна пара на измерение, содержащие минимальные и максимальные значения для того измерения, соответственно. У 1-мерного R*Tree таким образом есть 3 колонки. У 2-мерного R*Tree есть 5 колонок. У 3-мерного R*Tree есть 7 колонок. У 4-мерного R*Tree есть 9 колонок. И у 5-мерного R*Tree есть 11 колонок. SQLite R*Tree не поддерживает R*Trees шире, чем 5.

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

min/max- колонки пары сохранены как 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 zipcodes около Шарлотты, Северная Каролина. У реальной базы данных было бы много тысяч, миллионы или миллиарды таких записей, но этот маленький образец с 14 строками будет достаточен, чтобы иллюстрировать идеи.

3.3. Запрос индекса R*Tree

Любой действительный запрос будет работать для индекса R*Tree. Внедрение R*Tree просто делает некоторые виды запросов особенно эффективными. Запросы против первичного ключа эффективны:

SELECT * FROM demo_index WHERE id=28269;

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

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

Запрос выше быстро определит местонахождение всех zipcodes, которые содержат главный офис SQLite в их ограничительной рамке, даже если R*Tree содержит много записей. Предыдущим является пример запроса "содержит в". R*Tree также поддерживает "накладывающиеся" запросы. Например, чтобы найти все ограничительные рамки zipcode, которые накладываются на 28269 zipcode:

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 входа (так как каждая ограничительная рамка пересекается с собой), а также другой zipcode, который достаточно близок к 28269, на который накладываются их ограничительные рамки.

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

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

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

3.4. Ошибка Roundoff

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

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

3.5. Чтение и написание в то же время

Это природа алгоритма R-дерева Гуттмана, который при любой записи мог бы радикально реструктурировать дерево и в процессе изменять порядок просмотра узлов. Поэтому вообще невозможно изменить 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-дерева. Обычные таблицы в SQLite в состоянии читать и писать в то же время. Другие виртуальные таблицы могли бы (или не мог бы) сделать так же. R-дерево, может читать и писать в то же время при некоторых обстоятельствах, если оно может выяснить, как достоверно управлять запросом прежде, чем начать обновление. Но вы не должны рассчитывать на это для каждого запроса. Вообще говоря, лучше избегать управлять запросами и обновлениями того же самого R-дерева в то же время.

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

4. Использование R*Trees эффективно

Для версий SQLite до 3.24.0 (2018-06-04) единственной информацией, которую индекс R*Tree хранит об объекте, является свое целое число ID и своя ограничительная рамка. Дополнительная информация должна храниться в отдельных таблицах и связываться с индексом 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 используется, чтобы сузить поиск к списку объектов кандидата, и затем более подробные и дорогие вычисления сделаны на каждом кандидате, чтобы найти, подходит ли кандидат действительно критериям поиска.

Предположим, что demo_data.boundary содержит некоторое собственное описание данных сложной двумерной границы для zipcode, и предположите, что применение использовало sqlite3_create_function(), чтобы создать определенную применением функцию "contained_in(boundary,lat,long)", которая принимает объект, latitute, longitude и возвращает 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. Это тогда использует граничную область от таблицы 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 version 3.24.0 (2018-06-04), у таблиц r-tree могут быть вспомогательные колонки, которые хранят произвольные данные. Вспомогательные колонки могут использоваться вместо вторичных таблиц, таких как "demo_data".

Вспомогательные колонки отмечены символом "+" перед именем столбца. Вспомогательные колонки должны появиться после всех координационных граничных колонок. У таблицы RTREE может быть не больше, чем 100 общих колонок. Другими словами, количество колонок включая колонку первичного ключа целого числа, координационные граничные колонки и все вспомогательные колонки должно быть 100 или меньше. Следующий пример показывает таблицу из r-дерева со вспомогательными колонками, которая эквивалентна этим двум таблицам "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
);

Объединяя данные о местоположении и соответствующую информацию в единой таблице, вспомогательные колонки могут предоставить более чистую модель и уменьшить потребность соединений. Например, более раннее join between demo_index and 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. Integer-Valued 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-дерева.

6. Свои запросы R-дерева

При помощи стандартных SQL-выражений в операторе Where запроса Select программист может запросить все записи R*Tree, которые пересекаются с или содержатся в конкретной ограничительной рамке. Запросы R*Tree, используя оператор MATCH в операторе Where SELECT, позволяют программисту запросить набор записей R*Tree, который пересекает любой произвольный регион или форму, не только коробку. Эта способность полезна, например, в вычислении подмножества объектов в R*Tree, которые видимы от камеры, помещенной в 3D-пространство.

Регионы для обычного запроса 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 version 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-дерева и всегда является тем же самым для любого данного R*Tree. Количество координат 2 для 1-мерного R*Tree, 4 для 2-мерного R*Tree, 6 для 3-мерного R*Tree и т. д. Третьим аргументом aCoord[] является множество координат nCoord, которое определяет ограничительную рамку, которая будет проверена. Последний аргумент задает указатель, в который должен быть написан результат отзыва. Результат ноль, если ограничительная рамка, определенная aCoord[], полностью за пределами региона, определенного отзывом xGeom, и результат отличный от нуля, если ограничительная рамка внутри или пересекается с регионом xGeom. Отзыв должен обычно возвращать SQLITE_OK. Если xGeom возвратит что-нибудь кроме SQLITE_OK, то запрос r-дерева прервется с ошибкой.

Структура 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[] (size 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-дерева.

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 есть целое число "уровень". У листьев есть уровень 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 unsigned integer, которые говорят текущее число элементов в приоритетной очереди на каждом уровне.

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

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

Двум или больше операторам MATCH разрешают быть в том же самом операторе Where, пока они связаны операциями 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() выполняет следующие проверки:


WebMoney: WMZ Z294115950220 WMR R409981405661 WME E134003968233	Visa 4274 3200 2453 6495

1. Обзор