Postgres vs. SQL Server: B-Tree Index Differences & the Benefit of Deduplication

When it comes to optimizing query performance, indexing is one of the most powerful tools available to database engineers. Both PostgreSQL and Microsoft SQL Server (or Azure SQL) use B-Tree indexes as their default indexing structure, but the way each system implements, maintains, and uses those indexes varies in subtle but important ways.

In this blog post, we explore key areas where PostgreSQL and SQL Server diverge: how their B-Tree indexes implementations behave under the hood and how they store and access data on disk. We'll also benchmark the impact of deduplication of values on index size in each database system.

We've also included a comprehensive reference guide at the end (see Postgres vs. SQL Server Index Comparison Table). Whether you're optimizing queries or planning a migration, these differences can have a meaningful impact on both performance and indexing strategy.

How B-Tree indexing works in PostgreSQL vs. SQL Server

At a high level, both databases use B-Tree indexes to speed up equality and range queries. B-Trees maintain sorted order and are balanced for consistent read performance. But while the concept is similar in both databases, the way it's implemented has important performance consequences.

SQL Server uses clustered indexes to physically order the table's data by the indexed column. When a clustered index is defined, the rows in the table are stored in the same order as the index itself. Nonclustered indexes are stored separately and point to rows using a row locator, either a RID or the clustered key. This physical ordering can be beneficial for range scans or pagination queries, but it also means you're limited to one clustered index per table. More importantly, SQL Server stores each index entry in full, even if multiple entries have identical values on the same page. There's no deduplication, so indexes with many repeated values can grow large and consume excessive I/O.

PostgreSQL does not have clustered indexes in the SQL Server sense. All PostgreSQL tables are stored as unordered heaps, and indexes are purely logical structures that point to tuples in the heap. This design gives PostgreSQL some flexibility: it allows for easier index maintenance and avoids the complications of physical reordering.

However, it also means that you can't rely on an index to define how the table is physically laid out. If query performance depends on reading data in a particular order, Postgres does allow you to run the CLUSTER command, but it requires a full table lock. In production environments, you can use tools like pg_repack to achieve a similar result.

So while both databases use B-Tree indexes as their default, SQL Server's tight coupling between index and physical storage creates a different set of expectations and limitations. PostgreSQL's index model has some performance downsides (since there is no clustered index implementation), but distinct features like deduplication make it perform better in other situations.

PostgreSQL's B-Tree deduplication

Deduplication was introduced in PostgreSQL version 13 and addresses a common inefficiency in traditional B-Tree indexes. When many rows share the same indexed value—think status codes, boolean flags, or timestamps—standard B-Trees store each value and its corresponding tuple pointer individually. This results in bloated index pages and increased maintenance cost, especially for write-heavy workloads.

PostgreSQL deduplicates repeated values within a single index page by default. Instead of storing the same key value multiple times, it stores it once and maintains a compact structure that tracks all matching heap pointers. This reduces index size significantly and improves cache performance, since more index entries fit in memory.

SQL Server does not support deduplication. Each index entry is stored independently, even if the values are identical. In datasets with skewed distributions, PostgreSQL's approach leads to more compact, more efficient indexes, with fewer pages and less disk I/O.

Benchmarking B-Tree indexes on PostgreSQL vs. SQL Server

To understand how PostgreSQL's index deduplication affects real-world performance and storage, we ran a benchmark comparing B-Tree index sizes across PostgreSQL and SQL Server under varying levels of data duplication. Each test created a table of 10 million rows with differing levels of value repetition, ranging from entirely unique values to repeated values at a 1000x factor.

Here's how we structured the test in both databases, so you can reproduce it yourself.

PostgreSQL Test Setup

CREATE TABLE factor_1(col int);  
CREATE TABLE factor_10(col int);  
CREATE TABLE factor_100(col int);  
CREATE TABLE factor_1000(col int);

INSERT INTO factor_1 SELECT * FROM GENERATE_SERIES(1, 10000000);  
INSERT INTO factor_10 SELECT val / 10 FROM GENERATE_SERIES(1, 10000000) x(val);  
INSERT INTO factor_100 SELECT val / 100 FROM GENERATE_SERIES(1, 10000000) x(val);  
INSERT INTO factor_1000 SELECT val / 1000 FROM GENERATE_SERIES(1, 10000000) x(val);

CREATE INDEX factor_1_idx ON factor_1(col);  
CREATE INDEX factor_10_idx ON factor_10(col);  
CREATE INDEX factor_100_idx ON factor_100(col);  
CREATE INDEX factor_1000_idx ON factor_1000(col);

CREATE INDEX factor_1_idx_no_dup_fill100 ON factor_1(col) WITH (deduplicate_items = off, fillfactor = 100);  
CREATE INDEX factor_10_idx_no_dup_fill100 ON factor_10(col) WITH (deduplicate_items = off, fillfactor = 100);  
CREATE INDEX factor_100_idx_no_dup_fill100 ON factor_100(col) WITH (deduplicate_items = off, fillfactor = 100);  
CREATE INDEX factor_1000_idx_no_dup_fill100 ON factor_1000(col) WITH (deduplicate_items = off, fillfactor = 100);  

SQL Server Test Setup

CREATE TABLE factor_1(col int);  
CREATE TABLE factor_10(col int);  
CREATE TABLE factor_100(col int);  
CREATE TABLE factor_1000(col int);

INSERT INTO factor_1 SELECT * FROM GENERATE_SERIES(1, 10000000);  
INSERT INTO factor_10 SELECT value / 10 FROM GENERATE_SERIES(1, 10000000);  
INSERT INTO factor_100 SELECT value / 100 FROM GENERATE_SERIES(1, 10000000);  
INSERT INTO factor_1000 SELECT value / 1000 FROM GENERATE_SERIES(1, 10000000);

CREATE INDEX factor_1_idx ON factor_1(col);  
CREATE INDEX factor_10_idx ON factor_10(col);  
CREATE INDEX factor_100_idx ON factor_100(col);  
CREATE INDEX factor_1000_idx ON factor_1000(col);  

Benchmark results: PostgreSQL's deduplication reduces index size

When we benchmarked index sizes across PostgreSQL and SQL Server, we saw a sharp divergence as data duplication increased. With values repeated 1,000 times, a PostgreSQL index using deduplication was 3x smaller than the same index created with deduplication turned off. Compared to SQL Server, which does not support deduplication and stores each repeated value in full, PostgreSQL consistently produced smaller, more efficient indexes.

This difference matters. High-cardinality columns like status flags, timestamps, and categorical fields are common in production systems. When these values repeat across millions of rows, large indexes can quickly become a performance bottleneck, slowing scans, increasing I/O, and inflating memory usage.

PostgreSQL's deduplication reduces index size significantly, making it easier to keep indexes in memory and reduce disk pressure. For teams moving from SQL Server to PostgreSQL, or simply scaling out workloads with heavily used indexes, this optimization isn't just theoretical. It has a direct impact on resource usage, query performance, and overall operational efficiency.

Comparison Table: PostgreSQL vs. SQL Server Indexing

Index implementations for both B-Tree and other index types vary significantly between PostgreSQL and SQL Server. We've put together a comprehensive index comparison table to help you as a reference in your SQL Server to PostgreSQL migrations.

(Certain index types exist in SQL Server but not in PostgreSQL or vice versa. We've noted supportability as follows: 🟢 Supported index type 🔴 Not supported index type.)

Choosing the right index for your workload

Understanding the differences between PostgreSQL and SQL Server indexing is crucial when optimizing query performance, planning a migration, or designing a high-performance database. Choosing the right indexing strategy requires deep knowledge of query execution patterns and performance trade-offs. Many teams manually experiment with different indexing strategies, which can lead to over-indexing, redundant indexes, or missed optimization opportunities.

Instead of trial and error, pganalyze Index Advisor automatically detects missing indexes, redundant indexes, and optimal column order for multicolumn indexes by applying a constraint programming model against real query execution data. This removes the guesswork and ensures that PostgreSQL databases are indexed for maximum performance.

References:

• PostgreSQL Documentation: 17: 11.2. Index Types
• PostgreSQL Documentation: 16: 67.4. Deduplication
• Microsoft SQL Server Documentation: Indexes
• Microsoft Blog: SQL Server and Azure SQL index architecture and design guide
• pganalyze Blog: Introducing pganalyze Index Advisor 3.0