In this lesson, you will learn how prefix compression shrinks your B-Tree indexes by stripping away redundant characters from sorted keys stored within index pages.
The Problem: Repetitive Keys
In many B-Tree indexes, especially those involving strings, keys often share a common prefix. Imagine an index on a CustomerName column. If you have thousands of entries like "SMITH_JOHN", "SMITH_JANE", "SMITH_JOAN", and "SMITH_JERRY", the database is forced to store the "SMITH_" string repeatedly for every single entry. This wastes valuable space within your index pages, which limits the number of keys per page and can increase your tree depth.
How Prefix Compression Works
Because B-Tree keys are kept in sorted order, the storage engine can identify this commonality. Instead of repeating "SMITH_" for every entry, the system can store the common prefix once in the page header and then store only the unique "suffix" for each individual key record.
For example, a standard index page might store:
SMITH_JANE, SMITH_JERRY, SMITH_JOAN, SMITH_JOHN
With prefix compression enabled, the page physically stores:
Header: Common Prefix "SMITH_"
Entries: JANE, JERRY, JOAN, JOHN
Impact on Query Performance
By reducing the footprint of each key, you significantly increase the "branching factor"—the number of keys that can fit into a single database page.
- Higher Density: More keys fit into each page, meaning more of your index fits into the Buffer Pool.
- Reduced I/O: Since more of the index is resident in memory, the storage engine needs to perform fewer disk reads when navigating the tree to locate a row.
- Lower Depth: Denser pages mean the B-Tree doesn't need to grow as deep to accommodate the same number of rows, speeding up every search operation.
While this adds a tiny amount of CPU overhead during decompression when reading, the massive reduction in I/O wait time almost always leads to a net gain in overall query performance.
Key Takeaway: Prefix compression improves index efficiency by storing redundant shared character sequences only once per page, allowing for higher data density and fewer disk I/O operations.