[October 2026 edition]

Indexes and the Art of Searching, Part 1: What to Prepare Before Reading

Published: Oct 2, 2026
Reading time: ~11 min

0. Introduction

If you read everything, you will always find the answer. Scan a table from the first row to the last and you can pull out the matching rows for any condition at all. That scan slows down as the data grows, so engineers have built up a body of techniques for reading less. I find it useful to organize them into three stages: making data easy to search, searching it, and exploring.

In the first stage, making data easy to search, you work on the data before any query arrives, the way a dictionary is arranged in alphabetical order. Sorting gives the data an order, an index summarizes that order or other features, and hashing compresses identity or the extent of a change into an even smaller value. In the second stage, searching, you use an index to prune candidates and narrow down where the answer lives, then read only the part you need. Binary search, string scanning, inverted indexes, and vector search belong here.

The third stage, exploring, deals with problems where you cannot see the whole set of candidate answers. In car navigation routing or choosing the next move in shogi (Japanese chess), the number of candidates grows combinatorially. You approach the answer by going back and forth: evaluate the current position or route, discard branches with no promise, and look further ahead in the directions that remain. Each stage differs in what it computes ahead of time and when that computation happens, but all three share the goal of reaching the answer while reading less.

Route planning also uses approaches that preprocess the road network before any query. In a table from a survey of route planning techniques, Dijkstra’s algorithm takes about 2.2 seconds on the Western European road network, while Contraction Hierarchies, after 5 minutes of preprocessing, answers in about 110 microseconds (implementations and measurement environments differ between techniques).

Parts 1 and 2 of this series cover the first stage, making data easy to search. Part 1 looks at sorting and indexes as work you finish before a query arrives.

1. Processing That Sorting Supports

With sorted data, binary search can locate a position, and because identical keys sit next to each other, aggregation takes a single pass. Merging two sets and range queries also depend on order. Run-length encoding and delta encoding assume that adjacent values are similar, so sorting directly affects the compression ratio. Duplicate detection, bulk index construction, and range partitioning across distributed nodes all assume sorted input as well.

Sorting by comparing keys with each other and using nothing but which one is larger, much as you sort playing cards by looking at them side by side, is called comparison sorting. A single comparison tells you only which of two keys is larger, so narrowing all the possible orderings down to the correct one takes a certain number of comparisons, and comparison sorts have a general lower bound of O(n log n). Counting sort and radix sort use the key values themselves, so they work outside what textbooks call the comparison model, and when the key range is limited they run in linear time. For small integers such as ages or status codes, counting sort fits well: you prepare one bin per value, drop each row into its bin, and read the bins out in ascending order. For fixed-length keys and sorting on GPUs, radix sort is the usual choice; it processes the key one digit at a time, the way mail gets re-sorted digit by digit of the postal code.

The classic algorithms each still have a place. Insertion sort is strong on small or nearly sorted inputs and serves as the final stage of hybrid sorts. Selection sort performs few writes, which helps with certain small, specialized datasets. Merge sort is stable and suits sequential reads, so it underpins external sorting and parallel processing. Quicksort is fast on average with good locality, which makes it the general-purpose sort for data in main memory. Heapsort makes worst-case guarantees easy, so it appears in memory-constrained environments and as a fallback.

Many modern standard libraries combine several algorithms. Timsort, used for Python’s list sort, detects stretches of the input that are already sorted (runs) and merges them. CPython’s listsort.txt explains how the design targeted stability and adaptation to partially sorted real-world data.

Implementation details also shape performance. Implementations branch to insertion sort for small ranges or detect skewed inputs and switch algorithms, and they work to reduce branch mispredictions alongside the comparison count. Partitioning aligned to cache lines, SIMD processing of several keys at once, and attention to NUMA and memory bandwidth all help. Where an unstable sort is acceptable, some implementations cut the extra memory. Even among implementations with the same theoretical complexity, these differences move measured performance substantially.

Data larger than memory is sorted in chunks, and the sorted runs are combined with a multiway merge. This external merge sort is a foundation of DBMSs, search engines, log processing, and data warehouses. In MapReduce, the shuffle and sort, which partitions Map output by key, sorts it, and hands it to Reduce, sits at the core of processing; there, sorting also acts as the mechanism that routes data for distributed aggregation.

2. Search Optimization Through Physical Storage Order

Beyond being a transient operation, sorting also optimizes search as the physical order in which data is stored.

A ClickHouse MergeTree table stores rows in sort key order. Its index is sparse, placing one mark per granule, which is 8192 rows by default. A query binary-searches the marks and reads only the granules that might match. Because positions are recorded per granule, the index stays small enough to fit in memory.

The Apache Iceberg specification also lets a table declare a sort order, and writing engines can use that order to optimize data layout. This remains a hint about physical layout, though; only an explicit ORDER BY guarantees the order of SQL query results. If you treat physical sorting and ORDER BY as the same thing, results that happened to come back in order in development will fall apart in production.

Choosing a sort key amounts to anticipating the queries that will come and preparing for them in advance. Physical layout is fixed at write time, so that order helps pruning only for queries that filter on the sort key you planned for.

3. The Role and Classification of Indexes

The index at the back of a book takes you straight to the pages where a term appears, instead of reading the text from the beginning. A database index works the same way. By definition, it is an auxiliary structure that determines which data a query can skip, so that less has to be read.

Indexes can be classified along several axes, and the book analogy makes the distinctions easier to grasp. Most logical distinctions concern what you use as the heading to look things up. An index keyed on the primary key, which uniquely identifies a row, is a primary index; one keyed on any other column is a secondary index. Unique indexes, where heading values never repeat across rows, versus non-unique indexes, where the same value appears in several rows, and single-column indexes versus composite indexes that combine columns such as last name and first name, also split according to how the heading is chosen. A partial index gives headings only to the rows that meet a condition, such as unprocessed orders, and an expression index uses the result of applying an expression to a column, such as a name converted to lowercase, as its heading. A covering index also stores the columns a query needs, so the index alone can supply the answer. In book terms, a summary of the term sits right next to the heading, so you never have to open the main text. On the same axis, in relation to the order of the main text, sit clustered indexes, where the text itself is arranged in heading order like a dictionary, and non-clustered indexes, which build a separate back-of-book index independent of the text’s order.

Physically, there are dense indexes, which hold one heading for every row, and sparse indexes, which hold only a representative value for each range. The first and last words printed at the top of each dictionary page form a kind of sparse index, and the ClickHouse primary index from the previous section takes this form too. Indexes also divide by where they live, memory-resident or disk-resident, and by the granularity a single heading points to: row, page, or file. Further axes include ordered indexes, which keep key order so you can look up ranges, versus hash indexes, which give up order to jump directly to the position of a matching key, and exact indexes, which return every matching row precisely, versus approximate indexes, which tolerate some misses to return candidates quickly.

The choice of structure depends less on the data type than on the shape and selectivity of the query.

Query condition	Suitable structure
Equality lookup	Hash table, hash index
Range, before/after, ORDER BY	B-tree, B+ tree
Write-heavy workload	LSM-tree
Fast absence check	Bloom filter
Prefix, byte strings	Trie, radix tree, ART
Word and document search	Inverted index
Time series, correlation with physical order	BRIN, zone map, min-max index
Geographic and spatial	R-tree, GiST, SP-GiST
High-dimensional vectors	IVF, PQ, HNSW, DiskANN

4. Read Optimization and Write Optimization

A B-tree holds many keys per large block, such as a disk page, which keeps the tree shallow. Bayer and McCreight’s 1972 paper presented it as a structure for maintaining large ordered indexes with few I/O operations.

In the B+ tree family used by production databases, internal nodes hold search keys and references to the actual data are gathered in the leaves. Linking the leaves together makes range scans easy, at the cost of page splits on insert and reorganization on delete. Its strength is that it serves equality lookups, ranges, minimum and maximum, prefix matching, and sorted scans alike.

The LSM-tree, by contrast, prioritizes writes. It postpones writing data to its final location, accumulates updates in memory, flushes them as sorted files, and merges those files later. The 1996 original paper describes it as a structure that defers and batches changes to avoid the random update I/O of B-trees, moving them through multiple levels in a manner similar to merge sort.

A typical write path starts by appending to a write-ahead log (WAL), then flushes what was written to the memtable as a sorted SSTable. Reads search across several SSTables, and compaction consolidates duplicates and deleted data. Writes become sequential I/O, but in exchange three kinds of amplification appear. Read amplification comes from checking several SSTables in turn to read a single key. Write amplification means writing more data to disk than the application wrote, because compaction rewrites the same data again and again. Space amplification means using more capacity than the live data needs, because old versions and deleted values linger until they are merged. I/O spikes during compaction, accumulated tombstones, and lookups that cross several levels add to the burden.

An LSM-tree can be seen as an index that continuously merges sorted sets, so here too sorting sits at the center of index maintenance.

5. Index Maintenance and Placement

Data gets updated and deleted, and its distribution shifts, so an index has to be maintained long after it is built. The B+ tree page splits and LSM-tree compaction from the previous section are exactly that maintenance work. Faster reads come at the price of carrying this maintenance cost indefinitely.

Continuous updates, reflecting deletions, consistency with snapshots, and schema changes remain as problems outside the search algorithm itself. Distributed placement and rebuilding, freshness (the delay before updated data shows up in search results), observability, and online tuning are problems of the same kind. In that sense, an index is both a data structure and a system maintained on top of data that never stops changing.

There are also proposals about where indexes should live. Borycki’s “Puffin-Backed Vector Indexes: Attaching Approximate Nearest Neighbor Indexes to Apache Iceberg Snapshots for Compute-Disaggregated Query Engines” (June 2026) presented a design that stores a Vamana-family ANN index in Apache Iceberg’s Puffin sidecar files and links it through the snapshot summary. The proposal reduces index management to Iceberg’s snapshot operations, treating the index as an independent file within a lakehouse that separates compute from storage. ClickHouse Cloud has introduced index sharding, which distributes index analysis across multiple replicas; instead of fully replicating the index to every node, the nodes share the work.

Part 2 turns to structures for looking up by key: hash tables and six kinds of indexes, followed by mechanisms that cheaply answer “it isn’t here” and ways to check content identity with hashes.