Repository: paritytech/ink
Pull request #284 (2019-11-27 17:12:07)

Add BTreeMap storage primitive
- [x] Provide API for insert operations
- [x] Provide entry API
- [x] Provide API for removing elements
- [x] More doc comments
- [x] More tests

codecov-io: # [Codecov](https://codecov.io/gh/paritytech/ink/pull/284?src=pr&el=h1) Report
> Merging [#284](https://codecov.io/gh/paritytech/ink/pull/284?src=pr&el=desc) into [master](https://codecov.io/gh/paritytech/ink/commit/63163f73ae1254fe3f67741b38a71057d9ae591a?src=pr&el=desc) will **decrease** coverage by `85.87%`.
> The diff coverage is `n/a`.

[![Impacted file tree graph](https://codecov.io/gh/paritytech/ink/pull/284/graphs/tree.svg?width=650&token=tYyVaCZb7o&height=150&src=pr)](https://codecov.io/gh/paritytech/ink/pull/284?src=pr&el=tree)

```diff
@@             Coverage Diff             @@
##           master     #284       +/-   ##
===========================================
- Coverage     100%   14.12%   -85.88%     
===========================================
  Files           1        7        +6     
  Lines          30      354      +324     
===========================================
+ Hits           30       50       +20     
- Misses          0      304      +304
```


| [Impacted Files](https://codecov.io/gh/paritytech/ink/pull/284?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [lang2/macro/tests/compile\_tests.rs](https://codecov.io/gh/paritytech/ink/pull/284/diff?src=pr&el=tree#diff-bGFuZzIvbWFjcm8vdGVzdHMvY29tcGlsZV90ZXN0cy5ycw==) | | |
| [abi/derive/src/impl\_wrapper.rs](https://codecov.io/gh/paritytech/ink/pull/284/diff?src=pr&el=tree#diff-YWJpL2Rlcml2ZS9zcmMvaW1wbF93cmFwcGVyLnJz) | `0% <0%> (ø)` | |
| [abi/derive/src/lib.rs](https://codecov.io/gh/paritytech/ink/pull/284/diff?src=pr&el=tree#diff-YWJpL2Rlcml2ZS9zcmMvbGliLnJz) | `0% <0%> (ø)` | |
| [abi/derive/src/has\_layout.rs](https://codecov.io/gh/paritytech/ink/pull/284/diff?src=pr&el=tree#diff-YWJpL2Rlcml2ZS9zcmMvaGFzX2xheW91dC5ycw==) | `0% <0%> (ø)` | |
| [abi/src/layout.rs](https://codecov.io/gh/paritytech/ink/pull/284/diff?src=pr&el=tree#diff-YWJpL3NyYy9sYXlvdXQucnM=) | `41.66% <0%> (ø)` | |
| [abi/src/specs.rs](https://codecov.io/gh/paritytech/ink/pull/284/diff?src=pr&el=tree#diff-YWJpL3NyYy9zcGVjcy5ycw==) | `11.68% <0%> (ø)` | |
| [utils/src/hash.rs](https://codecov.io/gh/paritytech/ink/pull/284/diff?src=pr&el=tree#diff-dXRpbHMvc3JjL2hhc2gucnM=) | `0% <0%> (ø)` | |
| [abi/src/lib.rs](https://codecov.io/gh/paritytech/ink/pull/284/diff?src=pr&el=tree#diff-YWJpL3NyYy9saWIucnM=) | `0% <0%> (ø)` | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/paritytech/ink/pull/284?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/paritytech/ink/pull/284?src=pr&el=footer). Last update [63163f7...c279888](https://codecov.io/gh/paritytech/ink/pull/284?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

cmichi: @Robbepop I have implemented most requested changes and to the ones where I have something different to say I replied to your comment. So yeah from my perspective the PR is a good first version to iterate over once we have better benchmarking tools.

Could you please take another look?

Patch:
diff --git a/core/Cargo.toml b/core/Cargo.toml
index 30f01ff27d..3c7e62714e 100644
--- a/core/Cargo.toml
+++ b/core/Cargo.toml
@@ -34,6 +34,9 @@ num-traits = { version = "0.2.1", default-features = false, features = ["i128"]
 # Never use this crate outside of the off-chain environment!
 rand = { version = "0.7", default-features = false, features = ["alloc"], optional = true }
 
+[dev-dependencies]
+itertools = "0.8.2"
+
 [features]
 default = ["std"]
 std = [
diff --git a/core/src/storage/collections/btree_map/impls.rs b/core/src/storage/collections/btree_map/impls.rs
new file mode 100644
index 0000000000..bcd46e66c7
--- /dev/null
+++ b/core/src/storage/collections/btree_map/impls.rs
@@ -0,0 +1,1989 @@
+// Copyright 2018-2020 Parity Technologies (UK) Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+use self::{
+    HandleType::{
+        Branch,
+        Leaf,
+    },
+    InsertResult::{
+        Fit,
+        Split,
+    },
+};
+use super::search::{
+    self,
+    SearchResult::{
+        Found,
+        NotFound,
+    },
+};
+use crate::storage::{
+    self,
+    alloc::{
+        Allocate,
+        AllocateUsing,
+        Initialize,
+    },
+    btree_map::node::{
+        KVHandle,
+        KVPair,
+        KVRef,
+        Node,
+        NodeHandle,
+    },
+    chunk::SyncChunk,
+    Flush,
+};
+use core::{
+    borrow::Borrow,
+    cmp::Ord,
+};
+#[cfg(feature = "ink-generate-abi")]
+use ink_abi::{
+    HasLayout,
+    LayoutField,
+    LayoutStruct,
+    StorageLayout,
+};
+use scale::{
+    Codec,
+    Decode,
+    Encode,
+};
+#[cfg(feature = "ink-generate-abi")]
+use type_metadata::Metadata;
+
+/// Each node in the tree has 2 * B children.
+///
+/// For the moment we use the same number as the Rust standard library
+/// implementation here. There is no empiric evidence for the effectiveness
+/// of this number yet -- we just chose this number to have a first starting
+/// point.
+pub(super) const B: usize = 6;
+
+/// Number of elements (i.e. key/value pairs) which can be stored in one
+/// node of the tree. The `- 1` is because there needs to be an edge to
+/// the right of the last element.
+///
+/// ```no_compile
+/// const B: usize = 2;
+/// const CAPACITY: usize = 2 * B - 1;
+/// keys  = [    a,    b,    c    ];
+/// edges = [ 1,    2,    3,    4 ];
+/// ```
+pub(super) const CAPACITY: usize = 2 * B - 1;
+
+/// The index where a key/value pair is stored in `kv_pairs`.
+pub(super) type KVStorageIndex = u32;
+
+/// The node type, either a `Leaf` (a node without children) or `Branch`
+/// (a node with children). This distinction makes it easier to handle e.g.
+/// cases where nodes are merged or implementing recursion.
+pub(super) enum HandleType {
+    Leaf,
+    Branch,
+}
+
+/// This enum is used when recursively processing an underfull node (i.e. a node has so
+/// few elements that it could be merged with another one). This happens when a key/value
+/// pair is removed from a node.
+///
+/// This enum is returned as a result of `.handle_underfull_node`, which contains
+/// the underfull handling logic. Based on this result the recursion either proceeds or stops.
+enum UnderflowResult {
+    /// We are at the root now.
+    AtRoot,
+    /// The node has an empty parent, referred to by the `NodeHandle` in this tuple.
+    EmptyParent(NodeHandle),
+    /// The elements of an underfull node were merged into its neighboring child.
+    /// `NodeHandle` points to the parent node of these children nodes.
+    /// The node which was merged was subsequently removed.
+    Merged(NodeHandle),
+    /// If merging is not possible we "steal" an element from one child and put it into
+    /// its neighboring child. `NodeHandle` is the parent node.
+    Stole(NodeHandle),
+}
+
+/// Mapping stored in the contract storage.
+///
+/// This implementation follows the algorithm used by the Rust
+/// `BTreeMap` standard library implementation. The Rust implementation
+/// is in-memory, whereas this implementation uses the ink! storage
+/// primitives (`SyncChunk`, etc.).
+#[cfg_attr(feature = "ink-generate-abi", derive(Metadata))]
+pub struct BTreeMap<K, V> {
+    /// Stores densely packed general BTreeMap information.
+    header: storage::Value<BTreeMapHeader>,
+
+    /// Contains the nodes of the tree.
+    nodes: SyncChunk<InternalEntry<K, V>>,
+
+    /// The key/value pairs stored in the tree.
+    /// We don't store this in `nodes` for performance reasons. Instead each
+    /// node of the tree merely stores the storage index where the key/value
+    /// pair is stored.
+    /// This way it's more effective to balance the tree, since we only ever
+    /// have to move the `u32` index, instead of the whole `K`/`V` (which
+    /// would imply decoding, encoding, etc.).
+    kv_pairs: SyncChunk<InternalKVEntry<K, V>>,
+}
+
+/// Densely stored general information required by a map.
+///
+/// # Note
+///
+/// Separation of these fields into a sub structure has been made
+/// for performance reasons so that they all reside in the same
+/// storage entity. This allows implementations to perform less reads
+/// and writes to the underlying contract storage.
+#[derive(Encode, Decode)]
+#[cfg_attr(feature = "ink-generate-abi", derive(Metadata))]
+struct BTreeMapHeader {
+    /// The latest vacant node index.
+    next_vacant: Option<NodeHandle>,
+    /// The latest vacant pair index.
+    next_vacant_pair: Option<KVStorageIndex>,
+    /// The index of the root node.
+    root: Option<NodeHandle>,
+    /// The number of elements stored in the map.
+    ///
+    /// # Note
+    ///
+    /// We cannot simply use the underlying length of the vector
+    /// since it would include vacant slots as well.
+    len: u32,
+    /// Number of nodes the tree contains. This is not the number
+    /// of elements, since each node may contain multiple elements
+    /// (i.e. key/value pairs)!
+    node_count: u32,
+}
+
+impl Flush for BTreeMapHeader {
+    #[inline]
+    fn flush(&mut self) {
+        self.next_vacant.flush();
+        self.next_vacant_pair.flush();
+        self.root.flush();
+        self.len.flush();
+        self.node_count.flush();
+    }
+}
+
+impl<K, V> Initialize for BTreeMap<K, V> {
+    type Args = ();
+
+    #[inline(always)]
+    fn default_value() -> Option<Self::Args> {
+        Some(())
+    }
+
+    #[inline]
+    fn initialize(&mut self, _args: Self::Args) {
+        self.header.set(BTreeMapHeader {
+            next_vacant: None,
+            next_vacant_pair: None,
+            len: 0,
+            node_count: 0,
+            root: None,
+        });
+    }
+}
+
+impl<K: Ord, V> BTreeMap<K, V> {
+    /// Returns the number of elements stored in the map.
+    pub fn len(&self) -> u32 {
+        self.header.len
+    }
+
+    /// Returns `true` if the map contains no elements.
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+}
+
+impl<K, V> Flush for BTreeMap<K, V>
+where
+    K: Encode + Flush,
+    V: Encode + Flush,
+{
+    #[inline]
+    fn flush(&mut self) {
+        self.header.flush();
+        self.nodes.flush();
+        self.kv_pairs.flush();
+    }
+}
+
+impl<K, V> Encode for BTreeMap<K, V> {
+    fn encode_to<W: scale::Output>(&self, dest: &mut W) {
+        self.header.encode_to(dest);
+        self.nodes.encode_to(dest);
+        self.kv_pairs.encode_to(dest);
+    }
+}
+
+impl<K, V> Decode for BTreeMap<K, V> {
+    fn decode<I: scale::Input>(input: &mut I) -> Result<Self, scale::Error> {
+        let header = storage::Value::decode(input)?;
+        let entries = SyncChunk::decode(input)?;
+        let kv_pairs = SyncChunk::decode(input)?;
+        Ok(Self {
+            header,
+            nodes: entries,
+            kv_pairs,
+        })
+    }
+}
+
+impl<K, V> AllocateUsing for BTreeMap<K, V> {
+    #[inline]
+    unsafe fn allocate_using<A>(alloc: &mut A) -> Self
+    where
+        A: Allocate,
+    {
+        Self {
+            header: storage::Value::allocate_using(alloc),
+            nodes: SyncChunk::allocate_using(alloc),
+            kv_pairs: SyncChunk::allocate_using(alloc),
+        }
+    }
+}
+
+impl<K, V> BTreeMap<K, V> {
+    /// Returns the index of the root node.
+    pub(super) fn root(&self) -> &Option<NodeHandle> {
+        &self.header.root
+    }
+}
+
+impl<K, V> BTreeMap<K, V>
+where
+    K: Codec + Ord,
+    V: Codec,
+{
+    /// Returns the `HandleType` of `handle`. Either `Leaf` or `Branch`.
+    /// A branch node always has children, whereas a leaf doesn't.
+    pub(super) fn get_handle_type(&self, handle: NodeHandle) -> HandleType {
+        let children = self
+            .get_node(handle)
+            .expect("node must exist")
+            .edges_count();
+        if children == 0 {
+            Leaf
+        } else {
+            Branch
+        }
+    }
+
+    /// Returns the number of nodes which this tree consists of.
+    pub(super) fn node_count(&self) -> u32 {
+        self.header.node_count
+    }
+
+    /// Descends to the child node pointed to by this `handle`, if one is available.
+    pub(super) fn descend(&self, handle: KVHandle) -> Option<NodeHandle> {
+        let node = self
+            .get_node(handle.node())
+            .expect("node to descend from must exist");
+        node.edge(handle.idx())
+    }
+
+    /// Returns a reference to the node behind `handle`, if existent.
+    ///
+    /// *Note*
+    /// In practice this should never return `None` (except for tests which
+    /// explicitly test this). The calling side should apply an `.expect()`
+    /// to the return value and proof why this can never happen.
+    pub(super) fn get_node(&self, handle: NodeHandle) -> Option<&Node<K, V>> {
+        let entry = self.nodes.get(handle.node())?;
+        match entry {
+            InternalEntry::Occupied(occupied) => Some(occupied),
+            InternalEntry::Vacant(_) => None,
+        }
+    }
+
+    /// Returns the keys stored in this node.
+    pub(super) fn keys_in_node(&self, node: NodeHandle) -> [Option<&K>; CAPACITY] {
+        let node = self.get_node(node).expect("node must exist");
+        let mut ks: [Option<&K>; CAPACITY] = Default::default();
+
+        node.pairs()
+            .iter()
+            .enumerate()
+            .for_each(|(n, maybe_kv_storage_index)| {
+                ks[n] = match maybe_kv_storage_index {
+                    None => None,
+                    Some(kv_storage_index) => {
+                        self.get_kv_ref(*kv_storage_index)
+                            .map(|pair| pair.key_ref())
+                    }
+                };
+            });
+        ks
+    }
+
+    /// Returns a reference to the storage entry behind `storage_index`, if existent.
+    fn get_kv_ref(&self, storage_index: KVStorageIndex) -> Option<&KVPair<K, V>> {
+        let entry = self.kv_pairs.get(storage_index)?;
+        match entry {
+            InternalKVEntry::Occupied(occupied) => Some(occupied),
+            InternalKVEntry::Vacant(_) => None,
+        }
+    }
+
+    /// Returns a mutable reference to the storage entry behind `storage_index`, if existent.
+    fn get_value_mut_ref(&mut self, storage_index: KVStorageIndex) -> Option<&mut V> {
+        let entry = self.kv_pairs.get_mut(storage_index)?;
+        match entry {
+            InternalKVEntry::Occupied(occupied) => Some(occupied.value_ref_mut()),
+            InternalKVEntry::Vacant(_) => None,
+        }
+    }
+
+    /// Returns a reference to the key/value pair referenced by `handle`, if available.
+    fn get_kv(&self, handle: KVHandle) -> Option<KVRef<K, V>> {
+        let node = self.get_node(handle.node()).expect("node must exist");
+        let key_index = node.pair(handle.idx()).as_ref()?;
+        let pair = self.get_kv_ref(*key_index)?;
+        Some(KVRef::new(pair))
+    }
+
+    /// Returns the value referenced by `handle`, if available.
+    fn get_value(&self, handle: KVHandle) -> Option<&V> {
+        let node = self.get_node(handle.node()).expect("node must exist");
+        let value_index = node.pair(handle.idx()).as_ref()?;
+        self.get_kv_ref(*value_index).map(|pair| pair.value_ref())
+    }
+
+    /// If a parent node is set for the node referenced by `handle`, a handle to
+    /// this parent node will be returned.
+    fn ascend(&self, handle: NodeHandle) -> Option<KVHandle> {
+        let node = self
+            .get_node(handle)
+            .expect("node to ascend from must exist");
+
+        node.parent().map(|parent| {
+            let idx = node
+                .parent_idx()
+                .expect("if parent exists, parent_idx always exist as well; qed");
+            KVHandle::new(parent, idx)
+        })
+    }
+
+    /// Creates a root node with `key` and `val`.
+    ///
+    /// Returns the storage index of the inserted pair.
+    fn create_root(&mut self, key: K, val: V) -> KVStorageIndex {
+        debug_assert!(self.is_empty());
+        debug_assert!(self.root().is_none());
+
+        let pair = KVPair::<K, V>::new(key, val);
+        let storage_index = self.put_pair(pair);
+
+        let mut node = Node::<K, V>::new();
+        node.set_pair(0, Some(storage_index));
+        node.set_len(1);
+
+        let index = self.put(node);
+        self.header.len = 1;
+        self.header.root = Some(index);
+
+        storage_index
+    }
+
+    /// Inserts `key` and `val` at `handle`.
+    ///
+    /// Returns a reference to the inserted value.
+    fn insert_kv(&mut self, handle: KVHandle, key: K, val: V) -> KVStorageIndex {
+        let mut ins_pair_index;
+        let mut ins_edge;
+        let out_storage_index;
+
+        let pair = KVPair::<K, V>::new(key, val);
+        let pair_storage_index = self.put_pair(pair);
+
+        let mut cur_parent = match self.insert_into_node(handle, pair_storage_index) {
+            (Fit(_), idx) => return idx,
+            (Split(left, pair_index, right), storage_index) => {
+                ins_pair_index = pair_index;
+                ins_edge = right;
+                out_storage_index = storage_index;
+                self.ascend(left.node())
+            }
+        };
+
+        // This loop is run when the insert operation above resulted in a split node and
+        // we now have an element `ins_pair_index` which needs to be inserted at another
+        // place in the tree.
+        //
+        // The loop tries to recursively insert the element up the tree. This might well
+        // result in more split nodes with other `ins_pair_index` which then need to be
+        // inserted further up.
+        //
+        // The loop always breaks because if the root is reached and we still have an
+        // element to insert, we just create a new root with the old root as a child and
+        // insert the element into the new root then.
+        loop {
+            match cur_parent {
+                Some(parent) => {
+                    match self.insert_into_branch_node(parent, ins_pair_index, ins_edge) {
+                        Fit(_) => {
+                            self.header.len += 1;
+                            return out_storage_index
+                        }
+                        Split(left, storage_index, right) => {
+                            ins_pair_index = storage_index;
+                            ins_edge = right;
+                            cur_parent = self.ascend(left.node());
+                        }
+                    }
+                }
+                None => {
+                    let new_root = self.root_push_level();
+                    self.header.len += 1;
+                    self.push_branch(new_root, ins_pair_index, ins_edge);
+                    return out_storage_index
+                }
+            }
+        }
+    }
+
+    /// Traverses downwards from `handle`, always taking the first edge down.
+    /// Once a leaf is reached a handle to the first edge in the leaf is returned.
+    fn first_leaf_edge(&self, mut handle: NodeHandle) -> KVHandle {
+        loop {
+            match self.get_handle_type(handle) {
+                Leaf => return self.first_edge(handle),
+                Branch => {
+                    let first_edge = self.first_edge(handle);
+                    handle = self
+                        .descend(first_edge)
+                        .expect("every branch node has children; qed");
+                }
+            }
+        }
+    }
+
+    /// Returns a handle to the first edge in the node.
+    fn first_edge(&self, handle: NodeHandle) -> KVHandle {
+        KVHandle::new(handle, 0)
+    }
+
+    /// Returns the edge left to `handle`.
+    fn left_edge(&self, handle: KVHandle) -> KVHandle {
+        KVHandle::new(handle.node(), handle.idx())
+    }
+
+    /// Returns the edge right to `handle`.
+    fn right_edge(&self, handle: KVHandle) -> KVHandle {
+        KVHandle::new(handle.node(), handle.idx() + 1)
+    }
+
+    /// Returns a handle to the key/value pair storage index left of `handle`.
+    ///
+    /// If `handle` already points to the first element in the node
+    /// an `Err(handle)` is returned. The handle contained in `Err(handle)`
+    /// is the one supplied as the `handle` argument to this function.
+    fn left_kv(&self, handle: KVHandle) -> Option<KVHandle> {
+        if handle.idx() > 0 {
+            Some(KVHandle::new(handle.node(), handle.idx() - 1))
+        } else {
+            None
+        }
+    }
+
+    /// Returns a handle to the key/value pair storage index right of `handle`.
+    ///
+    /// If `handle` already points to the last element in the node an
+    /// `Err(handle)` is returned. The handle contained in `Err(handle)`
+    /// is the one supplied as the `handle` argument to this function.
+    fn right_kv(&self, handle: KVHandle) -> Option<KVHandle> {
+        let node = self
+            .get_node(handle.node())
+            .expect("node to descend from must exist");
+        if handle.idx() < node.len() {
+            Some(handle)
+        } else {
+            None
+        }
+    }
+
+    /// Removes the key/value pair storage index pointed to by `handle`.
+    ///
+    /// If through this removal an underfull node was created, appropriate strategies
+    /// will be deployed (`.handle_underfull_node`).
+    ///
+    /// Returns the removed value.
+    fn remove_kv(&mut self, handle: KVHandle) -> V {
+        debug_assert!(self.header.len > 0);
+        self.header.len -= 1;
+
+        let handle_type = self.get_handle_type(handle.node());
+        let (small_leaf, old_pair_index, mut new_len) = match handle_type {
+            Leaf => self.extract_handle(handle),
+            Branch => {
+                let child = self
+                    .right_child(handle)
+                    .expect("every branch node has children; qed");
+                let first_leaf = self.first_leaf_edge(child);
+
+                let to_remove = self.right_kv(first_leaf).expect("right_kv must exist");
+                let (hole, pair_storage_index, nl) = self.extract_handle(to_remove);
+
+                let node = self.get_node_mut(handle.node()).expect("node must exist");
+                let old_pair_index = node
+                    .set_pair(handle.idx(), Some(pair_storage_index))
+                    .expect("handle must be valid");
+                (hole, old_pair_index, nl)
+            }
+        };
+
+        let mut handle = small_leaf.node();
+        while new_len < CAPACITY / 2 {
+            match self.handle_underfull_node(handle) {
+                UnderflowResult::AtRoot => break,
+                UnderflowResult::EmptyParent(_) => unreachable!(
+                    "[ink_core::BTreeMap::remove_kv] Error: \
+                     while handling an underfull node it was found that its parent \
+                     node is empty. This can never happen since we always re-balance the tree \
+                     when an element is removed."
+                ),
+                UnderflowResult::Merged(parent) => {
+                    let parent_node =
+                        self.get_node(parent).expect("parent node must exist");
+                    if parent_node.len() == 0 {
+                        self.root_pop_level();
+                        break
+                    } else {
+                        handle = parent;
+                        new_len = parent_node.len();
+                    }
+                }
+                UnderflowResult::Stole(_) => break,
+            }
+        }
+
+        let old = self.remove_pair(old_pair_index).value();
+        if new_len == 0 {
+            debug_assert_eq!(
+                self.get_node(handle)
+                    .expect("node must exist")
+                    .edges_count(),
+                0
+            );
+            self.remove_node(handle);
+            self.header.root = None;
+            self.header.next_vacant = None;
+            self.header.next_vacant_pair = None;
+        }
+        old
+    }
+
+    /// An underfull node contains less than `CAPACITY / 2` elements and provides
+    /// an opportunity to reduce storage space by merging nodes together.
+    ///
+    /// If merging is not possible we "steal" an element from one node and
+    /// put it into its neighboring node.
+    ///
+    /// The returned `UnderflowResult` contains the result of handling the
+    /// underfull node.
+    fn handle_underfull_node(&mut self, node: NodeHandle) -> UnderflowResult {
+        let parent = if let Some(parent) = self.ascend(node) {
+            parent
+        } else {
+            return UnderflowResult::AtRoot
+        };
+
+        let (is_left, handle) = match self.left_kv(parent) {
+            Some(left) => (true, left),
+            None => {
+                match self.right_kv(parent) {
+                    Some(right) => (false, right),
+                    None => return UnderflowResult::EmptyParent(parent.node()),
+                }
+            }
+        };
+
+        if self.can_merge(handle) {
+            self.merge(handle);
+            UnderflowResult::Merged(handle.node())
+        } else {
+            if is_left {
+                self.steal_left(handle);
+            } else {
+                self.steal_right(handle);
+            }
+            UnderflowResult::Stole(handle.node())
+        }
+    }
+
+    /// Returns `true` if it is valid to call `.merge()`, i.e. whether there is
+    /// enough room in a node to hold the combination of the nodes to the left
+    /// and right of `handle` along with an additional key/value pair storage index.
+    fn can_merge(&self, handle: KVHandle) -> bool {
+        let len_left = self
+            .left_child_node(handle)
+            .expect("left child must exist")
+            .len();
+        let len_right = self
+            .right_child_node(handle)
+            .expect("right child must exist")
+            .len();
+
+        len_left + len_right < CAPACITY
+    }
+
+    /// Merges the right child of `handle` with the pair storage index pointed
+    /// to by `handle` into the left child. The right child is removed.
+    ///
+    /// Assumes that this edge `.can_merge()`.
+    fn merge(&mut self, handle: KVHandle) {
+        let right_child = self
+            .right_child(handle)
+            .expect("right child must exist 591");
+        let right_node = self.get_node(right_child).expect("right child must exist");
+        let right_edges = right_node.edges;
+        let right_pairs = right_node.pairs;
+        let right_len = right_node.len();
+
+        let (removed_pair_storage_index, old_node_len) =
+            self.extract_handle_for_merge(handle);
+
+        let left_child = self.left_child(handle).expect("left child must exist");
+        let left_node = self
+            .get_node_mut(left_child)
+            .expect("left child must exist");
+        let left_len = left_node.len();
+
+        debug_assert!(left_len + right_len < CAPACITY);
+
+        left_node.set_pair(left_len, removed_pair_storage_index);
+        let src = &right_pairs[..right_len];
+        let start = left_len + 1;
+        let end = left_len + 1 + right_len;
+        left_node.set_pair_range(src, start..end);
+        left_node.set_len(left_len + right_len + 1);
+
+        for i in handle.idx() + 1..old_node_len {
+            let h = KVHandle::new(handle.node(), i);
+            self.correct_parent_link(h);
+        }
+
+        // If the right child has children we need to take care of those
+        // by merging the edges of the child into the left node as well.
+        if self.has_children(right_child) {
+            let from = left_len + 1;
+            let to = right_len + 1;
+            let left_node = self
+                .get_node_mut(left_child)
+                .expect("left child must exist");
+            left_node.set_edges_range(&right_edges[..to], from..from + to);
+
+            for i in left_len + 1..left_len + right_len + 2 {
+                let h = KVHandle::new(left_child, i);
+                self.correct_parent_link(h);
+            }
+        }
+
+        self.remove_node(right_child);
+    }
+
+    /// Extracts the storage index referenced by `handle`, decreases the node
+    /// length and returns `(removed_pair_storage_index, old_length)`.
+    fn extract_handle_for_merge(
+        &mut self,
+        handle: KVHandle,
+    ) -> (Option<KVStorageIndex>, usize) {
+        let node = self.get_node_mut(handle.node()).expect("node must exist");
+        let _removed_edge = node.remove_edge_with_shift(handle.idx() + 1);
+        let removed_pair_storage_index = node.remove_pair_with_shift(handle.idx());
+        let old_len = node.len();
+        node.set_len(old_len - 1);
+        (removed_pair_storage_index, old_len)
+    }
+
+    /// Removes a key/value pair storage index from the end of the node referenced by `handle`.
+    /// If this is a branch node the edge that was to the right of that pair is also removed.
+    ///
+    /// Returns `(removed_pair_storage_index, Option<removed_edge>)`.
+    fn pop(&mut self, handle: NodeHandle) -> (KVStorageIndex, Option<NodeHandle>) {
+        let handle_type = self.get_handle_type(handle);
+        let (pair_storage_index, idx) = {
+            let node = self.get_node_mut(handle).expect("node must exist");
+            debug_assert!(node.len() > 0);
+            let idx = node.len() - 1;
+            let pair_index = node.take_pair(idx).expect("pair must exist");
+            node.set_len(node.len() - 1);
+            (pair_index, idx)
+        };
+        let edge = match handle_type {
+            Leaf => None,
+            Branch => {
+                // If `handle` is a reference to a branch node we also remove the edge right
+                // of it.
+                let edge = {
+                    let node = self.get_node_mut(handle).expect("node must exist");
+                    node.take_edge(idx + 1).expect("edge must exist")
+                };
+                let edge_handle = NodeHandle::new(edge.node());
+                self.set_parent(edge_handle, None, None);
+                Some(edge_handle)
+            }
+        };
+
+        (pair_storage_index, edge)
+    }
+
+    /// This removes a pair storage index from the left child and replaces it with the
+    /// storage index pointed to by `handle` while pushing the old storage index
+    /// of `handle` into the right child.
+    fn steal_left(&mut self, handle: KVHandle) {
+        let left_child = self.left_child(handle).expect("left child must exist");
+        let (pair_index, edge) = self.pop(left_child);
+
+        let node = self.get_node_mut(handle.node()).expect("node must exist");
+        let pair_storage_index = node
+            .set_pair(handle.idx(), Some(pair_index))
+            .expect("pair must exist");
+
+        let right = self.right_edge(handle);
+        let child = self.descend(right).expect("child must exist");
+        match self.get_handle_type(child) {
+            Leaf => self.push_front_leaf(child, pair_storage_index),
+            Branch => {
+                self.push_front_branch(
+                    child,
+                    pair_storage_index,
+                    edge.expect("edge always exists for branch nodes"),
+                )
+            }
+        }
+    }
+
+    /// This removes a key/value pair storage index from the right child and replaces it
+    /// with the key/value pair index pointed to by `handle` while pushing the old key/value
+    /// pair index of `handle` into the left child.
+    fn steal_right(&mut self, handle: KVHandle) {
+        let right = self.right_edge(handle);
+        let child = self.descend(right).expect("child must exist");
+        let (k, edge) = self.pop_front(child);
+
+        let node = self.get_node_mut(handle.node()).expect("node must exist");
+        let pair_storage_index = node
+            .set_pair(handle.idx(), Some(k))
+            .expect("pair must exist");
+
+        let left_child = self.left_child(handle).expect("left child must exist");
+        match self.get_handle_type(left_child) {
+            Leaf => self.push_leaf(left_child, pair_storage_index),
+            Branch => {
+                self.push_branch(
+                    left_child,
+                    pair_storage_index,
+                    edge.expect("edge always exists for branch node"),
+                )
+            }
+        }
+    }
+
+    /// Removes the storage index of a key/value pair from the beginning of this node.
+    /// If this is a branch node, also removes the edge that was to the left of that pair.
+    ///
+    /// *Note:* This method does not actually remove the storage entry! Just the pointer
+    /// to the index of it!
+    ///
+    /// Returns `(removed_storage_index, Option<removed_edge>)`.
+    fn pop_front(&mut self, handle: NodeHandle) -> (KVStorageIndex, Option<NodeHandle>) {
+        let typ = self.get_handle_type(handle);
+        let node = self.get_node_mut(handle).expect("node must exist");
+
+        debug_assert!(node.len() > 0);
+        let old_len = node.len();
+
+        let pair_storage_index = node.remove_pair_with_shift(0).expect("pair must exist");
+
+        let edge = match typ {
+            Leaf => None,
+            Branch => {
+                let edge = node.remove_edge_with_shift(0).expect("edge must exist");
+
+                // Create a new `NodeHandle` to the new root
+                let new_root = NodeHandle::new(edge.node());
+                self.set_parent(new_root, None, None);
+
+                for i in 0..old_len {
+                    let h = KVHandle::new(handle, i);
+                    self.correct_parent_link(h);
+                }
+
+                Some(new_root)
+            }
+        };
+
+        let node = self.get_node_mut(handle).expect("node must exist");
+        node.set_len(node.len() - 1);
+
+        (pair_storage_index, edge)
+    }
+
+    /// Adds a key/value pair storage index to the beginning of the node.
+    fn push_front_leaf(
+        &mut self,
+        handle: NodeHandle,
+        pair_storage_index: KVStorageIndex,
+    ) {
+        let node = self.get_node_mut(handle).expect("node must exist");
+        debug_assert!(node.len() < CAPACITY);
+
+        node.push_pair_to(0, pair_storage_index);
+        node.set_len(node.len() + 1);
+    }
+
+    /// Adds a key/value pair storage index to the beginning of the node.
+    /// Furthermore an `edge` to go to the left of that pair is added to
+    /// the beginning of the node.
+    fn push_front_branch(
+        &mut self,
+        handle: NodeHandle,
+        pair_storage_index: KVStorageIndex,
+        edge: NodeHandle,
+    ) {
+        let node = self.get_node_mut(handle).expect("node must exist");
+        debug_assert!(node.len() < CAPACITY);
+
+        node.push_pair_to(0, pair_storage_index);
+        node.push_edge_to(0, edge);
+        node.set_len(node.len() + 1);
+
+        self.correct_all_children_parent_links(handle);
+    }
+
+    /// Removes a node by replacing its storage entity with the index of the current
+    /// top element in the linked list of vacant storage entries and sets
+    /// `header.next_vacant` to the new top element -- `handle`.
+    fn remove_node(&mut self, handle: NodeHandle) {
+        let n = handle.node();
+        let _ = match self.nodes.get(n) {
+            None | Some(InternalEntry::Vacant(_)) => None,
+            Some(InternalEntry::Occupied(_)) => {
+                match self
+                    .nodes
+                    .put(n, InternalEntry::Vacant(self.header.next_vacant))
+                    .expect(
+                        "[ink_core::BTreeMap::remove_node] Error: \
+                         we already asserted that the entry at `n` exists",
+                    ) {
+                    InternalEntry::Occupied(val) => {
+                        // When removing a node set `next_vacant` to this node index
+                        self.header.next_vacant = Some(NodeHandle::new(n));
+                        self.header.node_count -= 1;
+                        Some(val)
+                    }
+                    InternalEntry::Vacant(_) => {
+                        unreachable!(
+                            "[ink_core::BTreeMap::remove_node] Error: \
+                             we already asserted that the entry is occupied"
+                        )
+                    }
+                }
+            }
+        };
+    }
+
+    /// Removes a pair by replacing its storage entity with the index of the current
+    /// top element in the linked list of vacant storage entries and setting
+    /// `header.next_vacant_pair` to the new top element -- `handle`.
+    fn remove_pair(&mut self, storage_index: KVStorageIndex) -> KVPair<K, V> {
+        let pair = match self.kv_pairs.get(storage_index) {
+            None | Some(InternalKVEntry::Vacant(_)) => None,
+            Some(InternalKVEntry::Occupied(_)) => {
+                match self
+                    .kv_pairs
+                    .put(
+                        storage_index,
+                        InternalKVEntry::Vacant(self.header.next_vacant_pair),
+                    )
+                    .expect(
+                        "[ink_core::BTreeMap::remove_pair] Error: \
+                         we already asserted that the pair at `n` exists",
+                    ) {
+                    InternalKVEntry::Occupied(val) => {
+                        // When removing a pair set `next_vacant_pair` to this node index
+                        self.header.next_vacant_pair = Some(storage_index);
+                        Some(val)
+                    }
+                    InternalKVEntry::Vacant(_) => {
+                        unreachable!(
+                            "[ink_core::BTreeMap::remove_pair] Error: \
+                             we already asserted that the pair is occupied"
+                        )
+                    }
+                }
+            }
+        };
+        pair.expect("must exist")
+    }
+
+    /// Extracts the key/value pair storage index pointed to by `handle`, returning
+    /// the edge between the now adjacent key/value pairs to the left and right of `handle`.
+    ///
+    /// Returns `(left_edge, removed_pair_storage_index, old_val, new_node_len)`.
+    fn extract_handle(&mut self, handle: KVHandle) -> (KVHandle, KVStorageIndex, usize) {
+        let node = self.get_node_mut(handle.node()).expect("node must exist");
+        let pair_storage_index = node
+            .remove_pair_with_shift(handle.idx())
+            .expect("pair must exist");
+        node.set_len(node.len() - 1);
+        let new_len = node.len();
+        (self.left_edge(handle), pair_storage_index, new_len)
+    }
+
+    /// Returns a mutable reference to the node referenced by `handle`.
+    fn get_node_mut(&mut self, handle: NodeHandle) -> Option<&mut Node<K, V>> {
+        let entry = self.nodes.get_mut(handle.node())?;
+        match entry {
+            InternalEntry::Occupied(occupied) => Some(occupied),
+            InternalEntry::Vacant(_) => None,
+        }
+    }
+
+    /// Put the element into the tree at the next vacant position.
+    ///
+    /// Returns the tree index that the element was put into.
+    fn put(&mut self, node: Node<K, V>) -> NodeHandle {
+        let node_handle = match self.header.next_vacant {
+            None => {
+                // then there is no vacant entry which we can reuse
+                self.nodes
+                    .set(self.node_count(), InternalEntry::Occupied(node));
+                NodeHandle::new(self.node_count())
+            }
+            Some(current_vacant) => {
+                // then there is a vacant entry which we can reuse
+                let next_vacant = match self
+                    .nodes
+                    .put(current_vacant.node(), InternalEntry::Occupied(node))
+                    .expect(
+                        "[ink_core::BTreeMap::put] Error: \
+                         expected a vacant entry here, but no entry was found",
+                    ) {
+                    InternalEntry::Vacant(next_vacant) => next_vacant,
+                    InternalEntry::Occupied(_) => {
+                        unreachable!(
+                            "[ink_core::BTreeMap::put] Error: \
+                             a next_vacant index can never point to an occupied entry"
+                        )
+                    }
+                };
+                // when putting node set next_vacant to the next_vacant which was found here
+                self.header.next_vacant = next_vacant;
+                current_vacant
+            }
+        };
+        self.header.node_count += 1;
+        node_handle
+    }
+
+    /// Put a key/value pair storage index into the tree at the next vacant position.
+    ///
+    /// Returns the storage index that the element was put into.
+    fn put_pair(&mut self, pair: KVPair<K, V>) -> KVStorageIndex {
+        match self.header.next_vacant_pair {
+            None => {
+                // then there is no vacant entry which we can reuse
+                self.kv_pairs
+                    .set(self.len(), InternalKVEntry::Occupied(pair));
+                self.len()
+            }
+            Some(current_vacant) => {
+                // then there is a vacant entry which we can reuse
+                let next_vacant = match self
+                    .kv_pairs
+                    .put(current_vacant, InternalKVEntry::Occupied(pair))
+                    .expect(
+                        "[ink_core::BTreeMap::put_pair] Error: \
+                         expected a vacant entry here, but no entry was found",
+                    ) {
+                    InternalKVEntry::Vacant(next_vacant) => next_vacant,
+                    InternalKVEntry::Occupied(_) => {
+                        unreachable!(
+                            "[ink_core::BTreeMap::put_pair] Error: \
+                             a next_vacant index can never point to an occupied entry"
+                        )
+                    }
+                };
+                // when putting node set next_vacant to the next_vacant which was found here
+                self.header.next_vacant_pair = next_vacant;
+                current_vacant
+            }
+        }
+    }
+
+    /// Adds the storage index of a key/value pair to the end of the `dst` node.
+    /// Furthermore an `edge` is added right of that pair, at the end of the node.
+    fn push_branch(
+        &mut self,
+        dst: NodeHandle,
+        pair_storage_index: KVStorageIndex,
+        edge: NodeHandle,
+    ) {
+        let node = self.get_node_mut(dst).expect("destination node must exist");
+        node.set_pair(node.len(), Some(pair_storage_index));
+        node.set_edge(node.len() + 1, Some(edge));
+
+        let handle = KVHandle::new(dst, node.len() + 1);
+        node.set_len(node.len() + 1);
+        self.correct_parent_link(handle);
+    }
+
+    /// Adds the storage index of a key/value pair to the end of the `dst` node.
+    fn push_leaf(&mut self, dst: NodeHandle, pair_storage_index: KVStorageIndex) {
+        let node = self.get_node_mut(dst).expect("destination node must exist");
+
+        debug_assert!(node.len() < CAPACITY);
+
+        let idx = node.len();
+        node.set_pair(idx, Some(pair_storage_index));
+        node.set_len(node.len() + 1);
+    }
+
+    /// Splits the underlying node into three parts:
+    ///
+    /// - The node is truncated to only contain the key/value pair storage index
+    ///   to the right of `handle`.
+    /// - The key and value pointed to by `handle` and extracted.
+    /// - All the key/value pairs to the right of `handle` are put into a newly
+    ///   allocated node.
+    ///
+    /// Returns a tuple of `(extracted_pair_storage_index, handle_to_new_node)`.
+    fn split_leaf(
+        &mut self,
+        handle: NodeHandle,
+        idx: usize,
+    ) -> (KVStorageIndex, NodeHandle) {
+        let node = self.get_node_mut(handle).expect("node to split must exist");
+
+        // We can only start splitting at leaf nodes.
+        debug_assert_eq!(node.edges_count(), 0);
+
+        let mut right = Node::new();
+        let pair_storage_index = node
+            .take_pair(idx)
+            .expect("pair must exist at split location");
+        node.set_len(node.len() - 1);
+
+        let from = idx + 1;
+        for i in from..CAPACITY {
+            let a = i - from;
+            right.set_pair(a, node.take_pair(i));
+            if right.pair(a).is_some() {
+                if node.len() > 0 {
+                    node.set_len(node.len() - 1);
+                }
+                right.set_len(right.len() + 1);
+            }
+        }
+
+        let right_handle = self.put(right);
+        (pair_storage_index, right_handle)
+    }
+
+    /// Splits the underlying node into three parts:
+    ///
+    /// - The node is truncated to only contain the edges and key/value pair index
+    ///   to the right of `handle`.
+    /// - The key and value pointed to by `handle` and extracted.
+    /// - All the edges and key/value pair storage index to the right of `handle` are
+    ///   put into a newly allocated node.
+    ///
+    /// Returns a tuple of `(extracted_key, extracted_value, handle_to_new_node)`.
+    fn split_branch(
+        &mut self,
+        parent: NodeHandle,
+        idx: usize,
+    ) -> (KVStorageIndex, NodeHandle) {
+        let node = self.get_node_mut(parent).expect("node to split must exist");
+
+        let count = node.len();
+        let new_len = count - idx - 1;
+
+        let mut right = Node::new();
+        right.set_parent(Some(parent));
+        right.set_parent_idx(Some(idx));
+
+        let pair_storage_index = node
+            .take_pair(idx)
+            .expect("pair must exist at split location");
+        node.set_len(node.len() - 1);
+
+        let from = idx + 1;
+        for a in 0..new_len {
+            let i = from + a;
+            right.set_pair(a, node.take_pair(i));
+            if right.pair(a).is_some() {
+                node.set_len(node.len() - 1);
+                right.set_len(right.len() + 1);
+            }
+        }
+        for a in 0..=new_len {
+            let i = from + a;
+            right.set_edge(a, node.take_edge(i));
+        }
+
+        let right_handle = self.put(right);
+        for i in 0..=new_len {
+            let handle = KVHandle::new(right_handle, i);
+            self.correct_parent_link(handle);
+        }
+
+        (pair_storage_index, right_handle)
+    }
+
+    /// Adds a new branch node with a single edge, pointing to the previous root, and make that
+    /// new node the root. This increases the height by 1 and is the opposite of `pop_level`.
+    ///
+    /// Returns a handle to the new root node.
+    fn root_push_level(&mut self) -> NodeHandle {
+        let current_root_handle = self.header.root.expect("node must exist");
+
+        let mut new_root = Node::<K, V>::new();
+        new_root.set_edge(0, Some(current_root_handle));
+        let new_root_handle = self.put(new_root);
+
+        self.set_parent(
+            self.header.root.expect("root must exist"),
+            Some(new_root_handle),
+            Some(0),
+        );
+
+        self.header.root = Some(new_root_handle);
+        new_root_handle
+    }
+
+    /// Removes the root node, using its first child as the new root. This cannot be called when
+    /// the tree consists only of a leaf node. As it is intended only to be called when the root
+    /// has only one edge, no cleanup is done on any of the other children are elements of the root.
+    /// This decreases the height by 1 and is the opposite of `push_level`.
+    fn root_pop_level(&mut self) {
+        let handle = self.header.root.expect("root must exist");
+        debug_assert!(
+            self.get_node(handle)
+                .expect("root must exist")
+                .edges_count()
+                == 1
+        );
+        let edge = self.first_edge(handle);
+
+        let child = self.descend(edge).expect("child must exist");
+        self.set_parent(child, None, None);
+
+        self.header.root = Some(child);
+
+        self.remove_node(handle);
+    }
+
+    /// Sets the parent node of `handle` to `parent` and its `idx` to `parent_idx`.
+    fn set_parent(
+        &mut self,
+        handle: NodeHandle,
+        parent_node: Option<NodeHandle>,
+        parent_idx: Option<usize>,
+    ) {
+        let node = self.get_node_mut(handle).expect("node must exist");
+        node.set_parent(parent_node);
+        node.set_parent_idx(parent_idx);
+    }
+
+    /// Inserts a key/value pair storage index at `handle`. If this results in an overfull
+    /// node the node is split.
+    ///
+    /// Returns the `(result_of_insert_operation, mutable_reference_to_inserted_value)`.
+    fn insert_into_node(
+        &mut self,
+        handle: KVHandle,
+        pair_storage_index: KVStorageIndex,
+    ) -> (InsertResult, KVStorageIndex) {
+        let node = self
+            .get_node(handle.node())
+            .expect("node to insert into must exist");
+        let len = node.len();
+
+        let pair = self
+            .get_kv_ref(pair_storage_index)
+            .expect("requested pair must always exist");
+        let k = &pair.key_ref();
+
+        if len < CAPACITY {
+            let h = match search::search_node(
+                node,
+                self.keys_in_node(handle.node()),
+                handle.node(),
+                k,
+            ) {
+                Found(h) => h,
+                NotFound(h) => h,
+            };
+            let a = self.insert_fit(h, pair_storage_index);
+            self.header.len += 1;
+            (Fit(handle), a)
+        } else {
+            let (extracted_pair_index, right) = self.split_leaf(handle.node(), B);
+
+            let index = if handle.idx() <= B {
+                // handle is left side
+                self.insert_fit(handle, pair_storage_index)
+            } else {
+                let h = KVHandle::new(right, handle.idx() - (B + 1));
+                self.insert_fit(h, pair_storage_index)
+            };
+
+            (Split(handle, extracted_pair_index, right), index)
+        }
+    }
+
+    /// Insert `K`, `V` and `edge` into `handle` if it fits. If it does not fit the node
+    /// referenced by `handle` is split.
+    ///
+    /// Returns the result of the insert operation.
+    fn insert_into_branch_node(
+        &mut self,
+        handle: KVHandle,
+        pair_storage_index: KVStorageIndex,
+        edge: NodeHandle,
+    ) -> InsertResult {
+        let pair = self
+            .get_kv_ref(pair_storage_index)
+            .expect("requested pair must always exist");
+        let k = &pair.key_ref();
+
+        let node = self
+            .get_node(handle.node())
+            .expect("parent to insert into must exist");
+
+        if node.len() < CAPACITY {
+            let kv_handle = match search::search_node(
+                node,
+                self.keys_in_node(handle.node()),
+                handle.node(),
+                &k,
+            ) {
+                Found(h) => h,
+                NotFound(h) => h,
+            };
+            self.insert_fit_edge(kv_handle, pair_storage_index, edge);
+            Fit(kv_handle)
+        } else {
+            let (extracted_pair_index, right) = self.split_branch(handle.node(), B);
+            if handle.idx() <= B {
+                // Handle is left side.
+                self.insert_fit_edge(handle, pair_storage_index, edge);
+            } else {
+                let h = KVHandle::new(right, handle.idx() - (B + 1));
+                self.insert_fit_edge(h, pair_storage_index, edge);
+            }
+
+            Split(handle, extracted_pair_index, right)
+        }
+    }
+
+    /// Inserts a new key/value pair storage index between the key/value pairs to the right
+    /// and left of this edge. This method assumes that there is enough space in the node for
+    /// the new pair to fit.
+    ///
+    /// The returned storage index points to the inserted value.
+    fn insert_fit(
+        &mut self,
+        handle: KVHandle,
+        pair_storage_index: KVStorageIndex,
+    ) -> KVStorageIndex {
+        let node = self
+            .get_node_mut(handle.node())
+            .expect("node to insert_fit into must exist");
+        debug_assert!(node.len() < CAPACITY);
+
+        node.push_pair_to(handle.idx(), pair_storage_index);
+        node.set_len(node.len() + 1);
+        pair_storage_index
+    }
+
+    /// Inserts a new key/value pair storage index and an edge that will go to the right of
+    /// that new pair between this edge and the key/value pair storage index to the right
+    /// of this edge.
+    /// This method assumes that there is enough space in the node for the new pair to fit.
+    fn insert_fit_edge(
+        &mut self,
+        handle: KVHandle,
+        pair_storage_index: KVStorageIndex,
+        edge: NodeHandle,
+    ) {
+        self.insert_fit(handle, pair_storage_index);
+
+        let node = self
+            .get_node_mut(handle.node())
+            .expect("node to insert (k, v, edge) into must exist");
+
+        node.push_edge_to(handle.idx() + 1, edge);
+
+        for idx in (handle.idx() + 1)..=node.len() {
+            let handle = KVHandle::new(handle.node(), idx);
+            self.correct_parent_link(handle);
+        }
+    }
+
+    /// Returns the node of the left child of `handle`.
+    fn left_child_node(&self, handle: KVHandle) -> Option<&Node<K, V>> {
+        let child = self.left_child(handle)?;
+        self.get_node(child)
+    }
+
+    /// Returns the node of the right child of `handle`.
+    fn right_child_node(&self, handle: KVHandle) -> Option<&Node<K, V>> {
+        let child = self.right_child(handle)?;
+        self.get_node(child)
+    }
+
+    /// Returns a handle to the left child of `handle`.
+    fn left_child(&self, handle: KVHandle) -> Option<NodeHandle> {
+        let left = self.left_edge(handle);
+        self.descend(left)
+    }
+
+    /// Returns a handle to the right child of `handle`.
+    fn right_child(&self, handle: KVHandle) -> Option<NodeHandle> {
+        let right = self.right_edge(handle);
+        self.descend(right)
+    }
+
+    /// Fixes the parent pointer and index in the child node below this edge. This is useful
+    /// when the ordering of edges has been changed, such as in the various `insert` methods.
+    /// Then the parent pointer in the child nodes has to be updated, otherwise they would
+    /// point to some entry in `edges` which is no longer correct.
+    fn correct_parent_link(&mut self, handle: KVHandle) {
+        let child = self
+            .descend(handle)
+            .expect("child in which to correct parent link must exist");
+        self.set_parent(child, Some(handle.node()), Some(handle.idx()));
+    }
+
+    /// Iterates through all children of a node and fixes the parent pointer in the child.
+    /// Each child contains a pointer to a position in the `edges` array. Sometimes (e.g. for
+    /// `insert` operations) the order in the `edges` array changes and the child pointers
+    /// have to be corrected.
+    fn correct_all_children_parent_links(&mut self, handle: NodeHandle) {
+        let node = self.get_node(handle).expect("node must exist");
+        let len = node.len();
+
+        for i in 0..=len {
+            let h = KVHandle::new(handle, i);
+            self.correct_parent_link(h);
+        }
+    }
+
+    /// Returns `true` if a node has children.
+    fn has_children(&mut self, handle: NodeHandle) -> bool {
+        let node = self.get_node(handle).expect("node must exist");
+        node.edges_count() > 0
+    }
+}
+
+impl<K, V> BTreeMap<K, V>
+where
+    K: Eq + Ord + Codec,
+    V: Codec,
+{
+    /// Returns a reference to the value corresponding to the key.
+    ///
+    /// The key may be any borrowed form of the map's key type, but the ordering
+    /// on the borrowed form *must* match the ordering on the key type.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```no_compile
+    /// use ink_core::storage::BTreeMap;
+    ///
+    /// let mut map = new_btree_map();
+    /// map.insert(1, "a");
+    /// assert_eq!(map.get(&1), Some(&"a"));
+    /// assert_eq!(map.get(&2), None);
+    /// ```
+    pub fn get<Q>(&self, key: &Q) -> Option<&V>
+    where
+        Q: Ord,
+        K: Borrow<Q>,
+    {
+        match search::search_tree(&self, key) {
+            Found(handle) => {
+                let v = self
+                    .get_value(handle)
+                    .expect("if found there is always a value; qed");
+                Some(v)
+            }
+            NotFound(_) => None,
+        }
+    }
+
+    /// Returns the key/value pair corresponding to `key`.
+    ///
+    /// The supplied key may be any borrowed form of the map's key type, but the ordering
+    /// on the borrowed form *must* match the ordering on the key type.
+    ///
+    /// # Examples
+    ///
+    /// ```no_compile
+    /// use ink_core::collections::BTreeMap;
+    ///
+    /// let mut map = new_btree_map();
+    /// map.insert(1, "a");
+    /// assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
+    /// assert_eq!(map.get_key_value(&2), None);
+    /// ```
+    pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
+    where
+        K: Borrow<Q>,
+        Q: Ord,
+    {
+        match search::search_tree(&self, key) {
+            Found(handle) => self.get_kv(handle).map(|kv| kv.kv()),
+            NotFound(_) => None,
+        }
+    }
+
+    /// Returns `true` if the map contains a value for the specified key.
+    ///
+    /// The key may be any borrowed form of the map's key type, but the ordering
+    /// on the borrowed form *must* match the ordering on the key type.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```no_compile
+    /// use ink_core::collections::BTreeMap;
+    ///
+    /// let mut map = new_btree_map();
+    /// map.insert(1, "a");
+    /// assert_eq!(map.contains_key(&1), true);
+    /// assert_eq!(map.contains_key(&2), false);
+    /// ```
+    pub fn contains_key<Q>(&self, key: &Q) -> bool
+    where
+        K: Borrow<Q>,
+        Q: Ord,
+    {
+        self.get(key).is_some()
+    }
+
+    /// Inserts a key/value pair into the map.
+    ///
+    /// If the map did not have this key present, `None` is returned.
+    ///
+    /// If the map did have this key present, the value is updated, and the old
+    /// value is returned. The key is not updated, though; this matters for
+    /// types that can be `==` without being identical. See the [module-level
+    /// documentation] for more.
+    ///
+    /// [module-level documentation]: index.html#insert-and-complex-keys
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```no_compile
+    /// use ink_core::storage::BTreeMap;
+    ///
+    /// let mut map = new_btree_map();
+    /// assert_eq!(map.insert(37, "a"), None);
+    /// assert_eq!(map.is_empty(), false);
+    ///
+    /// map.insert(37, "b");
+    /// assert_eq!(map.insert(37, "c"), Some("b"));
+    /// assert_eq!(map[&37], "c");
+    /// ```
+    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
+        match self.entry(key) {
+            Entry::Occupied(mut entry) => entry.insert(value),
+            Entry::Vacant(entry) => {
+                entry.insert(value);
+                None
+            }
+        }
+    }
+
+    /// Removes a key from the map, returning the value at the key if the key
+    /// was previously in the map.
+    ///
+    /// The key may be any borrowed form of the map's key type, but the ordering
+    /// on the borrowed form *must* match the ordering on the key type.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```no_compile
+    /// use ink_core::storage::BTreeMap;
+    ///
+    /// let mut map = new_btree_map();
+    /// map.insert(1, "a");
+    /// assert_eq!(map.remove(&1), Some("a"));
+    /// assert_eq!(map.remove(&1), None);
+    /// ```
+    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
+    where
+        Q: Ord,
+        K: Borrow<Q>,
+    {
+        match search::search_tree(&self, key) {
+            Found(handle) => {
+                let o = OccupiedEntry { tree: self, handle };
+                Some(o.remove())
+            }
+            NotFound(_) => None,
+        }
+    }
+
+    /// Gets the given key's corresponding entry in the map for in-place manipulation.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```no_compile
+    /// use ink_core::storage::BTreeMap;
+    ///
+    /// let mut count: BTreeMap<&str, usize> = new_btree_map();
+    ///
+    /// // count the number of occurrences of letters in the vec
+    /// for x in vec!["a","b","a","c","a","b"] {
+    ///     *count.entry(x).or_insert(0) += 1;
+    /// }
+    ///
+    /// assert_eq!(count["a"], 3);
+    /// ```
+    pub fn entry(&mut self, key: K) -> Entry<K, V> {
+        match search::search_tree(&self, &key) {
+            Found(handle) => Entry::Occupied(OccupiedEntry { tree: self, handle }),
+            NotFound(handle) => {
+                Entry::Vacant(VacantEntry {
+                    key: Some(key),
+                    tree: self,
+                    handle,
+                })
+            }
+        }
+    }
+}
+
+impl<'a, K, V> Entry<'a, K, V>
+where
+    K: Ord + Codec,
+    V: Codec,
+{
+    /// Ensures a value is in the entry by inserting the default if empty, and returns
+    /// a mutable reference to the value in the entry.
+    ///
+    /// # Examples
+    ///
+    /// ```no_compile
+    /// use ink_core::storage::BTreeMap;
+    ///
+    /// let mut map: BTreeMap<&str, usize> = new_btree_map();
+    /// map.entry("poneyland").or_insert(12);
+    ///
+    /// assert_eq!(map["poneyland"], 12);
+    /// ```
+    pub fn or_insert(self, default: V) -> &'a mut V {
+        match self {
+            Entry::Occupied(entry) => entry.into_mut(),
+            Entry::Vacant(entry) => entry.insert(default),
+        }
+    }
+
+    /// Returns a reference to this entry's key.
+    ///
+    /// # Examples
+    ///
+    /// ```no_compile
+    /// use ink_core::storage::BTreeMap;
+    ///
+    /// let mut map: BTreeMap<&str, usize> = new_btree_map();
+    /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
+    /// ```
+    pub fn key(&self) -> &K {
+        match *self {
+            Entry::Occupied(ref entry) => entry.key(),
+            Entry::Vacant(ref entry) => entry.key(),
+        }
+    }
+}
+
+#[cfg(feature = "ink-generate-abi")]
+impl<K, V> HasLayout for BTreeMap<K, V>
+where
+    K: Metadata + 'static,
+    V: Metadata + 'static,
+{
+    fn layout(&self) -> StorageLayout {
+        LayoutStruct::new(
+            Self::meta_type(),
+            vec![
+                LayoutField::of("header", &self.header),
+                LayoutField::of("entries", &self.nodes),
+                LayoutField::of("kv_pairs", &self.kv_pairs),
+            ],
+        )
+        .into()
+    }
+}
+
+/// The result of an insert operation.
+enum InsertResult {
+    /// The element did fit into the node.
+    Fit(KVHandle),
+    /// The element didn't fit into the node and the node was split.
+    /// The element behind `KVStorageIndex` is extracted during this split
+    /// and now needs to be inserted into a new place.
+    /// `KVHandle` references the resulting left node, `NodeHandle`
+    /// the right one.
+    Split(KVHandle, KVStorageIndex, NodeHandle),
+}
+
+/// A storage entity which contains either an occupied entry with a tree node
+/// or a vacant entry pointing to the next vacant entry.
+///
+/// Using this mechanism we build a linked list of vacant storage entries. On each
+/// insert we replace the top entry (`header.next_vacant`) of this vacant list with
+/// an `OccupiedEntry` and set `header.next_vacant` to the next element in the list.
+///
+/// In our implementation we distinguish between `InternalEntry` and `Entry`.
+///   - `Entry` is the public facing enum which is used in conjunction with the
+///     `.entry()` API. It contains a key/value pair.
+///   - `InternalEntry` is used internally in our implementation. It is a storage
+///     entity and contains a tree node with many key/value pair storage indices.
+#[derive(Encode, Decode)]
+#[cfg_attr(feature = "ink-generate-abi", derive(Metadata))]
+enum InternalEntry<K, V> {
+    /// A vacant entry pointing to the next vacant index.
+    Vacant(Option<NodeHandle>),
+    /// An occupied entry contains a tree node with its elements.
+    Occupied(Node<K, V>),
+}
+
+impl<K, V> Flush for InternalEntry<K, V>
+where
+    K: Encode + Flush,
+    V: Encode + Flush,
+{
+    #[inline]
+    fn flush(&mut self) {
+        match self {
+            InternalEntry::Vacant(vacant) => vacant.flush(),
+            InternalEntry::Occupied(occupied) => occupied.flush(),
+        }
+    }
+}
+
+/// A storage entity which contains either an occupied entry with a tree node
+/// or a vacant entry pointing to the next vacant entry.
+///
+/// Using this mechanism we build a linked list of vacant storage entries. On each
+/// insert we replace the top entry (`header.next_vacant`) of this vacant list with
+/// an `OccupiedEntry` and set `header.next_vacant` to the next element in the list.
+///
+/// In our implementation we distinguish between `InternalEntry` and `Entry`.
+///   - `Entry` is the public facing enum which is used in conjunction with the
+///     `.entry()` API. It contains a key/value pair.
+///   - `InternalEntry` is used internally in our implementation. It is a storage
+///     entity and contains a tree node with many key/value pairs.
+#[derive(Encode, Decode)]
+#[cfg_attr(feature = "ink-generate-abi", derive(Metadata))]
+enum InternalKVEntry<K, V> {
+    /// A vacant entry pointing to the next vacant index.
+    Vacant(Option<KVStorageIndex>),
+    /// An occupied entry contains a key/value pair.
+    Occupied(KVPair<K, V>),
+}
+
+impl<K, V> Flush for InternalKVEntry<K, V>
+where
+    K: Encode + Flush,
+    V: Encode + Flush,
+{
+    #[inline]
+    fn flush(&mut self) {
+        match self {
+            InternalKVEntry::Vacant(vacant) => vacant.flush(),
+            InternalKVEntry::Occupied(occupied) => occupied.flush(),
+        }
+    }
+}
+
+/// An entry of a storage map.
+///
+/// This can either store the entries key/value pair or represent an entry that was
+/// removed after it has been occupied with key and value.
+#[derive(Encode, Decode)]
+pub enum Entry<'a, K, V> {
+    /// A vacant entry pointing to the next vacant index.
+    Vacant(VacantEntry<'a, K, V>),
+    /// An occupied entry containing the value.
+    Occupied(OccupiedEntry<'a, K, V>),
+}
+
+/// An occupied entry of a storage map.
+pub struct OccupiedEntry<'a, K, V> {
+    tree: &'a mut BTreeMap<K, V>,
+    handle: KVHandle,
+}
+
+impl<'a, K, V> VacantEntry<'a, K, V>
+where
+    K: Encode + Decode + Ord,
+    V: Encode + Decode,
+{
+    /// Gets a reference to the key that would be used when inserting a value
+    /// through the VacantEntry.
+    ///
+    /// # Examples
+    ///
+    /// ```no_compile
+    /// use ink_core::storage::BTreeMap;
+    ///
+    /// let mut map: BTreeMap<&str, usize> = new_btree_map();
+    /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
+    /// ```
+    pub fn key(&self) -> &K {
+        self.key
+            .as_ref()
+            .expect("entry does always have a key; qed")
+    }
+
+    /// Sets the value of the entry with the `VacantEntry`'s key,
+    /// and returns a mutable reference to it.
+    ///
+    /// # Examples
+    ///
+    /// ```no_compile
+    /// use ink_core::storage::BTreeMap;
+    ///
+    /// let mut count: BTreeMap<&str, usize> = new_btree_map();
+    ///
+    /// // count the number of occurrences of letters in the vec
+    /// for x in vec!["a","b","a","c","a","b"] {
+    ///     *count.entry(x).or_insert(0) += 1;
+    /// }
+    ///
+    /// assert_eq!(count["a"], 3);
+    /// ```
+    pub fn insert(mut self, val: V) -> &'a mut V {
+        let key = self
+            .key
+            .take()
+            .expect("key is only taken when inserting, so must be there; qed");
+
+        let pair_index = if self.tree.is_empty() && self.tree.root().is_none() {
+            self.tree.create_root(key, val)
+        } else {
+            self.tree.insert_kv(self.handle, key, val)
+        };
+        self.tree
+            .get_value_mut_ref(pair_index)
+            .expect("value was just inserted; qed")
+    }
+}
+
+impl<'a, K, V> OccupiedEntry<'a, K, V>
+where
+    K: Encode + Decode + Ord,
+    V: Encode + Decode,
+{
+    /// Gets a reference to the key in the entry.
+    ///
+    /// # Examples
+    ///
+    /// ```no_compile
+    /// use ink_core::storage::BTreeMap;
+    ///
+    /// let mut map: BTreeMap<&str, usize> = new_btree_map();
+    /// map.entry("poneyland").or_insert(12);
+    /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
+    /// ```
+    pub fn key(&self) -> &K {
+        self.tree
+            .get_kv(self.handle)
+            .expect("every occupied entry always has a key/value pair; qed")
+            .key()
+    }
+
+    /// Gets a reference to the value in the entry.
+    ///
+    /// # Examples
+    ///
+    /// ```no_compile
+    /// use ink_core::storage::BTreeMap;
+    /// use ink_core::storage::btree_map::Entry;
+    ///
+    /// let mut map: BTreeMap<&str, usize> = new_btree_map();
+    /// map.entry("poneyland").or_insert(12);
+    ///
+    /// if let Entry::Occupied(o) = map.entry("poneyland") {
+    ///     assert_eq!(o.get(), &12);
+    /// }
+    /// ```
+    pub fn get(&self) -> &V {
+        self.tree
+            .get_value(self.handle)
+            .expect("every occupied entry always has a key/value pair; qed")
+    }
+
+    /// Gets a mutable reference to the value in the entry.
+    ///
+    /// # Examples
+    ///
+    /// ```no_compile
+    /// use ink_core::storage::BTreeMap;
+    /// use ink_core::storage::btree_map::Entry;
+    ///
+    /// let mut map: BTreeMap<&str, usize> = new_btree_map();
+    /// map.entry("poneyland").or_insert(12);
+    ///
+    /// assert_eq!(map["poneyland"], 12);
+    /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
+    ///     *o.get_mut() += 10;
+    ///     assert_eq!(*o.get(), 22);
+    ///
+    ///     // We can use the same Entry multiple times.
+    ///     *o.get_mut() += 2;
+    /// }
+    /// assert_eq!(map["poneyland"], 24);
+    /// ```
+    pub fn get_mut(&mut self) -> &mut V {
+        let idx = self.handle.idx();
+        let node = self
+            .tree
+            .get_node_mut(self.handle.node())
+            .expect("every occupied entry always belongs to a node; qed");
+        let storage_index = node
+            .pair(idx)
+            .expect("every occupied entry always has a pair stored in it; qed");
+        self.tree
+            .get_value_mut_ref(storage_index)
+            .expect("every pair always has a value; qed")
+    }
+
+    /// Converts the entry into a mutable reference to its value.
+    ///
+    /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
+    ///
+    /// [`get_mut`]: #method.get_mut
+    ///
+    /// # Examples
+    ///
+    /// ```no_compile
+    /// use ink_core::storage::BTreeMap;
+    /// use ink_core::storage::btree_map::Entry;
+    ///
+    /// let mut map: BTreeMap<&str, usize> = new_btree_map();
+    /// map.entry("poneyland").or_insert(12);
+    ///
+    /// assert_eq!(map["poneyland"], 12);
+    /// if let Entry::Occupied(o) = map.entry("poneyland") {
+    ///     *o.into_mut() += 10;
+    /// }
+    /// assert_eq!(map["poneyland"], 22);
+    /// ```
+    pub fn into_mut(self) -> &'a mut V {
+        self.into_value_mut()
+            .expect("every occupied entry always has a key/value pair; qed")
+    }
+
+    /// Takes the value of the entry out of the map, and returns it.
+    ///
+    /// # Examples
+    ///
+    /// ```no_compile
+    /// use ink_core::storage::BTreeMap;
+    /// use ink_core::storage::btree_map::Entry;
+    ///
+    /// let mut map: BTreeMap<&str, usize> = new_btree_map();
+    /// map.entry("poneyland").or_insert(12);
+    ///
+    /// if let Entry::Occupied(o) = map.entry("poneyland") {
+    ///     assert_eq!(o.remove(), 12);
+    /// }
+    /// // If we try to get "poneyland"'s value, it'll panic:
+    /// // println!("{}", map["poneyland"]);
+    /// ```
+    pub fn remove(self) -> V {
+        self.tree.remove_kv(self.handle)
+    }
+
+    /// Inserts a value into this entry.
+    /// Returns the replaced value.
+    fn insert(&mut self, value: V) -> Option<V> {
+        let node = self
+            .tree
+            .get_node_mut(self.handle.node())
+            .expect("every occupied entry always belongs to a node; qed");
+
+        let storage_index = node
+            .pair(self.handle.idx())
+            .expect("each occupied entry must already have a pair");
+        let entry = self
+            .tree
+            .kv_pairs
+            .take(storage_index)
+            .expect("each occupied entry must already have a pair");
+        match entry {
+            InternalKVEntry::Vacant(_) => {
+                unreachable!(
+                    "[ink_core::BTreeMap::insert] Error: \
+                     we already asserted that the entry is occupied"
+                )
+            }
+            InternalKVEntry::Occupied(occupied) => {
+                let (key, old_value) = occupied.kv();
+                let new_pair = KVPair::<K, V>::new(key, value);
+                self.tree
+                    .kv_pairs
+                    .set(storage_index, InternalKVEntry::Occupied(new_pair));
+                Some(old_value)
+            }
+        }
+    }
+
+    /// Transforms this object into a mutable reference to the value in it.
+    fn into_value_mut(self) -> Option<&'a mut V> {
+        let storage_index = {
+            let idx = self.handle.idx();
+            let node = self.tree.get_node_mut(self.handle.node())?;
+            let index = node.pair(idx).as_ref()?;
+            *index
+        };
+        self.tree.get_value_mut_ref(storage_index)
+    }
+}
+
+/// A vacant entry of a storage map.
+pub struct VacantEntry<'a, K, V> {
+    // The `key` needs to be moved for putting, hence we have to use `Option<K`>
+    // to prevent running into partial move errors.
+    key: Option<K>,
+    /// A reference to the `BTreeMap`.
+    tree: &'a mut BTreeMap<K, V>,
+    /// A reference to a specific point in the tree.
+    handle: KVHandle,
+}
diff --git a/core/src/storage/collections/btree_map/mod.rs b/core/src/storage/collections/btree_map/mod.rs
new file mode 100644
index 0000000000..86fddadf32
--- /dev/null
+++ b/core/src/storage/collections/btree_map/mod.rs
@@ -0,0 +1,58 @@
+// Copyright 2018-2020 Parity Technologies (UK) Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+//! A BTreeMap collection.
+//!
+//! This implementation follows the algorithm used by the Rust `BTreeMap` standard
+//! library implementation. The Rust implementation was in general the blueprint for
+//! this implementation. The major difference is that the Rust implementation is
+//! in-memory, whereas this implementation uses the ink! primitives for storage.
+//!
+//! See https://github.com/rust-lang/rust/blob/master/src/liballoc/collections/btree
+//! for the Rust implementation.
+//!
+//! The idea of a BTreeMap is to store many elements (i.e. key/value pairs)
+//! in one tree node. Each of these elements can have a left and right child.
+//! A simple node with three elements thus can look like this:
+//!
+//! ```no_compile
+//! keys  = [      key(a),      key(b),      key(c)    ];
+//! vals  = [    value(a),    value(b),    value(c)    ];
+//! edges = [        1,           2,           3,           4 ];
+//! ```
+//!
+//! Here the left child of element `a` would be the node with the index `1`, its
+//! right child the node with index `2`.
+//!
+//! This concept of multiple elements stored in one node suits our needs well,
+//! since expensive storage fetches are reduced.
+//!
+//! For a description of the tree algorithm itself it's best to see the merge/split
+//! method comments. A notable thing is that the algorithm will merge nodes if it's
+//! possible to reduce storage space (see `handle_underfull_nodes()` for more info).
+
+#[cfg(test)]
+mod test_utils;
+
+#[cfg(test)]
+mod tests;
+
+mod impls;
+mod node;
+mod search;
+
+pub use self::impls::{
+    BTreeMap,
+    Entry,
+};
diff --git a/core/src/storage/collections/btree_map/node.rs b/core/src/storage/collections/btree_map/node.rs
new file mode 100644
index 0000000000..a162589096
--- /dev/null
+++ b/core/src/storage/collections/btree_map/node.rs
@@ -0,0 +1,441 @@
+// Copyright 2018-2020 Parity Technologies (UK) Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+/// This file contains the logic and model for each node in the tree.
+use crate::storage::{
+    btree_map::impls::{
+        KVStorageIndex,
+        B,
+        CAPACITY,
+    },
+    Flush,
+};
+use core::{
+    marker::PhantomData,
+    ops::Range,
+};
+use scale::{
+    Decode,
+    Encode,
+};
+#[cfg(feature = "ink-generate-abi")]
+use type_metadata::Metadata;
+
+/// Number of edges each node has.
+///
+/// Note: `CAPACITY + 1 == EDGES` must always be true!
+const EDGES: usize = 2 * B;
+
+/// Reference to a key/value pair in the tree.
+#[derive(Encode, Decode)]
+#[cfg_attr(feature = "ink-generate-abi", derive(Metadata))]
+pub(super) struct KVPair<K, V> {
+    /// A key.
+    key: K,
+    /// A value.
+    value: V,
+}
+
+impl<K, V> KVPair<K, V> {
+    /// Creates a new `KVPair` from a `key` and a `value`.
+    pub fn new(key: K, value: V) -> Self {
+        Self { key, value }
+    }
+
+    /// Returns a tuple of (`key`, `value`) stored in this key/value pair.
+    pub(super) fn kv(self) -> (K, V) {
+        (self.key, self.value)
+    }
+
+    /// Returns a reference to the `key` stored in this key/value pair.
+    pub(super) fn key_ref(&self) -> &K {
+        &self.key
+    }
+
+    /// Returns the `value` stored in this key/value pair.
+    pub(super) fn value(self) -> V {
+        self.value
+    }
+
+    /// Returns a mutable reference to the `value` stored in this key/value pair.
+    pub(super) fn value_ref_mut(&mut self) -> &mut V {
+        &mut self.value
+    }
+
+    /// Returns a reference to the `value` stored in this key/value pair.
+    pub(super) fn value_ref(&self) -> &V {
+        &self.value
+    }
+}
+
+impl<K, V> Flush for KVPair<K, V>
+where
+    K: Encode + Flush,
+    V: Encode + Flush,
+{
+    #[inline]
+    fn flush(&mut self) {
+        self.key.flush();
+        self.value.flush();
+    }
+}
+
+/// Reference to a key/value pair in the tree.
+pub(super) struct KVRef<'a, K, V> {
+    /// Reference to the key.
+    key: &'a K,
+    /// Reference to the value.
+    value: &'a V,
+}
+
+impl<'a, K, V> KVRef<'a, K, V> {
+    /// Creates a `KVRef` from a `KVPair`.
+    pub(super) fn new(pair: &'a KVPair<K, V>) -> Self {
+        Self {
+            key: pair.key_ref(),
+            value: pair.value_ref(),
+        }
+    }
+
+    /// Returns a tuple with references to the `key` and `value`
+    /// stored in this key/value pair..
+    pub(super) fn kv(self) -> (&'a K, &'a V) {
+        (self.key, self.value)
+    }
+
+    /// Returns a reference to the `key` stored in this key/value pair.
+    pub(super) fn key(self) -> &'a K {
+        self.key
+    }
+}
+
+/// A node in the tree.
+///
+/// Each node contains `CAPACITY` keys and values and an edges array over
+/// which children nodes can be linked. Each child has a link to its parent.
+///
+/// Each node is stored as one storage entity. This reduces storage access,
+/// since with each fetch the entire content of a node (all its elements, etc.)
+/// are fetched.
+#[derive(PartialEq, Eq, Encode, Decode)]
+#[cfg_attr(feature = "ink-generate-abi", derive(Metadata))]
+pub(super) struct Node<K, V> {
+    /// A reference to this node's parent node.
+    parent: Option<NodeHandle>,
+
+    /// This node's index into the parent node's `edges` array.
+    /// If, for example, `parent_idx = Some(2)` this refers to the
+    /// second position in the `edges` array of its parent node.
+    parent_idx: Option<u32>,
+
+    /// The array storing the storage index of the key/value pairs in a node.
+    /// For performance reasons each node contains only the index where the
+    /// key/value pair is stored in `kv_pairs`. Otherwise re-balancing the tree
+    /// or moving entries would be very expensive. With this indirection we only
+    /// have to move the `u32` index.
+    pub(super) pairs: [Option<KVStorageIndex>; CAPACITY],
+
+    /// The pointers to the children of this node.
+    pub(super) edges: [Option<NodeHandle>; EDGES],
+
+    /// Number of elements stored in this node.
+    len: u32,
+
+    /// Marker for compile-time checking of correct key/value pair types.
+    marker: PhantomData<(K, V)>,
+}
+
+impl<K, V> Flush for Node<K, V>
+where
+    K: Encode + Flush,
+    V: Encode + Flush,
+{
+    #[inline]
+    fn flush(&mut self) {
+        self.parent.flush();
+        self.parent_idx.flush();
+        self.pairs.flush();
+        self.edges.flush();
+        self.len.flush();
+    }
+}
+
+impl<K, V> Node<K, V> {
+    /// Create a new `Node`. The node is empty and all fields are instantiated with `None`.
+    pub(super) fn new() -> Self {
+        Node {
+            parent: None,
+            parent_idx: None,
+            pairs: Default::default(),
+            edges: [None; 2 * B],
+            len: 0,
+            marker: Default::default(),
+        }
+    }
+
+    /// Returns the number of elements (i.e. key/value pairs) stored in this node.
+    pub(super) fn len(&self) -> usize {
+        self.len as usize
+    }
+
+    /// Returns a reference to the edges (i.e. the children) stored in this node.
+    #[cfg(test)]
+    pub(super) fn edges(&self) -> &[Option<NodeHandle>; EDGES] {
+        &self.edges
+    }
+
+    /// Sets a new `edge` at `idx`.
+    pub(super) fn set_edge(&mut self, idx: usize, edge: Option<NodeHandle>) {
+        self.edges[idx] = edge;
+    }
+
+    /// Takes the edge at `idx` and returns it. Puts `None` at `idx` instead then.
+    pub(super) fn take_edge(&mut self, idx: usize) -> Option<NodeHandle> {
+        self.edges[idx].take()
+    }
+
+    /// Sets a supplied range of `edges` to the ones from the supplied `src` slice.
+    pub(super) fn set_edges_range(
+        &mut self,
+        src: &[Option<NodeHandle>],
+        range: Range<usize>,
+    ) {
+        self.edges[range].copy_from_slice(src);
+    }
+
+    /// Returns a reference to the key/value `pairs` stored in this node.
+    pub(super) fn pairs(&self) -> &[Option<KVStorageIndex>; CAPACITY] {
+        &self.pairs
+    }
+
+    /// Pushes the storage index of a key/value pair into the `pairs` array of this
+    /// node while shifting all subsequent items to the right by one. The last element
+    /// of the slice will fall out.
+    pub(super) fn push_pair_to(&mut self, idx: usize, pair_index: KVStorageIndex) {
+        slice_insert(&mut self.pairs, idx, Some(pair_index));
+    }
+
+    /// Removes the storage index at `idx` from `pairs` while shifting all subsequent items to
+    /// the left by one.
+    ///
+    /// Returns the removed storage index.
+    pub(super) fn remove_pair_with_shift(
+        &mut self,
+        idx: usize,
+    ) -> Option<KVStorageIndex> {
+        slice_remove(&mut self.pairs, idx)
+    }
+
+    /// Returns a reference to the storage index of the key/value pair stored
+    /// at `idx` in this node. `idx` refers to the position of the pair within
+    /// the `pairs` array.
+    pub(super) fn pair(&self, idx: usize) -> &Option<KVStorageIndex> {
+        &self.pairs[idx]
+    }
+
+    /// Sets a new `parent` for this node.
+    pub(super) fn set_parent(&mut self, parent: Option<NodeHandle>) {
+        self.parent = parent;
+    }
+
+    /// Sets a new `parent_idx` for this node.
+    /// `parent_idx` refers to the position which the parent node has
+    /// within the `edges` array of the node behind `self.parent`.
+    pub(super) fn set_parent_idx(&mut self, parent_idx: Option<usize>) {
+        self.parent_idx = parent_idx.map(|p| p as u32);
+    }
+
+    /// Sets a new `pair_storage_index` at `idx`. Returns the old one at this `idx`, if existent.
+    pub(super) fn set_pair(
+        &mut self,
+        idx: usize,
+        pair_storage_index: Option<KVStorageIndex>,
+    ) -> Option<KVStorageIndex> {
+        match pair_storage_index {
+            Some(pair_index) => self.pairs[idx].replace(pair_index),
+            None => self.pairs[idx].take(),
+        }
+    }
+
+    /// Takes the pair at `idx` and returns it. Puts `None` at `idx` instead then.
+    pub(super) fn take_pair(&mut self, idx: usize) -> Option<KVStorageIndex> {
+        self.pairs[idx].take()
+    }
+
+    /// Sets a supplied range of `pairs` to the ones from the supplied `src` slice.
+    pub(super) fn set_pair_range(
+        &mut self,
+        src: &[Option<KVStorageIndex>],
+        range: Range<usize>,
+    ) {
+        self.pairs[range].copy_from_slice(src);
+    }
+
+    /// Returns the parent of the current node, if available.
+    pub(super) fn parent(&self) -> Option<NodeHandle> {
+        self.parent
+    }
+
+    /// Returns the number of edges (i.e. children) this node has.
+    pub(super) fn edges_count(&self) -> usize {
+        self.edges.iter().filter(|o| o.is_some()).count()
+    }
+
+    /// Returns the edge at position `idx`.
+    pub(super) fn edge(&self, idx: usize) -> Option<NodeHandle> {
+        self.edges[idx]
+    }
+
+    /// Pushes an edge into the `edges` array of this node while shifting all
+    /// subsequent items to the right by one. The last element of the slice
+    /// will fall out.
+    pub(super) fn push_edge_to(&mut self, idx: usize, edge: NodeHandle) {
+        slice_insert(&mut self.edges, idx, Some(edge));
+    }
+
+    /// Removes the element at `idx` from `edges` while shifting all subsequent items to
+    /// the left by one.
+    ///
+    /// Returns the removed element.
+    pub(super) fn remove_edge_with_shift(&mut self, idx: usize) -> Option<NodeHandle> {
+        slice_remove(&mut self.edges, idx)
+    }
+
+    /// Returns the position of this node in the parent node's `edges` array.
+    pub(super) fn parent_idx(&self) -> Option<usize> {
+        self.parent_idx.map(|v| v as usize)
+    }
+
+    /// Returns the number of edges (i.e. children) this node has.
+    pub(super) fn set_len(&mut self, new_len: usize) {
+        self.len = new_len as u32;
+    }
+}
+
+/// Points to a node in the tree.
+#[derive(Clone, Copy, Encode, Decode, PartialEq, Eq)]
+#[cfg_attr(feature = "ink-generate-abi", derive(Metadata))]
+pub(super) struct NodeHandle {
+    node: u32,
+}
+
+impl Flush for NodeHandle {
+    #[inline]
+    fn flush(&mut self) {
+        self.node.flush();
+    }
+}
+
+impl NodeHandle {
+    /// Create a new `NodeHandle` from a `u32` which must be the index
+    /// this node has in the `entries` storage.
+    pub(super) fn new(node: u32) -> Self {
+        Self { node }
+    }
+
+    /// Returns the node index for this node.
+    /// The index must point to the nodes position in the `entries` storage.
+    pub(super) fn node(self) -> u32 {
+        self.node
+    }
+}
+
+/// Points to a specific key/value pair within a node in the tree.
+#[derive(Clone, Copy)]
+pub(super) struct KVHandle {
+    /// Index of the node in the `entries` storage.
+    node: NodeHandle,
+    /// Index of the key/value pair within the node. This is a pointer
+    /// to the position in the `kv_pairs` array.
+    idx: u32,
+}
+
+impl KVHandle {
+    /// Creates a new `KVHandle` from a `NodeHandle` and an `idx`.
+    /// The `idx` is the node's index in the parent node's `edges` array.
+    pub(super) fn new(node: NodeHandle, idx: usize) -> Self {
+        Self {
+            node,
+            idx: idx as u32,
+        }
+    }
+
+    /// Returns the `NodeHandle` for this node.
+    /// The index should point to the nodes position in the `entries` storage.
+    pub(super) fn node(self) -> NodeHandle {
+        self.node
+    }
+
+    /// Returns the position in the parent node's `edges` array to which
+    /// this handle points.
+    pub(super) fn idx(self) -> usize {
+        self.idx as usize
+    }
+}
+
+/// Inserts `val` at `idx` into `slice` while shifting all subsequent items to
+/// the right by one. The last element of the slice will fall out.
+pub fn slice_insert<T: Copy>(slice: &mut [T], i: usize, val: T) {
+    let len = slice.len();
+    let from = i;
+    let to = i + 1;
+    slice.copy_within(from..len - 1, to);
+
+    slice[i] = val;
+}
+
+/// Extracts the element at `idx` from `slice` while shifting all subsequent items to
+/// the left by one.
+///
+/// Returns the extracted element.
+fn slice_remove<T: Copy>(slice: &mut [Option<T>], i: usize) -> Option<T> {
+    let len = slice.len();
+    let val = slice[i].take();
+    let from = i + 1;
+    let to = i;
+
+    slice.copy_within(from.., to);
+    slice[len - 1] = None;
+    val
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn slice_insert_works() {
+        // given
+        let mut sl = [Some(1), Some(2), Some(3), Some(4)];
+
+        // when
+        slice_insert(&mut sl, 2, Some(99));
+
+        // then
+        assert_eq!(sl, [Some(1), Some(2), Some(99), Some(3)]);
+    }
+
+    #[test]
+    fn slice_remove_works() {
+        // given
+        let mut sl = [Some(1), Some(2), Some(3), Some(4)];
+
+        // when
+        let removed = slice_remove(&mut sl, 2);
+
+        // then
+        assert_eq!(removed, Some(3));
+        assert_eq!(sl, [Some(1), Some(2), Some(4), None]);
+    }
+}
diff --git a/core/src/storage/collections/btree_map/search.rs b/core/src/storage/collections/btree_map/search.rs
new file mode 100644
index 0000000000..f95212b33a
--- /dev/null
+++ b/core/src/storage/collections/btree_map/search.rs
@@ -0,0 +1,119 @@
+// Copyright 2018-2019 Parity Technologies (UK) Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+use self::SearchResult::{
+    Found,
+    NotFound,
+};
+use crate::storage::btree_map::{
+    impls::{
+        BTreeMap,
+        HandleType::{
+            Branch,
+            Leaf,
+        },
+        CAPACITY,
+    },
+    node::{
+        KVHandle,
+        Node,
+        NodeHandle,
+    },
+};
+use core::{
+    borrow::Borrow,
+    cmp::{
+        Ord,
+        Ordering,
+    },
+};
+use scale::Codec;
+
+/// Result of a tree search.
+pub(super) enum SearchResult {
+    /// Found the entry at the supplied position.
+    Found(KVHandle),
+    /// No search result, contains the position where an insert could be made.
+    NotFound(KVHandle),
+}
+
+/// Searches the tree for `key`.
+///
+/// If found returns `Found(pos)`
+/// If not found returns `NotFound(last_pos_searched)`.
+pub(super) fn search_tree<K, V, Q>(tree: &BTreeMap<K, V>, key: &Q) -> SearchResult
+where
+    Q: Ord,
+    K: Ord + Borrow<Q> + Codec,
+    V: Codec,
+{
+    let current_root = tree.root();
+    if tree.is_empty() || current_root.is_none() {
+        return NotFound(KVHandle::new(NodeHandle::new(0), 0))
+    }
+
+    let mut cur =
+        current_root.expect("we would already have returned if no root exists; qed");
+    loop {
+        let node = tree.get_node(cur).expect(
+            "node which is iterated over is either root or child node, \
+             but it always exists; qed",
+        );
+        match search_node(&node, tree.keys_in_node(cur), cur, key) {
+            Found(handle) => return Found(handle),
+            NotFound(handle) => {
+                match tree.get_handle_type(handle.node()) {
+                    Leaf => return NotFound(handle),
+                    Branch => {
+                        // Go down then
+                        cur = tree
+                            .descend(handle)
+                            .expect("a branch node always has a child; qed");
+                        continue
+                    }
+                }
+            }
+        }
+    }
+}
+
+/// Conducts a linear search for `key` in the elements contained in `node`.
+///
+/// If found returns `Found(pos)`
+/// If not found returns `NotFound(last_pos_searched)`.
+pub(super) fn search_node<K, V, Q>(
+    node: &Node<K, V>,
+    keys_in_node: [Option<&K>; CAPACITY],
+    node_handle: NodeHandle,
+    key: &Q,
+) -> SearchResult
+where
+    Q: Ord,
+    K: Borrow<Q>,
+{
+    let iter = keys_in_node.iter().enumerate();
+    for (i, k) in iter {
+        match k {
+            None => return NotFound(KVHandle::new(node_handle, i)),
+            Some(node_key) => {
+                match key.cmp((**node_key).borrow()) {
+                    Ordering::Greater => {}
+                    Ordering::Equal => return Found(KVHandle::new(node_handle, i)),
+                    Ordering::Less => return NotFound(KVHandle::new(node_handle, i)),
+                }
+            }
+        }
+    }
+    NotFound(KVHandle::new(node_handle, node.len()))
+}
diff --git a/core/src/storage/collections/mod.rs b/core/src/storage/collections/mod.rs
index 05f84f8418..3702246e99 100644
--- a/core/src/storage/collections/mod.rs
+++ b/core/src/storage/collections/mod.rs
@@ -14,6 +14,7 @@
 
 pub mod binary_heap;
 pub mod bitvec;
+pub mod btree_map;
 pub mod hash_map;
 pub mod stash;
 pub mod vec;
diff --git a/core/src/storage/mod.rs b/core/src/storage/mod.rs
index 6b56d95bd0..efc0283124 100644
--- a/core/src/storage/mod.rs
+++ b/core/src/storage/mod.rs
@@ -86,6 +86,10 @@ pub use self::{
             self,
             BitVec,
         },
+        btree_map::{
+            self,
+            BTreeMap,
+        },
         hash_map::{
             self,
             HashMap,


Test patch:
diff --git a/core/src/storage/collections/btree_map/test_utils.rs b/core/src/storage/collections/btree_map/test_utils.rs
new file mode 100644
index 0000000000..4f3778428f
--- /dev/null
+++ b/core/src/storage/collections/btree_map/test_utils.rs
@@ -0,0 +1,135 @@
+// Copyright 2018-2020 Parity Technologies (UK) Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+use crate::storage::{
+    alloc::{
+        AllocateUsing,
+        BumpAlloc,
+        Initialize,
+    },
+    collections::btree_map::node::NodeHandle,
+    BTreeMap,
+};
+use ink_primitives::Key;
+use itertools::Itertools;
+
+/// Creates an empty map.
+pub fn empty_map() -> BTreeMap<i32, i32> {
+    unsafe {
+        let mut alloc = BumpAlloc::from_raw_parts(Key([0x0; 32]));
+        BTreeMap::allocate_using(&mut alloc).initialize_into(())
+    }
+}
+
+/// Creates a map pre-filled with some key/value pairs.
+pub fn filled_map() -> BTreeMap<i32, i32> {
+    let mut map = empty_map();
+    map.insert(5, 50);
+    map.insert(42, 420);
+    map.insert(1337, 13370);
+    map.insert(77, 770);
+    assert_eq!(map.len(), 4);
+    map
+}
+
+/// Returns all edges in the tree as one Vec.
+pub fn all_edges(map: &BTreeMap<i32, i32>) -> Vec<u32> {
+    let mut v = Vec::new();
+    let mut processed_nodes = 0;
+    let mut node_index = 0;
+    loop {
+        if processed_nodes == map.node_count() {
+            break
+        }
+
+        // We iterate over all storage entities of the tree and skip vacant entities.
+        let handle = NodeHandle::new(node_index);
+        if let Some(node) = map.get_node(handle) {
+            let edges = node
+                .edges()
+                .to_vec()
+                .into_iter()
+                .filter_map(|x| x.map(|v| v.node()));
+            v.extend(edges);
+            processed_nodes += 1;
+        }
+        node_index += 1;
+    }
+    v
+}
+
+/// Returns `true` if every edge exists only once in the tree.
+/// If duplicate edges are found each duplicate is printed to the console.
+pub fn every_edge_exists_only_once(map: &BTreeMap<i32, i32>) -> bool {
+    let all_edges = all_edges(map);
+    let unique_edges: Vec<u32> = all_edges.clone().into_iter().unique().collect();
+
+    let only_unique_edges = all_edges.len() == unique_edges.len();
+    if !only_unique_edges {
+        unique_edges.iter().for_each(|x| {
+            if all_edges.iter().any(|a| *a == *x) {
+                eprintln!("duplicate {:?}", x);
+            }
+        });
+    }
+    only_unique_edges
+}
+
+/// Conducts repeated insert and remove operations into the map by iterating
+/// over `xs`. For each odd number a defined number of insert operations
+/// are executed. For each even number it's asserted that the previously
+/// inserted elements are in the map and they are removed subsequently.
+///
+/// Using this scheme we get a sequence of insert and remove operations.
+pub fn insert_and_remove(xs: Vec<i32>) {
+    let mut map = empty_map();
+    let mut count_inserts = 0;
+    let mut previous_even_x = None;
+    let number_inserts = 3;
+
+    xs.iter().for_each(|x| {
+        let x = *x;
+        if x % 2 == 0 {
+            // On even numbers we insert new nodes.
+            for a in x..x + number_inserts {
+                if let None = map.insert(a, a * 10) {
+                    count_inserts += 1;
+                }
+                assert_eq!(map.len(), count_inserts);
+            }
+            previous_even_x = Some(x);
+        } else if x % 2 == 1 && previous_even_x.is_some() {
+            // if it's an odd number and we inserted in the previous run we assert
+            // that the insert worked correctly and remove the elements again.
+            let x = previous_even_x.unwrap();
+            for a in x..x + number_inserts {
+                assert_eq!(map.get(&a), Some(&(a * 10)));
+                assert_eq!(map.remove(&a), Some(a * 10));
+                assert_eq!(map.get(&a), None);
+                count_inserts -= 1;
+                assert_eq!(map.len(), count_inserts);
+            }
+            previous_even_x = None;
+        }
+        assert!(every_edge_exists_only_once(&map));
+    });
+}
+
+/// Asserts that there is no node in storage for the range `0..max_node_count`.
+pub fn storage_empty(map: &BTreeMap<i32, i32>, max_node_count: u32) -> bool {
+    for i in 0..max_node_count {
+        assert!(map.get_node(NodeHandle::new(i)).is_none());
+    }
+    true
+}
diff --git a/core/src/storage/collections/btree_map/tests.rs b/core/src/storage/collections/btree_map/tests.rs
new file mode 100644
index 0000000000..f7d5c45cc2
--- /dev/null
+++ b/core/src/storage/collections/btree_map/tests.rs
@@ -0,0 +1,444 @@
+// Copyright 2018-2020 Parity Technologies (UK) Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+use crate::{
+    env::{
+        self,
+        Result,
+    },
+    storage::{
+        alloc::{
+            AllocateUsing,
+            BumpAlloc,
+            Initialize,
+        },
+        btree_map::impls::{
+            Entry,
+            CAPACITY,
+        },
+        collections::btree_map::{
+            node::NodeHandle,
+            test_utils::*,
+        },
+        BTreeMap,
+    },
+};
+use ink_primitives::Key;
+use itertools::Itertools;
+
+#[test]
+fn empty_map_works() -> Result<()> {
+    env::test::run_test::<env::DefaultEnvTypes, _>(|_| {
+        // given
+        let map = empty_map();
+
+        // then
+        assert_eq!(map.len(), 0);
+        assert!(map.is_empty());
+        Ok(())
+    })
+}
+
+#[test]
+fn remove_element_from_empty_map() -> Result<()> {
+    env::test::run_test::<env::DefaultEnvTypes, _>(|_| {
+        let mut map = empty_map();
+        assert_eq!(map.remove(&4), None);
+        Ok(())
+    })
+}
+
+#[test]
+fn insert_into_empty_map_works() -> Result<()> {
+    env::test::run_test::<env::DefaultEnvTypes, _>(|_| {
+        // given
+        let mut map = empty_map();
+
+        // when
+        assert_eq!(map.insert(0, 10), None);
+
+        // then
+        assert_eq!(map.get(&0), Some(&10));
+        assert_eq!(map.contains_key(&0), true);
+        assert_eq!(map.get_key_value(&0), Some((&0, &10)));
+        Ok(())
+    })
+}
+
+#[test]
+fn remove_works() -> Result<()> {
+    env::test::run_test::<env::DefaultEnvTypes, _>(|_| {
+        // given
+        let mut map = empty_map();
+
+        // when
+        assert_eq!(map.insert(4, 40), None);
+        assert_eq!(map.get(&4), Some(&40));
+        assert_eq!(map.len(), 1);
+
+        // then
+        assert_eq!(map.remove(&4), Some(40));
+        assert_eq!(map.get(&4), None);
+        assert_eq!(map.len(), 0);
+        Ok(())
+    })
+}
+
+#[test]
+fn multiple_inserts_for_same_key_work() -> Result<()> {
+    env::test::run_test::<env::DefaultEnvTypes, _>(|_| {
+        // given
+        let mut map = empty_map();
+        assert_eq!(map.insert(0, 10), None);
+
+        // when
+        assert_eq!(map.insert(0, 20), Some(10));
+        assert_eq!(map.get(&0), Some(&20));
+        assert_eq!(map.len(), 1);
+
+        // then
+        assert_eq!(map.remove(&0), Some(20));
+        assert_eq!(map.get(&0), None);
+        assert_eq!(map.len(), 0);
+        Ok(())
+    })
+}
+
+#[test]
+fn putting_on_same_key_works() -> Result<()> {
+    env::test::run_test::<env::DefaultEnvTypes, _>(|_| {
+        // given
+        let mut map = empty_map();
+
+        // when
+        assert_eq!(map.insert(42, 420), None);
+        assert_eq!(map.len(), 1);
+        assert_eq!(map.insert(42, 520), Some(420));
+
+        // then
+        assert_eq!(map.len(), 1);
+        assert_eq!(map.get(&42), Some(&520));
+        Ok(())
+    })
+}
+
+#[test]
+fn filled_map_must_work() -> Result<()> {
+    env::test::run_test::<env::DefaultEnvTypes, _>(|_| {
+        // given
+        let mut map = filled_map();
+        assert_eq!(map.get(&5), Some(&50));
+        assert_eq!(map.get(&42), Some(&420));
+        assert_eq!(map.get(&1337), Some(&13370));
+        assert_eq!(map.get(&77), Some(&770));
+        assert_eq!(map.get(&4), None);
+        assert_eq!(map.len(), 4);
+
+        // when
+        assert_eq!(map.insert(4, 40), None);
+
+        // then
+        assert_eq!(map.get(&4), Some(&40));
+        assert_eq!(map.len(), 5);
+        Ok(())
+    })
+}
+
+#[test]
+fn tree_must_remain_balanced() -> Result<()> {
+    env::test::run_test::<env::DefaultEnvTypes, _>(|_| {
+        // given
+        let mut map = empty_map();
+        for i in 0..CAPACITY as i32 {
+            map.insert(i, i * 10);
+        }
+        assert_eq!(map.len(), CAPACITY as u32);
+        assert_eq!(map.node_count(), 1);
+
+        // when
+        // when one element more is inserted
+        let one_more = CAPACITY as i32;
+        assert_eq!(map.insert(one_more, one_more * 10), None);
+
+        // then
+        // the node count has to jump to three, since we then must
+        // have two children and a parent node.
+        assert_eq!(map.len(), CAPACITY as u32 + 1);
+        assert_eq!(map.node_count(), 3);
+
+        // when
+        // when the element is removed again the node count has
+        // to go back to one since the nodes should have been merged.
+        assert_eq!(map.remove(&one_more), Some(one_more * 10));
+        assert_eq!(map.len(), 11);
+
+        // then
+        assert_eq!(map.node_count(), 1);
+        assert!(map.get_node(NodeHandle::new(0)).is_some());
+        Ok(())
+    })
+}
+
+#[test]
+fn entry_api_works_with_empty_map() -> Result<()> {
+    env::test::run_test::<env::DefaultEnvTypes, _>(|_| {
+        // given
+        let mut map = empty_map();
+        let key = 5;
+        let val = 50;
+
+        // when
+        let entry = map.entry(key);
+        match entry {
+            Entry::Vacant(v) => {
+                v.insert(val);
+            }
+            Entry::Occupied(_) => {
+                unreachable!("map is created as empty");
+            }
+        }
+
+        // then
+        assert_eq!(map.get(&key), Some(&val));
+        assert_eq!(map.contains_key(&key), true);
+        assert_eq!(map.get_key_value(&key), Some((&key, &val)));
+        Ok(())
+    })
+}
+
+#[test]
+fn entry_api_works_with_filled_map() -> Result<()> {
+    env::test::run_test::<env::DefaultEnvTypes, _>(|_| {
+        let mut map = filled_map();
+        assert_eq!(map.entry(5).key(), &5);
+        assert_eq!(map.entry(-1).key(), &-1);
+        assert_eq!(map.entry(997).or_insert(9970), &9970);
+        Ok(())
+    })
+}
+
+#[test]
+fn entry_api_works_with_strings_and_multiple_calls() -> Result<()> {
+    env::test::run_test::<env::DefaultEnvTypes, _>(|_| {
+        // given
+        let mut map = unsafe {
+            let mut alloc = BumpAlloc::from_raw_parts(Key([0x0; 32]));
+            BTreeMap::allocate_using(&mut alloc).initialize_into(())
+        };
+        let k = String::from("poneyland");
+        map.entry(k.clone()).or_insert(12);
+
+        // when
+        match map.entry(k.clone()) {
+            Entry::Occupied(mut o) => {
+                *o.get_mut() += 10;
+                assert_eq!(*o.get(), 22);
+
+                *o.get_mut() += 2;
+            }
+            _ => unreachable!(),
+        };
+
+        // then
+        assert_eq!(map.get(&k).expect("must be there"), &24);
+        Ok(())
+    })
+}
+
+#[test]
+fn putting_and_removing_many_items_works() -> Result<()> {
+    env::test::run_test::<env::DefaultEnvTypes, _>(|_| {
+        // given
+        let count = CAPACITY as i32 * 100;
+        let mut map = empty_map();
+        let mut len = map.len();
+        for i in 0..count {
+            assert_eq!(map.insert(i, i * 10), None);
+            len += 1;
+            assert_eq!(map.len(), len);
+        }
+        let max_node_count = map.node_count();
+
+        // when
+        for i in 0..count {
+            assert_eq!(map.get(&i), Some(&(i * 10)));
+            assert_eq!(map.remove(&i), Some(i * 10));
+            assert_eq!(map.get(&i), None);
+            len -= 1;
+            assert_eq!(map.len(), len);
+        }
+
+        // then
+        assert_eq!(map.len(), 0);
+        assert_eq!(map.node_count(), 0);
+        assert!(storage_empty(&map, max_node_count));
+        Ok(())
+    })
+}
+
+#[test]
+fn simple_insert_and_removal() -> Result<()> {
+    env::test::run_test::<env::DefaultEnvTypes, _>(|_| {
+        // given
+        let mut map = empty_map();
+        let xs = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11];
+        let mut len = 0;
+        xs.iter().for_each(|i| {
+            if let Some(_) = map.insert(*i, i * 10) {
+                unreachable!("no element must already exist there");
+            }
+            assert_eq!(map.get(&i), Some(&(i * 10)));
+            len += 1;
+            assert_eq!(map.len(), len);
+        });
+        xs.iter().for_each(|k| {
+            let v = *k * 10;
+            assert_eq!(map.get(k), Some(&v));
+            assert_eq!(map.contains_key(k), true);
+            assert_eq!(map.get_key_value(k), Some((k, &v)));
+        });
+        let max_node_count = map.node_count();
+
+        // when
+        // remove all
+        xs.iter().for_each(|i| {
+            match map.remove(&i) {
+                Some(v) => {
+                    assert_eq!(v, i * 10);
+                    len -= 1;
+                }
+                None => unreachable!(),
+            };
+            assert_eq!(map.len(), len);
+        });
+
+        // then
+        assert_eq!(map.len(), 0);
+        assert_eq!(map.node_count(), 0);
+        assert!(storage_empty(&map, max_node_count));
+        Ok(())
+    })
+}
+
+#[test]
+fn alternating_inserts_and_remove_works() -> Result<()> {
+    env::test::run_test::<env::DefaultEnvTypes, _>(|_| {
+        // given
+        let mut map = empty_map();
+        let mut len = map.len();
+        let ops = vec![
+            CAPACITY as i32 * 20, // insert
+            CAPACITY as i32 * 10, // remove
+            CAPACITY as i32 * 10, // insert
+            CAPACITY as i32 * 20, // remove
+        ];
+        let mut max_node_count = 0;
+
+        // when
+        ops.iter().enumerate().for_each(|(p, n)| {
+            if p % 2 == 0 {
+                // if it's an even array index we insert `n` elements
+                for i in 1..*n {
+                    assert_eq!(map.insert(i, i * 10), None);
+                    assert_eq!(map.get(&i), Some(&(i * 10)));
+                    len += 1;
+                    assert_eq!(map.len(), len);
+
+                    let nodes = map.node_count();
+                    if nodes > max_node_count {
+                        max_node_count = nodes;
+                    }
+                }
+            } else {
+                // on odd indices we remove `n` elements
+                for i in 1..*n {
+                    assert_eq!(map.remove(&i), Some(i * 10));
+                    assert_eq!(map.get(&i), None);
+                    len -= 1;
+                    assert_eq!(map.len(), len);
+                }
+            }
+        });
+
+        // then
+        assert_eq!(map.len(), 0);
+        assert_eq!(map.node_count(), 0);
+        assert!(storage_empty(&map, max_node_count));
+        Ok(())
+    })
+}
+
+#[test]
+fn sorted_insert_and_removal() -> Result<()> {
+    env::test::run_test::<env::DefaultEnvTypes, _>(|_| {
+        // given
+        let mut map = empty_map();
+        let mut len = map.len();
+        let xs = vec![
+            -95, -89, -86, -67, -54, -13, -6, -1, 4, 13, 15, 21, 31, 40, 65,
+        ];
+        let mut xs = xs.clone();
+        xs.sort_by(|a, b| a.cmp(b));
+        xs = xs.into_iter().unique().collect();
+        let mut max_node_count = 0;
+
+        // first insert in sorted order
+        xs.iter().for_each(|i| {
+            assert_eq!(map.insert(*i, i * 10), None);
+            len += 1;
+            max_node_count += map.node_count();
+            assert_eq!(map.len(), len);
+            assert!(every_edge_exists_only_once(&map));
+        });
+
+        // when
+        // remove from the back
+        xs.sort_by(|a, b| b.cmp(a));
+        xs.iter().for_each(|i| {
+            assert_eq!(map.remove(&i), Some(i * 10));
+            len -= 1;
+            assert_eq!(map.len(), len);
+            assert!(every_edge_exists_only_once(&map));
+        });
+
+        // then
+        assert_eq!(map.len(), 0);
+        assert_eq!(map.node_count(), 0);
+        assert!(storage_empty(&map, max_node_count));
+        Ok(())
+    })
+}
+
+/// These are some cases which in the past have shown to generate complex trees
+/// for which the removal/insert operations touch all kinds of corner cases.
+#[test]
+fn complex_trees_work() -> Result<()> {
+    env::test::run_test::<env::DefaultEnvTypes, _>(|_| {
+        let xs = [
+            -72, -68, 36, -30, 0, -38, -74, -60, 4, -2, 28, -34, 60, -42, -14, 32, -48,
+            18, -6, 24, -10, 40, 62, -64, 48, -56, 14, 3,
+        ];
+        insert_and_remove(xs.to_vec());
+
+        let xs = [
+            2, -30, -26, 0, -34, -4, -38, -42, -8, -56, 66, 34, 16, 36, -62, -12, -20,
+            38, 30, -50, -66, 6, 70, 62, -16, 12, -70, 42, 31,
+        ];
+        insert_and_remove(xs.to_vec());
+
+        let xs = [-2, -66, -44, 34, -6, 62, 2, 6, -30, -70, 30, -62, 7, -44, 7];
+        insert_and_remove(xs.to_vec());
+        Ok(())
+    })
+}