小巧、快速、可靠。
任選三項。
任選三項。
R-Tree 是一種特別的索引，專門用於執行範圍查詢。R-Tree 最常使用於地理空間系統中，其中每個項目都是一個具有最小和最大 X 和 Y 座標的矩形。給定一個查詢矩形，R-Tree 能夠快速找到所有包含在查詢矩形中或與查詢矩形重疊的項目。這個概念可以輕鬆延伸到三維，以用於 CAD 系統中。R-Tree 也可用於時域範圍查詢。例如，假設一個資料庫記錄了大量事件的開始和結束時間。R-Tree 能夠快速找到在給定時間區間內任何時間都處於活動狀態的所有事件，或在特定時間區間內開始的所有事件，或在給定時間區間內開始和結束的所有事件，依此類推。
R-Tree 概念起源於 Toni Guttman：R-Trees：空間搜尋的動態索引結構，1984 年 ACM SIGMOD 國際資料管理會議論文集，第 47-57 頁。SQLite 中的實作是 Guttman 原始構想的改良版，通常稱為「R*Trees」，由 Norbert Beckmann、Hans-Peter Kriegel、Ralf Schneider、Bernhard Seeger 描述：R*-Tree：點和矩形的有效且穩健的存取方法。1990 年 SIGMOD 會議：322-331。
SQLite R*Tree 模組的原始程式碼包含在 合併中。不過，根據組態選項和您使用的 SQLite 特定版本，它可能預設啟用或停用。若要確保 R*Tree 模組已啟用，只要在編譯時定義 SQLITE_ENABLE_RTREE C 預處理器巨集即可。在許多編譯器中，這可透過將選項「-DSQLITE_ENABLE_RTREE=1」新增到編譯器命令列來達成。
SQLite R*Tree 模組實作為 虛擬表格。每個 R*Tree 索引都是一個虛擬表格，其欄位數為 3 到 11 之間的奇數。第一個欄位永遠是 64 位元有號整數主鍵。其他欄位是成對的，每個維度一對，分別包含該維度的最小值和最大值。因此，1 維 R*Tree 有 3 個欄位。2 維 R*Tree 有 5 個欄位。3 維 R*Tree 有 7 個欄位。4 維 R*Tree 有 9 個欄位。5 維 R*Tree 有 11 個欄位。SQLite R*Tree 實作不支援超過 5 維的 R*Tree。
SQLite R*Tree 的第一個欄位類似於一般 SQLite 表格的整數主鍵欄位。它只能儲存 64 位元有號整數值。將 NULL 值插入這個欄位會導致 SQLite 自動產生一個新的唯一主鍵值。如果嘗試將任何其他非整數值插入這個欄位，r-tree 模組會在將其寫入資料庫之前，默默地將其轉換為整數。
min/max 值對欄位儲存為「rtree」虛擬表格的 32 位元浮點值，或儲存為「rtree_i32」虛擬表格的 32 位元有號整數。與可以儲存各種資料類型和格式資料的常規 SQLite 表格不同，R*Tree 嚴格地強制執行這些儲存類型。如果將任何其他類型的值插入此類欄位，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 );
在 CREATE VIRTUAL TABLE 語句的「rtree」引數中，欄位的名稱取自每個引數的第一個標記。每個引數中所有後續的標記都會被自動忽略。舉例來說，這表示如果你嘗試賦予一個欄位一個型別相容性或新增一個約束（例如 UNIQUE、NOT NULL 或 DEFAULT）到一個欄位，這些額外的標記會被接受為有效，但它們不會改變 rtree 的行為。在一個 RTREE 虛擬表格中，第一個欄位永遠具有型別相容性 INTEGER，而所有其他資料欄位具有型別相容性 REAL。在一個 RTREE_I32 虛擬表格中，所有欄位都具有型別相容性 INTEGER。
建議的做法是在 rtree 規格中省略任何額外的標記。讓「rtree」的每個引數都是一個單一的普通標籤，作為對應欄位的名稱，並從引數清單中省略所有其他標記。
一般的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 列的小型範例就足以說明這些概念。
任何有效的查詢都會對一個 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;
即使 R*Tree 包含許多條目，上述查詢也會快速找出所有包含 SQLite 主要辦公室在其邊界框中的郵遞區號。上述範例是「包含在內」查詢。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 模組需要處理的約束越多，邊界框越小，結果回傳的速度就會越快。
預設情況下，座標會使用 32 位元浮點值儲存在 R*Tree 中。當某個座標無法以 32 位元浮點數精確表示時，下界座標會向下捨入，上界座標會向上捨入。因此，邊界框可能會比指定的稍大，但絕不會更小。這正是執行較常見的「重疊」查詢時所需要的，在這種查詢中，應用程式想要找出 R*Tree 中所有與查詢邊界框重疊的條目。如果條目邊界框的邊緣對應到查詢邊界框的邊緣，則向外捨入條目邊界框可能會導致額外的幾個條目出現在重疊查詢中。但重疊查詢絕不會遺漏有效的表格條目。
不過，對於「包含在內」樣式的查詢，將邊界框向外取整可能會導致某些項目被排除在結果集中，如果項目邊界框的邊緣與查詢邊界框的邊緣對應。為了防止這種情況，應用程式應略微擴展其包含在內的查詢框（0.000012%），方法是在每個維度中向下取整較低座標並向上取整較高座標。
Guttman R-Tree 演算法的特性是，任何寫入都可能徹底重新建構樹狀結構，並在過程中變更節點的掃描順序。因此，通常無法在 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。
對於 3.24.0 (2018-06-04) 之前的 SQLite 版本，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 索引用於將搜尋範圍縮小到候選物件清單，然後對每個候選物件執行更詳細且耗費資源的運算，以找出候選物件是否真的符合搜尋條件。
重點：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 表中查詢對應的項目。然後，它將 demo_data 表中的 boundary 欄位作為 contained_in() 函式的參數，如果該函式傳回 true，那麼我們就知道所尋找的座標位於該郵遞區號邊界中。
使用以下更簡單的查詢，我們可以在不使用 R*Tree 索引的情況下得到相同的答案
SELECT objname FROM demo_data WHERE contained_in(demo_data.boundary, 35.37785, -80.77470);
後者的查詢問題在於它必須對 demo_data 表中的所有項目套用 contained_in() 函式。在倒數第二個查詢中使用 R*Tree 會將對 contained_in() 函式的呼叫次數減少到整個表的子集。R*Tree 索引本身並未找到確切的答案，它僅限縮了搜尋範圍。
從 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;
對於輔助欄位，只有欄位名稱有意義。類型相似性 會被忽略。約束例如 NOT NULL、UNIQUE、REFERENCES 或 CHECK 也會被忽略。不過，SQLite 的未來版本可能會開始注意類型相似性和約束，因此建議輔助欄位的使用者將兩者都留空，以避免未來的相容性問題。
預設的虛擬表格 («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 演算法的一部分。
透過在 SELECT 查詢的 WHERE 子句中使用標準 SQL 表達式，程式設計師可以查詢與特定邊界框相交或包含在特定邊界框內的 R*Tree 所有項目。使用 SELECT 的 WHERE 子句中的 MATCH 運算子，自訂 R*Tree 查詢允許程式設計師查詢與任何任意區域或形狀相交的 R*Tree 項目集合，而不仅仅是方框。此功能很有用，例如在計算 R*Tree 中從位於 3D 空間中的攝影機可見的物件子集時。
自訂 R*Tree 查詢的區域由應用程式實作的 R*Tree 幾何回呼定義，並透過呼叫下列兩個 API 之一來向 SQLite 註冊
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）定義的回呼就會被呼叫，以判斷特定物件或子樹是否與所需的區域重疊。
例如，類似下列的查詢可用於尋找與圓心為 45.3,22.9，半徑為 5.0 的圓形重疊的所有 R*Tree 項目
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()）無關。然而，較新的查詢樣式回呼賦予應用程式更大的控制權，以控制查詢如何進行。
傳統 xGeom 回呼會使用四個引數來呼叫。第一個引數是指向 sqlite3_rtree_geometry 結構的指標，其中提供有關 SQL 函式如何呼叫的資訊。第二個引數是每個 r 樹條目的座標數，對於任何給定的 R* 樹來說，這個數值始終相同。座標數對於一維 R* 樹為 2，對於二維 R* 樹為 4，對於三維 R* 樹為 6，依此類推。第三個引數 aCoord[] 是定義要測試的邊界框的 nCoord 座標陣列。最後一個引數是指標，回呼結果應寫入其中。如果 aCoord[] 定義的邊界框完全在 xGeom 回呼定義的區域之外，則結果為零；如果邊界框在 xGeom 區域內或與其重疊，則結果為非零。xGeom 回呼通常應傳回 SQLITE_OK。如果 xGeom 傳回的不是 SQLITE_OK，則 r 樹查詢會中止並傳回錯誤。
xGeom 回呼的第一個引數所指的 sqlite3_rtree_geometry 結構具有以下所示的結構。在同一查詢中，對於相同的 MATCH 運算子，每個回呼都會使用完全相同的 sqlite3_rtree_geometry 結構。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 */
};
當註冊回呼時，sqlite3_rtree_geometry 結構的 pContext 成員始終設定為傳遞給 sqlite3_rtree_geometry_callback() 的 pContext 引數的副本。aParam[] 陣列 (大小為 nParam) 包含傳遞給 MATCH 運算子右側的 SQL 函式的參數值。在上述「圓形」查詢範例中，nParam 會設定為 3，而 aParam[] 陣列會包含三個值 45.3、22.9 和 5.0。
sqlite3_rtree_geometry 結構的 pUser 和 xDelUser 成員最初設定為 NULL。pUser 變數可以由回呼實作設定為任何任意值，這對於在同一個查詢中後續呼叫回呼可能很有用（例如，指向用於測試區域交集的複雜資料結構的指標）。如果 xDelUser 變數設定為非 NULL 值，則在查詢執行完畢後，SQLite 會自動呼叫它，並將 pUser 變數的值作為唯一引數。換句話說，xDelUser 可以設定為 pUser 值的解構函式。
更新的 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 必須將 sqlite3_rtree_query_info 的 eWithin 欄位設定為 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 的根節點具有最大的層級值。sqlite3_rtree_query_info 結構中的 mxLevel 條目是 R*Tree 根節點的層級值。sqlite3_rtree_query_info 中的 iLevel 條目提供正在查詢的物件的層級。
大多數 R*Tree 查詢使用深度優先搜尋。這是透過將 rScore 設為 iLevel 來完成的。深度優先搜尋通常較佳，因為它能將優先佇列中的元素數量減至最少，進而減少記憶體需求並加快處理速度。然而，某些應用程式可能偏好廣度優先搜尋，這可透過將 rScore 設為 mxLevel-iLevel 來完成。透過為 rScore 建立更複雜的公式，應用程式可以詳細控制搜尋子樹及傳回葉狀 R*Tree 條目的順序。例如，在有數百萬個 R*Tree 條目的應用程式中，rScore 可能會安排以傳回最大或最重要的條目為優先，讓應用程式能快速顯示最重要的資訊，並在有空時填入較小且較不重要的詳細資料。
如有需要，sqlite3_rtree_query_info 結構的其他資訊欄位可供 xQueryFunc 回呼使用。iRowid 欄位是正在考慮的元素的 rowid（R*Tree 中 3 至 11 個欄位的第一個）。iRowid 僅對葉狀節點有效。eParentWithin 和 rParentScore 值是從目前列的包含子樹複製而來的 eWithin 和 rScore 值。anQueue 欄位是一個包含 mxLevel+1 個無號整數的陣列，會告知每個層級中優先佇列中目前的元素數量。
自訂 R*Tree 查詢函式的 MATCH 算子必須是 WHERE 子句中頂層的 AND 連接詞，否則 R*Tree 查詢最佳化器將無法使用它，且查詢無法執行。例如，如果 MATCH 算子透過 OR 算子連接到 WHERE 子句的其他詞彙，查詢將會失敗並傳回錯誤訊息。
同一個 WHERE 子句中允許多個 MATCH 算子，只要它們透過 AND 算子連接即可。然而，R*Tree 查詢引擎只包含一個優先佇列。指定給搜尋中每個節點的優先順序是任何 MATCH 算子傳回的最低優先順序。
以下各節說明 R*Tree 實作的一些低階細節，這對問題排除或效能分析可能很有用。
R*Tree 索引的內容實際上儲存在三個以 R*Tree 名稱衍生的普通 SQLite 表格中。這三個表格稱為「影子表格」。這是他們的架構
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 欄位的名稱可能與實際的輔助欄位名稱不同。
純量 SQL 函數 rtreecheck(R) 或 rtreecheck(S,R) 會對資料庫 S 中名為 R 的 rtree 表格執行完整性檢查。此函數會傳回找到的任何問題的人類語言描述，或在一切都正常時傳回字串「ok」。對 R*Tree 虛擬表格執行 rtreecheck() 類似於對資料庫執行 PRAGMA integrity_check。
範例：若要驗證名為「demo_index」的 R*Tree 是否格式正確且內部一致，請執行
SELECT rtreecheck('demo_index');
rtreecheck() 函數會執行下列檢查
針對 r-tree 結構 (%_node 表格) 中的每個儲存格，即
對於每個維度，(coord1 <= coord2)。
除非儲存格位於根節點上，否則儲存格會受到父節點上的父儲存格約束。
對於葉節點，在 %_rowid 表中有一個條目對應於儲存格的 rowid 值，並指向正確的節點。
對於非葉節點上的儲存格，在 %_parent 表中有一個條目，從儲存格的子節點對應到它所在的節點。
在 %_rowid 表中的條目數與 r 樹結構中的葉儲存格數相同，並且每個 %_rowid 表中的條目都對應一個葉儲存格。
在 %_parent 表中的條目數與 r 樹結構中的非葉儲存格數相同，並且每個 %_parent 表中的條目都對應一個非葉儲存格。
此頁面最後修改於 2023-02-20 00:00:42 UTC