SQLite Forum

Visualizing r-tree structure
Login

Visualizing r-tree structure

(1) By Andrea Aime (andrea.aime) on 2020-06-19 10:43:54 [link] [source]

Hi, I'd like to visualize the structure of an R-TREE index, in terms of index nodes and their bounding box, from the root and down the leaves.

The structure of the database seems to be relatively straightforward, but wanted to confirm before delving into it:

  • The <rtree>_node contains the node ids
  • The <rtree>_parent contains the node parent/child relationships
  • The <rtree>_rowid associates each indexed row id to a node

I'm guessing the data column in the <rtree>_node table contains, among other things, the bbox of the node itself. Any suggestion on how to read it?

Or, if there is there a better way to dump the tree structure, I'm all ears.

By the way, thanks for the previous answers on the topic, have been pretty useful!

Best regards Andrea

(2) By ddevienne on 2020-06-19 11:02:48 in reply to 1 [source]

Regarding the visualization part, DRH had a nice demo:
https://sqlite.org/forum/forumpost/dcba8698b2

You'd need to turn the R-Tree bounding boxes into polygons I guess.

(3) By Richard Hipp (drh) on 2020-06-19 11:47:13 in reply to 1 [link] [source]

There is a wish script at ext/rtree/viewrtree.tcl that might help you with this.

To run it, I had to comment-out the "load" command at the top of the file and uncomment the nearby "package require". Then I observe that it only works with 2-D r-trees, which I don't have any of easily at hand, so I cannot say whether or not the script still works. But it is a start!

(4) By Andrea Aime (andrea.aime) on 2020-06-20 09:40:56 in reply to 3 [link] [source]

Hi, I did not quite manage to make the tcl tool work, but the source code was informative. I've found a "rtreenode" undocumented function that dumps the contents of the rtree_node "data" structure into a human readable way:

> select nodeno, rtreenode(2, data) as node from rtree_mytable_node;
1|{3 525005 525117 175036 175141} {2 525352 525497 175008 175195} {4 525053 525308 175144 175249} {5 525108 525214 175004 175137} {6 525222 525322 175004 175140} {7 525008 525323 175259 175442} {8 525343 525498 175216 175433}
2|{1447959 525492 525492 175008 175008} {1447960 525367 525367 175013 175013} {1927698 525488 525488 175039 175039} {1448315 525487 525487 175056 175056} {1447568 525355 525356 175099 175099} {1448332 525383 525383 175104 175104} {12083247 525398 525398 175108 175108} {1447961 525358 525358 175120 175120} {1447962 525358 525358 175122 175122} {1447963 525358 525358 175124 175124} {1448319 525378 525378 175125 175125} {1443934 525399 525399 175127 175127} {1443935 525399 525399 175130 175130} {1443937 525457 525457 175135 175135} {1443939 525457 525457 175138 175138} {1443936 525399 525399 175138 175138} {1447570 525360 525360 175139 175139} {9138129 525423 525423 175140 175140} {8143581 525433 525433 175142 175142} {13319193 525428 525428 175142 175142} {1447958 525493 525493 175143 175143} {3159014 525458 525458 175146 175146} {1443940 525433 525433 175153 175153} {2942623 525390 525390 175158 175158} {1443190 525389 525389 175160 175160} {1443191 525389 525389 175163 175163} {3400050 525420 525420 175169 175169} {1448333 525352 525352 175172 175172} {3833725 525455 525455 175173 175173} {1141777 525379 525379 175174 175174} {1441447 525497 525497 175180 175180} {1448316 525481 525481 175184 175184} {1443192 525451 525451 175191 175191} {1443193 525451 525451 175194 175194} {1446136 525486 525486 175195 175195} {14876320 525425 525425 175162 175162} {16352315 525412 525412 175191 175191} {20494186 525421 525421 175166 175166}
3|{1446979 525005 525005 175036 175036} {1441452 525008 525008 175132 175132} {1441448 525030 525030 175080 175080} {1446775 525034 525034 175060 175060} {1446777 525034 525034 175064 175064} {1447947 525039 525040 175077 175077} {1446778 525047 525047 175058 175058} {1446776 525047 525047 175054 175054} {1446772 525059 525059 175052 175052} {1446771 525060 525060 175048 175048} {1446773 525072 525072 175046 175046} {1446770 525072 525072 175042 175042} {1447969 525074 525074 175060 175060} {1446774 525086 525086 175041 175041} {1447970 525096 525096 175141 175141} {1441787 525099 525099 175101 175101} {1448311 525111 525111 175109 175109} {1448314 525114 525114 175072 175072} {1448330 525117 525117 175046 175046} {1448331 525008 525008 175077 175077} {1448339 525108 525108 175042 175043}
4|{1458380 525280 525281 175144 175144} {1446340 525193 525193 175145 175146} {1446339 525196 525197 175146 175146} {1446169 525225 525225 175150 175150} {1447967 525178 525178 175150 175150} {1446166 525186 525186 175154 175154} {1447574 525107 525107 175157 175157} {1441631 525298 525298 175160 175160} {1441630 525297 525297 175162 175162} {1446435 525102 525102 175166 175166} {1444983 525250 525250 175169 175169} {7847579 525177 525177 175189 175189} {1465675 525155 525155 175189 175189} {1448322 525186 525186 175190 175190} {1446670 525219 525219 175195 175195} {1442073 525053 525053 175198 175198} {1447571 525121 525121 175208 175208} {1446669 525212 525212 175210 175210} {1442543 525265 525265 175213 175213} {1447949 525057 525057 175214 175214} {1447948 525096 525096 175223 175223} {1439633 525175 525175 175224 175224} {1465342 525128 525128 175227 175227} {1442542 525308 525308 175227 175227} {1447567 525102 525102 175229 175229} {1448337 525158 525158 175231 175231} {1447566 525144 525144 175234 175234} {1447560 525097 525097 175237 175237} {1447561 525106 525106 175239 175239} {1446835 525218 525218 175249 175249} {16883460 525205 525205 175217 175217} {17485453 525180 525180 175189 175189}
5|{1448309 525122 525122 175069 175069} {1447575 525127 525127 175090 175090} {1448310 525127 525128 175093 175093} {1187560 525129 525129 175010 175010} {1448329 525139 525139 175034 175034} {1448313 525140 525140 175112 175112} {1448312 525144 525144 175068 175068} {1448318 525150 525150 175033 175033} {1448327 525155 525155 175062 175062} {1448328 525157 525157 175046 175046} {1446337 525168 525168 175105 175105} {1458360 525172 525172 175057 175057} {1446338 525175 525175 175111 175111} {1448325 525184 525184 175067 175067} {1448326 525186 525187 175051 175051} {1448338 525187 525187 175107 175107} {1444412 525188 525188 175137 175137} {1446164 525191 525191 175121 175121} {1442499 525194 525194 175104 175104} {1446168 525196 525196 175089 175089} {1446238 525198 525199 175114 175114} {1445972 525199 525199 175072 175072} {1448336 525201 525201 175049 175049} {1446239 525204 525204 175081 175081} {1448335 525205 525205 175041 175041} {1446244 525207 525207 175082 175082} {1461953 525214 525214 175066 175066} {2704923 525202 525202 175114 175114} {9878548 525108 525108 175008 175008} {21100549 525118 525119 175004 175004}
6|{1447964 525222 525222 175006 175006} {1442500 525230 525230 175060 175060} {1446167 525230 525230 175068 175068} {1446434 525231 525232 175134 175134} {1446433 525234 525234 175130 175130} {1458472 525240 525240 175047 175047} {1446436 525242 525242 175076 175076} {1447572 525244 525245 175008 175008} {1446165 525252 525252 175072 175072} {1141778 525268 525268 175140 175140} {1182182 525278 525278 175120 175120} {1447573 525278 525278 175013 175013} {1444782 525282 525282 175030 175030} {1182183 525283 525283 175098 175098} {1448334 525286 525286 175067 175067} {1182184 525288 525288 175079 175079} {1182181 525291 525291 175117 175117} {1444781 525293 525294 175050 175050} {1448324 525294 525294 175016 175016} {1465341 525296 525296 175011 175011} {1442072 525314 525314 175020 175020} {1442071 525317 525317 175013 175013} {1448317 525318 525318 175008 175008} {1448323 525320 525320 175004 175004} {1447569 525322 525322 175092 175092} {11892383 525241 525241 175079 175079}
7|{1446789 525272 525272 175259 175259} {1446788 525272 525272 175262 175262} {1447565 525154 525154 175262 175262} {1447562 525106 525106 175265 175265} {1447563 525125 525125 175267 175267} {1446241 525323 525323 175267 175268} {1446242 525323 525323 175271 175271} {1447564 525081 525081 175272 175272} {1447559 525111 525111 175292 175292} {1447950 525055 525055 175293 175293} {1447966 525083 525083 175296 175296} {1296813 525195 525195 175301 175301} {1447951 525008 525008 175305 175305} {1447965 525085 525085 175310 175310} {1441439 525205 525205 175317 175318} {1445575 525209 525209 175342 175342} {1446135 525077 525077 175342 175342} {1441438 525231 525231 175347 175347} {2518557 525234 525234 175366 175367} {4729899 525246 525246 175411 175411} {1444787 525255 525255 175442 175442} {1444780 525152 525152 175442 175442} {14687962 525234 525234 175369 175370} {17327612 525116 525116 175283 175283}
8|{1444710 525493 525493 175216 175216} {1185072 525357 525357 175243 175243} {1448320 525494 525495 175251 175251} {1448321 525494 525494 175254 175254} {11714971 525408 525409 175261 175261} {1446718 525483 525483 175273 175273} {1446243 525371 525372 175277 175278} {1446240 525371 525372 175281 175281} {1447955 525498 525498 175288 175288} {1447953 525491 525491 175294 175294} {1447954 525491 525491 175297 175297} {1444786 525480 525480 175302 175302} {1447952 525498 525498 175317 175317} {1446134 525485 525485 175320 175320} {1445609 525343 525343 175339 175339} {1444785 525472 525472 175380 175380} {1444709 525418 525418 175433 175433} {20669416 525345 525345 175309 175309}

> select nodeno, parentnode from rtree_mytable_parent;
2|1
3|1
4|1
5|1
6|1
7|1
8|1

So it looks that in this case 1, the root node, contains all other nodes, and has a bbox for each, while the other nodes point directly to a row in the rtree_mytable virtual table (or well, directly in the spatially indexed table) providing for each again the id in the table, and the bbox of the geometry. I can dump a shapefile from this, which can be then viewed with any GIS tool (e.g., QGIS) with good performance, even for large trees.

Thanks!