5.1Index design

For a database designer, it is not simply a matter of "more indexes are always better." While an index speeds up lookups, it must also be maintained on every row insert, update, and delete, so you must judge which columns to index, with which index type, and in what column order, based on estimating both read and write load. This section covers the characteristics of index structures and the design judgment needed to improve a slow query.

5.1.1How a B-tree index works and when it fits

• A B-tree index organizes key values into a tree structure that preserves ordering, letting a search traverse from root to leaf to locate the target row in roughly O(log n). It is the most general-purpose index structure and the default index type in most RDBMSs.
• Because the tree structure preserves ordering, it handles not only equality search (=) but also range search (>, <, BETWEEN) and sorting (ORDER BY) well. Most business queries—extracting a date range, prefix-matching a sequential number, etc.—can be sped up sufficiently with a B-tree.

5.1.2Hash indexes and bitmap indexes

• A hash index transforms a key value with a hash function and accesses the storage location directly based on the hash value. Equality search (=) runs at close to O(1), but because a hash value does not preserve ordering, it cannot be used for range search or sorting. It suits columns dominated by exact-match lookups with almost no range search, such as a unique lookup by session ID.
• A bitmap index represents, for each possible value of a column, whether each row matches that value as a bit string of 0/1. For columns with few distinct values (low selectivity), such as "gender" or "membership tier," AND/OR operations across bit strings can narrow down multiple conditions quickly. Conversely, for high-selectivity columns with many distinct values, or tables updated frequently, the cost of rewriting the bit string on every update is large, making it a poor fit.

Suppose a DBA at an e-commerce site receives a report that the following query against the orders table (orders) is slow: SELECT * FROM orders WHERE customer_id = 12345 AND order_date >= '2026-06-01' AND order_date < '2026-07-01'. Checking the execution plan reveals a full table scan, and with several million rows in the table, the speed is unworkable in practice. The first thing to check is whether an index exists—neither customer_id nor order_date had one. Next to consider is the column order of a composite index. In this business, most queries ask "a given customer's recent orders": customer_id is spread across tens of thousands of customers, while order_date further narrows within a day-level range. If a composite index is built in the order (order_date, customer_id), the query first narrows by date range and then searches by customer ID, so in a month where the date range hits many rows, the narrowing effect is weak. Conversely, building it in the order (customer_id, order_date) first narrows heavily on the high-selectivity customer_id, then applies the order_date range condition to the small remaining set of rows, so the index is far more effective. In general, the standard practice for a composite index is to place the column used in an equality condition and with high selectivity first, and the column used in a range condition later. However, since this orders table also sees frequent writes (new orders), one must not forget the trade-off that adding more indexes accumulates index-maintenance cost on every INSERT. After this analysis, the team decided to add only this one high-traffic composite index for now, and to judge any further indexes on other columns only after measuring the impact on write performance—a staged design decision.

5.1.3Section summary

• B-tree index is general-purpose, strong on equality/range search and sorting. Hash index is equality-search-only and cannot handle range search
• Bitmap index excels at combined conditions on low-selectivity columns but is a poor fit under frequent updates
• Standard practice for a composite index is to place the high-selectivity column first. Adding an index is a trade-off between search performance and update cost