Auto merge of #30426 - gereeter:btree-rewrite, r=Gankro

Despite being over 700 lines shorter, this implementation should use less memory than the previous one and is faster on at least insertions and iteration, the latter improving approximately 5x.

Technically a [breaking-change] due to removal of deprecated functions.

cc @apasel422 @Gankro @goyox86

Fixes #27865.

<!-- Reviewable:start -->
[<img src="https://reviewable.io/review_button.png" height=40 alt="Review on Reviewable"/>](https://reviewable.io/reviews/rust-lang/rust/30426)
<!-- Reviewable:end -->

6 files changed, 1914 insertions, 2593 deletions

diff --git a/src/libcollections/btree/map.rs b/src/libcollections/btree/map.rs
index 74895f16596..2375a63fbd7 100644
--- a/src/libcollections/btree/map.rs
+++ b/src/libcollections/btree/map.rs
@@ -1,4 +1,4 @@
-// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
 // file at the top-level directory of this distribution and at
 // http://rust-lang.org/COPYRIGHT.
 //
@@ -8,32 +8,24 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-// This implementation is largely based on the high-level description and analysis of B-Trees
-// found in *Open Data Structures* (ODS). Although our implementation does not use any of
-// the source found in ODS, if one wishes to review the high-level design of this structure, it
-// can be freely downloaded at http://opendatastructures.org/. Its contents are as of this
-// writing (August 2014) freely licensed under the following Creative Commons Attribution
-// License: [CC BY 2.5 CA](http://creativecommons.org/licenses/by/2.5/ca/).
-
-use self::Entry::*;
-
 use core::cmp::Ordering;
 use core::fmt::Debug;
 use core::hash::{Hash, Hasher};
-use core::iter::{Map, FromIterator};
+use core::iter::FromIterator;
 use core::ops::Index;
-use core::{fmt, mem, usize};
-use Bound::{self, Included, Excluded, Unbounded};
+use core::{fmt, intrinsics, mem, ptr};
 
 use borrow::Borrow;
-use vec_deque::VecDeque;
+use Bound::{self, Included, Excluded, Unbounded};
+
+use super::node::{self, NodeRef, Handle, marker};
+use super::search;
 
-use self::Continuation::{Continue, Finished};
-use self::StackOp::*;
-use super::node::ForceResult::{Leaf, Internal};
-use super::node::TraversalItem::{self, Elem, Edge};
-use super::node::{Traversal, MutTraversal, MoveTraversal};
-use super::node::{self, Node, Found, GoDown};
+use super::node::InsertResult::*;
+use super::node::ForceResult::*;
+use super::search::SearchResult::*;
+use self::UnderflowResult::*;
+use self::Entry::*;
 
 /// A map based on a B-Tree.
 ///
@@ -65,60 +57,173 @@ use super::node::{self, Node, Found, GoDown};
 /// It is a logic error for a key to be modified in such a way that the key's ordering relative to
 /// any other key, as determined by the `Ord` trait, changes while it is in the map. This is
 /// normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
-#[derive(Clone)]
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct BTreeMap<K, V> {
-    root: Node<K, V>,
-    length: usize,
-    depth: usize,
-    b: usize,
+    root: node::Root<K, V>,
+    length: usize
 }
 
-/// An abstract base over-which all other BTree iterators are built.
-#[derive(Clone)]
-struct AbsIter<T> {
-    traversals: VecDeque<T>,
-    size: usize,
+impl<K, V> Drop for BTreeMap<K, V> {
+    #[unsafe_destructor_blind_to_params]
+    fn drop(&mut self) {
+        unsafe {
+            for _ in ptr::read(self).into_iter() { }
+        }
+    }
+}
+
+impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> {
+    fn clone(&self) -> BTreeMap<K, V> {
+        fn clone_subtree<K: Clone, V: Clone>(
+                node: node::NodeRef<marker::Immut, K, V, marker::LeafOrInternal>)
+                -> BTreeMap<K, V> {
+
+            match node.force() {
+                Leaf(leaf) => {
+                    let mut out_tree = BTreeMap {
+                        root: node::Root::new_leaf(),
+                        length: 0
+                    };
+
+                    {
+                        let mut out_node = match out_tree.root.as_mut().force() {
+                            Leaf(leaf) => leaf,
+                            Internal(_) => unreachable!()
+                        };
+
+                        let mut in_edge = leaf.first_edge();
+                        while let Ok(kv) = in_edge.right_kv() {
+                            let (k, v) = kv.into_kv();
+                            in_edge = kv.right_edge();
+
+                            out_node.push(k.clone(), v.clone());
+                            out_tree.length += 1;
+                        }
+                    }
+
+                    out_tree
+                },
+                Internal(internal) => {
+                    let mut out_tree = clone_subtree(internal.first_edge().descend());
+
+                    {
+                        let mut out_node = out_tree.root.push_level();
+                        let mut in_edge = internal.first_edge();
+                        while let Ok(kv) = in_edge.right_kv() {
+                            let (k, v) = kv.into_kv();
+                            in_edge = kv.right_edge();
+
+                            let k = (*k).clone();
+                            let v = (*v).clone();
+                            let subtree = clone_subtree(in_edge.descend());
+
+                            // We can't destructure subtree directly
+                            // because BTreeMap implements Drop
+                            let (subroot, sublength) = unsafe {
+                                let root = ptr::read(&subtree.root);
+                                let length = subtree.length;
+                                mem::forget(subtree);
+                                (root, length)
+                            };
+
+                            out_node.push(k, v, subroot);
+                            out_tree.length += 1 + sublength;
+                        }
+                    }
+
+                    out_tree
+                }
+            }
+        }
+
+        clone_subtree(self.root.as_ref())
+    }
+}
+
+impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
+    where K: Borrow<Q> + Ord,
+          Q: Ord
+{
+    type Key = K;
+
+    fn get(&self, key: &Q) -> Option<&K> {
+        match search::search_tree(self.root.as_ref(), key) {
+            Found(handle) => Some(handle.into_kv().0),
+            GoDown(_) => None
+        }
+    }
+
+    fn take(&mut self, key: &Q) -> Option<K> {
+        match search::search_tree(self.root.as_mut(), key) {
+            Found(handle) => {
+                Some(OccupiedEntry {
+                    handle: handle,
+                    length: &mut self.length
+                }.remove_kv().0)
+            },
+            GoDown(_) => None
+        }
+    }
+
+    fn replace(&mut self, key: K) -> Option<K> {
+        match search::search_tree::<marker::Mut, K, (), K>(self.root.as_mut(), &key) {
+            Found(handle) => Some(mem::replace(handle.into_kv_mut().0, key)),
+            GoDown(handle) => {
+                VacantEntry {
+                    key: key,
+                    handle: handle,
+                    length: &mut self.length
+                }.insert(());
+                None
+            }
+        }
+    }
 }
 
 /// An iterator over a BTreeMap's entries.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Iter<'a, K: 'a, V: 'a> {
-    inner: AbsIter<Traversal<'a, K, V>>,
+    range: Range<'a, K, V>,
+    length: usize
 }
 
 /// A mutable iterator over a BTreeMap's entries.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct IterMut<'a, K: 'a, V: 'a> {
-    inner: AbsIter<MutTraversal<'a, K, V>>,
+    range: RangeMut<'a, K, V>,
+    length: usize
 }
 
 /// An owning iterator over a BTreeMap's entries.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct IntoIter<K, V> {
-    inner: AbsIter<MoveTraversal<K, V>>,
+    front: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
+    back: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
+    length: usize
 }
 
 /// An iterator over a BTreeMap's keys.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Keys<'a, K: 'a, V: 'a> {
-    inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>,
+    inner: Iter<'a, K, V>,
 }
 
 /// An iterator over a BTreeMap's values.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Values<'a, K: 'a, V: 'a> {
-    inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>,
+    inner: Iter<'a, K, V>,
 }
 
 /// An iterator over a sub-range of BTreeMap's entries.
 pub struct Range<'a, K: 'a, V: 'a> {
-    inner: AbsIter<Traversal<'a, K, V>>,
+    front: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>,
+    back: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>
 }
 
 /// A mutable iterator over a sub-range of BTreeMap's entries.
 pub struct RangeMut<'a, K: 'a, V: 'a> {
-    inner: AbsIter<MutTraversal<'a, K, V>>,
+    front: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
+    back: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>
 }
 
 /// A view into a single entry in a map, which may either be vacant or occupied.
@@ -141,28 +246,30 @@ pub enum Entry<'a, K: 'a, V: 'a> {
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct VacantEntry<'a, K: 'a, V: 'a> {
     key: K,
-    stack: stack::SearchStack<'a, K, V, node::handle::Edge, node::handle::Leaf>,
+    handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
+    length: &'a mut usize
 }
 
 /// An occupied Entry.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
-    stack: stack::SearchStack<'a, K, V, node::handle::KV, node::handle::LeafOrInternal>,
+    handle: Handle<NodeRef<
+        marker::Mut<'a>,
+        K, V,
+        marker::LeafOrInternal
+    >, marker::KV>,
+
+    length: &'a mut usize
 }
 
 impl<K: Ord, V> BTreeMap<K, V> {
     /// Makes a new empty BTreeMap with a reasonable choice for B.
     #[stable(feature = "rust1", since = "1.0.0")]
-    #[allow(deprecated)]
     pub fn new() -> BTreeMap<K, V> {
         BTreeMap {
-            length: 0,
-            depth: 1,
-            root: Node::make_leaf_root(6),
-            // FIXME(Gankro): Tune this as a function of size_of<K/V>?
-            b: 6,
+            root: node::Root::new_leaf(),
+            length: 0
         }
-
     }
 
     /// Clears the map, removing all values.
@@ -179,18 +286,10 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn clear(&mut self) {
-        // avoid recursive destructors by manually traversing the tree
-        for _ in mem::replace(self, BTreeMap::new()) {}
+        // FIXME(gereeter) .clear() allocates
+        *self = BTreeMap::new();
     }
 
-    // Searching in a B-Tree is pretty straightforward.
-    //
-    // Start at the root. Try to find the key in the current node. If we find it, return it.
-    // If it's not in there, follow the edge *before* the smallest key larger than
-    // the search key. If no such key exists (they're *all* smaller), then just take the last
-    // edge in the node. If we're in a leaf and we don't find our key, then it's not
-    // in the tree.
-
     /// 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
@@ -207,24 +306,10 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// assert_eq!(map.get(&2), None);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
-        where K: Borrow<Q>,
-              Q: Ord
-    {
-        let mut cur_node = &self.root;
-        loop {
-            match Node::search(cur_node, key) {
-                Found(handle) => return Some(handle.into_kv().1),
-                GoDown(handle) => {
-                    match handle.force() {
-                        Leaf(_) => return None,
-                        Internal(internal_handle) => {
-                            cur_node = internal_handle.into_edge();
-                            continue;
-                        }
-                    }
-                }
-            }
+    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>, Q: Ord {
+        match search::search_tree(self.root.as_ref(), key) {
+            Found(handle) => Some(handle.into_kv().1),
+            GoDown(_) => None
         }
     }
 
@@ -244,10 +329,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// assert_eq!(map.contains_key(&2), false);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
-        where K: Borrow<Q>,
-              Q: Ord
-    {
+    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where K: Borrow<Q>, Q: Ord {
         self.get(key).is_some()
     }
 
@@ -270,55 +352,13 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// ```
     // See `get` for implementation notes, this is basically a copy-paste with mut's added
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
-        where K: Borrow<Q>,
-              Q: Ord
-    {
-        // temp_node is a Borrowck hack for having a mutable value outlive a loop iteration
-        let mut temp_node = &mut self.root;
-        loop {
-            let cur_node = temp_node;
-            match Node::search(cur_node, key) {
-                Found(handle) => return Some(handle.into_kv_mut().1),
-                GoDown(handle) => {
-                    match handle.force() {
-                        Leaf(_) => return None,
-                        Internal(internal_handle) => {
-                            temp_node = internal_handle.into_edge_mut();
-                            continue;
-                        }
-                    }
-                }
-            }
+    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Ord {
+        match search::search_tree(self.root.as_mut(), key) {
+            Found(handle) => Some(handle.into_kv_mut().1),
+            GoDown(_) => None
         }
     }
 
-    // Insertion in a B-Tree is a bit complicated.
-    //
-    // First we do the same kind of search described in `find`. But we need to maintain a stack of
-    // all the nodes/edges in our search path. If we find a match for the key we're trying to
-    // insert, just swap the vals and return the old ones. However, when we bottom out in a leaf,
-    // we attempt to insert our key-value pair at the same location we would want to follow another
-    // edge.
-    //
-    // If the node has room, then this is done in the obvious way by shifting elements. However,
-    // if the node itself is full, we split node into two, and give its median key-value
-    // pair to its parent to insert the new node with. Of course, the parent may also be
-    // full, and insertion can propagate until we reach the root. If we reach the root, and
-    // it is *also* full, then we split the root and place the two nodes under a newly made root.
-    //
-    // Note that we subtly deviate from Open Data Structures in our implementation of split.
-    // ODS describes inserting into the node *regardless* of its capacity, and then
-    // splitting *afterwards* if it happens to be overfull. However, this is inefficient.
-    // Instead, we split beforehand, and then insert the key-value pair into the appropriate
-    // result node. This has two consequences:
-    //
-    // 1) While ODS produces a left node of size B-1, and a right node of size B,
-    // we may potentially reverse this. However, this shouldn't effect the analysis.
-    //
-    // 2) While ODS may potentially return the pair we *just* inserted after
-    // the split, we will never do this. Again, this shouldn't effect the analysis.
-
     /// Inserts a key-value pair into the map.
     ///
     /// If the map did not have this key present, `None` is returned.
@@ -343,98 +383,16 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// assert_eq!(map[&37], "c");
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn insert(&mut self, mut key: K, mut value: V) -> Option<V> {
-        // This is a stack of rawptrs to nodes paired with indices, respectively
-        // representing the nodes and edges of our search path. We have to store rawptrs
-        // because as far as Rust is concerned, we can mutate aliased data with such a
-        // stack. It is of course correct, but what it doesn't know is that we will only
-        // be popping and using these ptrs one at a time in child-to-parent order. The alternative
-        // to doing this is to take the Nodes from their parents. This actually makes
-        // borrowck *really* happy and everything is pretty smooth. However, this creates
-        // *tons* of pointless writes, and requires us to always walk all the way back to
-        // the root after an insertion, even if we only needed to change a leaf. Therefore,
-        // we accept this potential unsafety and complexity in the name of performance.
-        //
-        // Regardless, the actual dangerous logic is completely abstracted away from BTreeMap
-        // by the stack module. All it can do is immutably read nodes, and ask the search stack
-        // to proceed down some edge by index. This makes the search logic we'll be reusing in a
-        // few different methods much neater, and of course drastically improves safety.
-        let mut stack = stack::PartialSearchStack::new(self);
-
-        loop {
-            let result = stack.with(move |pusher, node| {
-                // Same basic logic as found in `find`, but with PartialSearchStack mediating the
-                // actual nodes for us
-                match Node::search(node, &key) {
-                    Found(mut handle) => {
-                        // Perfect match, swap the values and return the old one
-                        mem::swap(handle.val_mut(), &mut value);
-                        Finished(Some(value))
-                    }
-                    GoDown(handle) => {
-                        // We need to keep searching, try to get the search stack
-                        // to go down further
-                        match handle.force() {
-                            Leaf(leaf_handle) => {
-                                // We've reached a leaf, perform the insertion here
-                                pusher.seal(leaf_handle).insert(key, value);
-                                Finished(None)
-                            }
-                            Internal(internal_handle) => {
-                                // We've found the subtree to insert this key/value pair in,
-                                // keep searching
-                                Continue((pusher.push(internal_handle), key, value))
-                            }
-                        }
-                    }
-                }
-            });
-            match result {
-                Finished(ret) => return ret,
-                Continue((new_stack, renewed_key, renewed_val)) => {
-                    stack = new_stack;
-                    key = renewed_key;
-                    value = renewed_val;
-                }
+    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
+        match self.entry(key) {
+            Occupied(mut entry) => Some(entry.insert(value)),
+            Vacant(entry) => {
+                entry.insert(value);
+                None
             }
         }
     }
 
-    // Deletion is the most complicated operation for a B-Tree.
-    //
-    // First we do the same kind of search described in
-    // `find`. But we need to maintain a stack of all the nodes/edges in our search path.
-    // If we don't find the key, then we just return `None` and do nothing. If we do find the
-    // key, we perform two operations: remove the item, and then possibly handle underflow.
-    //
-    // # removing the item
-    //      If the node is a leaf, we just remove the item, and shift
-    //      any items after it back to fill the hole.
-    //
-    //      If the node is an internal node, we *swap* the item with the smallest item in
-    //      in its right subtree (which must reside in a leaf), and then revert to the leaf
-    //      case
-    //
-    // # handling underflow
-    //      After removing an item, there may be too few items in the node. We want nodes
-    //      to be mostly full for efficiency, although we make an exception for the root, which
-    //      may have as few as one item. If this is the case, we may first try to steal
-    //      an item from our left or right neighbour.
-    //
-    //      To steal from the left (right) neighbour,
-    //      we take the largest (smallest) item and child from it. We then swap the taken item
-    //      with the item in their mutual parent that separates them, and then insert the
-    //      parent's item and the taken child into the first (last) index of the underflowed node.
-    //
-    //      However, stealing has the possibility of underflowing our neighbour. If this is the
-    //      case, we instead *merge* with our neighbour. This of course reduces the number of
-    //      children in the parent. Therefore, we also steal the item that separates the now
-    //      merged nodes, and insert it into the merged node.
-    //
-    //      Merging may cause the parent to underflow. If this is the case, then we must repeat
-    //      the underflow handling process on the parent. If merging merges the last two children
-    //      of the root, then we replace the root with the merged node.
-
     /// Removes a key from the map, returning the value at the key if the key
     /// was previously in the map.
     ///
@@ -452,73 +410,201 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// assert_eq!(map.remove(&1), None);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
-        where K: Borrow<Q>,
-              Q: Ord
-    {
-        // See `swap` for a more thorough description of the stuff going on in here
-        let mut stack = stack::PartialSearchStack::new(self);
-        loop {
-            let result = stack.with(move |pusher, node| {
-                match Node::search(node, key) {
-                    Found(handle) => {
-                        // Perfect match. Terminate the stack here, and remove the entry
-                        Finished(Some(pusher.seal(handle).remove()))
-                    }
-                    GoDown(handle) => {
-                        // We need to keep searching, try to go down the next edge
-                        match handle.force() {
-                            // We're at a leaf; the key isn't in here
-                            Leaf(_) => Finished(None),
-                            Internal(internal_handle) => Continue(pusher.push(internal_handle)),
-                        }
-                    }
-                }
-            });
-            match result {
-                Finished(ret) => return ret.map(|(_, v)| v),
-                Continue(new_stack) => stack = new_stack,
-            }
+    pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: Ord {
+        match search::search_tree(self.root.as_mut(), key) {
+            Found(handle) => {
+                Some(OccupiedEntry {
+                    handle: handle,
+                    length: &mut self.length
+                }.remove())
+            },
+            GoDown(_) => None
         }
     }
-}
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<K, V> IntoIterator for BTreeMap<K, V> {
-    type Item = (K, V);
-    type IntoIter = IntoIter<K, V>;
-
-    /// Gets an owning iterator over the entries of the map.
+    /// Constructs a double-ended iterator over a sub-range of elements in the map, starting
+    /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
+    /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
+    /// Thus range(Unbounded, Unbounded) will yield the whole collection.
     ///
     /// # Examples
     ///
     /// ```
+    /// #![feature(btree_range, collections_bound)]
+    ///
     /// use std::collections::BTreeMap;
+    /// use std::collections::Bound::{Included, Unbounded};
     ///
     /// let mut map = BTreeMap::new();
-    /// map.insert(1, "a");
-    /// map.insert(2, "b");
-    /// map.insert(3, "c");
-    ///
-    /// for (key, value) in map.into_iter() {
+    /// map.insert(3, "a");
+    /// map.insert(5, "b");
+    /// map.insert(8, "c");
+    /// for (&key, &value) in map.range(Included(&4), Included(&8)) {
     ///     println!("{}: {}", key, value);
     /// }
+    /// assert_eq!(Some((&5, &"b")), map.range(Included(&4), Unbounded).next());
     /// ```
-    fn into_iter(self) -> IntoIter<K, V> {
-        let len = self.len();
-        let mut lca = VecDeque::new();
-        lca.push_back(Traverse::traverse(self.root));
-        IntoIter {
-            inner: AbsIter {
-                traversals: lca,
-                size: len,
+    #[unstable(feature = "btree_range",
+               reason = "matches collection reform specification, waiting for dust to settle",
+               issue = "27787")]
+    pub fn range<Min: ?Sized + Ord, Max: ?Sized + Ord>(&self,
+                                                       min: Bound<&Min>,
+                                                       max: Bound<&Max>)
+                                                       -> Range<K, V>
+        where K: Borrow<Min> + Borrow<Max>,
+    {
+        let front = match min {
+            Included(key) => match search::search_tree(self.root.as_ref(), key) {
+                Found(kv_handle) => match kv_handle.left_edge().force() {
+                    Leaf(bottom) => bottom,
+                    Internal(internal) => last_leaf_edge(internal.descend())
+                },
+                GoDown(bottom) => bottom
+            },
+            Excluded(key) => match search::search_tree(self.root.as_ref(), key) {
+                Found(kv_handle) => match kv_handle.right_edge().force() {
+                    Leaf(bottom) => bottom,
+                    Internal(internal) => first_leaf_edge(internal.descend())
+                },
+                GoDown(bottom) => bottom
             },
+            Unbounded => first_leaf_edge(self.root.as_ref())
+        };
+
+        let back = match max {
+            Included(key) => match search::search_tree(self.root.as_ref(), key) {
+                Found(kv_handle) => match kv_handle.right_edge().force() {
+                    Leaf(bottom) => bottom,
+                    Internal(internal) => first_leaf_edge(internal.descend())
+                },
+                GoDown(bottom) => bottom
+            },
+            Excluded(key) => match search::search_tree(self.root.as_ref(), key) {
+                Found(kv_handle) => match kv_handle.left_edge().force() {
+                    Leaf(bottom) => bottom,
+                    Internal(internal) => last_leaf_edge(internal.descend())
+                },
+                GoDown(bottom) => bottom
+            },
+            Unbounded => last_leaf_edge(self.root.as_ref())
+        };
+
+        Range {
+            front: front,
+            back: back
+        }
+    }
+
+    /// Constructs a mutable double-ended iterator over a sub-range of elements in the map, starting
+    /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
+    /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
+    /// Thus range(Unbounded, Unbounded) will yield the whole collection.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(btree_range, collections_bound)]
+    ///
+    /// use std::collections::BTreeMap;
+    /// use std::collections::Bound::{Included, Excluded};
+    ///
+    /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter()
+    ///                                                                       .map(|&s| (s, 0))
+    ///                                                                       .collect();
+    /// for (_, balance) in map.range_mut(Included("B"), Excluded("Cheryl")) {
+    ///     *balance += 100;
+    /// }
+    /// for (name, balance) in &map {
+    ///     println!("{} => {}", name, balance);
+    /// }
+    /// ```
+    #[unstable(feature = "btree_range",
+               reason = "matches collection reform specification, waiting for dust to settle",
+               issue = "27787")]
+    pub fn range_mut<Min: ?Sized + Ord, Max: ?Sized + Ord>(&mut self,
+                                                           min: Bound<&Min>,
+                                                           max: Bound<&Max>)
+                                                           -> RangeMut<K, V>
+        where K: Borrow<Min> + Borrow<Max>,
+    {
+        let root1 = self.root.as_mut();
+        let root2 = unsafe { ptr::read(&root1) };
+
+        let front = match min {
+            Included(key) => match search::search_tree(root1, key) {
+                Found(kv_handle) => match kv_handle.left_edge().force() {
+                    Leaf(bottom) => bottom,
+                    Internal(internal) => last_leaf_edge(internal.descend())
+                },
+                GoDown(bottom) => bottom
+            },
+            Excluded(key) => match search::search_tree(root1, key) {
+                Found(kv_handle) => match kv_handle.right_edge().force() {
+                    Leaf(bottom) => bottom,
+                    Internal(internal) => first_leaf_edge(internal.descend())
+                },
+                GoDown(bottom) => bottom
+            },
+            Unbounded => first_leaf_edge(root1)
+        };
+
+        let back = match max {
+            Included(key) => match search::search_tree(root2, key) {
+                Found(kv_handle) => match kv_handle.right_edge().force() {
+                    Leaf(bottom) => bottom,
+                    Internal(internal) => first_leaf_edge(internal.descend())
+                },
+                GoDown(bottom) => bottom
+            },
+            Excluded(key) => match search::search_tree(root2, key) {
+                Found(kv_handle) => match kv_handle.left_edge().force() {
+                    Leaf(bottom) => bottom,
+                    Internal(internal) => last_leaf_edge(internal.descend())
+                },
+                GoDown(bottom) => bottom
+            },
+            Unbounded => last_leaf_edge(root2)
+        };
+
+        RangeMut {
+            front: front,
+            back: back
+        }
+    }
+
+    /// Gets the given key's corresponding entry in the map for in-place manipulation.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use std::collections::BTreeMap;
+    ///
+    /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
+    ///
+    /// // 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);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn entry(&mut self, key: K) -> Entry<K, V> {
+        match search::search_tree(self.root.as_mut(), &key) {
+            Found(handle) => Occupied(OccupiedEntry {
+                handle: handle,
+                length: &mut self.length
+            }),
+            GoDown(handle) => Vacant(VacantEntry {
+                key: key,
+                handle: handle,
+                length: &mut self.length
+            })
         }
     }
 }
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, K, V> IntoIterator for &'a BTreeMap<K, V> {
+impl<'a, K: 'a, V: 'a> IntoIterator for &'a BTreeMap<K, V> {
     type Item = (&'a K, &'a V);
     type IntoIter = Iter<'a, K, V>;
 
@@ -527,769 +613,570 @@ impl<'a, K, V> IntoIterator for &'a BTreeMap<K, V> {
     }
 }
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, K, V> IntoIterator for &'a mut BTreeMap<K, V> {
-    type Item = (&'a K, &'a mut V);
-    type IntoIter = IterMut<'a, K, V>;
+impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
+    type Item = (&'a K, &'a V);
 
-    fn into_iter(mut self) -> IterMut<'a, K, V> {
-        self.iter_mut()
+    fn next(&mut self) -> Option<(&'a K, &'a V)> {
+        if self.length == 0 {
+            None
+        } else {
+            self.length -= 1;
+            unsafe { Some(self.range.next_unchecked()) }
+        }
     }
-}
 
-/// A helper enum useful for deciding whether to continue a loop since we can't
-/// return from a closure
-enum Continuation<A, B> {
-    Continue(A),
-    Finished(B),
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (self.length, Some(self.length))
+    }
 }
 
-/// The stack module provides a safe interface for constructing and manipulating a stack of ptrs
-/// to nodes. By using this module much better safety guarantees can be made, and more search
-/// boilerplate gets cut out.
-mod stack {
-    use core::marker;
-    use core::mem;
-    use core::ops::{Deref, DerefMut};
-    use super::BTreeMap;
-    use super::super::node::{self, Node, Fit, Split, Internal, Leaf};
-    use super::super::node::handle;
-    use vec::Vec;
-
-    struct InvariantLifetime<'id>(marker::PhantomData<::core::cell::Cell<&'id ()>>);
-
-    impl<'id> InvariantLifetime<'id> {
-        fn new() -> InvariantLifetime<'id> {
-            InvariantLifetime(marker::PhantomData)
+impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
+    fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
+        if self.length == 0 {
+            None
+        } else {
+            self.length -= 1;
+            unsafe { Some(self.range.next_back_unchecked()) }
         }
     }
+}
 
-    /// A generic mutable reference, identical to `&mut` except for the fact that its lifetime
-    /// parameter is invariant. This means that wherever an `IdRef` is expected, only an `IdRef`
-    /// with the exact requested lifetime can be used. This is in contrast to normal references,
-    /// where `&'static` can be used in any function expecting any lifetime reference.
-    pub struct IdRef<'id, T: 'id> {
-        inner: &'id mut T,
-        _marker: InvariantLifetime<'id>,
-    }
-
-    impl<'id, T> Deref for IdRef<'id, T> {
-        type Target = T;
+impl<'a, K: 'a, V: 'a> ExactSizeIterator for Iter<'a, K, V> {
+    fn len(&self) -> usize { self.length }
+}
 
-        fn deref(&self) -> &T {
-            &*self.inner
+impl<'a, K, V> Clone for Iter<'a, K, V> {
+    fn clone(&self) -> Iter<'a, K, V> {
+        Iter {
+            range: self.range.clone(),
+            length: self.length
         }
     }
+}
 
-    impl<'id, T> DerefMut for IdRef<'id, T> {
-        fn deref_mut(&mut self) -> &mut T {
-            &mut *self.inner
-        }
+impl<'a, K: 'a, V: 'a> IntoIterator for &'a mut BTreeMap<K, V> {
+    type Item = (&'a K, &'a mut V);
+    type IntoIter = IterMut<'a, K, V>;
+
+    fn into_iter(self) -> IterMut<'a, K, V> {
+        self.iter_mut()
     }
+}
 
-    type StackItem<K, V> = node::Handle<*mut Node<K, V>, handle::Edge, handle::Internal>;
-    type Stack<K, V> = Vec<StackItem<K, V>>;
+impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
+    type Item = (&'a K, &'a mut V);
 
-    /// A `PartialSearchStack` handles the construction of a search stack.
-    pub struct PartialSearchStack<'a, K: 'a, V: 'a> {
-        map: &'a mut BTreeMap<K, V>,
-        stack: Stack<K, V>,
-        next: *mut Node<K, V>,
+    fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
+        if self.length == 0 {
+            None
+        } else {
+            self.length -= 1;
+            unsafe { Some(self.range.next_unchecked()) }
+        }
     }
 
-    /// A `SearchStack` represents a full path to an element or an edge of interest. It provides
-    /// methods depending on the type of what the path points to for removing an element, inserting
-    /// a new element, and manipulating to element at the top of the stack.
-    pub struct SearchStack<'a, K: 'a, V: 'a, Type, NodeType> {
-        map: &'a mut BTreeMap<K, V>,
-        stack: Stack<K, V>,
-        top: node::Handle<*mut Node<K, V>, Type, NodeType>,
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (self.length, Some(self.length))
     }
+}
 
-    /// A `PartialSearchStack` that doesn't hold a reference to the next node, and is just
-    /// just waiting for a `Handle` to that next node to be pushed. See `PartialSearchStack::with`
-    /// for more details.
-    pub struct Pusher<'id, 'a, K: 'a, V: 'a> {
-        map: &'a mut BTreeMap<K, V>,
-        stack: Stack<K, V>,
-        _marker: InvariantLifetime<'id>,
+impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> {
+    fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
+        if self.length == 0 {
+            None
+        } else {
+            self.length -= 1;
+            unsafe { Some(self.range.next_back_unchecked()) }
+        }
     }
+}
 
-    impl<'a, K, V> PartialSearchStack<'a, K, V> {
-        /// Creates a new PartialSearchStack from a BTreeMap by initializing the stack with the
-        /// root of the tree.
-        pub fn new(map: &'a mut BTreeMap<K, V>) -> PartialSearchStack<'a, K, V> {
-            let depth = map.depth;
+impl<'a, K: 'a, V: 'a> ExactSizeIterator for IterMut<'a, K, V> {
+    fn len(&self) -> usize { self.length }
+}
 
-            PartialSearchStack {
-                next: &mut map.root as *mut _,
-                map: map,
-                stack: Vec::with_capacity(depth),
-            }
-        }
+impl<K, V> IntoIterator for BTreeMap<K, V> {
+    type Item = (K, V);
+    type IntoIter = IntoIter<K, V>;
 
-        /// Breaks up the stack into a `Pusher` and the next `Node`, allowing the given closure
-        /// to interact with, search, and finally push the `Node` onto the stack. The passed in
-        /// closure must be polymorphic on the `'id` lifetime parameter, as this statically
-        /// ensures that only `Handle`s from the correct `Node` can be pushed.
-        ///
-        /// The reason this works is that the `Pusher` has an `'id` parameter, and will only accept
-        /// handles with the same `'id`. The closure could only get references with that lifetime
-        /// through its arguments or through some other `IdRef` that it has lying around. However,
-        /// no other `IdRef` could possibly work - because the `'id` is held in an invariant
-        /// parameter, it would need to have precisely the correct lifetime, which would mean that
-        /// at least one of the calls to `with` wouldn't be properly polymorphic, wanting a
-        /// specific lifetime instead of the one that `with` chooses to give it.
-        ///
-        /// See also Haskell's `ST` monad, which uses a similar trick.
-        pub fn with<T, F: for<'id> FnOnce(Pusher<'id, 'a, K, V>,
-                                          IdRef<'id, Node<K, V>>) -> T>(self, closure: F) -> T {
-            let pusher = Pusher {
-                map: self.map,
-                stack: self.stack,
-                _marker: InvariantLifetime::new(),
-            };
-            let node = IdRef {
-                inner: unsafe { &mut *self.next },
-                _marker: InvariantLifetime::new(),
-            };
+    fn into_iter(self) -> IntoIter<K, V> {
+        let root1 = unsafe { ptr::read(&self.root).into_ref() };
+        let root2 = unsafe { ptr::read(&self.root).into_ref() };
+        let len = self.length;
+        mem::forget(self);
 
-            closure(pusher, node)
+        IntoIter {
+            front: first_leaf_edge(root1),
+            back: last_leaf_edge(root2),
+            length: len
         }
     }
+}
 
-    impl<'id, 'a, K, V> Pusher<'id, 'a, K, V> {
-        /// Pushes the requested child of the stack's current top on top of the stack. If the child
-        /// exists, then a new PartialSearchStack is yielded. Otherwise, a VacantSearchStack is
-        /// yielded.
-        pub fn push(mut self,
-                    mut edge: node::Handle<IdRef<'id, Node<K, V>>, handle::Edge, handle::Internal>)
-                    -> PartialSearchStack<'a, K, V> {
-            self.stack.push(edge.as_raw());
-            PartialSearchStack {
-                map: self.map,
-                stack: self.stack,
-                next: edge.edge_mut() as *mut _,
-            }
-        }
-
-        /// Converts the PartialSearchStack into a SearchStack.
-        pub fn seal<Type, NodeType>(self,
-                                    mut handle: node::Handle<IdRef<'id, Node<K, V>>,
-                                                             Type,
-                                                             NodeType>)
-                                    -> SearchStack<'a, K, V, Type, NodeType> {
-            SearchStack {
-                map: self.map,
-                stack: self.stack,
-                top: handle.as_raw(),
+impl<K, V> Drop for IntoIter<K, V> {
+    fn drop(&mut self) {
+        for _ in &mut *self { }
+        unsafe {
+            let leaf_node = ptr::read(&self.front).into_node();
+            if let Some(first_parent) = leaf_node.deallocate_and_ascend() {
+                let mut cur_node = first_parent.into_node();
+                while let Some(parent) = cur_node.deallocate_and_ascend() {
+                    cur_node = parent.into_node()
+                }
             }
         }
     }
+}
 
-    impl<'a, K, V, NodeType> SearchStack<'a, K, V, handle::KV, NodeType> {
-        /// Gets a reference to the value the stack points to.
-        pub fn peek(&self) -> &V {
-            unsafe { self.top.from_raw().into_kv().1 }
-        }
-
-        /// Gets a mutable reference to the value the stack points to.
-        pub fn peek_mut(&mut self) -> &mut V {
-            unsafe { self.top.from_raw_mut().into_kv_mut().1 }
-        }
+impl<K, V> Iterator for IntoIter<K, V> {
+    type Item = (K, V);
 
-        /// Converts the stack into a mutable reference to the value it points to, with a lifetime
-        /// tied to the original tree.
-        pub fn into_top(mut self) -> &'a mut V {
-            unsafe { &mut *(self.top.from_raw_mut().val_mut() as *mut V) }
+    fn next(&mut self) -> Option<(K, V)> {
+        if self.length == 0 {
+            return None;
+        } else {
+            self.length -= 1;
         }
-    }
 
-    impl<'a, K, V> SearchStack<'a, K, V, handle::KV, handle::Leaf> {
-        /// Removes the key and value in the top element of the stack, then handles underflows as
-        /// described in BTree's pop function.
-        fn remove_leaf(mut self) -> (K, V) {
-            self.map.length -= 1;
+        let handle = unsafe { ptr::read(&self.front) };
 
-            // Remove the key-value pair from the leaf that this search stack points to.
-            // Then, note if the leaf is underfull, and promptly forget the leaf and its ptr
-            // to avoid ownership issues.
-            let (key_val, mut underflow) = unsafe {
-                let key_val = self.top.from_raw_mut().remove_as_leaf();
-                let underflow = self.top.from_raw().node().is_underfull();
-                (key_val, underflow)
-            };
+        let mut cur_handle = match handle.right_kv() {
+            Ok(kv) => {
+                let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
+                let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
+                self.front = kv.right_edge();
+                return Some((k, v));
+            },
+            Err(last_edge) => unsafe {
+                unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
+            }
+        };
 
-            loop {
-                match self.stack.pop() {
-                    None => {
-                        // We've reached the root, so no matter what, we're done. We manually
-                        // access the root via the tree itself to avoid creating any dangling
-                        // pointers.
-                        if self.map.root.is_empty() && !self.map.root.is_leaf() {
-                            // We've emptied out the root, so make its only child the new root.
-                            // If it's a leaf, we just let it become empty.
-                            self.map.depth -= 1;
-                            self.map.root.hoist_lone_child();
-                        }
-                        return key_val;
-                    }
-                    Some(mut handle) => {
-                        if underflow {
-                            // Underflow! Handle it!
-                            unsafe {
-                                handle.from_raw_mut().handle_underflow();
-                                underflow = handle.from_raw().node().is_underfull();
-                            }
-                        } else {
-                            // All done!
-                            return key_val;
-                        }
-                    }
+        loop {
+            match cur_handle.right_kv() {
+                Ok(kv) => {
+                    let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
+                    let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
+                    self.front = first_leaf_edge(kv.right_edge().descend());
+                    return Some((k, v));
+                },
+                Err(last_edge) => unsafe {
+                    cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
                 }
             }
         }
     }
 
-    impl<'a, K, V> SearchStack<'a, K, V, handle::KV, handle::LeafOrInternal> {
-        /// Removes the key and value in the top element of the stack, then handles underflows as
-        /// described in BTree's pop function.
-        pub fn remove(self) -> (K, V) {
-            // Ensure that the search stack goes to a leaf. This is necessary to perform deletion
-            // in a BTree. Note that this may put the tree in an inconsistent state (further
-            // described in into_leaf's comments), but this is immediately fixed by the
-            // removing the value we want to remove
-            self.into_leaf().remove_leaf()
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (self.length, Some(self.length))
+    }
+}
+
+impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
+    fn next_back(&mut self) -> Option<(K, V)> {
+        if self.length == 0 {
+            return None;
+        } else {
+            self.length -= 1;
         }
 
-        /// Subroutine for removal. Takes a search stack for a key that might terminate at an
-        /// internal node, and mutates the tree and search stack to *make* it a search stack
-        /// for that same key that *does* terminates at a leaf. If the mutation occurs, then this
-        /// leaves the tree in an inconsistent state that must be repaired by the caller by
-        /// removing the entry in question. Specifically the key-value pair and its successor will
-        /// become swapped.
-        fn into_leaf(mut self) -> SearchStack<'a, K, V, handle::KV, handle::Leaf> {
-            unsafe {
-                let mut top_raw = self.top;
-                let mut top = top_raw.from_raw_mut();
-
-                let key_ptr = top.key_mut() as *mut _;
-                let val_ptr = top.val_mut() as *mut _;
-
-                // Try to go into the right subtree of the found key to find its successor
-                match top.force() {
-                    Leaf(mut leaf_handle) => {
-                        // We're a proper leaf stack, nothing to do
-                        return SearchStack {
-                            map: self.map,
-                            stack: self.stack,
-                            top: leaf_handle.as_raw(),
-                        };
-                    }
-                    Internal(mut internal_handle) => {
-                        let mut right_handle = internal_handle.right_edge();
-
-                        // We're not a proper leaf stack, let's get to work.
-                        self.stack.push(right_handle.as_raw());
-
-                        let mut temp_node = right_handle.edge_mut();
-                        loop {
-                            // Walk into the smallest subtree of this node
-                            let node = temp_node;
-
-                            match node.kv_handle(0).force() {
-                                Leaf(mut handle) => {
-                                    // This node is a leaf, do the swap and return
-                                    mem::swap(handle.key_mut(), &mut *key_ptr);
-                                    mem::swap(handle.val_mut(), &mut *val_ptr);
-                                    return SearchStack {
-                                        map: self.map,
-                                        stack: self.stack,
-                                        top: handle.as_raw(),
-                                    };
-                                }
-                                Internal(kv_handle) => {
-                                    // This node is internal, go deeper
-                                    let mut handle = kv_handle.into_left_edge();
-                                    self.stack.push(handle.as_raw());
-                                    temp_node = handle.into_edge_mut();
-                                }
-                            }
-                        }
-                    }
-                }
+        let handle = unsafe { ptr::read(&self.back) };
+
+        let mut cur_handle = match handle.left_kv() {
+            Ok(kv) => {
+                let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
+                let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
+                self.back = kv.left_edge();
+                return Some((k, v));
+            },
+            Err(last_edge) => unsafe {
+                unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
             }
-        }
-    }
+        };
 
-    impl<'a, K, V> SearchStack<'a, K, V, handle::Edge, handle::Leaf> {
-        /// Inserts the key and value into the top element in the stack, and if that node has to
-        /// split recursively inserts the split contents into the next element stack until
-        /// splits stop.
-        ///
-        /// Assumes that the stack represents a search path from the root to a leaf.
-        ///
-        /// An &mut V is returned to the inserted value, for callers that want a reference to this.
-        pub fn insert(mut self, key: K, val: V) -> &'a mut V {
-            unsafe {
-                self.map.length += 1;
-
-                // Insert the key and value into the leaf at the top of the stack
-                let (mut insertion, inserted_ptr) = self.top
-                                                        .from_raw_mut()
-                                                        .insert_as_leaf(key, val);
-
-                loop {
-                    match insertion {
-                        Fit => {
-                            // The last insertion went off without a hitch, no splits! We can stop
-                            // inserting now.
-                            return &mut *inserted_ptr;
-                        }
-                        Split(key, val, right) => {
-                            match self.stack.pop() {
-                                // The last insertion triggered a split, so get the next element on
-                                // the stack to recursively insert the split node into.
-                                None => {
-                                    // The stack was empty; we've split the root, and need to make a
-                                    // a new one. This is done in-place because we can't move the
-                                    // root out of a reference to the tree.
-                                    Node::make_internal_root(&mut self.map.root,
-                                                             self.map.b,
-                                                             key,
-                                                             val,
-                                                             right);
-
-                                    self.map.depth += 1;
-                                    return &mut *inserted_ptr;
-                                }
-                                Some(mut handle) => {
-                                    // The stack wasn't empty, do the insertion and recurse
-                                    insertion = handle.from_raw_mut()
-                                                      .insert_as_internal(key, val, right);
-                                    continue;
-                                }
-                            }
-                        }
-                    }
+        loop {
+            match cur_handle.left_kv() {
+                Ok(kv) => {
+                    let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
+                    let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
+                    self.back = last_leaf_edge(kv.left_edge().descend());
+                    return Some((k, v));
+                },
+                Err(last_edge) => unsafe {
+                    cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
                 }
             }
         }
     }
 }
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
-    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> BTreeMap<K, V> {
-        let mut map = BTreeMap::new();
-        map.extend(iter);
-        map
-    }
+impl<K, V> ExactSizeIterator for IntoIter<K, V> {
+    fn len(&self) -> usize { self.length }
 }
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
-    #[inline]
-    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
-        for (k, v) in iter {
-            self.insert(k, v);
-        }
+impl<'a, K, V> Iterator for Keys<'a, K, V> {
+    type Item = &'a K;
+
+    fn next(&mut self) -> Option<&'a K> {
+        self.inner.next().map(|(k, _)| k)
     }
-}
 
-#[stable(feature = "extend_ref", since = "1.2.0")]
-impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap<K, V> {
-    fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I) {
-        self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
     }
 }
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> {
-    fn hash<H: Hasher>(&self, state: &mut H) {
-        for elt in self {
-            elt.hash(state);
-        }
+impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
+    fn next_back(&mut self) -> Option<&'a K> {
+        self.inner.next_back().map(|(k, _)| k)
     }
 }
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<K: Ord, V> Default for BTreeMap<K, V> {
-    fn default() -> BTreeMap<K, V> {
-        BTreeMap::new()
+impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
+    fn len(&self) -> usize {
+        self.inner.len()
     }
 }
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
-    fn eq(&self, other: &BTreeMap<K, V>) -> bool {
-        self.len() == other.len() && self.iter().zip(other).all(|(a, b)| a == b)
+impl<'a, K, V> Clone for Keys<'a, K, V> {
+    fn clone(&self) -> Keys<'a, K, V> {
+        Keys {
+            inner: self.inner.clone()
+        }
     }
 }
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
+impl<'a, K, V> Iterator for Values<'a, K, V> {
+    type Item = &'a V;
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
-    #[inline]
-    fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
-        self.iter().partial_cmp(other.iter())
+    fn next(&mut self) -> Option<&'a V> {
+        self.inner.next().map(|(_, v)| v)
     }
-}
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
-    #[inline]
-    fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
-        self.iter().cmp(other.iter())
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
     }
 }
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        f.debug_map().entries(self.iter()).finish()
+impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
+    fn next_back(&mut self) -> Option<&'a V> {
+        self.inner.next_back().map(|(_, v)| v)
     }
 }
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for BTreeMap<K, V>
-    where K: Borrow<Q>,
-          Q: Ord
-{
-    type Output = V;
-
-    #[inline]
-    fn index(&self, key: &Q) -> &V {
-        self.get(key).expect("no entry found for key")
+impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
+    fn len(&self) -> usize {
+        self.inner.len()
     }
 }
 
-/// Genericizes over how to get the correct type of iterator from the correct type
-/// of Node ownership.
-trait Traverse<N> {
-    fn traverse(node: N) -> Self;
-}
-
-impl<'a, K, V> Traverse<&'a Node<K, V>> for Traversal<'a, K, V> {
-    fn traverse(node: &'a Node<K, V>) -> Traversal<'a, K, V> {
-        node.iter()
+impl<'a, K, V> Clone for Values<'a, K, V> {
+    fn clone(&self) -> Values<'a, K, V> {
+        Values {
+            inner: self.inner.clone()
+        }
     }
 }
 
-impl<'a, K, V> Traverse<&'a mut Node<K, V>> for MutTraversal<'a, K, V> {
-    fn traverse(node: &'a mut Node<K, V>) -> MutTraversal<'a, K, V> {
-        node.iter_mut()
-    }
-}
+impl<'a, K, V> Iterator for Range<'a, K, V> {
+    type Item = (&'a K, &'a V);
 
-impl<K, V> Traverse<Node<K, V>> for MoveTraversal<K, V> {
-    fn traverse(node: Node<K, V>) -> MoveTraversal<K, V> {
-        node.into_iter()
+    fn next(&mut self) -> Option<(&'a K, &'a V)> {
+        if self.front == self.back {
+            None
+        } else {
+            unsafe { Some(self.next_unchecked()) }
+        }
     }
 }
 
-/// Represents an operation to perform inside the following iterator methods.
-/// This is necessary to use in `next` because we want to modify `self.traversals` inside
-/// a match that borrows it. Similarly in `next_back`. Instead, we use this enum to note
-/// what we want to do, and do it after the match.
-enum StackOp<T> {
-    Push(T),
-    Pop,
-}
-impl<K, V, E, T> Iterator for AbsIter<T>
-    where T: DoubleEndedIterator<Item = TraversalItem<K, V, E>> + Traverse<E>
-{
-    type Item = (K, V);
+impl<'a, K, V> Range<'a, K, V> {
+    unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
+        let handle = self.front;
 
-    // Our iterator represents a queue of all ancestors of elements we have
-    // yet to yield, from smallest to largest.  Note that the design of these
-    // iterators permits an *arbitrary* initial pair of min and max, making
-    // these arbitrary sub-range iterators.
-    fn next(&mut self) -> Option<(K, V)> {
-        loop {
-            // We want the smallest element, so try to get the back of the queue
-            let op = match self.traversals.back_mut() {
-                None => return None,
-                // The queue wasn't empty, so continue along the node in its head
-                Some(iter) => {
-                    match iter.next() {
-                        // The head is empty, so Pop it off and continue the process
-                        None => Pop,
-                        // The head yielded an edge, so make that the new head
-                        Some(Edge(next)) => Push(Traverse::traverse(next)),
-                        // The head yielded an entry, so yield that
-                        Some(Elem(kv)) => {
-                            self.size -= 1;
-                            return Some(kv);
-                        }
-                    }
-                }
-            };
+        let mut cur_handle = match handle.right_kv() {
+            Ok(kv) => {
+                let ret = kv.into_kv();
+                self.front = kv.right_edge();
+                return ret;
+            },
+            Err(last_edge) => {
+                let next_level = last_edge.into_node().ascend().ok();
+                unwrap_unchecked(next_level)
+            }
+        };
 
-            // Handle any operation as necessary, without a conflicting borrow of the queue
-            match op {
-                Push(item) => {
-                    self.traversals.push_back(item);
-                }
-                Pop => {
-                    self.traversals.pop_back();
+        loop {
+            match cur_handle.right_kv() {
+                Ok(kv) => {
+                    let ret = kv.into_kv();
+                    self.front = first_leaf_edge(kv.right_edge().descend());
+                    return ret;
+                },
+                Err(last_edge) => {
+                    let next_level = last_edge.into_node().ascend().ok();
+                    cur_handle = unwrap_unchecked(next_level);
                 }
             }
         }
     }
+}
 
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        (self.size, Some(self.size))
+impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
+    fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
+        if self.front == self.back {
+            None
+        } else {
+            unsafe { Some(self.next_back_unchecked()) }
+        }
     }
 }
 
-impl<K, V, E, T> DoubleEndedIterator for AbsIter<T>
-    where T: DoubleEndedIterator<Item = TraversalItem<K, V, E>> + Traverse<E>
-{
-    // next_back is totally symmetric to next
-    #[inline]
-    fn next_back(&mut self) -> Option<(K, V)> {
-        loop {
-            let op = match self.traversals.front_mut() {
-                None => return None,
-                Some(iter) => {
-                    match iter.next_back() {
-                        None => Pop,
-                        Some(Edge(next)) => Push(Traverse::traverse(next)),
-                        Some(Elem(kv)) => {
-                            self.size -= 1;
-                            return Some(kv);
-                        }
-                    }
-                }
-            };
+impl<'a, K, V> Range<'a, K, V> {
+    unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
+        let handle = self.back;
 
-            match op {
-                Push(item) => {
-                    self.traversals.push_front(item);
-                }
-                Pop => {
-                    self.traversals.pop_front();
+        let mut cur_handle = match handle.left_kv() {
+            Ok(kv) => {
+                let ret = kv.into_kv();
+                self.back = kv.left_edge();
+                return ret;
+            },
+            Err(last_edge) => {
+                let next_level = last_edge.into_node().ascend().ok();
+                unwrap_unchecked(next_level)
+            }
+        };
+
+        loop {
+            match cur_handle.left_kv() {
+                Ok(kv) => {
+                    let ret = kv.into_kv();
+                    self.back = last_leaf_edge(kv.left_edge().descend());
+                    return ret;
+                },
+                Err(last_edge) => {
+                    let next_level = last_edge.into_node().ascend().ok();
+                    cur_handle = unwrap_unchecked(next_level);
                 }
             }
         }
     }
 }
 
-impl<'a, K, V> Clone for Iter<'a, K, V> {
-    fn clone(&self) -> Iter<'a, K, V> {
-        Iter { inner: self.inner.clone() }
-    }
-}
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, K, V> Iterator for Iter<'a, K, V> {
-    type Item = (&'a K, &'a V);
-
-    fn next(&mut self) -> Option<(&'a K, &'a V)> {
-        self.inner.next()
-    }
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        self.inner.size_hint()
-    }
-}
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
-    fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
-        self.inner.next_back()
+impl<'a, K, V> Clone for Range<'a, K, V> {
+    fn clone(&self) -> Range<'a, K, V> {
+        Range {
+            front: self.front,
+            back: self.back
+        }
     }
 }
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {}
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, K, V> Iterator for IterMut<'a, K, V> {
+impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
     type Item = (&'a K, &'a mut V);
 
     fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
-        self.inner.next()
-    }
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        self.inner.size_hint()
-    }
-}
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
-    fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
-        self.inner.next_back()
+        if self.front == self.back {
+            None
+        } else {
+            unsafe { Some (self.next_unchecked()) }
+        }
     }
 }
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {}
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<K, V> Iterator for IntoIter<K, V> {
-    type Item = (K, V);
+impl<'a, K, V> RangeMut<'a, K, V> {
+    unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
+        let handle = ptr::read(&self.front);
 
-    fn next(&mut self) -> Option<(K, V)> {
-        self.inner.next()
-    }
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        self.inner.size_hint()
-    }
-}
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
-    fn next_back(&mut self) -> Option<(K, V)> {
-        self.inner.next_back()
-    }
-}
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<K, V> ExactSizeIterator for IntoIter<K, V> {}
+        let mut cur_handle = match handle.right_kv() {
+            Ok(kv) => {
+                let (k, v) = ptr::read(&kv).into_kv_mut();
+                self.front = kv.right_edge();
+                return (k, v);
+            },
+            Err(last_edge) => {
+                let next_level = last_edge.into_node().ascend().ok();
+                unwrap_unchecked(next_level)
+            }
+        };
 
-impl<'a, K, V> Clone for Keys<'a, K, V> {
-    fn clone(&self) -> Keys<'a, K, V> {
-        Keys { inner: self.inner.clone() }
+        loop {
+            match cur_handle.right_kv() {
+                Ok(kv) => {
+                    let (k, v) = ptr::read(&kv).into_kv_mut();
+                    self.front = first_leaf_edge(kv.right_edge().descend());
+                    return (k, v);
+                },
+                Err(last_edge) => {
+                    let next_level = last_edge.into_node().ascend().ok();
+                    cur_handle = unwrap_unchecked(next_level);
+                }
+            }
+        }
     }
 }
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, K, V> Iterator for Keys<'a, K, V> {
-    type Item = &'a K;
 
-    fn next(&mut self) -> Option<(&'a K)> {
-        self.inner.next()
-    }
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        self.inner.size_hint()
-    }
-}
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
-    fn next_back(&mut self) -> Option<(&'a K)> {
-        self.inner.next_back()
+impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
+    fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
+        if self.front == self.back {
+            None
+        } else {
+            unsafe { Some(self.next_back_unchecked()) }
+        }
     }
 }
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {}
 
+impl<'a, K, V> RangeMut<'a, K, V> {
+    unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
+        let handle = ptr::read(&self.back);
 
-impl<'a, K, V> Clone for Values<'a, K, V> {
-    fn clone(&self) -> Values<'a, K, V> {
-        Values { inner: self.inner.clone() }
-    }
-}
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, K, V> Iterator for Values<'a, K, V> {
-    type Item = &'a V;
+        let mut cur_handle = match handle.left_kv() {
+            Ok(kv) => {
+                let (k, v) = ptr::read(&kv).into_kv_mut();
+                self.back = kv.left_edge();
+                return (k, v);
+            },
+            Err(last_edge) => {
+                let next_level = last_edge.into_node().ascend().ok();
+                unwrap_unchecked(next_level)
+            }
+        };
 
-    fn next(&mut self) -> Option<(&'a V)> {
-        self.inner.next()
-    }
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        self.inner.size_hint()
+        loop {
+            match cur_handle.left_kv() {
+                Ok(kv) => {
+                    let (k, v) = ptr::read(&kv).into_kv_mut();
+                    self.back = last_leaf_edge(kv.left_edge().descend());
+                    return (k, v);
+                },
+                Err(last_edge) => {
+                    let next_level = last_edge.into_node().ascend().ok();
+                    cur_handle = unwrap_unchecked(next_level);
+                }
+            }
+        }
     }
 }
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
-    fn next_back(&mut self) -> Option<(&'a V)> {
-        self.inner.next_back()
+
+impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
+    fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> {
+        let mut map = BTreeMap::new();
+        map.extend(iter);
+        map
     }
 }
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {}
 
-impl<'a, K, V> Clone for Range<'a, K, V> {
-    fn clone(&self) -> Range<'a, K, V> {
-        Range { inner: self.inner.clone() }
+impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
+    #[inline]
+    fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
+        for (k, v) in iter {
+            self.insert(k, v);
+        }
     }
 }
-impl<'a, K, V> Iterator for Range<'a, K, V> {
-    type Item = (&'a K, &'a V);
 
-    fn next(&mut self) -> Option<(&'a K, &'a V)> {
-        self.inner.next()
+impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap<K, V> {
+    fn extend<I: IntoIterator<Item=(&'a K, &'a V)>>(&mut self, iter: I) {
+        self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
     }
 }
-impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
-    fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
-        self.inner.next_back()
+
+impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        for elt in self {
+            elt.hash(state);
+        }
     }
 }
 
-impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
-    type Item = (&'a K, &'a mut V);
-
-    fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
-        self.inner.next()
+impl<K: Ord, V> Default for BTreeMap<K, V> {
+    fn default() -> BTreeMap<K, V> {
+        BTreeMap::new()
     }
 }
-impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
-    fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
-        self.inner.next_back()
+
+impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
+    fn eq(&self, other: &BTreeMap<K, V>) -> bool {
+        self.len() == other.len() &&
+            self.iter().zip(other).all(|(a, b)| a == b)
     }
 }
 
-impl<'a, K: Ord, V> Entry<'a, K, V> {
-    #[stable(feature = "rust1", since = "1.0.0")]
-    /// Ensures a value is in the entry by inserting the default if empty, and returns
-    /// a mutable reference to the value in the entry.
-    pub fn or_insert(self, default: V) -> &'a mut V {
-        match self {
-            Occupied(entry) => entry.into_mut(),
-            Vacant(entry) => entry.insert(default),
-        }
-    }
+impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
 
-    #[stable(feature = "rust1", since = "1.0.0")]
-    /// Ensures a value is in the entry by inserting the result of the default function if empty,
-    /// and returns a mutable reference to the value in the entry.
-    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
-        match self {
-            Occupied(entry) => entry.into_mut(),
-            Vacant(entry) => entry.insert(default()),
-        }
+impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
+    #[inline]
+    fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
+        self.iter().partial_cmp(other.iter())
     }
 }
 
-impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
-    /// Sets the value of the entry with the VacantEntry's key,
-    /// and returns a mutable reference to it.
-    #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn insert(self, value: V) -> &'a mut V {
-        self.stack.insert(self.key, value)
+impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
+    #[inline]
+    fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
+        self.iter().cmp(other.iter())
     }
 }
 
-impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
-    /// Gets a reference to the value in the entry.
-    #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn get(&self) -> &V {
-        self.stack.peek()
+impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_map().entries(self.iter()).finish()
     }
+}
 
-    /// Gets a mutable reference to the value in the entry.
-    #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn get_mut(&mut self) -> &mut V {
-        self.stack.peek_mut()
-    }
+impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for BTreeMap<K, V>
+    where K: Borrow<Q>, Q: Ord
+{
+    type Output = V;
 
-    /// Converts the entry into a mutable reference to its value.
-    #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn into_mut(self) -> &'a mut V {
-        self.stack.into_top()
+    #[inline]
+    fn index(&self, key: &Q) -> &V {
+        self.get(key).expect("no entry found for key")
     }
+}
 
-    /// Sets the value of the entry with the OccupiedEntry's key,
-    /// and returns the entry's old value.
-    #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn insert(&mut self, mut value: V) -> V {
-        mem::swap(self.stack.peek_mut(), &mut value);
-        value
+fn first_leaf_edge<BorrowType, K, V>(
+        mut node: NodeRef<BorrowType,
+                          K, V,
+                          marker::LeafOrInternal>
+        ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
+    loop {
+        match node.force() {
+            Leaf(leaf) => return leaf.first_edge(),
+            Internal(internal) => {
+                node = internal.first_edge().descend();
+            }
+        }
     }
+}
 
-    /// Takes the value of the entry out of the map, and returns it.
-    #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn remove(self) -> V {
-        self.stack.remove().1
+fn last_leaf_edge<BorrowType, K, V>(
+        mut node: NodeRef<BorrowType,
+                          K, V,
+                          marker::LeafOrInternal>
+        ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
+    loop {
+        match node.force() {
+            Leaf(leaf) => return leaf.last_edge(),
+            Internal(internal) => {
+                node = internal.last_edge().descend();
+            }
+        }
     }
 }
 
+#[inline(always)]
+unsafe fn unwrap_unchecked<T>(val: Option<T>) -> T {
+    val.unwrap_or_else(|| {
+        if cfg!(debug_assertions) {
+            panic!("'unchecked' unwrap on None in BTreeMap");
+        } else {
+            intrinsics::unreachable();
+        }
+    })
+}
+
 impl<K, V> BTreeMap<K, V> {
     /// Gets an iterator over the entries of the map.
     ///
@@ -1312,15 +1199,12 @@ impl<K, V> BTreeMap<K, V> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn iter(&self) -> Iter<K, V> {
-        let len = self.len();
-        // NB. The initial capacity for ringbuf is large enough to avoid reallocs in many cases.
-        let mut lca = VecDeque::new();
-        lca.push_back(Traverse::traverse(&self.root));
         Iter {
-            inner: AbsIter {
-                traversals: lca,
-                size: len,
+            range: Range {
+                front: first_leaf_edge(self.root.as_ref()),
+                back: last_leaf_edge(self.root.as_ref())
             },
+            length: self.length
         }
     }
 
@@ -1345,14 +1229,14 @@ impl<K, V> BTreeMap<K, V> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn iter_mut(&mut self) -> IterMut<K, V> {
-        let len = self.len();
-        let mut lca = VecDeque::new();
-        lca.push_back(Traverse::traverse(&mut self.root));
+        let root1 = self.root.as_mut();
+        let root2 = unsafe { ptr::read(&root1) };
         IterMut {
-            inner: AbsIter {
-                traversals: lca,
-                size: len,
+            range: RangeMut {
+                front: first_leaf_edge(root1),
+                back: last_leaf_edge(root2),
             },
+            length: self.length
         }
     }
 
@@ -1372,12 +1256,7 @@ impl<K, V> BTreeMap<K, V> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
-        fn first<A, B>((a, _): (A, B)) -> A {
-            a
-        }
-        let first: fn((&'a K, &'a V)) -> &'a K = first; // coerce to fn pointer
-
-        Keys { inner: self.iter().map(first) }
+        Keys { inner: self.iter() }
     }
 
     /// Gets an iterator over the values of the map.
@@ -1396,12 +1275,7 @@ impl<K, V> BTreeMap<K, V> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn values<'a>(&'a self) -> Values<'a, K, V> {
-        fn second<A, B>((_, b): (A, B)) -> B {
-            b
-        }
-        let second: fn((&'a K, &'a V)) -> &'a V = second; // coerce to fn pointer
-
-        Values { inner: self.iter().map(second) }
+        Values { inner: self.iter() }
     }
 
     /// Returns the number of elements in the map.
@@ -1439,357 +1313,207 @@ impl<K, V> BTreeMap<K, V> {
     }
 }
 
-macro_rules! range_impl {
-    ($root:expr, $min:expr, $max:expr, $as_slices_internal:ident, $iter:ident, $Range:ident,
-                                       $edges:ident, [$($mutability:ident)*]) => (
-        {
-            // A deque that encodes two search paths containing (left-to-right):
-            // a series of truncated-from-the-left iterators, the LCA's doubly-truncated iterator,
-            // and a series of truncated-from-the-right iterators.
-            let mut traversals = VecDeque::new();
-            let (root, min, max) = ($root, $min, $max);
-
-            let mut leftmost = None;
-            let mut rightmost = None;
+impl<'a, K: Ord, V> Entry<'a, K, V> {
+    /// Ensures a value is in the entry by inserting the default if empty, and returns
+    /// a mutable reference to the value in the entry.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn or_insert(self, default: V) -> &'a mut V {
+        match self {
+            Occupied(entry) => entry.into_mut(),
+            Vacant(entry) => entry.insert(default),
+        }
+    }
 
-            match (&min, &max) {
-                (&Unbounded, &Unbounded) => {
-                    traversals.push_back(Traverse::traverse(root))
-                }
-                (&Unbounded, &Included(_)) | (&Unbounded, &Excluded(_)) => {
-                    rightmost = Some(root);
-                }
-                (&Included(_), &Unbounded) | (&Excluded(_), &Unbounded) => {
-                    leftmost = Some(root);
-                }
-                  (&Included(min_key), &Included(max_key))
-                | (&Included(min_key), &Excluded(max_key))
-                | (&Excluded(min_key), &Included(max_key))
-                | (&Excluded(min_key), &Excluded(max_key)) => {
-                    // lca represents the Lowest Common Ancestor, above which we never
-                    // walk, since everything else is outside the range to iterate.
-                    //       ___________________
-                    //      |__0_|_80_|_85_|_90_|  (root)
-                    //      |    |    |    |    |
-                    //           |
-                    //           v
-                    //  ___________________
-                    // |__5_|_15_|_30_|_73_|
-                    // |    |    |    |    |
-                    //                |
-                    //                v
-                    //       ___________________
-                    //      |_33_|_58_|_63_|_68_|  lca for the range [41, 65]
-                    //      |    |\___|___/|    |  iterator at traversals[2]
-                    //           |         |
-                    //           |         v
-                    //           v         rightmost
-                    //           leftmost
-                    let mut is_leaf = root.is_leaf();
-                    let mut lca = root.$as_slices_internal();
-                    loop {
-                        let slice = lca.slice_from(min_key).slice_to(max_key);
-                        if let [ref $($mutability)* edge] = slice.edges {
-                            // Follow the only edge that leads the node that covers the range.
-                            is_leaf = edge.is_leaf();
-                            lca = edge.$as_slices_internal();
-                        } else {
-                            let mut iter = slice.$iter();
-                            if is_leaf {
-                                leftmost = None;
-                                rightmost = None;
-                            } else {
-                                // Only change the state of nodes with edges.
-                                leftmost = iter.next_edge_item();
-                                rightmost = iter.next_edge_item_back();
-                            }
-                            traversals.push_back(iter);
-                            break;
-                        }
-                    }
-                }
-            }
-            // Keep narrowing the range by going down.
-            //               ___________________
-            //              |_38_|_43_|_48_|_53_|
-            //              |    |____|____|____/ iterator at traversals[1]
-            //                   |
-            //                   v
-            //  ___________________
-            // |_39_|_40_|_41_|_42_|  (leaf, the last leftmost)
-            //           \_________|  iterator at traversals[0]
-            match min {
-                Included(key) | Excluded(key) =>
-                    while let Some(left) = leftmost {
-                        let is_leaf = left.is_leaf();
-                        let mut iter = left.$as_slices_internal().slice_from(key).$iter();
-                        leftmost = if is_leaf {
-                            None
-                        } else {
-                            // Only change the state of nodes with edges.
-                            iter.next_edge_item()
-                        };
-                        traversals.push_back(iter);
-                    },
-                _ => {}
-            }
-            // If the leftmost iterator starts with an element, then it was an exact match.
-            if let (Excluded(_), Some(leftmost_iter)) = (min, traversals.back_mut()) {
-                // Drop this excluded element. `next_kv_item` has no effect when
-                // the next item is an edge.
-                leftmost_iter.next_kv_item();
-            }
+    /// Ensures a value is in the entry by inserting the result of the default function if empty,
+    /// and returns a mutable reference to the value in the entry.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
+        match self {
+            Occupied(entry) => entry.into_mut(),
+            Vacant(entry) => entry.insert(default()),
+        }
+    }
+}
 
-            // The code for the right side is similar.
-            match max {
-                Included(key) | Excluded(key) =>
-                    while let Some(right) = rightmost {
-                        let is_leaf = right.is_leaf();
-                        let mut iter = right.$as_slices_internal().slice_to(key).$iter();
-                        rightmost = if is_leaf {
-                            None
-                        } else {
-                            iter.next_edge_item_back()
-                        };
-                        traversals.push_front(iter);
-                    },
-                _ => {}
-            }
-            if let (Excluded(_), Some(rightmost_iter)) = (max, traversals.front_mut()) {
-                rightmost_iter.next_kv_item_back();
+impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
+    /// Sets the value of the entry with the VacantEntry's key,
+    /// and returns a mutable reference to it.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn insert(self, value: V) -> &'a mut V {
+        *self.length += 1;
+
+        let out_ptr;
+
+        let mut ins_k;
+        let mut ins_v;
+        let mut ins_edge;
+
+        let mut cur_parent = match self.handle.insert(self.key, value) {
+            (Fit(handle), _) => return handle.into_kv_mut().1,
+            (Split(left, k, v, right), ptr) => {
+                ins_k = k;
+                ins_v = v;
+                ins_edge = right;
+                out_ptr = ptr;
+                left.ascend().map_err(|n| n.into_root_mut())
             }
+        };
 
-            $Range {
-                inner: AbsIter {
-                    traversals: traversals,
-                    size: usize::MAX, // unused
+        loop {
+            match cur_parent {
+                Ok(parent) => match parent.insert(ins_k, ins_v, ins_edge) {
+                    Fit(_) => return unsafe { &mut *out_ptr },
+                    Split(left, k, v, right) => {
+                        ins_k = k;
+                        ins_v = v;
+                        ins_edge = right;
+                        cur_parent = left.ascend().map_err(|n| n.into_root_mut());
+                    }
+                },
+                Err(root) => {
+                    root.push_level().push(ins_k, ins_v, ins_edge);
+                    return unsafe { &mut *out_ptr };
                 }
             }
         }
-    )
+    }
 }
 
-impl<K: Ord, V> BTreeMap<K, V> {
-    /// Constructs a double-ended iterator over a sub-range of elements in the map, starting
-    /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
-    /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
-    /// Thus range(Unbounded, Unbounded) will yield the whole collection.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// #![feature(btree_range, collections_bound)]
-    ///
-    /// use std::collections::BTreeMap;
-    /// use std::collections::Bound::{Included, Unbounded};
-    ///
-    /// let mut map = BTreeMap::new();
-    /// map.insert(3, "a");
-    /// map.insert(5, "b");
-    /// map.insert(8, "c");
-    /// for (&key, &value) in map.range(Included(&4), Included(&8)) {
-    ///     println!("{}: {}", key, value);
-    /// }
-    /// assert_eq!(Some((&5, &"b")), map.range(Included(&4), Unbounded).next());
-    /// ```
-    #[unstable(feature = "btree_range",
-               reason = "matches collection reform specification, waiting for dust to settle",
-               issue = "27787")]
-    pub fn range<Min: ?Sized + Ord, Max: ?Sized + Ord>(&self,
-                                                       min: Bound<&Min>,
-                                                       max: Bound<&Max>)
-                                                       -> Range<K, V>
-        where K: Borrow<Min> + Borrow<Max>
-    {
-        range_impl!(&self.root,
-                    min,
-                    max,
-                    as_slices_internal,
-                    iter,
-                    Range,
-                    edges,
-                    [])
+impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
+    /// Gets a reference to the value in the entry.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn get(&self) -> &V {
+        self.handle.reborrow().into_kv().1
     }
 
-    /// Constructs a mutable double-ended iterator over a sub-range of elements in the map, starting
-    /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative
-    /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity".
-    /// Thus range(Unbounded, Unbounded) will yield the whole collection.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// #![feature(btree_range, collections_bound)]
-    ///
-    /// use std::collections::BTreeMap;
-    /// use std::collections::Bound::{Included, Excluded};
-    ///
-    /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter()
-    ///                                                                       .map(|&s| (s, 0))
-    ///                                                                       .collect();
-    /// for (_, balance) in map.range_mut(Included("B"), Excluded("Cheryl")) {
-    ///     *balance += 100;
-    /// }
-    /// for (name, balance) in &map {
-    ///     println!("{} => {}", name, balance);
-    /// }
-    /// ```
-    #[unstable(feature = "btree_range",
-               reason = "matches collection reform specification, waiting for dust to settle",
-               issue = "27787")]
-    pub fn range_mut<Min: ?Sized + Ord, Max: ?Sized + Ord>(&mut self,
-                                                           min: Bound<&Min>,
-                                                           max: Bound<&Max>)
-                                                           -> RangeMut<K, V>
-        where K: Borrow<Min> + Borrow<Max>
-    {
-        range_impl!(&mut self.root,
-                    min,
-                    max,
-                    as_slices_internal_mut,
-                    iter_mut,
-                    RangeMut,
-                    edges_mut,
-                    [mut])
+    /// Gets a mutable reference to the value in the entry.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn get_mut(&mut self) -> &mut V {
+        self.handle.kv_mut().1
     }
 
-    /// Gets the given key's corresponding entry in the map for in-place manipulation.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// use std::collections::BTreeMap;
-    ///
-    /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
-    ///
-    /// // 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);
-    /// ```
+    /// Converts the entry into a mutable reference to its value.
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn entry(&mut self, mut key: K) -> Entry<K, V> {
-        // same basic logic of `swap` and `pop`, blended together
-        let mut stack = stack::PartialSearchStack::new(self);
-        loop {
-            let result = stack.with(move |pusher, node| {
-                match Node::search(node, &key) {
-                    Found(handle) => {
-                        // Perfect match
-                        Finished(Occupied(OccupiedEntry { stack: pusher.seal(handle) }))
-                    }
-                    GoDown(handle) => {
-                        match handle.force() {
-                            Leaf(leaf_handle) => {
-                                Finished(Vacant(VacantEntry {
-                                    stack: pusher.seal(leaf_handle),
-                                    key: key,
-                                }))
-                            }
-                            Internal(internal_handle) => {
-                                Continue((pusher.push(internal_handle), key))
-                            }
-                        }
-                    }
-                }
-            });
-            match result {
-                Finished(finished) => return finished,
-                Continue((new_stack, renewed_key)) => {
-                    stack = new_stack;
-                    key = renewed_key;
-                }
-            }
-        }
+    pub fn into_mut(self) -> &'a mut V {
+        self.handle.into_kv_mut().1
     }
-}
 
-impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
-    where K: Borrow<Q> + Ord,
-          Q: Ord
-{
-    type Key = K;
+    /// Sets the value of the entry with the OccupiedEntry's key,
+    /// and returns the entry's old value.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn insert(&mut self, value: V) -> V {
+        mem::replace(self.get_mut(), value)
+    }
 
-    fn get(&self, key: &Q) -> Option<&K> {
-        let mut cur_node = &self.root;
-        loop {
-            match Node::search(cur_node, key) {
-                Found(handle) => return Some(handle.into_kv().0),
-                GoDown(handle) => {
-                    match handle.force() {
-                        Leaf(_) => return None,
-                        Internal(internal_handle) => {
-                            cur_node = internal_handle.into_edge();
-                            continue;
-                        }
-                    }
-                }
-            }
-        }
+    /// Takes the value of the entry out of the map, and returns it.
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn remove(self) -> V {
+        self.remove_kv().1
     }
 
-    fn take(&mut self, key: &Q) -> Option<K> {
-        // See `remove` for an explanation of this.
+    fn remove_kv(self) -> (K, V) {
+        *self.length -= 1;
 
-        let mut stack = stack::PartialSearchStack::new(self);
-        loop {
-            let result = stack.with(move |pusher, node| {
-                match Node::search(node, key) {
-                    Found(handle) => {
-                        // Perfect match. Terminate the stack here, and remove the entry
-                        Finished(Some(pusher.seal(handle).remove()))
-                    }
-                    GoDown(handle) => {
-                        // We need to keep searching, try to go down the next edge
-                        match handle.force() {
-                            // We're at a leaf; the key isn't in here
-                            Leaf(_) => Finished(None),
-                            Internal(internal_handle) => Continue(pusher.push(internal_handle)),
-                        }
-                    }
-                }
-            });
-            match result {
-                Finished(ret) => return ret.map(|(k, _)| k),
-                Continue(new_stack) => stack = new_stack,
+        let (small_leaf, old_key, old_val) = match self.handle.force() {
+            Leaf(leaf) => {
+                let (hole, old_key, old_val) = leaf.remove();
+                (hole.into_node(), old_key, old_val)
+            },
+            Internal(mut internal) => {
+                let key_loc = internal.kv_mut().0 as *mut K;
+                let val_loc = internal.kv_mut().1 as *mut V;
+
+                let to_remove = first_leaf_edge(internal.right_edge().descend()).right_kv().ok();
+                let to_remove = unsafe { unwrap_unchecked(to_remove) };
+
+                let (hole, key, val) = to_remove.remove();
+
+                let old_key = unsafe {
+                    mem::replace(&mut *key_loc, key)
+                };
+                let old_val = unsafe {
+                    mem::replace(&mut *val_loc, val)
+                };
+
+                (hole.into_node(), old_key, old_val)
+            }
+        };
+
+        // Handle underflow
+        let mut cur_node = small_leaf.forget_type();
+        while cur_node.len() < node::CAPACITY / 2 {
+            match handle_underfull_node(cur_node) {
+                AtRoot => break,
+                EmptyParent(_) => unreachable!(),
+                Merged(parent) => if parent.len() == 0 {
+                    // We must be at the root
+                    parent.into_root_mut().pop_level();
+                    break;
+                } else {
+                    cur_node = parent.forget_type();
+                },
+                Stole(_) => break
             }
         }
+
+        (old_key, old_val)
     }
+}
 
-    fn replace(&mut self, mut key: K) -> Option<K> {
-        // See `insert` for an explanation of this.
+enum UnderflowResult<'a, K, V> {
+    AtRoot,
+    EmptyParent(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
+    Merged(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
+    Stole(NodeRef<marker::Mut<'a>, K, V, marker::Internal>)
+}
 
-        let mut stack = stack::PartialSearchStack::new(self);
+fn handle_underfull_node<'a, K, V>(node: NodeRef<marker::Mut<'a>,
+                                                 K, V,
+                                                 marker::LeafOrInternal>)
+                                                 -> UnderflowResult<'a, K, V> {
+    let parent = if let Ok(parent) = node.ascend() {
+        parent
+    } else {
+        return AtRoot;
+    };
+
+    let (is_left, mut handle) = match parent.left_kv() {
+        Ok(left) => (true, left),
+        Err(parent) => match parent.right_kv() {
+            Ok(right) => (false, right),
+            Err(parent) => {
+                return EmptyParent(parent.into_node());
+            }
+        }
+    };
+
+    if handle.can_merge() {
+        return Merged(handle.merge().into_node());
+    } else {
+        unsafe {
+            let (k, v, edge) = if is_left {
+                handle.reborrow_mut().left_edge().descend().pop()
+            } else {
+                handle.reborrow_mut().right_edge().descend().pop_front()
+            };
 
-        loop {
-            let result = stack.with(move |pusher, node| {
-                match Node::search::<K, _>(node, &key) {
-                    Found(mut handle) => {
-                        mem::swap(handle.key_mut(), &mut key);
-                        Finished(Some(key))
-                    }
-                    GoDown(handle) => {
-                        match handle.force() {
-                            Leaf(leaf_handle) => {
-                                pusher.seal(leaf_handle).insert(key, ());
-                                Finished(None)
-                            }
-                            Internal(internal_handle) => {
-                                Continue((pusher.push(internal_handle), key, ()))
-                            }
-                        }
-                    }
+            let k = mem::replace(handle.reborrow_mut().into_kv_mut().0, k);
+            let v = mem::replace(handle.reborrow_mut().into_kv_mut().1, v);
+
+            // FIXME: reuse cur_node?
+            if is_left {
+                match handle.reborrow_mut().right_edge().descend().force() {
+                    Leaf(mut leaf) => leaf.push_front(k, v),
+                    Internal(mut internal) => internal.push_front(k, v, edge.unwrap())
                 }
-            });
-            match result {
-                Finished(ret) => return ret,
-                Continue((new_stack, renewed_key, _)) => {
-                    stack = new_stack;
-                    key = renewed_key;
+            } else {
+                match handle.reborrow_mut().left_edge().descend().force() {
+                    Leaf(mut leaf) => leaf.push(k, v),
+                    Internal(mut internal) => internal.push(k, v, edge.unwrap())
                 }
             }
         }
+
+        return Stole(handle.into_node());
     }
 }
diff --git a/src/libcollections/btree/mod.rs b/src/libcollections/btree/mod.rs
index d424cb7e29d..087c9f228d4 100644
--- a/src/libcollections/btree/mod.rs
+++ b/src/libcollections/btree/mod.rs
@@ -9,6 +9,7 @@
 // except according to those terms.
 
 mod node;
+mod search;
 pub mod map;
 pub mod set;
 
diff --git a/src/libcollections/btree/node.rs b/src/libcollections/btree/node.rs
index e55b1597a21..2e2a39df347 100644
--- a/src/libcollections/btree/node.rs
+++ b/src/libcollections/btree/node.rs
@@ -8,1632 +8,1120 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-// This module represents all the internal representation and logic for a B-Tree's node
-// with a safe interface, so that BTreeMap itself does not depend on any of these details.
-
-pub use self::InsertionResult::*;
-pub use self::SearchResult::*;
-pub use self::ForceResult::*;
-pub use self::TraversalItem::*;
+// This is an attempt at an implementation following the ideal
+//
+// ```
+// struct BTreeMap<K, V> {
+//     height: usize,
+//     root: Option<Box<Node<K, V, height>>>
+// }
+//
+// struct Node<K, V, height: usize> {
+//     keys: [K; 2 * B - 1],
+//     vals: [V; 2 * B - 1],
+//     edges: if height > 0 {
+//         [Box<Node<K, V, height - 1>>; 2 * B]
+//     } else { () },
+//     parent: *const Node<K, V, height + 1>,
+//     parent_idx: u16,
+//     len: u16,
+// }
+// ```
+//
+// Since Rust doesn't acutally have dependent types and polymorphic recursion,
+// we make do with lots of unsafety.
 
-use core::cmp::Ordering::{Greater, Less, Equal};
-use core::intrinsics::arith_offset;
-use core::iter::Zip;
-use core::marker::PhantomData;
-use core::ops::{Deref, DerefMut, Index, IndexMut};
-use core::ptr::Unique;
-use core::{slice, mem, ptr, cmp};
 use alloc::heap;
-
-use borrow::Borrow;
-
-/// Represents the result of an Insertion: either the item fit, or the node had to split
-pub enum InsertionResult<K, V> {
-    /// The inserted element fit
-    Fit,
-    /// The inserted element did not fit, so the node was split
-    Split(K, V, Node<K, V>),
-}
-
-/// Represents the result of a search for a key in a single node
-pub enum SearchResult<NodeRef> {
-    /// The element was found at the given index
-    Found(Handle<NodeRef, handle::KV, handle::LeafOrInternal>),
-    /// The element wasn't found, but if it's anywhere, it must be beyond this edge
-    GoDown(Handle<NodeRef, handle::Edge, handle::LeafOrInternal>),
-}
-
-/// A B-Tree Node. We keep keys/edges/values separate to optimize searching for keys.
-#[unsafe_no_drop_flag]
-pub struct Node<K, V> {
-    // To avoid the need for multiple allocations, we allocate a single buffer with enough space
-    // for `capacity` keys, `capacity` values, and (in internal nodes) `capacity + 1` edges.
-    // Despite this, we store three separate pointers to the three "chunks" of the buffer because
-    // the performance drops significantly if the locations of the vals and edges need to be
-    // recalculated upon access.
-    //
-    // These will never be null during normal usage of a `Node`. However, to avoid the need for a
-    // drop flag, `Node::drop` zeroes `keys`, signaling that the `Node` has already been cleaned
-    // up.
-    keys: Unique<K>,
-    vals: Unique<V>,
-
-    // In leaf nodes, this will be None, and no space will be allocated for edges.
-    edges: Option<Unique<Node<K, V>>>,
-
-    // At any given time, there will be `_len` keys, `_len` values, and (in an internal node)
-    // `_len + 1` edges. In a leaf node, there will never be any edges.
-    //
-    // Note: instead of accessing this field directly, please call the `len()` method, which should
-    // be more stable in the face of representation changes.
-    _len: usize,
-
-    // FIXME(gereeter) It shouldn't be necessary to store the capacity in every node, as it should
-    // be constant throughout the tree. Once a solution to this is found, it might be possible to
-    // also pass down the offsets into the buffer that vals and edges are stored at, removing the
-    // need for those two pointers.
-    //
-    // Note: instead of accessing this field directly, please call the `capacity()` method, which
-    // should be more stable in the face of representation changes.
-    _capacity: usize,
-}
-
-pub struct NodeSlice<'a, K: 'a, V: 'a> {
-    keys: &'a [K],
-    vals: &'a [V],
-    pub edges: &'a [Node<K, V>],
-    head_is_edge: bool,
-    tail_is_edge: bool,
-    has_edges: bool,
-}
-
-pub struct MutNodeSlice<'a, K: 'a, V: 'a> {
-    keys: &'a [K],
-    vals: &'a mut [V],
-    pub edges: &'a mut [Node<K, V>],
-    head_is_edge: bool,
-    tail_is_edge: bool,
-    has_edges: bool,
-}
-
-/// Rounds up to a multiple of a power of two. Returns the closest multiple
-/// of `target_alignment` that is higher or equal to `unrounded`.
-///
-/// # Panics
-///
-/// Fails if `target_alignment` is not a power of two.
-#[inline]
-fn round_up_to_next(unrounded: usize, target_alignment: usize) -> usize {
-    assert!(target_alignment.is_power_of_two());
-    (unrounded + target_alignment - 1) & !(target_alignment - 1)
-}
-
-#[test]
-fn test_rounding() {
-    assert_eq!(round_up_to_next(0, 4), 0);
-    assert_eq!(round_up_to_next(1, 4), 4);
-    assert_eq!(round_up_to_next(2, 4), 4);
-    assert_eq!(round_up_to_next(3, 4), 4);
-    assert_eq!(round_up_to_next(4, 4), 4);
-    assert_eq!(round_up_to_next(5, 4), 8);
-}
-
-// Returns a tuple of (val_offset, edge_offset),
-// from the start of a mallocated array.
-#[inline]
-fn calculate_offsets(keys_size: usize,
-                     vals_size: usize,
-                     vals_align: usize,
-                     edges_align: usize)
-                     -> (usize, usize) {
-    let vals_offset = round_up_to_next(keys_size, vals_align);
-    let end_of_vals = vals_offset + vals_size;
-
-    let edges_offset = round_up_to_next(end_of_vals, edges_align);
-
-    (vals_offset, edges_offset)
-}
-
-// Returns a tuple of (minimum required alignment, array_size),
-// from the start of a mallocated array.
-#[inline]
-fn calculate_allocation(keys_size: usize,
-                        keys_align: usize,
-                        vals_size: usize,
-                        vals_align: usize,
-                        edges_size: usize,
-                        edges_align: usize)
-                        -> (usize, usize) {
-    let (_, edges_offset) = calculate_offsets(keys_size, vals_size, vals_align, edges_align);
-    let end_of_edges = edges_offset + edges_size;
-
-    let min_align = cmp::max(keys_align, cmp::max(vals_align, edges_align));
-
-    (min_align, end_of_edges)
-}
-
-#[test]
-fn test_offset_calculation() {
-    assert_eq!(calculate_allocation(128, 8, 15, 1, 4, 4), (8, 148));
-    assert_eq!(calculate_allocation(3, 1, 2, 1, 1, 1), (1, 6));
-    assert_eq!(calculate_allocation(6, 2, 12, 4, 24, 8), (8, 48));
-    assert_eq!(calculate_offsets(128, 15, 1, 4), (128, 144));
-    assert_eq!(calculate_offsets(3, 2, 1, 1), (3, 5));
-    assert_eq!(calculate_offsets(6, 12, 4, 8), (8, 24));
+use core::marker::PhantomData;
+use core::mem;
+use core::nonzero::NonZero;
+use core::ptr::{self, Unique};
+use core::slice;
+
+use boxed::Box;
+
+const B: usize = 6;
+pub const CAPACITY: usize = 2 * B - 1;
+
+struct LeafNode<K, V> {
+    keys: [K; CAPACITY],
+    vals: [V; CAPACITY],
+    parent: *const InternalNode<K, V>,
+    parent_idx: u16,
+    len: u16,
 }
 
-fn calculate_allocation_generic<K, V>(capacity: usize, is_leaf: bool) -> (usize, usize) {
-    let (keys_size, keys_align) = (capacity * mem::size_of::<K>(), mem::align_of::<K>());
-    let (vals_size, vals_align) = (capacity * mem::size_of::<V>(), mem::align_of::<V>());
-    let (edges_size, edges_align) = if is_leaf {
-        // allocate one edge to ensure that we don't pass size 0 to `heap::allocate`
-        if mem::size_of::<K>() == 0 && mem::size_of::<V>() == 0 {
-            (1, mem::align_of::<Node<K, V>>())
-        } else {
-            (0, 1)
+impl<K, V> LeafNode<K, V> {
+    unsafe fn new() -> Self {
+        LeafNode {
+            keys: mem::uninitialized(),
+            vals: mem::uninitialized(),
+            parent: ptr::null(),
+            parent_idx: mem::uninitialized(),
+            len: 0
         }
-    } else {
-        ((capacity + 1) * mem::size_of::<Node<K, V>>(),
-         mem::align_of::<Node<K, V>>())
-    };
-
-    calculate_allocation(keys_size,
-                         keys_align,
-                         vals_size,
-                         vals_align,
-                         edges_size,
-                         edges_align)
-}
-
-fn calculate_offsets_generic<K, V>(capacity: usize, is_leaf: bool) -> (usize, usize) {
-    let keys_size = capacity * mem::size_of::<K>();
-    let vals_size = capacity * mem::size_of::<V>();
-    let vals_align = mem::align_of::<V>();
-    let edges_align = if is_leaf {
-        1
-    } else {
-        mem::align_of::<Node<K, V>>()
-    };
-
-    calculate_offsets(keys_size, vals_size, vals_align, edges_align)
+    }
 }
 
-/// An iterator over a slice that owns the elements of the slice but not the allocation.
-struct RawItems<T> {
-    head: *const T,
-    tail: *const T,
+// We use repr(C) so that a pointer to an internal node can be
+// directly used as a pointer to a leaf node
+#[repr(C)]
+struct InternalNode<K, V> {
+    data: LeafNode<K, V>,
+    edges: [BoxedNode<K, V>; 2 * B],
 }
 
-impl<T> RawItems<T> {
-    unsafe fn from_slice(slice: &[T]) -> RawItems<T> {
-        RawItems::from_parts(slice.as_ptr(), slice.len())
-    }
-
-    unsafe fn from_parts(ptr: *const T, len: usize) -> RawItems<T> {
-        if mem::size_of::<T>() == 0 {
-            RawItems {
-                head: ptr,
-                tail: arith_offset(ptr as *const i8, len as isize) as *const T,
-            }
-        } else {
-            RawItems {
-                head: ptr,
-                tail: ptr.offset(len as isize),
-            }
-        }
-    }
-
-    unsafe fn push(&mut self, val: T) {
-        ptr::write(self.tail as *mut T, val);
-
-        if mem::size_of::<T>() == 0 {
-            self.tail = arith_offset(self.tail as *const i8, 1) as *const T;
-        } else {
-            self.tail = self.tail.offset(1);
+impl<K, V> InternalNode<K, V> {
+    unsafe fn new() -> Self {
+        InternalNode {
+            data: LeafNode::new(),
+            edges: mem::uninitialized()
         }
     }
 }
 
-impl<T> Iterator for RawItems<T> {
-    type Item = T;
-
-    fn next(&mut self) -> Option<T> {
-        if self.head == self.tail {
-            None
-        } else {
-            unsafe {
-                let ret = Some(ptr::read(self.head));
-
-                if mem::size_of::<T>() == 0 {
-                    self.head = arith_offset(self.head as *const i8, 1) as *const T;
-                } else {
-                    self.head = self.head.offset(1);
-                }
+struct BoxedNode<K, V> {
+    ptr: Unique<LeafNode<K, V>> // we don't know if this points to a leaf node or an internal node
+}
 
-                ret
-            }
+impl<K, V> BoxedNode<K, V> {
+    fn from_leaf(node: Box<LeafNode<K, V>>) -> Self {
+        unsafe {
+            BoxedNode { ptr: Unique::new(Box::into_raw(node)) }
         }
     }
-}
-
-impl<T> DoubleEndedIterator for RawItems<T> {
-    fn next_back(&mut self) -> Option<T> {
-        if self.head == self.tail {
-            None
-        } else {
-            unsafe {
-                if mem::size_of::<T>() == 0 {
-                    self.tail = arith_offset(self.tail as *const i8, -1) as *const T;
-                } else {
-                    self.tail = self.tail.offset(-1);
-                }
 
-                Some(ptr::read(self.tail))
-            }
+    fn from_internal(node: Box<InternalNode<K, V>>) -> Self {
+        unsafe {
+            BoxedNode { ptr: Unique::new(Box::into_raw(node) as *mut LeafNode<K, V>) }
         }
     }
-}
 
-impl<T> Drop for RawItems<T> {
-    #[unsafe_destructor_blind_to_params]
-    fn drop(&mut self) {
-        for _ in self {}
+    unsafe fn from_ptr(ptr: NonZero<*mut LeafNode<K, V>>) -> Self {
+        BoxedNode { ptr: Unique::new(*ptr) }
     }
-}
 
-impl<K, V> Drop for Node<K, V> {
-    #[unsafe_destructor_blind_to_params]
-    fn drop(&mut self) {
-        if self.keys.is_null() ||
-           (unsafe { self.keys.get() as *const K as usize == mem::POST_DROP_USIZE }) {
-            // Since we have #[unsafe_no_drop_flag], we have to watch
-            // out for the sentinel value being stored in self.keys. (Using
-            // null is technically a violation of the `Unique`
-            // requirements, though.)
-            return;
-        }
-
-        // Do the actual cleanup.
+    fn as_ptr(&self) -> NonZero<*mut LeafNode<K, V>> {
         unsafe {
-            drop(RawItems::from_slice(self.keys()));
-            drop(RawItems::from_slice(self.vals()));
-            drop(RawItems::from_slice(self.edges()));
-
-            self.destroy();
+            NonZero::new(*self.ptr)
         }
-
-        self.keys = unsafe { Unique::new(ptr::null_mut()) };
     }
 }
 
-impl<K, V> Node<K, V> {
-    /// Make a new internal node. The caller must initialize the result to fix the invariant that
-    /// there are `len() + 1` edges.
-    unsafe fn new_internal(capacity: usize) -> Node<K, V> {
-        let (alignment, size) = calculate_allocation_generic::<K, V>(capacity, false);
-
-        let buffer = heap::allocate(size, alignment);
-        if buffer.is_null() {
-            ::alloc::oom();
-        }
+/// An owned tree. Note that despite being owned, this does not have a destructor,
+/// and must be cleaned up manually.
+pub struct Root<K, V> {
+    node: BoxedNode<K, V>,
+    height: usize
+}
 
-        let (vals_offset, edges_offset) = calculate_offsets_generic::<K, V>(capacity, false);
+unsafe impl<K: Sync, V: Sync> Sync for Root<K, V> { }
+unsafe impl<K: Send, V: Send> Send for Root<K, V> { }
 
-        Node {
-            keys: Unique::new(buffer as *mut K),
-            vals: Unique::new(buffer.offset(vals_offset as isize) as *mut V),
-            edges: Some(Unique::new(buffer.offset(edges_offset as isize) as *mut Node<K, V>)),
-            _len: 0,
-            _capacity: capacity,
+impl<K, V> Root<K, V> {
+    pub fn new_leaf() -> Self {
+        Root {
+            node: BoxedNode::from_leaf(Box::new(unsafe { LeafNode::new() })),
+            height: 0
         }
     }
 
-    /// Make a new leaf node
-    fn new_leaf(capacity: usize) -> Node<K, V> {
-        let (alignment, size) = calculate_allocation_generic::<K, V>(capacity, true);
-
-        let buffer = unsafe { heap::allocate(size, alignment) };
-        if buffer.is_null() {
-            ::alloc::oom();
-        }
-
-        let (vals_offset, _) = calculate_offsets_generic::<K, V>(capacity, true);
-
-        Node {
-            keys: unsafe { Unique::new(buffer as *mut K) },
-            vals: unsafe { Unique::new(buffer.offset(vals_offset as isize) as *mut V) },
-            edges: None,
-            _len: 0,
-            _capacity: capacity,
+    pub fn as_ref(&self)
+            -> NodeRef<marker::Immut, K, V, marker::LeafOrInternal> {
+        NodeRef {
+            height: self.height,
+            node: self.node.as_ptr(),
+            root: self as *const _ as *mut _,
+            _marker: PhantomData,
         }
     }
 
-    unsafe fn destroy(&mut self) {
-        let (alignment, size) = calculate_allocation_generic::<K, V>(self.capacity(),
-                                                                     self.is_leaf());
-        heap::deallocate(*self.keys as *mut u8, size, alignment);
-    }
-
-    #[inline]
-    pub fn as_slices<'a>(&'a self) -> (&'a [K], &'a [V]) {
-        unsafe {
-            (slice::from_raw_parts(*self.keys, self.len()),
-             slice::from_raw_parts(*self.vals, self.len()))
+    pub fn as_mut(&mut self)
+            -> NodeRef<marker::Mut, K, V, marker::LeafOrInternal> {
+        NodeRef {
+            height: self.height,
+            node: self.node.as_ptr(),
+            root: self as *mut _,
+            _marker: PhantomData,
         }
     }
 
-    #[inline]
-    pub fn as_slices_mut<'a>(&'a mut self) -> (&'a mut [K], &'a mut [V]) {
-        unsafe {
-            (slice::from_raw_parts_mut(*self.keys, self.len()),
-             slice::from_raw_parts_mut(*self.vals, self.len()))
+    pub fn into_ref(self)
+            -> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
+        NodeRef {
+            height: self.height,
+            node: self.node.as_ptr(),
+            root: ptr::null_mut(), // FIXME: Is there anything better to do here?
+            _marker: PhantomData,
         }
     }
 
-    #[inline]
-    pub fn as_slices_internal<'b>(&'b self) -> NodeSlice<'b, K, V> {
-        let is_leaf = self.is_leaf();
-        let (keys, vals) = self.as_slices();
-        let edges: &[_] = if self.is_leaf() {
-            &[]
-        } else {
-            unsafe {
-                let data = match self.edges {
-                    None => heap::EMPTY as *const Node<K, V>,
-                    Some(ref p) => **p as *const Node<K, V>,
-                };
-                slice::from_raw_parts(data, self.len() + 1)
-            }
-        };
-        NodeSlice {
-            keys: keys,
-            vals: vals,
-            edges: edges,
-            head_is_edge: true,
-            tail_is_edge: true,
-            has_edges: !is_leaf,
-        }
-    }
+    /// Add a new internal 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`.
+    pub fn push_level(&mut self)
+            -> NodeRef<marker::Mut, K, V, marker::Internal> {
+        let mut new_node = Box::new(unsafe { InternalNode::new() });
+        new_node.edges[0] = unsafe { BoxedNode::from_ptr(self.node.as_ptr()) };
 
-    #[inline]
-    pub fn as_slices_internal_mut<'b>(&'b mut self) -> MutNodeSlice<'b, K, V> {
-        let len = self.len();
-        let is_leaf = self.is_leaf();
-        let keys = unsafe { slice::from_raw_parts_mut(*self.keys, len) };
-        let vals = unsafe { slice::from_raw_parts_mut(*self.vals, len) };
-        let edges: &mut [_] = if is_leaf {
-            &mut []
-        } else {
-            unsafe {
-                let data = match self.edges {
-                    None => heap::EMPTY as *mut Node<K, V>,
-                    Some(ref mut p) => **p as *mut Node<K, V>,
-                };
-                slice::from_raw_parts_mut(data, len + 1)
-            }
-        };
-        MutNodeSlice {
-            keys: keys,
-            vals: vals,
-            edges: edges,
-            head_is_edge: true,
-            tail_is_edge: true,
-            has_edges: !is_leaf,
-        }
-    }
+        self.node = BoxedNode::from_internal(new_node);
+        self.height += 1;
 
-    #[inline]
-    pub fn keys<'a>(&'a self) -> &'a [K] {
-        self.as_slices().0
-    }
+        let mut ret = NodeRef {
+            height: self.height,
+            node: self.node.as_ptr(),
+            root: self as *mut _,
+            _marker: PhantomData
+        };
 
-    #[inline]
-    pub fn keys_mut<'a>(&'a mut self) -> &'a mut [K] {
-        self.as_slices_mut().0
-    }
+        unsafe {
+            ret.reborrow_mut().first_edge().correct_parent_link();
+        }
 
-    #[inline]
-    pub fn vals<'a>(&'a self) -> &'a [V] {
-        self.as_slices().1
+        ret
     }
 
-    #[inline]
-    pub fn vals_mut<'a>(&'a mut self) -> &'a mut [V] {
-        self.as_slices_mut().1
-    }
+    /// Remove 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`.
+    pub fn pop_level(&mut self) {
+        debug_assert!(self.height > 0);
 
-    #[inline]
-    pub fn edges<'a>(&'a self) -> &'a [Node<K, V>] {
-        self.as_slices_internal().edges
-    }
+        let top = *self.node.ptr as *mut u8;
 
-    #[inline]
-    pub fn edges_mut<'a>(&'a mut self) -> &'a mut [Node<K, V>] {
-        self.as_slices_internal_mut().edges
-    }
-}
-
-// FIXME(gereeter) Write an efficient clone_from
-impl<K: Clone, V: Clone> Clone for Node<K, V> {
-    fn clone(&self) -> Node<K, V> {
-        let mut ret = if self.is_leaf() {
-            Node::new_leaf(self.capacity())
-        } else {
-            unsafe { Node::new_internal(self.capacity()) }
+        self.node = unsafe {
+            BoxedNode::from_ptr(self.as_mut()
+                                    .cast_unchecked::<marker::Internal>()
+                                    .first_edge()
+                                    .descend()
+                                    .node)
         };
+        self.height -= 1;
+        self.as_mut().as_leaf_mut().parent = ptr::null();
 
         unsafe {
-            // For failure safety
-            let mut keys = RawItems::from_parts(ret.keys().as_ptr(), 0);
-            let mut vals = RawItems::from_parts(ret.vals().as_ptr(), 0);
-            let mut edges = RawItems::from_parts(ret.edges().as_ptr(), 0);
-
-            for key in self.keys() {
-                keys.push(key.clone())
-            }
-            for val in self.vals() {
-                vals.push(val.clone())
-            }
-            for edge in self.edges() {
-                edges.push(edge.clone())
-            }
-
-            mem::forget(keys);
-            mem::forget(vals);
-            mem::forget(edges);
-
-            ret._len = self.len();
+            heap::deallocate(
+                top,
+                mem::size_of::<InternalNode<K, V>>(),
+                mem::align_of::<InternalNode<K, V>>()
+            );
         }
-
-        ret
     }
 }
 
-/// A reference to something in the middle of a `Node`. There are two `Type`s of `Handle`s,
-/// namely `KV` handles, which point to key/value pairs, and `Edge` handles, which point to edges
-/// before or after key/value pairs. Methods are provided for removing pairs, inserting into edges,
-/// accessing the stored values, and moving around the `Node`.
-///
-/// This handle is generic, and can take any sort of reference to a `Node`. The reason for this is
-/// two-fold. First of all, it reduces the amount of repetitive code, implementing functions that
-/// don't need mutability on both mutable and immutable references. Secondly and more importantly,
-/// this allows users of the `Handle` API to associate metadata with the reference. This is used in
-/// `BTreeMap` to give `Node`s temporary "IDs" that persist to when the `Node` is used in a
-/// `Handle`.
+/// A reference to a node.
 ///
-/// # A note on safety
-///
-/// Unfortunately, the extra power afforded by being generic also means that safety can technically
-/// be broken. For sensible implementations of `Deref` and `DerefMut`, these handles are perfectly
-/// safe. As long as repeatedly calling `.deref()` results in the same Node being returned each
-/// time, everything should work fine. However, if the `Deref` implementation swaps in multiple
-/// different nodes, then the indices that are assumed to be in bounds suddenly stop being so. For
-/// example:
-///
-/// ```rust,ignore
-/// struct Nasty<'a> {
-///     first: &'a Node<usize, usize>,
-///     second: &'a Node<usize, usize>,
-///     flag: &'a Cell<bool>,
-/// }
-///
-/// impl<'a> Deref for Nasty<'a> {
-///     type Target = Node<usize, usize>;
-///
-///     fn deref(&self) -> &Node<usize, usize> {
-///         if self.flag.get() {
-///             &*self.second
-///         } else {
-///             &*self.first
-///         }
-///     }
-/// }
-///
-/// fn main() {
-///     let flag = Cell::new(false);
-///     let mut small_node = Node::make_leaf_root(3);
-///     let mut large_node = Node::make_leaf_root(100);
-///
-///     for i in 0..100 {
-///         // Insert to the end
-///         large_node.edge_handle(i).insert_as_leaf(i, i);
-///     }
-///
-///     let nasty = Nasty {
-///         first: &large_node,
-///         second: &small_node,
-///         flag: &flag
-///     }
-///
-///     // The handle points at index 75.
-///     let handle = Node::search(nasty, 75);
-///
-///     // Now the handle still points at index 75, but on the small node, which has no index 75.
-///     flag.set(true);
-///
-///     println!("Uninitialized memory: {:?}", handle.into_kv());
-/// }
-/// ```
-#[derive(Copy, Clone)]
-pub struct Handle<NodeRef, Type, NodeType> {
-    node: NodeRef,
-    index: usize,
-    marker: PhantomData<(Type, NodeType)>,
+/// This type has a number of paramaters that controls how it acts:
+/// - `BorrowType`: This can be `Immut<'a>` or `Mut<'a>` for some `'a` or `Owned`.
+///    When this is `Immut<'a>`, the `NodeRef` acts roughly like `&'a Node`,
+///    when this is `Mut<'a>`, the `NodeRef` acts roughly like `&'a mut Node`,
+///    and when this is `Owned`, the `NodeRef` acts roughly like `Box<Node>`.
+/// - `K` and `V`: These control what types of things are stored in the nodes.
+/// - `Type`: This can be `Leaf`, `Internal`, or `LeafOrInternal`. When this is
+///   `Leaf`, the `NodeRef` points to a leaf node, when this is `Internal` the
+///   `NodeRef` points to an internal node, and when this is `LeafOrInternal` the
+///   `NodeRef` could be pointing to either type of node.
+pub struct NodeRef<BorrowType, K, V, Type> {
+    height: usize,
+    node: NonZero<*mut LeafNode<K, V>>,
+    root: *mut Root<K, V>,
+    _marker: PhantomData<(BorrowType, Type)>
 }
 
-pub mod handle {
-    // Handle types.
-    pub enum KV {}
-    pub enum Edge {}
-
-    // Handle node types.
-    pub enum LeafOrInternal {}
-    pub enum Leaf {}
-    pub enum Internal {}
+impl<'a, K: 'a, V: 'a, Type> Copy for NodeRef<marker::Immut<'a>, K, V, Type> { }
+impl<'a, K: 'a, V: 'a, Type> Clone for NodeRef<marker::Immut<'a>, K, V, Type> {
+    fn clone(&self) -> Self {
+        *self
+    }
 }
 
-impl<K: Ord, V> Node<K, V> {
-    /// Searches for the given key in the node. If it finds an exact match,
-    /// `Found` will be yielded with the matching index. If it doesn't find an exact match,
-    /// `GoDown` will be yielded with the index of the subtree the key must lie in.
-    pub fn search<Q: ?Sized, NodeRef: Deref<Target = Node<K, V>>>(node: NodeRef,
-                                                                  key: &Q)
-                                                                  -> SearchResult<NodeRef>
-        where K: Borrow<Q>,
-              Q: Ord
-    {
-        // FIXME(Gankro): Tune when to search linear or binary based on B (and maybe K/V).
-        // For the B configured as of this writing (B = 6), binary search was *significantly*
-        // worse for usizes.
-        match node.as_slices_internal().search_linear(key) {
-            (index, true) => {
-                Found(Handle {
-                    node: node,
-                    index: index,
-                    marker: PhantomData,
-                })
-            }
-            (index, false) => {
-                GoDown(Handle {
-                    node: node,
-                    index: index,
-                    marker: PhantomData,
-                })
-            }
+unsafe impl<BorrowType, K: Sync, V: Sync, Type> Sync
+    for NodeRef<BorrowType, K, V, Type> { }
+
+unsafe impl<'a, K: Sync + 'a, V: Sync + 'a, Type> Send
+   for NodeRef<marker::Immut<'a>, K, V, Type> { }
+unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send
+   for NodeRef<marker::Mut<'a>, K, V, Type> { }
+unsafe impl<K: Send, V: Send, Type> Send
+   for NodeRef<marker::Owned, K, V, Type> { }
+
+impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::Internal> {
+    fn as_internal(&self) -> &InternalNode<K, V> {
+        unsafe {
+            &*(*self.node as *const InternalNode<K, V>)
         }
     }
 }
 
-// Public interface
-impl<K, V> Node<K, V> {
-    /// Make a leaf root from scratch
-    pub fn make_leaf_root(b: usize) -> Node<K, V> {
-        Node::new_leaf(capacity_from_b(b))
-    }
-
-    /// Make an internal root and swap it with an old root
-    pub fn make_internal_root(left_and_out: &mut Node<K, V>,
-                              b: usize,
-                              key: K,
-                              value: V,
-                              right: Node<K, V>) {
-        let node = mem::replace(left_and_out,
-                                unsafe { Node::new_internal(capacity_from_b(b)) });
-        left_and_out._len = 1;
+impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
+    fn as_internal_mut(&mut self) -> &mut InternalNode<K, V> {
         unsafe {
-            ptr::write(left_and_out.keys_mut().get_unchecked_mut(0), key);
-            ptr::write(left_and_out.vals_mut().get_unchecked_mut(0), value);
-            ptr::write(left_and_out.edges_mut().get_unchecked_mut(0), node);
-            ptr::write(left_and_out.edges_mut().get_unchecked_mut(1), right);
+            &mut *(*self.node as *mut InternalNode<K, V>)
         }
     }
+}
 
-    /// How many key-value pairs the node contains
-    pub fn len(&self) -> usize {
-        self._len
-    }
 
-    /// Does the node not contain any key-value pairs
-    pub fn is_empty(&self) -> bool {
-        self.len() == 0
+impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
+    pub fn len(&self) -> usize {
+        self.as_leaf().len as usize
     }
 
-    /// How many key-value pairs the node can fit
-    pub fn capacity(&self) -> usize {
-        self._capacity
+    pub fn forget_type(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
+        NodeRef {
+            height: self.height,
+            node: self.node,
+            root: self.root,
+            _marker: PhantomData
+        }
     }
 
-    /// If the node has any children
-    pub fn is_leaf(&self) -> bool {
-        self.edges.is_none()
+    fn reborrow<'a>(&'a self) -> NodeRef<marker::Immut<'a>, K, V, Type> {
+        NodeRef {
+            height: self.height,
+            node: self.node,
+            root: self.root,
+            _marker: PhantomData
+        }
     }
 
-    /// if the node has too few elements
-    pub fn is_underfull(&self) -> bool {
-        self.len() < min_load_from_capacity(self.capacity())
+    fn as_leaf(&self) -> &LeafNode<K, V> {
+        unsafe {
+            &**self.node
+        }
     }
 
-    /// if the node cannot fit any more elements
-    pub fn is_full(&self) -> bool {
-        self.len() == self.capacity()
+    pub fn keys(&self) -> &[K] {
+        self.reborrow().into_slices().0
     }
-}
 
-impl<K, V, NodeRef: Deref<Target = Node<K, V>>, Type, NodeType> Handle<NodeRef, Type, NodeType> {
-    /// Returns a reference to the node that contains the pointed-to edge or key/value pair. This
-    /// is very different from `edge` and `edge_mut` because those return children of the node
-    /// returned by `node`.
-    pub fn node(&self) -> &Node<K, V> {
-        &*self.node
+    pub fn vals(&self) -> &[V] {
+        self.reborrow().into_slices().1
     }
-}
 
-impl<K, V, NodeRef, Type, NodeType> Handle<NodeRef, Type, NodeType>
-    where NodeRef: Deref<Target = Node<K, V>> + DerefMut
-{
-    /// Converts a handle into one that stores the same information using a raw pointer. This can
-    /// be useful in conjunction with `from_raw` when the type system is insufficient for
-    /// determining the lifetimes of the nodes.
-    pub fn as_raw(&mut self) -> Handle<*mut Node<K, V>, Type, NodeType> {
-        Handle {
-            node: &mut *self.node as *mut _,
-            index: self.index,
-            marker: PhantomData,
+    pub fn ascend(self) -> Result<
+        Handle<
+            NodeRef<
+                BorrowType,
+                K, V,
+                marker::Internal
+            >,
+            marker::Edge
+        >,
+        Self
+    > {
+        if self.as_leaf().parent.is_null() {
+            Err(self)
+        } else {
+            Ok(Handle {
+                node: NodeRef {
+                    height: self.height + 1,
+                    node: unsafe {
+                        NonZero::new(self.as_leaf().parent as *mut LeafNode<K, V>)
+                    },
+                    root: self.root,
+                    _marker: PhantomData
+                },
+                idx: self.as_leaf().parent_idx as usize,
+                _marker: PhantomData
+            })
         }
     }
-}
 
-impl<K, V, Type, NodeType> Handle<*mut Node<K, V>, Type, NodeType> {
-    /// Converts from a handle stored with a raw pointer, which isn't directly usable, to a handle
-    /// stored with a reference. This is an unsafe inverse of `as_raw`, and together they allow
-    /// unsafely extending the lifetime of the reference to the `Node`.
-    pub unsafe fn from_raw<'a>(&'a self) -> Handle<&'a Node<K, V>, Type, NodeType> {
-        Handle {
-            node: &*self.node,
-            index: self.index,
-            marker: PhantomData,
-        }
+    pub fn first_edge(self) -> Handle<Self, marker::Edge> {
+        Handle::new_edge(self, 0)
     }
 
-    /// Converts from a handle stored with a raw pointer, which isn't directly usable, to a handle
-    /// stored with a mutable reference. This is an unsafe inverse of `as_raw`, and together they
-    /// allow unsafely extending the lifetime of the reference to the `Node`.
-    pub unsafe fn from_raw_mut<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, Type, NodeType> {
-        Handle {
-            node: &mut *self.node,
-            index: self.index,
-            marker: PhantomData,
-        }
+    pub fn last_edge(self) -> Handle<Self, marker::Edge> {
+        let len = self.len();
+        Handle::new_edge(self, len)
     }
 }
 
-impl<'a, K: 'a, V: 'a> Handle<&'a Node<K, V>, handle::Edge, handle::Internal> {
-    /// Turns the handle into a reference to the edge it points at. This is necessary because the
-    /// returned pointer has a larger lifetime than what would be returned by `edge` or `edge_mut`,
-    /// making it more suitable for moving down a chain of nodes.
-    pub fn into_edge(self) -> &'a Node<K, V> {
-        unsafe { self.node.edges().get_unchecked(self.index) }
+impl<K, V> NodeRef<marker::Owned, K, V, marker::Leaf> {
+    pub unsafe fn deallocate_and_ascend(self) -> Option<
+        Handle<
+            NodeRef<
+                marker::Owned,
+                K, V,
+                marker::Internal
+            >,
+            marker::Edge
+        >
+    > {
+        let ptr = self.as_leaf() as *const LeafNode<K, V> as *const u8 as *mut u8;
+        let ret = self.ascend().ok();
+        heap::deallocate(ptr, mem::size_of::<LeafNode<K, V>>(), mem::align_of::<LeafNode<K, V>>());
+        ret
     }
 }
 
-impl<'a, K: 'a, V: 'a> Handle<&'a mut Node<K, V>, handle::Edge, handle::Internal> {
-    /// Turns the handle into a mutable reference to the edge it points at. This is necessary
-    /// because the returned pointer has a larger lifetime than what would be returned by
-    /// `edge_mut`, making it more suitable for moving down a chain of nodes.
-    pub fn into_edge_mut(self) -> &'a mut Node<K, V> {
-        unsafe { self.node.edges_mut().get_unchecked_mut(self.index) }
+impl<K, V> NodeRef<marker::Owned, K, V, marker::Internal> {
+    pub unsafe fn deallocate_and_ascend(self) -> Option<
+        Handle<
+            NodeRef<
+                marker::Owned,
+                K, V,
+                marker::Internal
+            >,
+            marker::Edge
+        >
+    > {
+        let ptr = self.as_internal() as *const InternalNode<K, V> as *const u8 as *mut u8;
+        let ret = self.ascend().ok();
+        heap::deallocate(
+            ptr,
+            mem::size_of::<InternalNode<K, V>>(),
+            mem::align_of::<InternalNode<K, V>>()
+        );
+        ret
     }
 }
 
-impl<K, V, NodeRef: Deref<Target = Node<K, V>>> Handle<NodeRef, handle::Edge, handle::Internal> {
-    // This doesn't exist because there are no uses for it,
-    // but is fine to add, analogous to edge_mut.
-    //
-    // /// Returns a reference to the edge pointed-to by this handle. This should not be
-    // /// confused with `node`, which references the parent node of what is returned here.
-    // pub fn edge(&self) -> &Node<K, V>
-}
-
-pub enum ForceResult<NodeRef, Type> {
-    Leaf(Handle<NodeRef, Type, handle::Leaf>),
-    Internal(Handle<NodeRef, Type, handle::Internal>),
-}
+impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
+    unsafe fn cast_unchecked<NewType>(&mut self)
+            -> NodeRef<marker::Mut, K, V, NewType> {
 
-impl<K, V, NodeRef: Deref<Target = Node<K, V>>, Type>
-    Handle<NodeRef, Type, handle::LeafOrInternal>
-{
-    /// Figure out whether this handle is pointing to something in a leaf node or to something in
-    /// an internal node, clarifying the type according to the result.
-    pub fn force(self) -> ForceResult<NodeRef, Type> {
-        if self.node.is_leaf() {
-            Leaf(Handle {
-                node: self.node,
-                index: self.index,
-                marker: PhantomData,
-            })
-        } else {
-            Internal(Handle {
-                node: self.node,
-                index: self.index,
-                marker: PhantomData,
-            })
+        NodeRef {
+            height: self.height,
+            node: self.node,
+            root: self.root,
+            _marker: PhantomData
         }
     }
-}
-impl<K, V, NodeRef> Handle<NodeRef, handle::Edge, handle::Leaf>
-    where NodeRef: Deref<Target = Node<K, V>> + DerefMut
-{
-    /// Tries to insert this key-value pair at the given index in this leaf node
-    /// If the node is full, we have to split it.
-    ///
-    /// Returns a *mut V to the inserted value, because the caller may want this when
-    /// they're done mutating the tree, but we don't want to borrow anything for now.
-    pub fn insert_as_leaf(mut self, key: K, value: V) -> (InsertionResult<K, V>, *mut V) {
-        if !self.node.is_full() {
-            // The element can fit, just insert it
-            (Fit, unsafe { self.node.insert_kv(self.index, key, value) as *mut _ })
-        } else {
-            // The element can't fit, this node is full. Split it into two nodes.
-            let (new_key, new_val, mut new_right) = self.node.split();
-            let left_len = self.node.len();
-
-            let ptr = unsafe {
-                if self.index <= left_len {
-                    self.node.insert_kv(self.index, key, value)
-                } else {
-                    // We need to subtract 1 because in splitting we took out new_key and new_val.
-                    // Just being in the right node means we are past left_len k/v pairs in the
-                    // left node and 1 k/v pair in the parent node.
-                    new_right.insert_kv(self.index - left_len - 1, key, value)
-                }
-            } as *mut _;
-
-            (Split(new_key, new_val, new_right), ptr)
-        }
-    }
-}
-
-impl<K, V, NodeRef> Handle<NodeRef, handle::Edge, handle::Internal>
-    where NodeRef: Deref<Target = Node<K, V>> + DerefMut
-{
-    /// Returns a mutable reference to the edge pointed-to by this handle. This should not be
-    /// confused with `node`, which references the parent node of what is returned here.
-    pub fn edge_mut(&mut self) -> &mut Node<K, V> {
-        unsafe { self.node.edges_mut().get_unchecked_mut(self.index) }
-    }
-
-    /// Tries to insert this key-value pair at the given index in this internal node
-    /// If the node is full, we have to split it.
-    pub fn insert_as_internal(mut self,
-                              key: K,
-                              value: V,
-                              right: Node<K, V>)
-                              -> InsertionResult<K, V> {
-        if !self.node.is_full() {
-            // The element can fit, just insert it
-            unsafe {
-                self.node.insert_kv(self.index, key, value);
-                self.node.insert_edge(self.index + 1, right); // +1 to insert to the right
-            }
-            Fit
-        } else {
-            // The element can't fit, this node is full. Split it into two nodes.
-            let (new_key, new_val, mut new_right) = self.node.split();
-            let left_len = self.node.len();
 
-            if self.index <= left_len {
-                unsafe {
-                    self.node.insert_kv(self.index, key, value);
-                    self.node.insert_edge(self.index + 1, right); // +1 to insert to the right
-                }
-            } else {
-                unsafe {
-                    // The -1 here is for the same reason as in insert_as_internal - because we
-                    // split, there are actually left_len + 1 k/v pairs before the right node, with
-                    // the extra 1 being put in the parent.
-                    new_right.insert_kv(self.index - left_len - 1, key, value);
-                    new_right.insert_edge(self.index - left_len, right);
-                }
-            }
-
-            Split(new_key, new_val, new_right)
+    unsafe fn reborrow_mut(&mut self) -> NodeRef<marker::Mut, K, V, Type> {
+        NodeRef {
+            height: self.height,
+            node: self.node,
+            root: self.root,
+            _marker: PhantomData
         }
     }
 
-    /// Handle an underflow in this node's child. We favor handling "to the left" because we know
-    /// we're empty, but our neighbour can be full. Handling to the left means when we choose to
-    /// steal, we pop off the end of our neighbour (always fast) and "unshift" ourselves
-    /// (always slow, but at least faster since we know we're half-empty).
-    /// Handling "to the right" reverses these roles. Of course, we merge whenever possible
-    /// because we want dense nodes, and merging is about equal work regardless of direction.
-    pub fn handle_underflow(mut self) {
+    fn as_leaf_mut(&mut self) -> &mut LeafNode<K, V> {
         unsafe {
-            if self.index > 0 {
-                self.handle_underflow_to_left();
-            } else {
-                self.handle_underflow_to_right();
-            }
+            &mut **self.node
         }
     }
 
-    /// Right is underflowed. Tries to steal from left,
-    /// but merges left and right if left is low too.
-    unsafe fn handle_underflow_to_left(&mut self) {
-        let left_len = self.node.edges()[self.index - 1].len();
-        if left_len > min_load_from_capacity(self.node.capacity()) {
-            self.left_kv().steal_rightward();
-        } else {
-            self.left_kv().merge_children();
-        }
+    pub fn keys_mut(&mut self) -> &mut [K] {
+        unsafe { self.reborrow_mut().into_slices_mut().0 }
     }
 
-    /// Left is underflowed. Tries to steal from the right,
-    /// but merges left and right if right is low too.
-    unsafe fn handle_underflow_to_right(&mut self) {
-        let right_len = self.node.edges()[self.index + 1].len();
-        if right_len > min_load_from_capacity(self.node.capacity()) {
-            self.right_kv().steal_leftward();
-        } else {
-            self.right_kv().merge_children();
-        }
+    pub fn vals_mut(&mut self) -> &mut [V] {
+        unsafe { self.reborrow_mut().into_slices_mut().1 }
     }
 }
 
-impl<K, V, NodeRef, NodeType> Handle<NodeRef, handle::Edge, NodeType>
-    where NodeRef: Deref<Target = Node<K, V>> + DerefMut
-{
-    /// Gets the handle pointing to the key/value pair just to the left of the pointed-to edge.
-    /// This is unsafe because the handle might point to the first edge in the node, which has no
-    /// pair to its left.
-    unsafe fn left_kv<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::KV, NodeType> {
-        Handle {
-            node: &mut *self.node,
-            index: self.index - 1,
-            marker: PhantomData,
+impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> {
+    pub fn into_slices(self) -> (&'a [K], &'a [V]) {
+        unsafe {
+            (
+                slice::from_raw_parts(
+                    self.as_leaf().keys.as_ptr(),
+                    self.len()
+                ),
+                slice::from_raw_parts(
+                    self.as_leaf().vals.as_ptr(),
+                    self.len()
+                )
+            )
         }
     }
+}
 
-    /// Gets the handle pointing to the key/value pair just to the right of the pointed-to edge.
-    /// This is unsafe because the handle might point to the last edge in the node, which has no
-    /// pair to its right.
-    unsafe fn right_kv<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::KV, NodeType> {
-        Handle {
-            node: &mut *self.node,
-            index: self.index,
-            marker: PhantomData,
+impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
+    pub fn into_root_mut(self) -> &'a mut Root<K, V> {
+        unsafe {
+            &mut *self.root
         }
     }
-}
 
-impl<'a, K: 'a, V: 'a, NodeType> Handle<&'a Node<K, V>, handle::KV, NodeType> {
-    /// Turns the handle into references to the key and value it points at. This is necessary
-    /// because the returned pointers have larger lifetimes than what would be returned by `key`
-    /// or `val`.
-    pub fn into_kv(self) -> (&'a K, &'a V) {
-        let (keys, vals) = self.node.as_slices();
+    pub fn into_slices_mut(mut self) -> (&'a mut [K], &'a mut [V]) {
         unsafe {
-            (keys.get_unchecked(self.index),
-             vals.get_unchecked(self.index))
+            (
+                slice::from_raw_parts_mut(
+                    &mut self.as_leaf_mut().keys as *mut [K] as *mut K,
+                    self.len()
+                ),
+                slice::from_raw_parts_mut(
+                    &mut self.as_leaf_mut().vals as *mut [V] as *mut V,
+                    self.len()
+                )
+            )
         }
     }
 }
 
-impl<'a, K: 'a, V: 'a, NodeType> Handle<&'a mut Node<K, V>, handle::KV, NodeType> {
-    /// Turns the handle into mutable references to the key and value it points at. This is
-    /// necessary because the returned pointers have larger lifetimes than what would be returned
-    /// by `key_mut` or `val_mut`.
-    pub fn into_kv_mut(self) -> (&'a mut K, &'a mut V) {
-        let (keys, vals) = self.node.as_slices_mut();
+impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Leaf> {
+    pub fn push(&mut self, key: K, val: V) {
+        // Necessary for correctness, but this is an internal module
+        debug_assert!(self.len() < CAPACITY);
+
+        let idx = self.len();
+
         unsafe {
-            (keys.get_unchecked_mut(self.index),
-             vals.get_unchecked_mut(self.index))
+            ptr::write(self.keys_mut().get_unchecked_mut(idx), key);
+            ptr::write(self.vals_mut().get_unchecked_mut(idx), val);
         }
+
+        self.as_leaf_mut().len += 1;
     }
 
-    /// Convert this handle into one pointing at the edge immediately to the left of the key/value
-    /// pair pointed-to by this handle. This is useful because it returns a reference with larger
-    /// lifetime than `left_edge`.
-    pub fn into_left_edge(self) -> Handle<&'a mut Node<K, V>, handle::Edge, NodeType> {
-        Handle {
-            node: &mut *self.node,
-            index: self.index,
-            marker: PhantomData,
+    pub fn push_front(&mut self, key: K, val: V) {
+        // Necessary for correctness, but this is an internal module
+        debug_assert!(self.len() < CAPACITY);
+
+        unsafe {
+            slice_insert(self.keys_mut(), 0, key);
+            slice_insert(self.vals_mut(), 0, val);
         }
+
+        self.as_leaf_mut().len += 1;
     }
 }
 
+impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::Internal> {
+    pub fn push(&mut self, key: K, val: V, edge: Root<K, V>) {
+        // Necessary for correctness, but this is an internal module
+        debug_assert!(edge.height == self.height - 1);
+        debug_assert!(self.len() < CAPACITY);
 
-impl<'a, K: 'a, V: 'a, NodeRef: Deref<Target = Node<K, V>> + 'a, NodeType> Handle<NodeRef,
-                                                                                  handle::KV,
-                                                                                  NodeType> {
-    // These are fine to include, but are currently unneeded.
-    //
-    // /// Returns a reference to the key pointed-to by this handle. This doesn't return a
-    // /// reference with a lifetime as large as `into_kv_mut`, but it also does not consume the
-    // /// handle.
-    // pub fn key(&'a self) -> &'a K {
-    //     unsafe { self.node.keys().get_unchecked(self.index) }
-    // }
-    //
-    // /// Returns a reference to the value pointed-to by this handle. This doesn't return a
-    // /// reference with a lifetime as large as `into_kv_mut`, but it also does not consume the
-    // /// handle.
-    // pub fn val(&'a self) -> &'a V {
-    //     unsafe { self.node.vals().get_unchecked(self.index) }
-    // }
-}
+        let idx = self.len();
 
-impl<'a, K: 'a, V: 'a, NodeRef, NodeType> Handle<NodeRef, handle::KV, NodeType>
-    where NodeRef: 'a + Deref<Target = Node<K, V>> + DerefMut
-{
-    /// Returns a mutable reference to the key pointed-to by this handle. This doesn't return a
-    /// reference with a lifetime as large as `into_kv_mut`, but it also does not consume the
-    /// handle.
-    pub fn key_mut(&'a mut self) -> &'a mut K {
-        unsafe { self.node.keys_mut().get_unchecked_mut(self.index) }
-    }
+        unsafe {
+            ptr::write(self.keys_mut().get_unchecked_mut(idx), key);
+            ptr::write(self.vals_mut().get_unchecked_mut(idx), val);
+            ptr::write(self.as_internal_mut().edges.get_unchecked_mut(idx + 1), edge.node);
 
-    /// Returns a mutable reference to the value pointed-to by this handle. This doesn't return a
-    /// reference with a lifetime as large as `into_kv_mut`, but it also does not consume the
-    /// handle.
-    pub fn val_mut(&'a mut self) -> &'a mut V {
-        unsafe { self.node.vals_mut().get_unchecked_mut(self.index) }
-    }
-}
+            self.as_leaf_mut().len += 1;
 
-impl<K, V, NodeRef, NodeType> Handle<NodeRef, handle::KV, NodeType>
-    where NodeRef: Deref<Target = Node<K, V>> + DerefMut
-{
-    /// Gets the handle pointing to the edge immediately to the left of the key/value pair pointed
-    /// to by this handle.
-    pub fn left_edge<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::Edge, NodeType> {
-        Handle {
-            node: &mut *self.node,
-            index: self.index,
-            marker: PhantomData,
+            Handle::new_edge(self.reborrow_mut(), idx + 1).correct_parent_link();
         }
     }
 
-    /// Gets the handle pointing to the edge immediately to the right of the key/value pair pointed
-    /// to by this handle.
-    pub fn right_edge<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::Edge, NodeType> {
-        Handle {
-            node: &mut *self.node,
-            index: self.index + 1,
-            marker: PhantomData,
+    pub fn push_front(&mut self, key: K, val: V, edge: Root<K, V>) {
+        // Necessary for correctness, but this is an internal module
+        debug_assert!(edge.height == self.height - 1);
+        debug_assert!(self.len() < CAPACITY);
+
+        unsafe {
+            slice_insert(self.keys_mut(), 0, key);
+            slice_insert(self.vals_mut(), 0, val);
+            slice_insert(
+                slice::from_raw_parts_mut(
+                    self.as_internal_mut().edges.as_mut_ptr(),
+                    self.len()+1
+                ),
+                0,
+                edge.node
+            );
+
+            self.as_leaf_mut().len += 1;
+
+            for i in 0..self.len()+1 {
+                Handle::new_edge(self.reborrow_mut(), i).correct_parent_link();
+            }
         }
-    }
-}
 
-impl<K, V, NodeRef> Handle<NodeRef, handle::KV, handle::Leaf>
-    where NodeRef: Deref<Target = Node<K, V>> + DerefMut
-{
-    /// Removes the key/value pair at the handle's location.
-    ///
-    /// # Panics (in debug build)
-    ///
-    /// Panics if the node containing the pair is not a leaf node.
-    pub fn remove_as_leaf(mut self) -> (K, V) {
-        unsafe { self.node.remove_kv(self.index) }
     }
 }
 
-impl<K, V, NodeRef> Handle<NodeRef, handle::KV, handle::Internal>
-    where NodeRef: Deref<Target = Node<K, V>> + DerefMut
-{
-    /// Steal! Stealing is roughly analogous to a binary tree rotation.
-    /// In this case, we're "rotating" right.
-    unsafe fn steal_rightward(&mut self) {
-        // Take the biggest stuff off left
-        let (mut key, mut val, edge) = {
-            let mut left_handle = self.left_edge();
-            let left = left_handle.edge_mut();
-            let (key, val) = left.pop_kv();
-            let edge = if left.is_leaf() {
-                None
-            } else {
-                Some(left.pop_edge())
+impl<'a, K, V> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> {
+    pub fn pop(&mut self) -> (K, V, Option<Root<K, V>>) {
+        // Necessary for correctness, but this is an internal module
+        debug_assert!(self.len() > 0);
+
+        let idx = self.len() - 1;
+
+        unsafe {
+            let key = ptr::read(self.keys().get_unchecked(idx));
+            let val = ptr::read(self.vals().get_unchecked(idx));
+            let edge = match self.reborrow_mut().force() {
+                ForceResult::Leaf(_) => None,
+                ForceResult::Internal(internal) => {
+                    let edge = ptr::read(internal.as_internal().edges.get_unchecked(idx + 1));
+                    let mut new_root = Root { node: edge, height: internal.height - 1 };
+                    new_root.as_mut().as_leaf_mut().parent = ptr::null();
+                    Some(new_root)
+                }
             };
 
+            self.as_leaf_mut().len -= 1;
             (key, val, edge)
-        };
-
-        // Swap the parent's separating key-value pair with left's
-        mem::swap(&mut key, self.key_mut());
-        mem::swap(&mut val, self.val_mut());
-
-        // Put them at the start of right
-        let mut right_handle = self.right_edge();
-        let right = right_handle.edge_mut();
-        right.insert_kv(0, key, val);
-        match edge {
-            Some(edge) => right.insert_edge(0, edge),
-            None => {}
         }
     }
 
-    /// Steal! Stealing is roughly analogous to a binary tree rotation.
-    /// In this case, we're "rotating" left.
-    unsafe fn steal_leftward(&mut self) {
-        // Take the smallest stuff off right
-        let (mut key, mut val, edge) = {
-            let mut right_handle = self.right_edge();
-            let right = right_handle.edge_mut();
-            let (key, val) = right.remove_kv(0);
-            let edge = if right.is_leaf() {
-                None
-            } else {
-                Some(right.remove_edge(0))
-            };
+    pub fn pop_front(&mut self) -> (K, V, Option<Root<K, V>>) {
+        // Necessary for correctness, but this is an internal module
+        debug_assert!(self.len() > 0);
 
-            (key, val, edge)
-        };
+        let old_len = self.len();
 
-        // Swap the parent's separating key-value pair with right's
-        mem::swap(&mut key, self.key_mut());
-        mem::swap(&mut val, self.val_mut());
-
-        // Put them at the end of left
-        let mut left_handle = self.left_edge();
-        let left = left_handle.edge_mut();
-        left.push_kv(key, val);
-        match edge {
-            Some(edge) => left.push_edge(edge),
-            None => {}
-        }
-    }
+        unsafe {
+            let key = slice_remove(self.keys_mut(), 0);
+            let val = slice_remove(self.vals_mut(), 0);
+            let edge = match self.reborrow_mut().force() {
+                ForceResult::Leaf(_) => None,
+                ForceResult::Internal(mut internal) => {
+                    let edge = slice_remove(
+                        slice::from_raw_parts_mut(
+                            internal.as_internal_mut().edges.as_mut_ptr(),
+                            old_len+1
+                        ),
+                        0
+                    );
+
+                    let mut new_root = Root { node: edge, height: internal.height - 1 };
+                    new_root.as_mut().as_leaf_mut().parent = ptr::null();
+
+                    for i in 0..old_len {
+                        Handle::new_edge(internal.reborrow_mut(), i).correct_parent_link();
+                    }
+
+                    Some(new_root)
+                }
+            };
 
-    /// Merge! Smooshes left and right into one node, along with the key-value
-    /// pair that separated them in their parent.
-    unsafe fn merge_children(mut self) {
-        // Permanently remove right's index, and the key-value pair that separates
-        // left and right
-        let (key, val) = self.node.remove_kv(self.index);
-        let right = self.node.remove_edge(self.index + 1);
+            self.as_leaf_mut().len -= 1;
 
-        // Give left right's stuff.
-        self.left_edge()
-            .edge_mut()
-            .absorb(key, val, right);
+            (key, val, edge)
+        }
     }
 }
 
-impl<K, V> Node<K, V> {
-    /// Returns the mutable handle pointing to the key/value pair at a given index.
-    ///
-    /// # Panics (in debug build)
-    ///
-    /// Panics if the given index is out of bounds.
-    pub fn kv_handle(&mut self,
-                     index: usize)
-                     -> Handle<&mut Node<K, V>, handle::KV, handle::LeafOrInternal> {
-        // Necessary for correctness, but in a private module
-        debug_assert!(index < self.len(), "kv_handle index out of bounds");
-        Handle {
-            node: self,
-            index: index,
-            marker: PhantomData,
+impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
+    pub fn force(self) -> ForceResult<
+        NodeRef<BorrowType, K, V, marker::Leaf>,
+        NodeRef<BorrowType, K, V, marker::Internal>
+    > {
+        if self.height == 0 {
+            ForceResult::Leaf(NodeRef {
+                height: self.height,
+                node: self.node,
+                root: self.root,
+                _marker: PhantomData
+            })
+        } else {
+            ForceResult::Internal(NodeRef {
+                height: self.height,
+                node: self.node,
+                root: self.root,
+                _marker: PhantomData
+            })
         }
     }
+}
 
-    pub fn iter<'a>(&'a self) -> Traversal<'a, K, V> {
-        self.as_slices_internal().iter()
-    }
+pub struct Handle<Node, Type> {
+    node: Node,
+    idx: usize,
+    _marker: PhantomData<Type>
+}
 
-    pub fn iter_mut<'a>(&'a mut self) -> MutTraversal<'a, K, V> {
-        self.as_slices_internal_mut().iter_mut()
+impl<Node: Copy, Type> Copy for Handle<Node, Type> { }
+impl<Node: Copy, Type> Clone for Handle<Node, Type> {
+    fn clone(&self) -> Self {
+        *self
     }
+}
 
-    pub fn into_iter(self) -> MoveTraversal<K, V> {
-        unsafe {
-            let ret = MoveTraversal {
-                inner: MoveTraversalImpl {
-                    keys: RawItems::from_slice(self.keys()),
-                    vals: RawItems::from_slice(self.vals()),
-                    edges: RawItems::from_slice(self.edges()),
-
-                    ptr: Unique::new(*self.keys as *mut u8),
-                    capacity: self.capacity(),
-                    is_leaf: self.is_leaf(),
-                },
-                head_is_edge: true,
-                tail_is_edge: true,
-                has_edges: !self.is_leaf(),
-            };
-            mem::forget(self);
-            ret
-        }
+impl<Node, Type> Handle<Node, Type> {
+    pub fn into_node(self) -> Node {
+        self.node
     }
+}
 
-    /// When a node has no keys or values and only a single edge, extract that edge.
-    pub fn hoist_lone_child(&mut self) {
+impl<BorrowType, K, V, NodeType> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV> {
+    pub fn new_kv(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
         // Necessary for correctness, but in a private module
-        debug_assert!(self.is_empty());
-        debug_assert!(!self.is_leaf());
+        debug_assert!(idx < node.len());
 
-        unsafe {
-            let ret = ptr::read(self.edges().get_unchecked(0));
-            self.destroy();
-            ptr::write(self, ret);
+        Handle {
+            node: node,
+            idx: idx,
+            _marker: PhantomData
         }
     }
-}
-
-// Vector functions (all unchecked)
-impl<K, V> Node<K, V> {
-    // This must be followed by push_edge on an internal node.
-    #[inline]
-    unsafe fn push_kv(&mut self, key: K, val: V) {
-        let len = self.len();
-
-        ptr::write(self.keys_mut().get_unchecked_mut(len), key);
-        ptr::write(self.vals_mut().get_unchecked_mut(len), val);
 
-        self._len += 1;
+    pub fn left_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
+        Handle::new_edge(self.node, self.idx)
     }
 
-    // This can only be called immediately after a call to push_kv.
-    #[inline]
-    unsafe fn push_edge(&mut self, edge: Node<K, V>) {
-        let len = self.len();
-
-        ptr::write(self.edges_mut().get_unchecked_mut(len), edge);
+    pub fn right_edge(self) -> Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
+        Handle::new_edge(self.node, self.idx + 1)
     }
+}
 
-    // This must be followed by insert_edge on an internal node.
-    #[inline]
-    unsafe fn insert_kv(&mut self, index: usize, key: K, val: V) -> &mut V {
-        ptr::copy(self.keys().as_ptr().offset(index as isize),
-                  self.keys_mut().as_mut_ptr().offset(index as isize + 1),
-                  self.len() - index);
-        ptr::copy(self.vals().as_ptr().offset(index as isize),
-                  self.vals_mut().as_mut_ptr().offset(index as isize + 1),
-                  self.len() - index);
+impl<BorrowType, K, V, NodeType, HandleType> PartialEq
+        for Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType> {
 
-        ptr::write(self.keys_mut().get_unchecked_mut(index), key);
-        ptr::write(self.vals_mut().get_unchecked_mut(index), val);
+    fn eq(&self, other: &Self) -> bool {
+        self.node.node == other.node.node && self.idx == other.idx
+    }
+}
 
-        self._len += 1;
+impl<BorrowType, K, V, NodeType, HandleType>
+        Handle<NodeRef<BorrowType, K, V, NodeType>, HandleType> {
 
-        self.vals_mut().get_unchecked_mut(index)
-    }
+    pub fn reborrow(&self)
+            -> Handle<NodeRef<marker::Immut, K, V, NodeType>, HandleType> {
 
-    // This can only be called immediately after a call to insert_kv.
-    #[inline]
-    unsafe fn insert_edge(&mut self, index: usize, edge: Node<K, V>) {
-        ptr::copy(self.edges().as_ptr().offset(index as isize),
-                  self.edges_mut().as_mut_ptr().offset(index as isize + 1),
-                  self.len() - index);
-        ptr::write(self.edges_mut().get_unchecked_mut(index), edge);
+        // We can't use Handle::new_kv or Handle::new_edge because we don't know our type
+        Handle {
+            node: self.node.reborrow(),
+            idx: self.idx,
+            _marker: PhantomData
+        }
     }
+}
 
-    // This must be followed by pop_edge on an internal node.
-    #[inline]
-    unsafe fn pop_kv(&mut self) -> (K, V) {
-        let key = ptr::read(self.keys().get_unchecked(self.len() - 1));
-        let val = ptr::read(self.vals().get_unchecked(self.len() - 1));
+impl<'a, K, V, NodeType, HandleType>
+        Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, HandleType> {
 
-        self._len -= 1;
+    pub unsafe fn reborrow_mut(&mut self)
+            -> Handle<NodeRef<marker::Mut, K, V, NodeType>, HandleType> {
 
-        (key, val)
+        // We can't use Handle::new_kv or Handle::new_edge because we don't know our type
+        Handle {
+            node: self.node.reborrow_mut(),
+            idx: self.idx,
+            _marker: PhantomData
+        }
     }
+}
 
-    // This can only be called immediately after a call to pop_kv.
-    #[inline]
-    unsafe fn pop_edge(&mut self) -> Node<K, V> {
-        let edge = ptr::read(self.edges().get_unchecked(self.len() + 1));
-
-        edge
-    }
+impl<BorrowType, K, V, NodeType>
+        Handle<NodeRef<BorrowType, K, V, NodeType>, marker::Edge> {
 
-    // This must be followed by remove_edge on an internal node.
-    #[inline]
-    unsafe fn remove_kv(&mut self, index: usize) -> (K, V) {
-        let key = ptr::read(self.keys().get_unchecked(index));
-        let val = ptr::read(self.vals().get_unchecked(index));
+    pub fn new_edge(node: NodeRef<BorrowType, K, V, NodeType>, idx: usize) -> Self {
+        // Necessary for correctness, but in a private module
+        debug_assert!(idx <= node.len());
 
-        ptr::copy(self.keys().as_ptr().offset(index as isize + 1),
-                  self.keys_mut().as_mut_ptr().offset(index as isize),
-                  self.len() - index - 1);
-        ptr::copy(self.vals().as_ptr().offset(index as isize + 1),
-                  self.vals_mut().as_mut_ptr().offset(index as isize),
-                  self.len() - index - 1);
+        Handle {
+            node: node,
+            idx: idx,
+            _marker: PhantomData
+        }
+    }
 
-        self._len -= 1;
+    pub fn left_kv(self)
+            -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
 
-        (key, val)
+        if self.idx > 0 {
+            Ok(Handle::new_kv(self.node, self.idx - 1))
+        } else {
+            Err(self)
+        }
     }
 
-    // This can only be called immediately after a call to remove_kv.
-    #[inline]
-    unsafe fn remove_edge(&mut self, index: usize) -> Node<K, V> {
-        let edge = ptr::read(self.edges().get_unchecked(index));
+    pub fn right_kv(self)
+            -> Result<Handle<NodeRef<BorrowType, K, V, NodeType>, marker::KV>, Self> {
 
-        ptr::copy(self.edges().as_ptr().offset(index as isize + 1),
-                  self.edges_mut().as_mut_ptr().offset(index as isize),
-                  // index can be == len+1, so do the +1 first to avoid underflow.
-                  (self.len() + 1) - index);
-
-        edge
+        if self.idx < self.node.len() {
+            Ok(Handle::new_kv(self.node, self.idx))
+        } else {
+            Err(self)
+        }
     }
 }
 
-// Private implementation details
-impl<K, V> Node<K, V> {
-    /// Node is full, so split it into two nodes, and yield the middle-most key-value pair
-    /// because we have one too many, and our parent now has one too few
-    fn split(&mut self) -> (K, V, Node<K, V>) {
-        // Necessary for correctness, but in a private function
-        debug_assert!(!self.is_empty());
-
-        let mut right = if self.is_leaf() {
-            Node::new_leaf(self.capacity())
-        } else {
-            unsafe { Node::new_internal(self.capacity()) }
-        };
+impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
+    fn insert_fit(&mut self, key: K, val: V) -> *mut V {
+        // Necessary for correctness, but in a private module
+        debug_assert!(self.node.len() < CAPACITY);
 
         unsafe {
-            right._len = self.len() / 2;
-            let right_offset = self.len() - right.len();
-            ptr::copy_nonoverlapping(self.keys().as_ptr().offset(right_offset as isize),
-                                     right.keys_mut().as_mut_ptr(),
-                                     right.len());
-            ptr::copy_nonoverlapping(self.vals().as_ptr().offset(right_offset as isize),
-                                     right.vals_mut().as_mut_ptr(),
-                                     right.len());
-            if !self.is_leaf() {
-                ptr::copy_nonoverlapping(self.edges().as_ptr().offset(right_offset as isize),
-                                         right.edges_mut().as_mut_ptr(),
-                                         right.len() + 1);
-            }
-
-            let key = ptr::read(self.keys().get_unchecked(right_offset - 1));
-            let val = ptr::read(self.vals().get_unchecked(right_offset - 1));
+            slice_insert(self.node.keys_mut(), self.idx, key);
+            slice_insert(self.node.vals_mut(), self.idx, val);
 
-            self._len = right_offset - 1;
+            self.node.as_leaf_mut().len += 1;
 
-            (key, val, right)
+            self.node.vals_mut().get_unchecked_mut(self.idx)
         }
     }
 
-    /// Take all the values from right, separated by the given key and value
-    fn absorb(&mut self, key: K, val: V, mut right: Node<K, V>) {
-        // Necessary for correctness, but in a private function
-        // Just as a sanity check, make sure we can fit this guy in
-        debug_assert!(self.len() + right.len() <= self.capacity());
-        debug_assert!(self.is_leaf() == right.is_leaf());
+    pub fn insert(mut self, key: K, val: V)
+            -> (InsertResult<'a, K, V, marker::Leaf>, *mut V) {
 
-        unsafe {
-            let old_len = self.len();
-            self._len += right.len() + 1;
-
-            ptr::write(self.keys_mut().get_unchecked_mut(old_len), key);
-            ptr::write(self.vals_mut().get_unchecked_mut(old_len), val);
-
-            ptr::copy_nonoverlapping(right.keys().as_ptr(),
-                                     self.keys_mut().as_mut_ptr().offset(old_len as isize + 1),
-                                     right.len());
-            ptr::copy_nonoverlapping(right.vals().as_ptr(),
-                                     self.vals_mut().as_mut_ptr().offset(old_len as isize + 1),
-                                     right.len());
-            if !self.is_leaf() {
-                ptr::copy_nonoverlapping(right.edges().as_ptr(),
-                                         self.edges_mut()
-                                             .as_mut_ptr()
-                                             .offset(old_len as isize + 1),
-                                         right.len() + 1);
-            }
-
-            right.destroy();
-            mem::forget(right);
+        if self.node.len() < CAPACITY {
+            let ptr = self.insert_fit(key, val);
+            (InsertResult::Fit(Handle::new_kv(self.node, self.idx)), ptr)
+        } else {
+            let middle = Handle::new_kv(self.node, B);
+            let (mut left, k, v, mut right) = middle.split();
+            let ptr = if self.idx <= B {
+                unsafe {
+                    Handle::new_edge(left.reborrow_mut(), self.idx).insert_fit(key, val)
+                }
+            } else {
+                unsafe {
+                    Handle::new_edge(
+                        right.as_mut().cast_unchecked::<marker::Leaf>(),
+                        self.idx - (B + 1)
+                    ).insert_fit(key, val)
+                }
+            };
+            (InsertResult::Split(left, k, v, right), ptr)
         }
     }
 }
 
-/// Get the capacity of a node from the order of the parent B-Tree
-fn capacity_from_b(b: usize) -> usize {
-    2 * b - 1
-}
-
-/// Get the minimum load of a node from its capacity
-fn min_load_from_capacity(cap: usize) -> usize {
-    // B - 1
-    cap / 2
-}
+impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
+    fn correct_parent_link(mut self) {
+        let idx = self.idx as u16;
+        let ptr = self.node.as_internal_mut() as *mut _;
+        let mut child = self.descend();
+        child.as_leaf_mut().parent = ptr;
+        child.as_leaf_mut().parent_idx = idx;
+    }
 
-/// A trait for pairs of `Iterator`s, one over edges and the other over key/value pairs. This is
-/// necessary, as the `MoveTraversalImpl` needs to have a destructor that deallocates the `Node`,
-/// and a pair of `Iterator`s would require two independent destructors.
-pub trait TraversalImpl {
-    type Item;
-    type Edge;
+    unsafe fn cast_unchecked<NewType>(&mut self)
+            -> Handle<NodeRef<marker::Mut, K, V, NewType>, marker::Edge> {
 
-    fn next_kv(&mut self) -> Option<Self::Item>;
-    fn next_kv_back(&mut self) -> Option<Self::Item>;
+        Handle::new_edge(self.node.cast_unchecked(), self.idx)
+    }
 
-    fn next_edge(&mut self) -> Option<Self::Edge>;
-    fn next_edge_back(&mut self) -> Option<Self::Edge>;
-}
+    fn insert_fit(&mut self, key: K, val: V, edge: Root<K, V>) {
+        // Necessary for correctness, but in an internal module
+        debug_assert!(self.node.len() < CAPACITY);
+        debug_assert!(edge.height == self.node.height - 1);
 
-/// A `TraversalImpl` that actually is backed by two iterators. This works in the non-moving case,
-/// as no deallocation needs to be done.
-#[derive(Clone)]
-pub struct ElemsAndEdges<Elems, Edges>(Elems, Edges);
+        unsafe {
+            self.cast_unchecked::<marker::Leaf>().insert_fit(key, val);
+
+            slice_insert(
+                slice::from_raw_parts_mut(
+                    self.node.as_internal_mut().edges.as_mut_ptr(),
+                    self.node.len()
+                ),
+                self.idx + 1,
+                edge.node
+            );
+
+            for i in (self.idx+1)..(self.node.len()+1) {
+                Handle::new_edge(self.node.reborrow_mut(), i).correct_parent_link();
+            }
+        }
+    }
 
-impl<K, V, E, Elems: DoubleEndedIterator, Edges: DoubleEndedIterator>
-        TraversalImpl for ElemsAndEdges<Elems, Edges>
-    where Elems : Iterator<Item=(K, V)>, Edges : Iterator<Item=E>
-{
-    type Item = (K, V);
-    type Edge = E;
+    pub fn insert(mut self, key: K, val: V, edge: Root<K, V>)
+            -> InsertResult<'a, K, V, marker::Internal> {
 
-    fn next_kv(&mut self) -> Option<(K, V)> { self.0.next() }
-    fn next_kv_back(&mut self) -> Option<(K, V)> { self.0.next_back() }
+        // Necessary for correctness, but this is an internal module
+        debug_assert!(edge.height == self.node.height - 1);
 
-    fn next_edge(&mut self) -> Option<E> { self.1.next() }
-    fn next_edge_back(&mut self) -> Option<E> { self.1.next_back() }
+        if self.node.len() < CAPACITY {
+            self.insert_fit(key, val, edge);
+            InsertResult::Fit(Handle::new_kv(self.node, self.idx))
+        } else {
+            let middle = Handle::new_kv(self.node, B);
+            let (mut left, k, v, mut right) = middle.split();
+            if self.idx <= B {
+                unsafe {
+                    Handle::new_edge(left.reborrow_mut(), self.idx).insert_fit(key, val, edge);
+                }
+            } else {
+                unsafe {
+                    Handle::new_edge(
+                        right.as_mut().cast_unchecked::<marker::Internal>(),
+                        self.idx - (B + 1)
+                    ).insert_fit(key, val, edge);
+                }
+            }
+            InsertResult::Split(left, k, v, right)
+        }
+    }
 }
 
-/// A `TraversalImpl` taking a `Node` by value.
-pub struct MoveTraversalImpl<K, V> {
-    keys: RawItems<K>,
-    vals: RawItems<V>,
-    edges: RawItems<Node<K, V>>,
+impl<BorrowType, K, V>
+        Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> {
 
-    // For deallocation when we are done iterating.
-    ptr: Unique<u8>,
-    capacity: usize,
-    is_leaf: bool,
+    pub fn descend(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
+        NodeRef {
+            height: self.node.height - 1,
+            node: unsafe { self.node.as_internal().edges.get_unchecked(self.idx).as_ptr() },
+            root: self.node.root,
+            _marker: PhantomData
+        }
+    }
 }
 
-unsafe impl<K: Sync, V: Sync> Sync for MoveTraversalImpl<K, V> {}
-unsafe impl<K: Send, V: Send> Send for MoveTraversalImpl<K, V> {}
-
-impl<K, V> TraversalImpl for MoveTraversalImpl<K, V> {
-    type Item = (K, V);
-    type Edge = Node<K, V>;
+impl<'a, K: 'a, V: 'a, NodeType>
+        Handle<NodeRef<marker::Immut<'a>, K, V, NodeType>, marker::KV> {
 
-    fn next_kv(&mut self) -> Option<(K, V)> {
-        match (self.keys.next(), self.vals.next()) {
-            (Some(k), Some(v)) => Some((k, v)),
-            _ => None,
+    pub fn into_kv(self) -> (&'a K, &'a V) {
+        let (keys, vals) = self.node.into_slices();
+        unsafe {
+            (keys.get_unchecked(self.idx), vals.get_unchecked(self.idx))
         }
     }
+}
 
-    fn next_kv_back(&mut self) -> Option<(K, V)> {
-        match (self.keys.next_back(), self.vals.next_back()) {
-            (Some(k), Some(v)) => Some((k, v)),
-            _ => None,
-        }
-    }
+impl<'a, K: 'a, V: 'a, NodeType>
+        Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
 
-    fn next_edge(&mut self) -> Option<Node<K, V>> {
-        // Necessary for correctness, but in a private module
-        debug_assert!(!self.is_leaf);
-        self.edges.next()
+    pub fn into_kv_mut(self) -> (&'a mut K, &'a mut V) {
+        let (mut keys, mut vals) = self.node.into_slices_mut();
+        unsafe {
+            (keys.get_unchecked_mut(self.idx), vals.get_unchecked_mut(self.idx))
+        }
     }
+}
 
-    fn next_edge_back(&mut self) -> Option<Node<K, V>> {
-        // Necessary for correctness, but in a private module
-        debug_assert!(!self.is_leaf);
-        self.edges.next_back()
+impl<'a, K, V, NodeType> Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV> {
+    pub fn kv_mut(&mut self) -> (&mut K, &mut V) {
+        unsafe {
+            let (mut keys, mut vals) = self.node.reborrow_mut().into_slices_mut();
+            (keys.get_unchecked_mut(self.idx), vals.get_unchecked_mut(self.idx))
+        }
     }
 }
 
-impl<K, V> Drop for MoveTraversalImpl<K, V> {
-    #[unsafe_destructor_blind_to_params]
-    fn drop(&mut self) {
-        // We need to cleanup the stored values manually, as the RawItems destructor would run
-        // after our deallocation.
-        for _ in self.keys.by_ref() {}
-        for _ in self.vals.by_ref() {}
-        for _ in self.edges.by_ref() {}
+impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::KV> {
+    pub fn split(mut self)
+            -> (NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, K, V, Root<K, V>) {
+        unsafe {
+            let mut new_node = Box::new(LeafNode::new());
+
+            let k = ptr::read(self.node.keys().get_unchecked(self.idx));
+            let v = ptr::read(self.node.vals().get_unchecked(self.idx));
+
+            let new_len = self.node.len() - self.idx - 1;
+
+            ptr::copy_nonoverlapping(
+                self.node.keys().as_ptr().offset(self.idx as isize + 1),
+                new_node.keys.as_mut_ptr(),
+                new_len
+            );
+            ptr::copy_nonoverlapping(
+                self.node.vals().as_ptr().offset(self.idx as isize + 1),
+                new_node.vals.as_mut_ptr(),
+                new_len
+            );
+
+            self.node.as_leaf_mut().len = self.idx as u16;
+            new_node.len = new_len as u16;
+
+            (
+                self.node,
+                k, v,
+                Root {
+                    node: BoxedNode::from_leaf(new_node),
+                    height: 0
+                }
+            )
+        }
+    }
 
-        let (alignment, size) = calculate_allocation_generic::<K, V>(self.capacity, self.is_leaf);
-        unsafe { heap::deallocate(*self.ptr, size, alignment) };
+    pub fn remove(mut self)
+            -> (Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>, K, V) {
+        unsafe {
+            let k = slice_remove(self.node.keys_mut(), self.idx);
+            let v = slice_remove(self.node.vals_mut(), self.idx);
+            self.node.as_leaf_mut().len -= 1;
+            (self.left_edge(), k, v)
+        }
     }
 }
 
-/// An abstraction over all the different kinds of traversals a node supports
-#[derive(Clone)]
-pub struct AbsTraversal<Impl> {
-    inner: Impl,
-    head_is_edge: bool,
-    tail_is_edge: bool,
-    has_edges: bool,
-}
+impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::KV> {
+    pub fn split(mut self)
+            -> (NodeRef<marker::Mut<'a>, K, V, marker::Internal>, K, V, Root<K, V>) {
+        unsafe {
+            let mut new_node = Box::new(InternalNode::new());
+
+            let k = ptr::read(self.node.keys().get_unchecked(self.idx));
+            let v = ptr::read(self.node.vals().get_unchecked(self.idx));
+
+            let height = self.node.height;
+            let new_len = self.node.len() - self.idx - 1;
+
+            ptr::copy_nonoverlapping(
+                self.node.keys().as_ptr().offset(self.idx as isize + 1),
+                new_node.data.keys.as_mut_ptr(),
+                new_len
+            );
+            ptr::copy_nonoverlapping(
+                self.node.vals().as_ptr().offset(self.idx as isize + 1),
+                new_node.data.vals.as_mut_ptr(),
+                new_len
+            );
+            ptr::copy_nonoverlapping(
+                self.node.as_internal().edges.as_ptr().offset(self.idx as isize + 1),
+                new_node.edges.as_mut_ptr(),
+                new_len + 1
+            );
+
+            self.node.as_leaf_mut().len = self.idx as u16;
+            new_node.data.len = new_len as u16;
+
+            let mut new_root = Root {
+                node: BoxedNode::from_internal(new_node),
+                height: height
+            };
 
-/// A single atomic step in a traversal.
-pub enum TraversalItem<K, V, E> {
-    /// An element is visited. This isn't written as `Elem(K, V)` just because `opt.map(Elem)`
-    /// requires the function to take a single argument. (Enum constructors are functions.)
-    Elem((K, V)),
-    /// An edge is followed.
-    Edge(E),
-}
+            for i in 0..(new_len+1) {
+                Handle::new_edge(new_root.as_mut().cast_unchecked(), i).correct_parent_link();
+            }
 
-/// A traversal over a node's entries and edges
-pub type Traversal<'a, K, V> = AbsTraversal<ElemsAndEdges<Zip<slice::Iter<'a, K>,
-                                                              slice::Iter<'a, V>>,
-                                                          slice::Iter<'a, Node<K, V>>>>;
+            (
+                self.node,
+                k, v,
+                new_root
+            )
+        }
+    }
 
-/// A mutable traversal over a node's entries and edges
-pub type MutTraversal<'a, K, V> = AbsTraversal<ElemsAndEdges<Zip<slice::Iter<'a, K>,
-                                                                 slice::IterMut<'a, V>>,
-                                                             slice::IterMut<'a, Node<K, V>>>>;
+    pub fn can_merge(&self) -> bool {
+        (
+            self.reborrow()
+                .left_edge()
+                .descend()
+                .len()
+          + self.reborrow()
+                .right_edge()
+                .descend()
+                .len()
+          + 1
+        ) <= CAPACITY
+    }
+
+    pub fn merge(mut self)
+            -> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, marker::Edge> {
+        let self1 = unsafe { ptr::read(&self) };
+        let self2 = unsafe { ptr::read(&self) };
+        let mut left_node = self1.left_edge().descend();
+        let left_len = left_node.len();
+        let mut right_node = self2.right_edge().descend();
+        let right_len = right_node.len();
+
+        // necessary for correctness, but in a private module
+        debug_assert!(left_len + right_len + 1 <= CAPACITY);
 
-/// An owning traversal over a node's entries and edges
-pub type MoveTraversal<K, V> = AbsTraversal<MoveTraversalImpl<K, V>>;
+        unsafe {
+            ptr::write(left_node.keys_mut().get_unchecked_mut(left_len),
+                       slice_remove(self.node.keys_mut(), self.idx));
+            ptr::copy_nonoverlapping(
+                right_node.keys().as_ptr(),
+                left_node.keys_mut().as_mut_ptr().offset(left_len as isize + 1),
+                right_len
+            );
+            ptr::write(left_node.vals_mut().get_unchecked_mut(left_len),
+                       slice_remove(self.node.vals_mut(), self.idx));
+            ptr::copy_nonoverlapping(
+                right_node.vals().as_ptr(),
+                left_node.vals_mut().as_mut_ptr().offset(left_len as isize + 1),
+                right_len
+            );
+
+            slice_remove(&mut self.node.as_internal_mut().edges, self.idx + 1);
+            for i in self.idx+1..self.node.len() {
+                Handle::new_edge(self.node.reborrow_mut(), i).correct_parent_link();
+            }
+            self.node.as_leaf_mut().len -= 1;
+
+            if self.node.height > 1 {
+                ptr::copy_nonoverlapping(
+                    right_node.cast_unchecked().as_internal().edges.as_ptr(),
+                    left_node.cast_unchecked()
+                             .as_internal_mut()
+                             .edges
+                             .as_mut_ptr()
+                             .offset(left_len as isize + 1),
+                    right_len + 1
+                );
+
+                for i in left_len+1..left_len+right_len+2 {
+                    Handle::new_edge(
+                        left_node.cast_unchecked().reborrow_mut(),
+                        i
+                    ).correct_parent_link();
+                }
 
+                heap::deallocate(
+                    *right_node.node as *mut u8,
+                    mem::size_of::<InternalNode<K, V>>(),
+                    mem::align_of::<InternalNode<K, V>>()
+                );
+            } else {
+                heap::deallocate(
+                    *right_node.node as *mut u8,
+                    mem::size_of::<LeafNode<K, V>>(),
+                    mem::align_of::<LeafNode<K, V>>()
+                );
+            }
 
-impl<K, V, E, Impl> Iterator for AbsTraversal<Impl>
-    where Impl: TraversalImpl<Item = (K, V), Edge = E>
-{
-    type Item = TraversalItem<K, V, E>;
+            left_node.as_leaf_mut().len += right_len as u16 + 1;
 
-    fn next(&mut self) -> Option<TraversalItem<K, V, E>> {
-        self.next_edge_item().map(Edge).or_else(|| self.next_kv_item().map(Elem))
+            Handle::new_edge(self.node, self.idx)
+        }
     }
 }
 
-impl<K, V, E, Impl> DoubleEndedIterator for AbsTraversal<Impl>
-    where Impl: TraversalImpl<Item = (K, V), Edge = E>
-{
-    fn next_back(&mut self) -> Option<TraversalItem<K, V, E>> {
-        self.next_edge_item_back().map(Edge).or_else(|| self.next_kv_item_back().map(Elem))
+impl<BorrowType, K, V, HandleType>
+        Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, HandleType> {
+
+    pub fn force(self) -> ForceResult<
+        Handle<NodeRef<BorrowType, K, V, marker::Leaf>, HandleType>,
+        Handle<NodeRef<BorrowType, K, V, marker::Internal>, HandleType>
+    > {
+        match self.node.force() {
+            ForceResult::Leaf(node) => ForceResult::Leaf(Handle {
+                node: node,
+                idx: self.idx,
+                _marker: PhantomData
+            }),
+            ForceResult::Internal(node) => ForceResult::Internal(Handle {
+                node: node,
+                idx: self.idx,
+                _marker: PhantomData
+            })
+        }
     }
 }
 
-impl<K, V, E, Impl> AbsTraversal<Impl> where Impl: TraversalImpl<Item = (K, V), Edge = E> {
-    /// Advances the iterator and returns the item if it's an edge. Returns None
-    /// and does nothing if the first item is not an edge.
-    pub fn next_edge_item(&mut self) -> Option<E> {
-        // NB. `&& self.has_edges` might be redundant in this condition.
-        let edge = if self.head_is_edge && self.has_edges {
-            self.inner.next_edge()
-        } else {
-            None
-        };
-        self.head_is_edge = false;
-        edge
-    }
-
-    /// Advances the iterator and returns the item if it's an edge. Returns None
-    /// and does nothing if the last item is not an edge.
-    pub fn next_edge_item_back(&mut self) -> Option<E> {
-        let edge = if self.tail_is_edge && self.has_edges {
-            self.inner.next_edge_back()
-        } else {
-            None
-        };
-        self.tail_is_edge = false;
-        edge
-    }
-
-    /// Advances the iterator and returns the item if it's a key-value pair. Returns None
-    /// and does nothing if the first item is not a key-value pair.
-    pub fn next_kv_item(&mut self) -> Option<(K, V)> {
-        if !self.head_is_edge {
-            self.head_is_edge = true;
-            self.inner.next_kv()
-        } else {
-            None
-        }
-    }
+pub enum ForceResult<Leaf, Internal> {
+    Leaf(Leaf),
+    Internal(Internal)
+}
 
-    /// Advances the iterator and returns the item if it's a key-value pair. Returns None
-    /// and does nothing if the last item is not a key-value pair.
-    pub fn next_kv_item_back(&mut self) -> Option<(K, V)> {
-        if !self.tail_is_edge {
-            self.tail_is_edge = true;
-            self.inner.next_kv_back()
-        } else {
-            None
-        }
-    }
+pub enum InsertResult<'a, K, V, Type> {
+    Fit(Handle<NodeRef<marker::Mut<'a>, K, V, Type>, marker::KV>),
+    Split(NodeRef<marker::Mut<'a>, K, V, Type>, K, V, Root<K, V>)
 }
 
-macro_rules! node_slice_impl {
-    ($NodeSlice:ident, $Traversal:ident,
-     $as_slices_internal:ident, $index:ident, $iter:ident) => {
-        impl<'a, K: Ord + 'a, V: 'a> $NodeSlice<'a, K, V> {
-            /// Performs linear search in a slice. Returns a tuple of (index, is_exact_match).
-            fn search_linear<Q: ?Sized>(&self, key: &Q) -> (usize, bool)
-                    where K: Borrow<Q>, Q: Ord {
-                for (i, k) in self.keys.iter().enumerate() {
-                    match key.cmp(k.borrow()) {
-                        Greater => {},
-                        Equal => return (i, true),
-                        Less => return (i, false),
-                    }
-                }
-                (self.keys.len(), false)
-            }
+pub mod marker {
+    use core::marker::PhantomData;
 
-            /// Returns a sub-slice with elements starting with `min_key`.
-            pub fn slice_from<Q: ?Sized + Ord>(self, min_key: &Q) -> $NodeSlice<'a, K, V> where
-                K: Borrow<Q>,
-            {
-                //  _______________
-                // |_1_|_3_|_5_|_7_|
-                // |   |   |   |   |
-                // 0 0 1 1 2 2 3 3 4  index
-                // |   |   |   |   |
-                // \___|___|___|___/  slice_from(&0); pos = 0
-                //     \___|___|___/  slice_from(&2); pos = 1
-                //     |___|___|___/  slice_from(&3); pos = 1; result.head_is_edge = false
-                //         \___|___/  slice_from(&4); pos = 2
-                //             \___/  slice_from(&6); pos = 3
-                //                \|/ slice_from(&999); pos = 4
-                let (pos, pos_is_kv) = self.search_linear(min_key);
-                $NodeSlice {
-                    has_edges: self.has_edges,
-                    edges: if !self.has_edges {
-                        self.edges
-                    } else {
-                        self.edges.$index(pos ..)
-                    },
-                    keys: &self.keys[pos ..],
-                    vals: self.vals.$index(pos ..),
-                    head_is_edge: !pos_is_kv,
-                    tail_is_edge: self.tail_is_edge,
-                }
-            }
+    pub enum Leaf { }
+    pub enum Internal { }
+    pub enum LeafOrInternal { }
 
-            /// Returns a sub-slice with elements up to and including `max_key`.
-            pub fn slice_to<Q: ?Sized + Ord>(self, max_key: &Q) -> $NodeSlice<'a, K, V> where
-                K: Borrow<Q>,
-            {
-                //  _______________
-                // |_1_|_3_|_5_|_7_|
-                // |   |   |   |   |
-                // 0 0 1 1 2 2 3 3 4  index
-                // |   |   |   |   |
-                //\|/  |   |   |   |  slice_to(&0); pos = 0
-                // \___/   |   |   |  slice_to(&2); pos = 1
-                // \___|___|   |   |  slice_to(&3); pos = 1; result.tail_is_edge = false
-                // \___|___/   |   |  slice_to(&4); pos = 2
-                // \___|___|___/   |  slice_to(&6); pos = 3
-                // \___|___|___|___/  slice_to(&999); pos = 4
-                let (pos, pos_is_kv) = self.search_linear(max_key);
-                let pos = pos + if pos_is_kv { 1 } else { 0 };
-                $NodeSlice {
-                    has_edges: self.has_edges,
-                    edges: if !self.has_edges {
-                        self.edges
-                    } else {
-                        self.edges.$index(.. (pos + 1))
-                    },
-                    keys: &self.keys[..pos],
-                    vals: self.vals.$index(.. pos),
-                    head_is_edge: self.head_is_edge,
-                    tail_is_edge: !pos_is_kv,
-                }
-            }
-        }
+    pub enum Owned { }
+    pub struct Immut<'a>(PhantomData<&'a ()>);
+    pub struct Mut<'a>(PhantomData<&'a mut ()>);
 
-        impl<'a, K: 'a, V: 'a> $NodeSlice<'a, K, V> {
-            /// Returns an iterator over key/value pairs and edges in a slice.
-            #[inline]
-            pub fn $iter(self) -> $Traversal<'a, K, V> {
-                let mut edges = self.edges.$iter();
-                // Skip edges at both ends, if excluded.
-                if !self.head_is_edge { edges.next(); }
-                if !self.tail_is_edge { edges.next_back(); }
-                // The key iterator is always immutable.
-                $Traversal {
-                    inner: ElemsAndEdges(
-                        self.keys.iter().zip(self.vals.$iter()),
-                        edges
-                    ),
-                    head_is_edge: self.head_is_edge,
-                    tail_is_edge: self.tail_is_edge,
-                    has_edges: self.has_edges,
-                }
-            }
-        }
-    }
+    pub enum KV { }
+    pub enum Edge { }
 }
 
-node_slice_impl!(NodeSlice, Traversal, as_slices_internal, index, iter);
-node_slice_impl!(MutNodeSlice, MutTraversal, as_slices_internal_mut, index_mut, iter_mut);
+unsafe fn slice_insert<T>(slice: &mut [T], idx: usize, val: T) {
+    ptr::copy(
+        slice.as_ptr().offset(idx as isize),
+        slice.as_mut_ptr().offset(idx as isize + 1),
+        slice.len() - idx
+    );
+    ptr::write(slice.get_unchecked_mut(idx), val);
+}
+
+unsafe fn slice_remove<T>(slice: &mut [T], idx: usize) -> T {
+    let ret = ptr::read(slice.get_unchecked(idx));
+    ptr::copy(
+        slice.as_ptr().offset(idx as isize + 1),
+        slice.as_mut_ptr().offset(idx as isize),
+        slice.len() - idx - 1
+    );
+    ret
+}
diff --git a/src/libcollections/btree/search.rs b/src/libcollections/btree/search.rs
new file mode 100644
index 00000000000..c94b570bfed
--- /dev/null
+++ b/src/libcollections/btree/search.rs
@@ -0,0 +1,76 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use core::cmp::Ordering;
+
+use borrow::Borrow;
+
+use super::node::{Handle, NodeRef, marker};
+
+use super::node::ForceResult::*;
+use self::SearchResult::*;
+
+pub enum SearchResult<BorrowType, K, V, FoundType, GoDownType> {
+    Found(Handle<NodeRef<BorrowType, K, V, FoundType>, marker::KV>),
+    GoDown(Handle<NodeRef<BorrowType, K, V, GoDownType>, marker::Edge>)
+}
+
+pub fn search_tree<BorrowType, K, V, Q: ?Sized>(
+    mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
+    key: &Q
+) -> SearchResult<BorrowType, K, V, marker::LeafOrInternal, marker::Leaf>
+        where Q: Ord, K: Borrow<Q> {
+
+    loop {
+        match search_node(node, key) {
+            Found(handle) => return Found(handle),
+            GoDown(handle) => match handle.force() {
+                Leaf(leaf) => return GoDown(leaf),
+                Internal(internal) => {
+                    node = internal.descend();
+                    continue;
+                }
+            }
+        }
+    }
+}
+
+pub fn search_node<BorrowType, K, V, Type, Q: ?Sized>(
+    node: NodeRef<BorrowType, K, V, Type>,
+    key: &Q
+) -> SearchResult<BorrowType, K, V, Type, Type>
+        where Q: Ord, K: Borrow<Q> {
+
+    match search_linear(&node, key) {
+        (idx, true) => Found(
+            Handle::new_kv(node, idx)
+        ),
+        (idx, false) => SearchResult::GoDown(
+            Handle::new_edge(node, idx)
+        )
+    }
+}
+
+fn search_linear<BorrowType, K, V, Type, Q: ?Sized>(
+    node: &NodeRef<BorrowType, K, V, Type>,
+    key: &Q
+) -> (usize, bool)
+        where Q: Ord, K: Borrow<Q> {
+
+    for (i, k) in node.keys().iter().enumerate() {
+        match key.cmp(k.borrow()) {
+            Ordering::Greater => {},
+            Ordering::Equal => return (i, true),
+            Ordering::Less => return (i, false)
+        }
+    }
+    (node.keys().len(), false)
+}
+
diff --git a/src/libcollections/lib.rs b/src/libcollections/lib.rs
index 8b876df32af..41f52b67079 100644
--- a/src/libcollections/lib.rs
+++ b/src/libcollections/lib.rs
@@ -43,8 +43,8 @@
 #![feature(iter_arith)]
 #![feature(iter_arith)]
 #![feature(lang_items)]
+#![feature(nonzero)]
 #![feature(num_bits_bytes)]
-#![feature(oom)]
 #![feature(pattern)]
 #![feature(shared)]
 #![feature(slice_bytes)]
@@ -55,7 +55,7 @@
 #![feature(unboxed_closures)]
 #![feature(unicode)]
 #![feature(unique)]
-#![feature(unsafe_no_drop_flag, filling_drop)]
+#![feature(unsafe_no_drop_flag)]
 #![cfg_attr(test, feature(clone_from_slice, rand, test))]
 
 #![no_std]
diff --git a/src/libcollectionstest/btree/map.rs b/src/libcollectionstest/btree/map.rs
index dfb72d78d46..c4473b64066 100644
--- a/src/libcollectionstest/btree/map.rs
+++ b/src/libcollectionstest/btree/map.rs
@@ -346,6 +346,38 @@ fn test_bad_zst() {
     }
 }
 
+#[test]
+fn test_clone() {
+    let mut map = BTreeMap::new();
+    let size = 100;
+    assert_eq!(map.len(), 0);
+
+    for i in 0..size {
+        assert_eq!(map.insert(i, 10*i), None);
+        assert_eq!(map.len(), i + 1);
+        assert_eq!(map, map.clone());
+    }
+
+    for i in 0..size {
+        assert_eq!(map.insert(i, 100*i), Some(10*i));
+        assert_eq!(map.len(), size);
+        assert_eq!(map, map.clone());
+    }
+
+    for i in 0..size/2 {
+        assert_eq!(map.remove(&(i*2)), Some(i*200));
+        assert_eq!(map.len(), size - i - 1);
+        assert_eq!(map, map.clone());
+    }
+
+    for i in 0..size/2 {
+        assert_eq!(map.remove(&(2*i)), None);
+        assert_eq!(map.remove(&(2*i+1)), Some(i*200 + 100));
+        assert_eq!(map.len(), size/2 - i - 1);
+        assert_eq!(map, map.clone());
+    }
+}
+
 mod bench {
     use std::collections::BTreeMap;
     use std::__rand::{Rng, thread_rng};