SQL Server Indexes: Clustered, Non-Clustered and B-Tree

When an application slows down, the database is usually the first place to look. If a query reads millions of rows one by one every time it runs, caching, compression or a bigger server only hide the problem for a while. In this article I explain what an index is, how clustered and non-clustered indexes differ in SQL Server, how a lookup walks a B-Tree step by step, and which columns deserve an index. The examples use SQL Server; the core ideas are largely the same in PostgreSQL and MySQL.

What is an index?

Imagine looking for the page where "B-Tree" appears in a thick book. You can read it from the first page to the last, or you can check the index at the back and go straight to page 214. A database index is the same thing: a separate structure that keeps the values of one or more columns in order and tells the database how to reach the row for each value.

Indexes are not free. They take disk space, and every INSERT, UPDATE or DELETE on the table has to update them too. An index speeds up reads and slows down writes a little; good indexing means striking that balance for the queries your application actually runs.

Without an index: the table scan

The examples use a customer table like the one below. Assume it holds a million rows:

CREATE TABLE Musteriler (          -- Customers
    Id          INT IDENTITY(1,1) NOT NULL,
    Ad          NVARCHAR(50)  NOT NULL,  -- first name
    Soyad       NVARCHAR(50)  NOT NULL,  -- last name
    Email       NVARCHAR(256) NOT NULL,
    Sehir       NVARCHAR(50)  NULL,      -- city
    KayitTarihi DATETIME2     NOT NULL,  -- sign-up date
    CONSTRAINT PK_Musteriler PRIMARY KEY CLUSTERED (Id)
);

Now let's look up a customer by email:

SET STATISTICS IO ON;

SELECT Id, Ad, Soyad
FROM Musteriler
WHERE Email = 'ayse@example.com';

There is no index on Email, so SQL Server has no way of knowing where the row is. It reads every page of the table and compares the email on each row. This is a scan: even when the result is a single row, the whole table is read. With SET STATISTICS IO ON, the logical reads figure in the Messages tab tells you how many data pages the query read; comparing it before and after adding an index is the easiest way to measure the effect. Run the query with Include Actual Execution Plan (Ctrl+M) in SQL Server Management Studio and the plan shows a Clustered Index Scan step.

B-Tree: inside an index

SQL Server stores indexes as a balanced tree from the B-Tree family (technically a B+ tree). Every node is an 8 KB data page, and the tree has three kinds of levels:

• Root: the single page where every lookup starts. It holds key ranges and which child page to follow for each range.
• Intermediate levels: the same job over narrower ranges. As the table grows, new levels are added.
• Leaf level: where the lookup ends. In a clustered index it holds the rows themselves; in a non-clustered index, the key and a pointer to the row. Leaf pages are linked to each other, so range queries simply walk along the leaf level.

Say we are looking for the row with key 13:

1. Root: 13 lies between 10 and 20, so the lookup follows the middle branch. The branches for values below 10 and above 20 are never read.
2. Intermediate level: the keys 13 and 16 in this node say "values from 13 up to 16 are on this page". The lookup moves to the leaf page that holds 13.
3. Leaf: 13 is found among the sorted rows on the page. In a clustered index every column of the row is already here.

Each step cuts the search space dramatically, which is why the depth of the tree grows very slowly with the row count: on a million-row table with an integer key, an index is usually three levels deep. A scan reads thousands of pages; an index lookup reads three or four.

Clustered index

In a clustered index, the leaf level of the B-Tree is the table's data itself. Rows are not stored anywhere else; they live in the leaf pages, sorted by the index key. Because data can only be kept in one order, a table can have only one clustered index.

A common misconception is that "the row with Id 7 is physically written in seventh place on disk". The order is a logical one, kept inside pages and through the links between them. Pages are not guaranteed to sit next to each other on disk; as rows are inserted in between, pages split and the index becomes fragmented over time.

When you define a PRIMARY KEY in SQL Server, it is created as the clustered index unless you say otherwise. That is why PK_Musteriler in the table above is clustered. Trying to create a second clustered index on the same table fails:

-- Fails: the table already has a clustered index, PK_Musteriler.
CREATE CLUSTERED INDEX IX_Musteriler_Soyad ON Musteriler (Soyad);

-- Msg 1902: Cannot create more than one clustered index on table 'Musteriler'.

What to look for in a clustered key:

• Narrow: every non-clustered index carries the clustered key to reach the row. A small key such as INT or BIGINT keeps every index small.
• Unique and stable: a row whose key changes has to move to its new position.
• Ever-increasing: with a growing key such as IDENTITY, new rows always go to the last page. Random GUIDs from NEWID() land all over the table and cause frequent page splits and fragmentation. If you need a GUID, NEWSEQUENTIALID() or a sequentially generated GUID type is a better fit.

Because the data is sorted by the key, a clustered index is excellent for range queries and sorting: WHERE Id BETWEEN 1000 AND 2000 descends to a single point at the leaf level and reads the following pages from there.

Non-clustered index

A non-clustered index is a second B-Tree, separate from the table. Its leaf level holds the values of the indexed columns and a pointer to the row, not the row itself. If the table has a clustered index, that pointer is the clustered key; on a table without one (a heap), it is the row's physical address (RID). A table can have many non-clustered indexes.

Let's speed up the email lookup:

CREATE UNIQUE NONCLUSTERED INDEX IX_Musteriler_Email
    ON Musteriler (Email);

SELECT Id, Ad, Soyad
FROM Musteriler
WHERE Email = 'ayse@example.com';

SQL Server now finds the email in the IX_Musteriler_Email tree first (an Index Seek). Id is already in the index because it is the clustered key. Ad and Soyad are not, so SQL Server takes the Id it found and goes to the clustered index once more to fetch them. This extra step is a Key Lookup. For a single row it doesn't matter, but if the query returns thousands of rows, it does one lookup per row, and the optimizer will often abandon the index and scan the table instead.

One more correction: you will often read that a non-clustered index "uses less disk space". It is a separate structure next to the table, so it takes additional space. What is smaller is the index itself compared with the table; the total size grows with every index you add.

Covering indexes and INCLUDE

The way to avoid the Key Lookup is to put every column the query needs into the index. An index that can answer a query on its own is a covering index. Instead of adding columns that are never searched on to the index key, add them to the leaf level only with INCLUDE:

CREATE NONCLUSTERED INDEX IX_Musteriler_Sehir
    ON Musteriler (Sehir)
    INCLUDE (Ad, Soyad);

-- Every column is in the index: no Key Lookup.
SELECT Ad, Soyad
FROM Musteriler
WHERE Sehir = N'İzmir';

In indexes over several columns (composite indexes), column order matters. An index on (Soyad, Ad) is sorted like a phone book: by last name, then by first name. It can seek for WHERE Soyad = ... and for WHERE Soyad = ... AND Ad = ..., but a query that only says WHERE Ad = ... cannot use that order. A good rule of thumb: columns compared with equality first, the column compared with a range last.

Clustered vs non-clustered

Which columns should you index?

• Columns that appear often in WHERE, JOIN and ORDER BY: especially selective ones with many distinct values. An email is selective; an IsActive column with two values is a weak candidate on its own.
• Foreign keys: SQL Server does not index foreign key columns automatically. These indexes make a big difference in JOINs and in the checks that run on delete. (EF Core migrations create them for you.)
• Tables queried for a specific subset: if most rows are soft-deleted and queries always look for the rest, a filtered index with WHERE IsDeleted = 0 is both small and fast.
• Restraint on write-heavy tables: every index is updated on every insert. On log or event tables, a few well-chosen indexes beat many.

The most common reason an index exists but goes unused is wrapping the column in a function. With WHERE YEAR(KayitTarihi) = 2025, SQL Server has to compute the function for every row and cannot seek the index. Writing the same filter as a range brings the index back into play:

-- Cannot seek: YEAR() is computed for every row.
SELECT Id FROM Musteriler WHERE YEAR(KayitTarihi) = 2025;

-- Can seek: the same result, written as a range.
SELECT Id FROM Musteriler
WHERE KayitTarihi >= '2025-01-01' AND KayitTarihi < '2026-01-01';

The same goes for searches that start with a wildcard: LIKE 'Kara%' can use the index, LIKE '%guzel' cannot.

Finally, add indexes by measuring, not guessing. The execution plan, STATISTICS IO and SQL Server's Query Store show which queries are actually expensive. SQL Server's "missing index" suggestions are a good starting point, but they are generated per query; applying every one blindly leaves you with dozens of near-identical indexes.

Defining indexes with EF Core

If you work Code First, you define indexes in the model configuration, and the migration generates the equivalent of the SQL above:

protected override void OnModelCreating(ModelBuilder modelBuilder)
{
    modelBuilder.Entity<Musteri>()
        .HasIndex(m => m.Email)
        .IsUnique();

    // SQL Server specific: INCLUDE columns and a filtered index.
    modelBuilder.Entity<Musteri>()
        .HasIndex(m => m.Sehir)
        .IncludeProperties(m => new { m.Ad, m.Soyad })
        .HasFilter("[Sehir] IS NOT NULL");
}

How EF Core turns queries into SQL, and how to make that SQL lighter, is the subject of EF Core query performance. If you are new to EF Core, start with the first article of the EF Core series.

Conclusion

An index is the database's book index: the right index on the right column turns a lookup in a million-row table from reading thousands of pages into reading a handful. A clustered index holds the data itself in key order, and there is one per table; non-clustered indexes are separate structures, there can be many, and INCLUDE lets them answer a query on their own. Keep in mind that every index costs writes and space, and decide by looking at the execution plan and the pages read. For the wider picture of site speed, see Website Speed and Core Web Vitals.

For further reading, I recommend the "Clustered and nonclustered indexes" and "SQL Server index architecture and design guide" pages in Microsoft's SQL Server documentation.