B+Tree Index Seek vs Index Scan

In this article I explore the performance impact of database index seek vs index scan. While these are mostly SQL Server terminologies, they are fundamental to how B+Tree are searched in DBMS platforms.

To Seek or To Scan

An Index Seek traverses the B+Tree from the root node to look up a single value in a leaf page. This causes at least 2 I/Os depending on the depth of the B+Tree. An Index Scan however works by scanning the B+Tree leaf pages which are already ordered and linked.

Index scans are better suited for range queries or large values that are close to each other while seeks are great for more selective queries that return very few results.

To better illustrate this, the students table with ID integer fields among others. We are particularly interested in the B+Tree index on ID field.

Assuming a page size that can carry up to 2000 elements (key value) the structure might look like this.

Lets take some examples.

Index Seek Example

Consider the following query against the students table