search: more in-memory search work. make tests verify Scan doesn't hit Storage.

also some string interning work.

Change-Id: I7864b56eb97318bce943afdca3b1212f4729a9a8