 
   TreeSearch
 
-  (search [this k]
+  (lookup [this k]
     (when-let [child (get children k)]
       (if (satisfies? TreeSearch child)
-        (search child k)
+        (lookup child k)
         child))))
 
 
-(defn b+tree [b]
+#_(defn b+tree [b]
   (->B+TreeNode b 0 (sorted-map) true))

     (last ks1)
     (leaf-node b m2 (- partition-size (rem size 2)))]))

(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]
  (let [nn (lnode-ins n k v)]
    (if (>= (-> nn :m count) b)
      (lnode-split nn)
      [nn])))


(defn- node? [{:keys [type] :as n}]
  (or (= type :internal)
      (= type :leaf)))


(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]
  #_(print "L")
  (case type
    :internal (inode-lookup n k)
    :leaf     (lnode-lookup n k)))

(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]
  #_(println "=== LOOKUP ===")
  (loop [[_ v] (lookup* n k)]
    (if (node? v)
      (recur (lookup* v k))
      v)))

(defn tree [b]
  (leaf-node 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)]
