Database Indexing Explained: B-Trees, Bitmap and Covering Indexes

When a query executes against a multi-gigabyte table without an index, the database engine has no choice but to perform a sequential full-table scan. It pulls every 8 KB or 16 KB data page from disk into memory, iterating through every tuple to evaluate filter predicates. On a table with 50 million rows, this turns a sub-millisecond retrieval into a multi-second bottleneck that saturates disk I/O and starves the buffer cache.

Understanding how data structures map to persistent storage is one of the most critical database fundamentals for any data engineer or backend architect. With proper database indexing explained through architectural mechanics rather than high-level analogies, engineers can systematically eliminate I/O overhead. Below, we break down three foundational indexing architectures—B-Trees, Bitmap indexes, and Covering indexes—explaining how they function under the hood, where they excel, and how to implement them effectively.

---

1. B-Tree Indexes: The General-Purpose Workhorse

The Balanced Tree (more specifically, the $B^+$ Tree in almost all modern relational engines like PostgreSQL, MySQL InnoDB, and SQL Server) is the default indexing structure. It is engineered specifically for block-storage architectures where minimizing disk seeks is paramount.

How B-Trees Work Internally

A $B^+$ Tree organizes index entries into a hierarchical tree consisting of a single root node, intermediate branch nodes, and leaf nodes. Unlike a standard binary search tree:

• High Fan-Out: Every node corresponds to a filesystem block (page) containing hundreds of keys and child pointers, resulting in a short, wide tree. A tree with a height of only 3 or 4 can index hundreds of millions of records.
• Leaf-Level Linked Lists: Leaf nodes contain all index keys alongside row locators (a tuple ID/CTID in heap-based engines like PostgreSQL, or the primary key value in clustered-index engines like MySQL InnoDB). These leaf nodes are doubly linked, allowing bidirectional range scans without re-traversing parent nodes.
• $O(\log N)$ Traversal: Equality lookups require traversing only from root to leaf (typically 3–4 page reads, almost always cached in memory), followed by a single random read against the heap table to retrieve non-indexed columns.

-- PostgreSQL B-Tree Index
CREATE INDEX idx_customers_created_at 
ON customers USING btree (created_at DESC);

When to Use B-Trees

B-Trees thrive on high-cardinality columns—fields with many unique values, such as UUIDs, sequential IDs, emails, and precise timestamps. They support:

• Exact-match lookups (WHERE id = '...')
• Range scans (WHERE created_at BETWEEN '2024-01-01' AND '2024-01-31')
• Prefix matching on strings (WHERE last_name LIKE 'Smi%')
• Sorting and grouping operations (ORDER BY, GROUP BY)

The Performance Trade-Off: Write Amplification

B-Trees require active maintenance. Every INSERT, UPDATE (of indexed columns), or DELETE requires updating the index structure. If an inserted key lands on a leaf page that is already full, the engine must execute a page split—allocating a new page, moving half the keys over, and updating the parent branch node. This generates write amplification, fragments physical storage, and increases WAL (Write-Ahead Log) pressure.

---

2. Bitmap Indexes: High-Speed Analytics on Low Cardinality

While B-Trees dominate transactional (OLTP) workloads, Bitmap indexes are engineered for read-heavy analytical (OLAP) environments, such as traditional data warehouses and reporting engines (e.g., Oracle Database, ClickHouse, Apache Druid).

Mechanical Breakdown

Instead of storing pointers to individual rows alongside each key, a Bitmap index creates an array of individual bits (0s and 1s) for every distinct value in the indexed column. The length of each bitmap matches the total row count of the table.

Consider a users table with 8 rows and an account_tier column containing three values: FREE, PRO, ENTERPRISE.

If a query filters with WHERE account_tier = 'PRO' AND is_active = TRUE, the engine fetches the bitmap for account_tier = 'PRO' and the bitmap for is_active = TRUE, performing a raw bitwise AND operation across CPU registers:

PRO:       0 1 0 0 1 1 0 0
ACTIVE:    1 1 0 0 1 0 0 1
---------------------------
RESULT:    0 1 0 0 1 0 0 0  --> Matches Row 2 and Row 5

Because modern CPUs can process 64-bit or 256-bit (AVX) registers in a single instruction cycle, filtering millions of rows takes microseconds.

Limitations: The Concurrency Killer

Bitmap indexes are fundamentally unsuited for high-concurrency OLTP databases. If an update modifies a single bit in a compressed bitmap block, the database engine frequently must place an exclusive lock on the entire bitmap segment or vector. This locks thousands of surrounding rows from concurrent writes, creating severe transaction lock contention.

(Note: While engines like PostgreSQL do not offer persistent, on-disk bitmap indexes, their cost-based optimizer can dynamically generate in-memory bitmaps on the fly using a "Bitmap Index Scan" to combine results from multiple independent B-Trees.)

---

3. Covering Indexes: Eliminating the Heap Fetch

When a query finds matching rows in a standard secondary index, the engine must perform a secondary step known as a table lookup, bookmark lookup, or heap fetch to read the non-indexed columns requested by the SELECT clause.

If an index scan matches 50,000 rows, that means 50,000 separate random I/O operations to fetch the actual table records. This often causes the query optimizer to abandon the index entirely and default to a sequential table scan.

A covering index solves this problem by including every column required by the query inside the index itself. When all requested columns reside in the index leaf nodes, the engine executes an Index-Only Scan, bypassing the underlying table storage completely.

Implementing Covering Indexes with the INCLUDE Clause

Modern SQL dialects allow you to attach non-searchable payload columns to an index using the INCLUDE clause. These included columns are stored exclusively in the leaf nodes, keeping branch nodes lean:

-- Query:
SELECT order_id, total_amount, order_status 
FROM orders 
WHERE customer_id = 45209;

-- Optimized Covering Index:
CREATE INDEX idx_orders_customer_covering 
ON orders (customer_id) 
INCLUDE (order_id, total_amount, order_status);

In this scenario:

1. customer_id is the B-Tree search key, maintaining sorting and tree hierarchy.
2. order_id, total_amount, and order_status are appended directly to the leaf pages as non-key attributes.
3. The query optimizer reads the leaf pages and returns the data immediately—zero random heap reads.

When our engineering team at Izan Technologies optimizes high-throughput database layers, implementing covering indexes on read-heavy hot paths routinely cuts query latency by 80% to 95% while keeping write overhead lower than composite multi-column indexing keys.

---

Architectural Comparison: Index Selection Matrix

---

Beyond the Relational Engine: Modern Cloud Lakehouses

With indexing explained in traditional engines, it is vital to contrast these patterns with modern cloud analytical platforms like Snowflake, Databricks, and AWS Redshift.

Modern lakehouses and cloud warehouses operate on immutable columnar formats (Parquet, ORC, micro-partitions) rather than mutable row-based page blocks. As a result, they largely eschew manual B-Tree indexing in favor of:

• Micro-Partition Pruning: Automatically storing min/max metadata for every column across 16 MB–500 MB data chunks.
• Liquid Clustering and Z-Ordering: Physically sorting data along multi-dimensional space-filling curves to skip non-relevant data files entirely during scans.

Understanding both paradigms is essential. A sound architecture pairs fine-tuned operational indexing in PostgreSQL, MySQL, or DynamoDB with optimized partitioning, clustering, and materialized views in Databricks and Snowflake.

---

How Izan Technologies Helps

Designing performant data architectures requires balancing write throughput, query latency, and operational cost. At Izan Technologies, we design and build enterprise-grade data platforms, custom AI models, and real-time data pipelines on AWS, Azure, Databricks, and Snowflake.

Whether you need to eliminate database bottlenecks, migrate legacy warehouses to modern lakehouses, or deploy production ML systems, our engineers deliver tailored solutions built directly into your environment. Best of all, our customers own 100% of the IP we build—giving you complete architectural freedom without vendor lock-in.

Ready to optimize your data infrastructure? Try our Smart AI DataStudio or talk to an expert today.