Comment by cookguyruffles
5 years ago
Both the index and table data are btrees. These are trees - the root node sits in some known location (offset) in the file, referenced by the file header and metadata. As SQLite traverses the tree, it encounters new descendents it would like to visit, presumably identified by their byte offset in the file, which is all needed for this VFS magic to issue a suitable range request.
- SQlite opens the file and reads 4kb worth of header -> range request for byte 0-4096
- headers/metadata refers to index table with root node at 8192kb
- user issues SELECT * from index WHERE name = 'foo'
- SQLite reads root node from the file (range request for 8192kb..)
- Root node indicates left branch covers 'foo'. Left branch node at address 12345kb
- Fetch left branch (range request for 12345kb)
- New node contains an index entry for 'foo', row 55 of data page at 919191kb
- SQLite reads data page (range request for 91919191kb..)
etc etc etc
Thanks, I too was struggling to understand how it's able to do such efficient targeted range requests, you explained it nicely.