# \`BTreeMap\\` -\> \`BTreeMap\\`: Fast and memory efficient **URL:** \ **Category:** language design\ **Created:** [November 26, 2025, 3:14pm UTC](https://internals.rust-lang.org/t/btreemap-a-b-btreemap-a-c-fast-and-memory-efficient/23776 "2025-11-26T15:14:41Z")\ **Posts on this page:** 18\ **Page:** 1
**Author:** ![kpcyrd](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/kpcyrd/32/13832_2.png) [@kpcyrd](https://internals.rust-lang.org/u/kpcyrd)\ **Post date:** [November 26, 2025, 3:14pm UTC](https://internals.rust-lang.org/t/btreemap-a-b-btreemap-a-c-fast-and-memory-efficient/23776/1 "2025-11-26T15:14:41Z")
Considering the following problem: - I have a `BTreeMap` - I have a `Fn(B) -> C` - I want a `BTreeMap` I currently have two options, to pick from: - `BTreeMap::from_iter(map.into_iter().map(f))` - cpu efficient but memory inefficient: since `from_iter` can't assume the iterator is already sorted, [it consumes the entire iterator into a temporary heap allocation](https://github.com/rust-lang/rust/blob/6840234806e4a57e14112a1137783c885b7a23db/library/alloc/src/collections/btree/map.rs#L2350-L2367), then sorts it, then calls the internal `bulk_build_from_sorted_iter` function (which is very fast). Assuming a `BTreeMap` with 10\_000\_000 entries on a 64bit computer, this is going to cause an additional 457MiB allocation for the Vec however. - `new_map.extend(old_map.into_iter().map(f))` - memory efficient but cpu inefficient: this calls `.insert()` for each item, effectively copying them over one-by-one. This doesn't have any unexpected spikes in memory usage, but each insert is going to traverse the tree to find the correct insert position, over and over. There was some prior discussion about exposing `bulk_build_from_sorted_iter` so we can make our own function that is both fast+efficient: > [@\[Feature Request\] Expose bulk\_build\_from\_sorted\_iter in BTreeMap](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815): > > BTreeMap's from\_iter implementation collects all values into a vec and sorts them, before passing into bulk\_build\_from\_sorted\_iter. Sometimes, the data comes sorted. For my use case, from\_iter is already insanely fast; I am looking mainly to avoid the extra Vec allocation necessary for sorting. Use case is a dictionary of 1mil+ terms each containing some misc info, parsed using a custom iterator (not in contiguous Vec\<\_\> form so I think this can't possibly be compiler-optimized away). This is a… > > > Use case: I'm trying to merge \`BTreeMap\`s, but in the case of a duplicate key, I…'d prefer to add the values instead of ignoring the first. To do this, I was planning on implementing a custom MergeIter, which seems simple enough. However, I encountered one problem: BTreeMap's \`from\_sorted\_iter\` is private, meaning that I cannot efficiently use this iterator to merge maps. > > I think the reasoning behind this being private is that being passed an unsorted iterator would result in a logic error in the BTreeMap. However, it's already possible to cause this in safe code with an unreliable Cmp implementation. > > If the function is made public, I'd recommend a couple of changes to make it ready for use without other internal functions. First, don't take \`self\`, but instead start with an empty map. Note that we might also consider just asserting that the map is empty to start with, as I think this change would require either an unnecessary BTreeMap creation or \`mem::uninitialized\` in \`BTreeMap::append\`. Second, add \`fix\_right\_edge()\` to the end of the function. This change shouldn't cause any problems for \`BTreeMap::append\` as it's already calling it afterwords. To avoid the discussion about "should it panic, should it be unsafe { }" (me personally would prefer "may panic" over "unsafe"), and since `BTreeMap` already gives us `Ord` guarantees, there could be the following APIs (slightly pseudo-code-y): - `BTreeMap::map_values V>(self, F) -> Self` - `BTreeMap::try_map_values Result>(self, F) -> Result, E>` This is the first time I'm proposing language improvements like this (also first post in the internals forum), let me know what you think! ✨ ---
**Author:** ![josh](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/josh/32/5934_2.png) [@josh](https://internals.rust-lang.org/u/josh)\ **Post date:** [November 26, 2025, 3:21pm UTC](https://internals.rust-lang.org/t/btreemap-a-b-btreemap-a-c-fast-and-memory-efficient/23776/2 "2025-11-26T15:21:26Z")
👍 for having `from_sorted_iter` (and agreed that it should check sortedness and panic). And 👍 for `map_values` and `try_map_values`. ---
**Author:** ![pitaj](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/pitaj/32/11262_2.png) [@pitaj](https://internals.rust-lang.org/u/pitaj)\ **Post date:** [November 26, 2025, 3:41pm UTC](https://internals.rust-lang.org/t/btreemap-a-b-btreemap-a-c-fast-and-memory-efficient/23776/3 "2025-11-26T15:41:53Z")
How do you ensure that the mapped value has the same order as the original value? What if we just gave a sorted happy path to `extend`? Have it track the maximum item so it can skip the traversal in that case. ---
**Author:** ![josh](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/josh/32/5934_2.png) [@josh](https://internals.rust-lang.org/u/josh)\ **Post date:** [November 26, 2025, 3:50pm UTC](https://internals.rust-lang.org/t/btreemap-a-b-btreemap-a-c-fast-and-memory-efficient/23776/4 "2025-11-26T15:50:41Z")
> [@pitaj](#): > > How do you ensure that the mapped value has the same order as the original value? `BTreeMap` is sorted by key, so if you're only mapping values the order doesn't change. > [@pitaj](#): > > What if we just gave a sorted happy path to `extend`? Have it track the maximum item so it can skip the traversal in that case. That seems like a great potential optimization. ---
**Author:** ![kpcyrd](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/kpcyrd/32/13832_2.png) [@kpcyrd](https://internals.rust-lang.org/u/kpcyrd)\ **Post date:** [November 26, 2025, 4:08pm UTC](https://internals.rust-lang.org/t/btreemap-a-b-btreemap-a-c-fast-and-memory-efficient/23776/5 "2025-11-26T16:08:41Z")
A comment from irc: > 15:31 \ kpcyrd: with the try version the original collection gets dropped on an error? Most of the time I'd probably be fine with dropping both collections in case of an error, this would be analogous to: ```rust impl FromIterator> for Result where V: FromIterator, ``` Alternatively `BTreeMap::try_map_values` could return a `Result, (E, BTreeMap, BTreeMap)>` (error, old collection, new collection - the type complexity is slightly unfortunate though, and the value that was causing the error would be missing/lost). Having an optimized `.extend()` would also work for my use-case. 🙂 ---
**Author:** ![idanarye](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/idanarye/32/3346_2.png) [@idanarye](https://internals.rust-lang.org/u/idanarye)\ **Post date:** [November 26, 2025, 11:51pm UTC](https://internals.rust-lang.org/t/btreemap-a-b-btreemap-a-c-fast-and-memory-efficient/23776/6 "2025-11-26T23:51:40Z")
> [@pitaj](#): > > What if we just gave a sorted happy path to `extend`? Have it track the maximum item so it can skip the traversal in that case. This whole "sorted happy path" for binary tree insertions sounds weird to me. The tree still has depth - you still need to traverse it and rebalance it on every insertion, and for that it doesn't really matter if the items are sorted or not - it's still `O(log n)` per insertion. I'd understand if `bulk_build_from_sorted_iter` was accepting an `ExactSizeIterator` (and then it could easily deduce the entire structure of the tree) but it doesn't - so I although I did not look into how it works, I doubt its optimizations are as good as what `map_values` can achieve. The biggest advantage of `map_values` is that it can just copy the structure of the original tree over to the new one. This means that it doesn't need to navigate the tree from the root on each insertion, and doesn't need to rebalance it - it'll be unbalanced during its construction and only be fully balanced at the very end. This, BTW, mean it's worthwhile to also make `&` (and `&mut`) versions of these methods (`where K: Clone`, of course) ---
**Author:** ![jdahlstrom](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/jdahlstrom/32/3351_2.png) [@jdahlstrom](https://internals.rust-lang.org/u/jdahlstrom)\ **Post date:** [November 27, 2025, 12:37am UTC](https://internals.rust-lang.org/t/btreemap-a-b-btreemap-a-c-fast-and-memory-efficient/23776/7 "2025-11-27T00:37:08Z")
> [@idanarye](#): > > This whole "sorted happy path" for binary tree insertions sounds weird to me But BTree is _not_ a binary tree. It's a b-tree with a much higher branching factor. Binary search trees are definitely not a very good idea on today's machines that love sequential memory access and hate indirection and branches. And unpredictable branches even more. ---
**Author:** ![idanarye](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/idanarye/32/3346_2.png) [@idanarye](https://internals.rust-lang.org/u/idanarye)\ **Post date:** [November 27, 2025, 2:58pm UTC](https://internals.rust-lang.org/t/btreemap-a-b-btreemap-a-c-fast-and-memory-efficient/23776/8 "2025-11-27T14:58:25Z")
Okay, but my point stands - it's still a tree and insertions still require traversal and balancing, so copying the original tree's structure should be faster. ---
**Author:** ![the8472](https://avatars.discourse-cdn.com/v4/letter/t/0ea827/32.png) [@the8472](https://internals.rust-lang.org/u/the8472)\ **Post date:** [November 27, 2025, 7:47pm UTC](https://internals.rust-lang.org/t/btreemap-a-b-btreemap-a-c-fast-and-memory-efficient/23776/9 "2025-11-27T19:47:18Z")
> [@kpcyrd](#): > > `BTreeMap::from_iter(map.into_iter().map(f))` With specialization this could be made to just work™, similar to Vecs. ---
**Author:** ![pacak](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/pacak/32/11934_2.png) [@pacak](https://internals.rust-lang.org/u/pacak)\ **Post date:** [November 28, 2025, 11:25am UTC](https://internals.rust-lang.org/t/btreemap-a-b-btreemap-a-c-fast-and-memory-efficient/23776/10 "2025-11-28T11:25:47Z")
Can it check that `f` makes no changes to the key? ---
**Author:** ![the8472](https://avatars.discourse-cdn.com/v4/letter/t/0ea827/32.png) [@the8472](https://internals.rust-lang.org/u/the8472)\ **Post date:** [November 28, 2025, 11:49am UTC](https://internals.rust-lang.org/t/btreemap-a-b-btreemap-a-c-fast-and-memory-efficient/23776/11 "2025-11-28T11:49:51Z")
It'd have to check that keys remain in the same order, i.e. that each is Ordering::Greater than the previous. When that is violated it'd have to fall back to the regular approach that allocates new nodes. ---
**Author:** ![FeldrinH](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/feldrinh/32/12286_2.png) [@FeldrinH](https://internals.rust-lang.org/u/FeldrinH)\ **Post date:** [December 2, 2025, 12:42am UTC](https://internals.rust-lang.org/t/btreemap-a-b-btreemap-a-c-fast-and-memory-efficient/23776/12 "2025-12-02T00:42:31Z")
> [@idanarye](#): > > Okay, but my point stands - it's still a tree and insertions still require traversal and balancing, so copying the original tree's structure should be faster. If the keys are sorted then AFAIK you can just construct a balanced tree with empty nodes and copy the keys and values into it in the correct order. No balancing needed, because you create the new tree with a balanced structure from the outset. ---
**Author:** ![tczajka](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tczajka/32/8923_2.png) [@tczajka](https://internals.rust-lang.org/u/tczajka)\ **Post date:** [December 2, 2025, 1:24am UTC](https://internals.rust-lang.org/t/btreemap-a-b-btreemap-a-c-fast-and-memory-efficient/23776/13 "2025-12-02T01:24:56Z")
> [@idanarye](#): > > This whole "sorted happy path" for binary tree insertions sounds weird to me. The tree still has depth - you still need to traverse it and rebalance it on every insertion, and for that it doesn't really matter if the items are sorted or not - it's still `O(log n)` per insertion. I'd understand if `bulk_build_from_sorted_iter` was accepting an `ExactSizeIterator` (and then it could easily deduce the entire structure of the tree) but it doesn't - so I although I did not look into how it works, I doubt its optimizations are as good as what `map_values` can achieve. It's possible to build a B-tree from a sorted iterator in O(1) time per element. You keep a pointer to the rightmost leaf and most of the time you just append to the leaf in O(1) time. It's only when the leaf is full you have to go up one level and rebalance. Even less often you have to go up 2 levels. Etc. It all amortizes to O(1) per element. You can also make it even faster and just keep appending at all levels without rebalancing, and only once at the end rebalance the single rightmost path of non-full nodes. ---
**Author:** ![toc](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/toc/32/6692_2.png) [@toc](https://internals.rust-lang.org/u/toc)\ **Post date:** [December 2, 2025, 1:49am UTC](https://internals.rust-lang.org/t/btreemap-a-b-btreemap-a-c-fast-and-memory-efficient/23776/14 "2025-12-02T01:49:54Z")
> [@tczajka](#): > > O(1) time. It's only when the leaf is full you have to go up one level and rebalance. Even less often you have to go up 2 levels. Etc. It all amortizes to O(1) per element. ~~How much less often? Like `O(log n)` so often? That is me being glib but constructing a B tree is going to make `O(n log n)` so much stuff. It's a small `log n`, which is part of what makes B trees a very nice data structure, but it is there.~~ Edit: Ah nvm whoops. One could pre-allocate the entire tree structure knowing `n`, and I'm sure there are other tricks. Construction from a sorted iterator sounds more generally useful, and only benchmarks will tell if it is useful/fast enough. ---
**Author:** ![tczajka](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tczajka/32/8923_2.png) [@tczajka](https://internals.rust-lang.org/u/tczajka)\ **Post date:** [December 2, 2025, 2:00am UTC](https://internals.rust-lang.org/t/btreemap-a-b-btreemap-a-c-fast-and-memory-efficient/23776/15 "2025-12-02T02:00:10Z")
> [@toc](#): > > How much less often? Like `O(log n)` so often? That is me being glib but constructing a B tree is going to make `O(n log n)` so much stuff. It's a small `log n`, which is part of what makes B trees a very nice data structure, but it is there. B times less often to go up one level, B^2 times less often to go up two levels, etc. So the whole thing amortizes to 1 + (1/B) \* B + (1/B^2) \* B + (1/B^3) \* B + ... \< 1 + 1 + 1/2 + 1/4 + ... \< 3 = O(1) per element. Memory use of the whole B-tree is O(n), not O(n log n). All nodes (except root) are at least half full, after all. Most space is taken up by leaves. ---
**Author:** ![JarredAllen](https://avatars.discourse-cdn.com/v4/letter/j/a183cd/32.png) [@JarredAllen](https://internals.rust-lang.org/u/JarredAllen)\ **Post date:** [December 2, 2025, 9:05pm UTC](https://internals.rust-lang.org/t/btreemap-a-b-btreemap-a-c-fast-and-memory-efficient/23776/16 "2025-12-02T21:05:14Z")
> [@kpcyrd](#): > > "should it panic, should it be unsafe { }" (me personally would prefer "may panic" over "unsafe") I see no reason why we couldn't just have both, like many other stdlib APIs that give a checked and an unchecked version. And in this case, I don't think the unchecked version would even need to be unsafe. Per the docs on `BTreeMap`, it already handles the case of incorrectly-sorted keys because of interior-mutability: > It is a logic error for a key to be modified in such a way that the key’s ordering relative to any other key, as determined by the [`Ord`](https://doc.rust-lang.org/std/cmp/trait.Ord.html) trait, changes while it is in the map. This is normally only possible through [`Cell`](https://doc.rust-lang.org/std/cell/struct.Cell.html), [`RefCell`](https://doc.rust-lang.org/std/cell/struct.RefCell.html), global state, I/O, or unsafe code. The behavior resulting from such a logic error is not specified, but will be encapsulated to the `BTreeMap` that observed the logic error and not result in undefined behavior. This could include panics, incorrect results, aborts, memory leaks, and non-termination. So using `from_sorted_iter_unchecked` with an unsorted iterator wouldn't be any worse than using interior-mutable values to unsort the keys after insertion. It might still be desirable to mark it as `unsafe`, if only to make people think twice about correctness before calling it. I can't think of any other functions in the standard library that can set up such deferred pathological-but-sound behavior for a wide range of possible inputs. ---
**Author:** ![tczajka](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tczajka/32/8923_2.png) [@tczajka](https://internals.rust-lang.org/u/tczajka)\ **Post date:** [December 2, 2025, 9:12pm UTC](https://internals.rust-lang.org/t/btreemap-a-b-btreemap-a-c-fast-and-memory-efficient/23776/17 "2025-12-02T21:12:01Z")
> [@JarredAllen](#): > > And in this case, I don't think the unchecked version would even need to be unsafe. Per the docs on `BTreeMap`, it already handles the case of incorrectly-sorted keys because of interior-mutability: Verifying the order is very cheap compared to, say, looking up all those keys once, so there isn't much value in the unchecked version. I think it would need to be `unsafe` because `BTreeSet` is guaranteed to be ordered. ---
**Author:** ![SkiFire13](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/skifire13/32/7579_2.png) [@SkiFire13](https://internals.rust-lang.org/u/SkiFire13)\ **Post date:** [December 2, 2025, 10:05pm UTC](https://internals.rust-lang.org/t/btreemap-a-b-btreemap-a-c-fast-and-memory-efficient/23776/18 "2025-12-02T22:05:39Z")
> [@JarredAllen](#): > > And in this case, I don't think the unchecked version would even need to be unsafe. Per the docs on `BTreeMap`, it already handles the case of incorrectly-sorted keys because of interior-mutability: It handles that case by not causing UB, but it can result in panics or other weird behaviour. From the point of view of a user of `BTreeMap` this is currently the case only for keys with interior-mutability, i.e. if I receive a `BTreeMap` I expect it to always behave correctly, and a safe `from_sorted_iter_unchecked` would break this.