SEARCH TABLE vs SCAN TABLE

Question

sqlite> .schema actor
CREATE TABLE actor (
  id INTEGER PRIMARY KEY, name TEXT, gender TEXT
  );
sqlite> explain query plan
   ...> select * from actor where id = '305453';
0|0|0|SEARCH TABLE actor USING INTEGER PRIMARY KEY (rowid=?)
sqlite> explain query plan
   ...> select * from actor where name = 'Connery, Sean';
0|0|0|SCAN TABLE actor
sqlite>

---

SEARCH TABLE actor USING INTEGER PRIMARY KEY (rowid=?) is taking significantly less time compared to SCAN TABLE actor

---

It is obvious that SCAN TABLE actor is an exhaustive scan of actor table due to chance of duplication, but,

1) Are SCAN TABLE & SEARCH TABLE scanning B-TREE or sequence of records?

2) If it is B-Tree, then how SEARCH TABLE query faster?

Answer 1

SEARCH TABLE means it uses an index, which is a fast way to find rows with a specific column value. The primary key is automatically indexed, for other columns you need to add an index explicitly with the CREATE INDEX command. Searching a B-tree like this is O(log n).

SCAN TABLE means it has to perform an exhaustive search, reading all the rows in the table. Scanning the entire table is O(n). This is done when you're matching a non-indexed column, like name in your example.

For more information about SQLite indexes see Squeezing Performance from SQLite: Indexes? Indexes!. And detailed documentation of the design of SQLite indexes is in Query Planning.