Optimize a search between two values

I have a table that has an integer timestamp as primary key. Almost every query on this table will be of the pattern

SELECT * FROM table WHERE timestamp BETWEEN x AND y

These ranges are usually significantly smaller than the total range of stamps. Insertions happen very rarely and usually at timestamps after every other existing stamp.

Can I somehow tell my database (SQLite) to keep these entries 'sorted' and then make the selects only from the start timestamp, search through rows from there, and then stop as soon as the end timestamp has been surpassed in order to avoid having to scan the entire table and compare the value for each row? Or is this already happening?

What you're looking for is called indexing and it will allow both of your goals to be met.

Indexes save the data pre-sorted on the order of the column(s) defined for the index. They also (typically) use a B-Tree data structure to efficiently store the data so that the entire table doesn't have to be scanned when it's faster to just seek on the range of nodes in the tree that contain the data needed to serve your query.

In SQLite, the primary key is automatically created as a clustered index too. So you actually don't need to do anything additional. But if in your specific example, you cared about indexing a field that wasn't the primary key, then you'd want to define an index like such:

CREATE INDEX IX_IndexName ON TableName (SomeOtherFieldNotInThePrimaryKey)

For further information on indexing, please see this article.

StackExchange Database Administrators Q#308014, answer score: 4