Database Indexing: B-Tree and Hash Indexes

In data-driven applications, query performance often determines user experience and system scalability. Database indexes are auxiliary data structures that act like a book's index, enabling you to locate specific records instantly without scanning every row in a table. Mastering B-tree and hash indexes allows you to design systems where queries execute in milliseconds instead of seconds, making this knowledge essential for any engineer working with databases.

What Are Database Indexes and Why Do They Matter?

An index is a separate, ordered data structure that stores a subset of a table's columns—typically a key column and a pointer to the full row—to accelerate data retrieval. Without an index, a database must perform a full table scan, reading every row to find matching records, which is prohibitively slow for large tables. Think of an index as a high-speed directory: instead of flipping through every page of a phone book to find a name, you jump directly to the correct letter section. Indexes are crucial because they reduce disk I/O and CPU usage, directly translating to faster response times for users and more efficient resource utilization for your systems.

B-Tree Indexes: The Workhorse for Range Queries

The B-tree index (Balanced Tree) is the most common index type, valued for its ability to maintain sorted data and support efficient range queries. A B-tree is a self-balancing, hierarchical tree structure where each node contains multiple keys and pointers. The tree remains balanced, meaning all leaf nodes are at the same depth, guaranteeing that lookup, insertion, and deletion operations take logarithmic time—$O(logn)$. This structure is ideal for queries involving ranges, such as SELECT * FROM orders WHERE order_date BETWEEN '2023-01-01' AND '2023-01-31'; or ordering with ORDER BY. Because the keys are sorted in the leaf nodes, the database can quickly navigate to the starting point and sequentially read adjacent entries to satisfy the range.

For example, indexing a customer_id column with a B-tree allows the database to find a specific ID rapidly. More importantly, it enables efficient queries like finding all IDs within a certain block (e.g., 1000 to 2000). The B-tree's design also supports partial key searches and sorting operations, making it versatile for many real-world scenarios where data needs to be queried based on comparative operators like >, <, or LIKE 'A%'.

Hash Indexes: Lightning-Fast Equality Lookups

In contrast, a hash index is optimized for single-value equality queries, such as SELECT * FROM users WHERE username = 'jdoe';. It uses a hash function to map key values to a fixed-size hash code, which directly points to the location of the corresponding row in memory or on disk. The lookup time is typically constant—$O(1)$—making it exceptionally fast for exact matches. Imagine a hash index as a library where each book has a unique code; you compute the code from the title, and it tells you the exact shelf and position.

However, hash indexes have significant limitations. They cannot support range queries because the hash function scrambles the logical order of keys; a query for WHERE score > 90 would require scanning all entries. They are also generally inefficient for sorting or partial matching. Hash indexes excel in scenarios where the only queries are point lookups, such as primary key accesses in key-value stores or session lookups by session ID. The choice between B-tree and hash hinges entirely on your query patterns: use hash for equality, B-tree for ranges and sorting.

Analyzing Index Selectivity and Overhead

Creating an index isn't free; you must analyze selectivity and overhead to ensure performance gains outweigh costs. Selectivity measures how unique the values in an indexed column are. A highly selective index (e.g., on a primary key) filters out most rows, making it very efficient. Selectivity is often calculated as the ratio of distinct values to total rows: $selectivity=\frac{numberofdistinctvalues}{totalnumberofrows}$. A selectivity close to 1.0 indicates high uniqueness, while a low value suggests many duplicates.

Overhead refers to the storage and maintenance costs of an index. Each index consumes additional disk space and requires updates (inserts, deletes, modifies) to stay synchronized with the table data, which can slow down write operations. For instance, adding an index on a frequently updated column might degrade write performance. To choose columns wisely, prioritize indexing columns used in WHERE, JOIN, or ORDER BY clauses that have high selectivity and are queried often. Avoid indexing columns with very low selectivity, like a gender column with only two values, as the index might not be used by the optimizer.

Choosing Columns and Using Indexes in Query Optimization

The query optimizer is a database component that determines the most efficient way to execute a SQL statement, and it relies heavily on index metadata. When you issue a query, the optimizer evaluates available indexes, estimates I/O costs, and selects an execution plan that minimizes response time. For example, for a query joining orders and customers on customer_id, having indexes on both join columns can enable an index join, which is far faster than a full table scan.

You should index foreign key columns to speed up joins and columns frequently used in filter conditions. Consider composite indexes for multi-column queries, but order matters: place the most selective column first. For a query like SELECT * FROM logs WHERE date = '2023-10-05' AND user_id = 123, a composite index on (date, user_id) could be effective. Remember that the optimizer may not use an index if it deems a full scan cheaper, such as when retrieving a large percentage of rows. Understanding these dynamics helps you design indexing strategies that align with your application's specific query workload.

Common Pitfalls

1. Over-Indexing Tables: Creating indexes on every column leads to excessive overhead. Each index consumes storage and slows down write operations, as all indexes must be updated on data modification. Correction: Index strategically based on query patterns. Use database monitoring tools to identify unused indexes and remove them.

1. Ignoring Selectivity: Indexing a column with very low selectivity, like a status field with only 'active' and 'inactive' values, often provides little benefit. The query optimizer might skip the index altogether. Correction: Analyze selectivity before indexing. Focus on columns with many unique values or combinations that narrow results significantly.

1. Misapplying Index Types: Using a hash index for range queries or a B-tree for simple equality lookups when a hash would be faster. Correction: Match the index type to the query pattern: hash for exact matches, B-tree for ranges, sorts, and prefixes.

1. Neglecting Composite Index Order: Creating a composite index with columns in the wrong order can render it useless for queries. For instance, an index on (last_name, first_name) won't optimize a query filtering only on first_name. Correction: Order composite index columns based on selectivity and query conditions. Place columns used in equality predicates before those used in ranges.

Summary

• Indexes are auxiliary structures that enable fast record lookup by avoiding full table scans, drastically improving query performance.
• B-tree indexes maintain sorted data and excel at range queries, sorting, and partial matches, operating in logarithmic time.
• Hash indexes provide constant-time lookups for equality queries but cannot support range operations or ordering.
• Analyze index selectivity (uniqueness of values) and overhead (storage and maintenance costs) to balance read speed against write performance.
• Choose indexing columns based on query patterns—prioritize those in WHERE, JOIN, and ORDER BY clauses with high selectivity.
• The query optimizer uses index metadata to select efficient execution plans, so proper indexing directly influences how quickly your queries run.