SQLite Rtree Mapping id(s) from Shadow table to Original table

Question

I have created an Rtree data structure using SQLite, which generates 4 tables (one for the original table, and three shadow tables). And I am trying to figure out how retrieve the id of a row in the original table using the nodeno attribute in the shadow tables.

According to the SQLite documentation, the %rowid table can be used to map the id(s) from the shadow tables to the original table. Below is what the documentation states

"The data structure for a single virtual r-tree table is stored in three native SQLite tables declared as follows. In each case, the '%' character in the table name is replaced with the user-supplied name of the r-tree table.

CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB)

CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)

CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)

The data for each node of the r-tree structure is stored in the %_node table. For each node that is not the root node of the r-tree, there is an entry in the %_parent table associating the node with its parent. And for each row of data in the table, there is an entry in the %_rowid table that maps from the entries rowid to the id of the node that it is stored on."

I have tried to run the following query

SELECT p.id 
FROM mytable_rowid r, mytable p 
WHERE r.rowid = p.id  
AND r.nodeno = 9341;

I was expecting that this query would return the id of a single node in the original table (mytable) that has a value of 9341 in the nodeno attribute of the shadow tables, but instead it retrieved several rows from the original table.

score 0 · Answer 1 · answered Apr 09 '17 at 23:13

0

A node can (must, unless it is the root node) store multiple rows.

The nodes are the bounding boxes of the tree, aren't they?

See the R-tree paper, it has a parameter for this.

answered Apr 09 '17 at 23:13

Has QUIT--Anony-Mousse

76,138
12
138
194

Yes, but nodeno = 9341 is a **leaf node** in the rtree – M.S Apr 10 '17 at 01:19
This also applies to leaf nodes. No reason to wrap every data point into a separate leaf node, is there? – Has QUIT--Anony-Mousse Apr 10 '17 at 06:19

score 0 · Answer 2 · edited May 23 '17 at 11:46

The source code says:

If the node is the root node (node 1), then the first 2 bytes of the node contain the tree depth as a big-endian integer. For non-root nodes, the first 2 bytes are left unused.

The next 2 bytes contain the number of entries currently stored in the node.

The remainder of the node contains the node entries. Each entry consists of a single 8-byte integer followed by an even number of 4-byte coordinates. For leaf nodes the integer is the rowid of a record. For internal nodes it is the node number of a child page.

So you do not need to look into the _rowid table; you can get it directly from the entry in the leaf node (if you know which entry you want).

(You cannot search in the R-tree without looking into all the nodes' entries.)

SQLite Rtree Mapping id(s) from Shadow table to Original table

2 Answers2