SQLite表扫描机制问询：无约束查询时的扫描及B+-tree遍历逻辑

Great question! Let's break down exactly how SQLite handles full table scans when your query doesn't include any filtering constraints, and clarify how it interacts with the underlying B-tree structures (whether using rowids, non-integer keys, or composite keys).

1. Regular Tables (With Default Rowid) #

By default, every SQLite table (unless you specify WITHOUT ROWID) has an implicit rowid column that acts as the primary key. This rowid is stored in a B-tree structure where:

• The leaf nodes of the B-tree contain the actual row data, ordered by rowid.
• Leaf nodes are linked together in a doubly linked list, allowing sequential traversal.

When performing a full table scan without constraints:

• SQLite doesn't traverse the entire B-tree (including intermediate index nodes). Instead, it directly jumps to the first leaf node in the B-tree and iterates through the leaf node chain.
• This is far more efficient because it skips the overhead of navigating intermediate index levels, and reads rows in the order they're stored in the leaf pages.

2. WITHOUT ROWID Tables #

If you've created a table with the WITHOUT ROWID clause, the table uses its declared primary key (which can be non-integer, composite, etc.) as the clustered index. In this case:

• The entire table is structured as a B-tree where the leaf nodes store the full row data, ordered by the primary key.
• Just like with rowid tables, a full table scan will directly traverse the linked list of leaf nodes. SQLite doesn't need to go through intermediate index nodes—it starts at the first leaf and follows the chain until all rows are read.

What About Secondary Indexes? #

If your table has secondary indexes (created with CREATE INDEX), SQLite will ignore them during an unconstrained full table scan. Using a secondary index would require extra work: the index's leaf nodes only store the index key and a pointer to the actual row, so SQLite would have to perform a "lookup" for each row to retrieve the full data. The query optimizer will always choose the more efficient path of scanning the main table's leaf nodes directly.

Key Takeaway #

No matter if your table uses a rowid, non-integer primary key, or composite key, SQLite's full table scan bypasses intermediate B-tree nodes. It leverages the linked leaf node structure to read rows sequentially, minimizing unnecessary IO and maximizing scan efficiency.

内容的提问来源于stack exchange，提问作者Joe C