skip to content

Why is Rust's std BTreeMap built as a B-tree with multi-key nodes rather than a binary search tree, and when does HashMap still beat it?

level: seniorimportance: should knowfreq 38%

answer

  1. allocations and pointer chasing
  2. many keys per node
  3. how a node is searched
  4. more comparisons per lookup
  5. expensive comparisons, point lookups only

basics

~20 s

A binary tree allocates one node per entry and risks a cache miss at every comparison. std's B-tree currently packs up to 11 keys per node in contiguous arrays and scans them linearly. HashMap still wins on large, lookup-only workloads with costly-to-compare keys.

solid answer

~50 s

The std docs explain the choice. A balanced binary search tree does the fewest comparisons, but every entry is its own heap allocation and every step down is a likely cache miss. `BTreeMap` instead stores B−1 to 2B−1 keys per node in contiguous arrays. The 1.99.1 source sets B = 6, so a node holds up to 11 keys and 12 child pointers. That cuts allocations by roughly a factor of B and keeps a node's keys next to each other in memory. Inside a node it currently runs a plain linear scan, which the docs admit costs about B·log(n) comparisons, more than a binary tree, yet performs excellently for small, cheap keys. `HashMap` still wins for point lookups on a large map, especially with expensive comparisons such as long `String` keys sharing prefixes. Hashing reads the key once, plus an equality check. Measure with your own keys before switching.

go deeper

for a junior

Recall that BTreeMap is a B-tree whose nodes hold several sorted keys each, not a binary tree with one key per node.

for a middle

Explain that multi-key nodes mean fewer allocations and pointer hops, at the price of more comparisons per lookup.

for a senior

Diagnose a slow map from its keys and access pattern: long string keys and lookup-only traffic favour HashMap, small keys and ordered queries favour BTreeMap, and benchmarks decide.

for a principal

Treat collection choice as a measured default: set a team rule of HashMap for lookup-only maps and BTreeMap where order or determinism is part of the contract.

## What the std source says about the choice The doc comment on `BTreeMap` in the standard library explains the design directly. A perfectly balanced **binary search tree** performs the theoretical minimum number of comparisons, about log2(n). But in practice: - every element sits in its **own heap-allocated node**, so every insert is an allocation; - every comparison on the way down follows a pointer to a new node, and the docs call each one **a potential cache miss**. Allocation and cache misses are both expensive on modern hardware. So std uses a **B-tree**, whose nodes each hold a whole array of keys. The docs describe it as a compromise between cache efficiency and the number of comparisons. ## The node layout in rustc 1.99.1 These are implementation details from `alloc/src/collections/btree/node.rs`. They are not API guarantees, but they show what the docs mean: - The branching constant is **`B = 6`**, so a node holds at most **`2 * B - 1 = 11`** keys. Every non-root node keeps at least **5** keys (`MIN_LEN`). - A `LeafNode` stores `keys: [MaybeUninit<K>; 11]` and `vals: [MaybeUninit<V>; 11]` as **two contiguous arrays**, plus a `len`, a parent pointer and its index in the parent. - An `InternalNode` adds `edges: [MaybeUninit<BoxedNode<K, V>>; 12]`, one child pointer more than its keys. - Keys and values live in separate arrays, so a search scans keys packed side by side without touching the values. Compared with one allocation per entry, the docs put the saving at **a factor of B fewer allocations**. Because each node branches many ways, the tree is also much shallower than a binary tree over the same keys. ## How a lookup searches a node Inside a node, the current implementation runs a **naive linear search**: it compares the target with each key from the left until it finds an equal key or a greater one. You can see this in `find_key_index` in `search.rs`. The docs are candid about the cost: a lookup takes about **B * log(n) comparisons**, which is "generally worse than a BST". They also say this performs excellently on small nodes of cheap-to-compare elements, and that better strategies may be explored later. ## Comparing the options | | Binary search tree (one node per entry) | std `BTreeMap` | std `HashMap` | |---|---|---|---| | Allocations | one per entry | one per node of up to 11 entries | one table, regrown as it fills | | Comparisons per lookup | about log2(n) | about B * log(n), mostly in-node scans | one hash plus usually one equality check | | Pointer hops per lookup | about log2(n) | about the tree height, far fewer | usually one probe into the table | | Order and range queries | yes | yes | no | | Pre-sizing | n/a | none: no `with_capacity` or `reserve` | `with_capacity`, `reserve` | ## When `HashMap` still wins, and when it does not `HashMap` tends to win when: 1. the workload is **point lookups only**, with no ordering, ranges or ends; 2. **comparisons are expensive**: long `String` keys with shared prefixes are compared byte by byte at every step of the scan, while a hash map reads the key once to hash it, then checks equality on a hit; 3. the map is **large and hot**, and you can size it up front with `with_capacity`. `BTreeMap` holds its own when: 1. keys are **small and cheap to compare**, such as integers, where its scans are fast and no hashing runs. The default hasher's cost is covered with the hash map material; 2. you need **order** anyway, because sorting a `HashMap`'s keys on every report costs more than keeping them sorted; 3. **memory growth should be incremental**. A `BTreeMap` allocates node by node, while a `HashMap` grows by reallocating its table. ## What a senior answer adds The honest conclusion is **measure with your keys and your access pattern**, not the big-O column. Note the bulk-build path too: `collect()` into a `BTreeMap` (its `FromIterator` impl) gathers the input into a `Vec`, sorts it stably, and builds the tree from the sorted run, rather than inserting one key at a time. Some answers to avoid in an interview: "B-tree" as a synonym for "binary tree", "BTreeMap is O(1)", or "std uses a red-black tree".

  • Why does Rust's BTreeMap scan a node linearly instead of using binary search inside it?
    The std docs say the current implementation simply performs a naive linear search. That gives excellent performance on small nodes of cheap-to-compare elements, at about B·log(n) comparisons per lookup. The docs leave other strategies, including binary search or skipping ahead by a stride, as possible future work. With at most 11 keys per node, a linear scan over contiguous memory is cheap.
  • Can you pre-size a Rust BTreeMap the way HashMap::with_capacity does?
    No. `BTreeMap` has no `with_capacity`, `reserve` or `capacity`; it allocates node by node as it grows. If you have all the entries up front, `collect()` into the map: its `FromIterator` impl sorts the input and builds the tree from the sorted run instead of inserting keys one at a time.

A binary tree is a trail of single signposts, each a short walk from the last; a B-tree is a few street directories, each listing a dozen roads you skim in one glance before the next walk.

  • BTreeMap is a binary tree, a red-black tree under another name.
  • BTreeMap lookups are O(1), just like HashMap.
  • A B-tree does fewer comparisons per lookup than a balanced binary tree.
  • BTreeMap::with_capacity avoids reallocations when the size is known.
  • HashMap always beats BTreeMap, even for small integer-keyed maps.