[October 2026 edition]

Indexes and the Art of Searching, Part 2: Key Lookup, Absence Checks, and Identity

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

Part 1 covered sorting and indexes, the work you finish before a query arrives. Part 2 deals with structures that check whether a key matches.

1. Hash Tables: Equality Lookup at the Cost of Order

A hash table speeds up equality lookups by deciding each key’s slot in the table from an integer computed from the key, then running the same computation at lookup time to go straight to that slot. Textbooks call this computation a hash function, which maps keys into an integer space. A hash function is designed to scatter keys evenly across the table, so even keys with close values land in unrelated positions. Since positions reveal nothing about how keys compare, hash indexes cannot serve range queries. Hash indexes are reserved for equality lookups, and range queries and ORDER BY normally use a B-tree, which preserves order. Put a hash index on a condition that asks for “at least,” “less than,” or “the next value,” and you still end up scanning every row.

When different keys are assigned the same slot, that is called a collision. Two ways to handle it are separate chaining, which links the keys that land in the same slot into a single list, and linear probing, which checks adjacent slots in turn. Quadratic probing, which widens the gap as it searches, double hashing, which uses a second hash function to set the step size, and Robin Hood hashing, which evens out probe distances, are also in use. Cuckoo hashing gives each key several candidate positions and, on a collision, pushes an existing element out to another position. It limits the places a lookup has to check and aims to finish every lookup in constant time even in the worst case.

Among recent production hash tables, the Swiss Table family has spread. Separately from keys and values, it lays out control metadata: small tags, each holding part of a hash value. A lookup compares the tags of several slots at once in SIMD fashion and checks the keys only in slots whose tags match. Abseil’s design splits the hash value into a part for the table position and a part for metadata matching. Go 1.24 moved map to a Swiss Table–style structure, adopting open addressing, per-group control information, and incremental table growth. Two structures can share the name “hash table” and still perform very differently, depending on whether the implementation is built around the cache hierarchy and parallel comparison of modern CPUs.

2. Indexes as Predictive Models

In a sorted index, you can guess roughly where a heading sits in the index from the heading itself. Even if the headings are unevenly distributed, knowing what fraction of all headings come before a given heading tells you its position, and that fraction expressed for every heading is called the cumulative distribution. A learned index does the same thing for a database index. Instead of walking a tree as a B-tree does, it trains a model on the cumulative distribution of the sorted keys, and given a key, it predicts roughly which position the key occupies. The cumulative distribution increases as keys get larger, so the predicted positions also follow key order, and the same model can find the positions of both ends of a range query.

Predictions miss, so a separate search around the predicted position absorbs the error. In an evaluation using SOSD, under the conditions of a read-only, dense in-memory array, learned indexes beat traditional indexes on the combination of size and performance. That advantage was measured only under read-only conditions, though. When updates shift the distribution, the model needs retraining, and worst-case performance is hard to guarantee. Whether the advantage appears depends on the data distribution; Part 8 covers the measurements. Learned sorting has also been proposed, with reported results that beat existing radix sorts for certain distributions and data types. Those results, however, depend on the input distribution and the training cost, and outliers affect them as well.

Some designs contain the damage from a bad prediction. Starting at the predicted position, the search doubles the range it examines each step, and once it has bracketed the true position it switches to binary search. If η is the distance between the predicted and true positions, this takes at most 2 log η comparisons. Since η is no larger than the array length, the comparison count stays within twice that of binary search however far off the prediction is. Algorithms with Predictions gives this as an example of a design that is near-optimal when predictions are good and falls back to the no-prediction worst case when they miss.

3. Why One Database Ships Six Kinds of Indexes

The access methods that PostgreSQL 18 provides out of the box come in six kinds: B-tree, Hash, GiST, SP-GiST, GIN, and BRIN. Bloom can be added as an extension. This lineup reflects how each index works for a different set of conditions.

Each of the six handles different conditions. B-tree handles ranges and ordering of comparable values, and Hash handles equality conditions only. GIN works when a single row contains multiple search keys, as with arrays, full text, and JSON; it keeps a list of matching rows for each key, in the same shape as a book’s back index listing the pages for each term. GiST keeps a common skeleton for walking a tree to narrow candidates and lets each data type plug in its own predicates such as “overlaps” and “contains,” which is why it is called a framework for extending the search structure itself. SP-GiST takes on structures that partition space unevenly: it divides dense areas finely and sparse areas coarsely, so branch depth varies from place to place in the tree. BRIN keeps summaries such as the minimum and maximum for each range of pages, and skips whole page ranges when the condition’s value falls outside a summary’s range. Bloom checks the possible presence of values across multiple columns probabilistically; by keeping a Bloom filter, covered in the next section, for each row, it keeps as candidates only the rows that are likely to match the specified combination of column values.

In DuckDB, an Adaptive Radix Tree is created automatically for PRIMARY KEY and UNIQUE constraints. ART speeds up single-key lookups (point lookups) and queries where matching rows make up less than 0.1% of the table (queries with selectivity below 0.1%); join, aggregation, and sort performance is the same with or without ART.

Adding indexes makes reads faster, but it also increases the load of writes, deletes, VACUUM, compaction, and backups, along with memory usage. When you index every column, the degradation on the write side tends to cancel out the read gains. Column order also matters in composite indexes. (tenant_id, created_at) and (created_at, tenant_id) support different search conditions and range scans, so choose the column order to match the order in which queries narrow results, rather than how the data model looks.

4. Indexes That Cheaply Answer “It Isn’t Here”

Traditional indexes have mostly pointed directly at record positions. In large-scale analytics, excluding whole pages or files works better than holding exact positions one record at a time. BRIN, zone maps, min-max indexes, and Bloom filters are all structures for this kind of exclusion. File statistics in Parquet and Iceberg and partition pruning serve the same purpose.

ClickHouse’s skip indexes skip data chunks for which they can determine that no matching value exists. They extend the pruning that the primary index performs per granule to columns outside the sort key. Skip indexes come in several types, and a Bloom filter is one of the options.

A Bloom filter uses several hash functions and a bit array to represent possible set membership in very little space. To register a key, you run it through each hash function and set every bit at the resulting positions. To query, you check the bits at the same positions; if any of them is unset, the key was definitely never registered. If all of them are set, they might simply overlap with bits set by other keys, so the answer is “possibly present,” and this error of reporting an unregistered key as present is called a false positive. The 1970 original paper addressed the trade-off between time and space for membership tests that allow errors. The answers are asymmetric: “not present” is always correct, while “present” may include false positives. The questions a Bloom filter answers are limited to ones like these: do we need to read this SSTable, might this key be in the cache, is a network query necessary, should this duplicate candidate be examined more closely. What it can prove is absence alone; proving content identity or the location of a change lies outside its scope.

There are also learned Bloom filters, which use a learned model to decide membership. Algorithms with Predictions presents this proposal by Kraska et al. as an example that places a backup Bloom filter behind the model to prevent false negatives, where a registered key is reported as “not present.” Even when the model is wrong, the property holds that anything judged “not present” is definitely not present.

As a result, a single table’s read path lines up several structures at once. In a ClickHouse table, a sparse primary index at granule granularity sits on top of a physical layout in sort key order. Skip indexes work on columns outside the sort key, and a Bloom filter can be one of their types. Structures proposed in separate contexts over half a century sit side by side inside the implementation.

Structures that answer “it’s here” exactly and structures that cheaply answer “it isn’t here” do the same job, in that both reduce how much you read.

5. Compressing Identity and Change Extent with Hashes

Besides building search keys, hashes are also used to detect whether content has changed.

The simplest approach compares the hash of an entire file or object with its previous value. Build caches, update checks for distributed files, backups, object storage, tamper detection, and deduplication use it. Changing even one byte changes the hash of the whole, so it tells you only whether something changed; locating the change takes a different mechanism.

Git is designed as a content-addressable filesystem that computes object IDs from content. Blobs, trees, and commits are referenced by IDs derived from their content, so identical content gets the same ID, and walking tree objects lets you detect changes at the directory level. A repository format that uses SHA-256 is also available, with a specification for migrating from the older SHA-1 format.

Insert a few bytes into the middle of a large file, and with block splitting at fixed positions, every block after that point appears to have changed. rsync builds checksums over fixed blocks on the receiving side, while the sending side slides a window one byte at a time and updates a rolling checksum. When it finds a candidate match, it confirms it with a stronger checksum and sends only the parts that differ. It works in two tiers: a cheap summary that can collide finds the candidates, and a strong hash confirms them exactly.

The idea of updating a hash incrementally as something moves also appears in game search. Zobrist hashing builds a position’s hash by XORing together random numbers assigned to each piece-square pair, and after each move it updates the hash by XORing only the contributions of the pieces that moved. It is used in transposition tables, which reuse the results of positions already searched, and Part 5 returns to it.

Content-Defined Chunking (CDC) cuts chunks at boundaries computed from the content rather than at fixed byte counts. Typically it slides a window one byte at a time, computes a hash of the bytes in the window, and places a boundary wherever that value satisfies a predetermined condition. Because each boundary position depends only on the content around it, when data is inserted at the start of a file, the boundaries tend to resynchronize at the same places as long as the same content follows. FastCDC was proposed in 2016 as a method that keeps the cost of CDC down while achieving both a good deduplication ratio and high throughput. VectorCDC, presented at FAST in 2025, performs the boundary search of hashless CDC algorithms with SIMD instructions and reports throughput 8.35 to 26.2 times higher than existing vectorized implementations.

In a Merkle tree, the leaves hold hashes of data blocks and each parent holds the hash of its children.

                root hash
              /           \
         branch A       branch B
          /    \         /    \
        h1     h2      h3     h4

If two roots are equal, the entire trees are equal; if they differ, you can pinpoint the changed region by descending only the branches that differ. Amazon Dynamo used Merkle trees in anti-entropy, the process by which replicas compare their contents and repair discrepancies, to identify the key ranges that diverge between replicas without transferring all the data. Typical uses include detecting differences between distributed replicas, synchronizing large directories, object storage, version control, blockchains, tamper verification, and incremental builds.

Target	Technique	What you learn
Small objects	Whole-content hash	Whether anything changed
Large files	Block hashes	Which blocks changed
Files with frequent inserts and deletes	Rolling hash / CDC	Which content can be reused
Directories and datasets	Merkle tree	Which subtrees changed
Set membership checks	Bloom filter	Definite absence
Storage and reference by content	Content addressing	Sharing of identical content
Adversarial tamper detection	Cryptographic hash	Integrity verification

Before picking a type of hash function, there are eight things to settle: what counts as one unit of comparison, how often to recompute, whether you need the location of a change, whether a collision is a performance problem or a security problem, whether to normalize the input, whether a difference in order counts as a change, whether to include metadata, and how to represent deletions. Only once these are settled does the choice of hash function lead to stable operation. If JSON key order, time representations, floating-point formatting, and Unicode normalization remain unstable, semantically identical data produces different hashes, causing needless cache misses, rebuilds, and resyncs. Fast non-cryptographic hashes are suited to detecting accidental changes; where you must guard against deliberate collisions or tampering, you need a cryptographic hash.

Part 3 takes up searching by words instead of keys, moving from string scanning and inverted indexes to ranking the documents that are found.