         children.append(left)
         children.append(right)
         count = left.count + right.count + 1
-    }
-
-    private mutating func insertAndSplit(key: Key, _ payload: Payload) -> (separator: (Key, Payload), splinter: BTree<Key, Payload>)? {
-        count += 1
-        let slot = slotOf(key).index
+        return old
+    }
+
+    private mutating func insertAndSplit(key: Key, _ payload: Payload, replace: Bool) -> (old: Payload?, (separator: (Key, Payload), splinter: BTree<Key, Payload>)?) {
+        let slot = slotOf(key)
+        if slot.match && replace {
+            let old = payloads[slot.index]
+            keys[slot.index] = key
+            payloads[slot.index] = payload
+            return (old, nil)
+        }
         if isLeaf {
-            keys.insert(key, atIndex: slot)
-            payloads.insert(payload, atIndex: slot)
-        }
-        else {
-            guard let (separator, splinter) = children[slot].insertAndSplit(key, payload) else { return nil }
-            keys.insert(separator.0, atIndex: slot)
-            payloads.insert(separator.1, atIndex: slot)
-            children.insert(splinter, atIndex: slot + 1)
-        }
-        return isTooLarge ? split() : nil
+            keys.insert(key, atIndex: slot.index)
+            payloads.insert(payload, atIndex: slot.index)
+            count += 1
+            return (nil, (isTooLarge ? split() : nil))
+        }
+
+        let (old, splinter) = children[slot.index].insertAndSplit(key, payload, replace: replace)
+        if old == nil {
+            count += 1
+        }
+        guard let (separator, right) = splinter else { return (old, nil) }
+        keys.insert(separator.0, atIndex: slot.index)
+        payloads.insert(separator.1, atIndex: slot.index)
+        children.insert(right, atIndex: slot.index + 1)
+        return (old, (isTooLarge ? split() : nil))
     }
 
     private mutating func split() -> (separator: (Key, Payload), splinter: BTree<Key, Payload>) {

    }
}

//MARK: Internal limits and properties

extension BTree {

    internal var isTooSmall: Bool { return keys.count < minKeys }
    internal var isTooLarge: Bool { return keys.count > maxKeys }
    internal var isBalanced: Bool { return keys.count >= minKeys && keys.count <= maxKeys }

    internal var depth: Int {
        var depth = 0
        var node = self
        while !node.isLeaf {
            node = node.children[0]
            depth += 1
        }
        return depth
    }
}

//MARK: Lookup
