      (last ks1)
      (leaf-node b m2 (- partition-size (rem size 2)))]))
 
-(defn- lnode-ins [{:keys [b m size] :as n} k v]
+#_(defn- lnode-ins [{:keys [b m size] :as n} k v]
   (let [nm (assoc m k v)]
     #_(println "LINS" nm)
     (leaf-node b nm (inc size))))
 
-(defn- lnode-insert [{:keys [b m] :as n} k v]
+#_(defn- lnode-insert [{:keys [b m] :as n} k v]
   (let [nn (lnode-ins n k v)]
     (if (>= (-> nn :m count) b)
       (lnode-split nn)
       [nn])))
 
 
-(defn- node? [{:keys [type] :as n}]
+#_(defn- node? [{:keys [type] :as n}]
   (or (= type :internal)
       (= type :leaf)))
 
 
-(defn- insert* [{:keys [type] :as n} k v]
+#_(defn- insert* [{:keys [type] :as n} k v]
   (case type
     :internal (inode-insert n k v)
     :leaf     (lnode-insert n k v)))
 
-(defn- lookup* [{:keys [type] :as n} k]
+#_(defn- lookup* [{:keys [type] :as n} k]
   #_(print "L")
   (case type
     :internal (inode-lookup n k)
     :leaf     (lnode-lookup n k)))
 
-(defn insert [{:keys [b] :as n} k v]
+#_(defn insert [{:keys [b] :as n} k v]
   #_(println "=== INSERT ===")
   (let [[n1 k n2] (insert* n k v)]
     (if (nil? n2)
       n1
       (internal-node b [k] [n1 n2] 1))))
 
-(defn lookup [n k]
+#_(defn lookup [n k]
   #_(println "=== LOOKUP ===")
   (loop [[_ v] (lookup* n k)]
     (if (node? v)
       (recur (lookup* v k))
       v)))
 
-(defn tree [b]
-  (leaf-node b))
-
-
-#_(-> (tree 3)
+
+(defrecord B+TreeInternalNode [b size ks vs]
+
+  TreeModify
+
+  (insert [this k v]
+    (letfn [(split [{:keys [b ks vs size] :as n}]
+              (let [partition-size  (-> size (/ 2) Math/ceil int)
+                    [ks1 ks2]       (partition-all partition-size ks)
+                    [ks1 nk]        [(butlast ks1) (last ks1)]
+                    [vs1 vs2a vs2b] (partition-all partition-size vs)
+                    vs2             (concat vs2a vs2b)]
+                [(->B+TreeInternalNode b (dec partition-size) ks1 vs1)
+                 nk
+                 (->B+TreeInternalNode b (- partition-size (rem size 2)) ks2 vs2)]))
+
+            (ins [{:keys [b ks vs size] :as n} k v]
+              (if-not (= k ::inf)
+                (let [[ks1 ks2] (split-with #(< (compare % k) 0) ks)
+                      [vs1 vs2] (split-at (count ks1) vs)
+                      replace?  (= (compare (first ks2) k) 0)
+                      ks2       (if replace? (rest ks2) ks2)
+                      vs2       (if replace? (rest vs2) vs2)
+                      nsize     (if replace? size (inc size))
+                      nks       (concat ks1 [k] ks2)
+                      nvs       (concat vs1 [v] vs2)]
+                  (->B+TreeInternalNode b nsize nks nvs))
+                (let [nvs (-> vs butlast (concat [v]))]
+                  (->B+TreeInternalNode b size ks nvs))))]
+
+      (let [[childk childv] (lookup this k)
+            [n1 nk n2]      (insert childv k v)
+            nn              (if (nil? n2)
+                              (ins this childk n1)
+                              (-> (ins this nk n1)
+                                  (ins childk n2)))]
+        (if (>= (-> nn :size) b)
+          (split nn)
+          [nn]))))
+
+  TreeLookup
+
+  (lookup [this k]
+    (loop [[k* & ks*] ks
+           [v* & vs*] vs]
+      (cond
+        (nil? k*)             [::inf v*]
+        (<= (compare k k*) 0) [k* v*]
+        true                  (recur ks* vs*)))))
+
+
+(defrecord B+TreeLeafNode [b size m]
+
+  TreeModify
+
+  (insert [this k v]
+    (letfn [(split [{:keys [b m size] :as n}]
+              (let [partition-size (-> size (/ 2) Math/ceil int)
+                    [ks1 ks2] (partition-all partition-size (keys m))
+                    m1 (apply dissoc m ks2)
+                    m2 (apply dissoc m ks1)]
+                [(->B+TreeLeafNode b partition-size m1)
+                 (last ks1)
+                 (->B+TreeLeafNode b (- partition-size (rem size 2)) m2)]))
+
+            (ins [{:keys [b m size] :as n} k v]
+              (let [nm (assoc m k v)]
+                (->B+TreeLeafNode b (inc size) nm)))]
+
+      (let [nn (ins this k v)]
+        (if (>= (-> nn :size) b)
+          (split nn)
+          [nn]))))
+
+  TreeLookup
+
+  (lookup [this k]
+    [k (get m k)]))
+
+
+(defrecord B+Tree [b root]
+
+  TreeModify
+
+  (insert [this k v]
+    (let [[n1 k n2] (insert root k v)
+          nroot (if (nil? n2)
+                  n1
+                  (->B+TreeInternalNode b 1 [k] [n1 n2]))]
+      (->B+Tree b nroot)))
+
+  TreeLookup
+
+  (lookup [this k]
+    (loop [[_ v] (lookup root k)]
+      (if (satisfies? TreeLookup v)
+        (recur (lookup v k))
+        v))))
+
+
+(defn b+tree [b]
+  (->B+Tree b (->B+TreeLeafNode b 0 (sorted-map))))
+
+
+#_(-> (b+tree 3)
     (insert 5 55)
     (insert 9 99)
     (insert 3 33)

      (<= (compare k k*) 0) [k* v*]
      true                  (recur ks* vs*))))

(defn- inode-split [{:keys [b ks vs size] :as n}]
  (let [partition-size  (-> size (/ 2) Math/ceil int)
        [ks1 ks2]       (partition-all partition-size ks)
        [ks1 nk]        [(butlast ks1) (last ks1)]


  TreeSearch

  (lookup [this k]
    (when-let [child (get children k)]
      (if (satisfies? TreeSearch child)
        (lookup child k)
        child))))


#_(defn b+tree [b]
  (->B+TreeNode b 0 (sorted-map) true))
