 ;; resulting node would be empty. The resulting candidate node may have any
 ;; number of children, meaning it can either underflow, be valid, or overflow,
 ;; depending on the changes applied.
-
-,,,
-
-
+;;
+;;              ..O..
+;;             /     \
+;;            /       \
+;;           O        .O.
+;;          / \      / | \
+;;         O   O    O  O  O
+;;        /|\  |\  /|\/|\/ \
+;;     > x x[U]# # ####### #
+;;
+;; When a node has only a single child, it is 'pulled' up the tree recursively
+;; so it can be passed down the next branch for merging into the next branch.
+;;
+;;              ..O..
+;;             /     \
+;;            /       \
+;;           O        .O.
+;;          / \      / | \
+;;     >  [U]  O    O  O  O
+;;             |\  /|\/|\/ \
+;;             # # ####### #
+;;
+;;              ..O..
+;;             /     \
+;;            /       \
+;;     >    [O](U)    .O.
+;;           |       / | \
+;;           O      O  O  O
+;;          / \    /|\/|\/ \
+;;         #   #   ####### #
+;;
+;; When a subtree is being passed to the next branch, and the current node's
+;; height is one more than the subtree root, insert it as a child of the
+;; current node:
+;;
+;;              ..O..
+;;             /     \
+;;            /       \
+;;           O        .O.
+;;           |       / | \
+;;     >    [*]     O  O  O
+;;          /|\    /|\/|\/ \
+;;        (U)# #   ####### #
+;;
+;;              ..O..
+;;             /     \
+;;            /       \
+;;           O        .O.
+;;           |       / | \
+;;           *      O  O  O
+;;          /|\    /|\/|\/ \
+;;     >   U x[U]  ####### #
+;;
 ;; ### Redistribute Children
 ;;
 ;; In the **distribution** phase, any candidate children which have over or

;; - The "parent" is the current top level node we're recursing on.
;; - The "children" are the direct descendants of the parent node.
;; - The "candidates" are changed but unstored descendant nodes.


;; ### Divide Changes
;;
;; In the first **downward** phase, changes at the parent are grouped by the
;; child which links to the subtree containing the referenced keys.

,,,


;; of valid nodes. Otherwise, resolve the last link before the run and add it
;; to the pool to redistribute. Use the link after if the run includes the
;; first child.
;;
;; Two underflowing partitions need to be merged, but still form an
;; underflowing partition:
;;
;;              ..O..
;;             /     \
;;            /       \
;;           O        .O.
;;           |       / | \
;;           *      O  O  O
;;           |     /|\/|\/ \
;;     >  [->U<-]  ####### #
;;
;;              ..O..
;;             /     \
;;            /       \
;;           O        .O.
;;           |       / | \
;;     >    [U]     O  O  O
;;                 /|\/|\/ \
;;                 ####### #
;;
;;              ..O..
;;             /     \
;;            /       \
;;     >    [U]       .O.
;;                   / | \
;;                  O  O  O
;;                 /|\/|\/ \
;;                 ####### #
;;
;;     >       [O](U)
;;              |
;;            ..O..
;;           /  |  \
;;          O   O   O
;;         /|\ /|\ / \
;;         ### ### # #
;;
;;              O
;;              |
;;     >      .[O]. (U)
;;           /  |  \
;;          O   O   O
;;         /|\ /|\ / \
;;         ### ### # #
;;
;;              O
;;              |
;;            ..O..
;;           /  |  \
;;     >   [O]  O   O
;;        // \\/|\ / \
;;        U# U@### # #
;;
;; Again, redistribute the records in the underflowing partitions.
;;
;;              O
;;              |
;;            ..O..
;;           /  |  \
;;          O   O   O
;;         /|\ /|\ / \
;;     >  [@@@]### # #
;;
;;              O
;;              |
;;            ..O..
;;           /  |  \
;;     >   [*]  O   O
;;         /|\ /|\ / \
;;         @@@ ### # #
;;
;;              O
;;              |
;;     >      .[*].
;;           /  |  \
;;          *   O   O
;;         /|\ /|\ / \
;;         @@@ ### # #
;;
;; Fast forward, deleting a subtree...
;;
;;              O
;;              |
;;            ..*..
;;           /  |  \
;;     >    *  [x]  O
;;         /|\ /|\ / \
;;     >   @@@[xxx]# #
;;
;; Insert nodes into right subtree, resulting in splitting multiple partitions.
;;
;;              O
;;              |
;;            ..*..
;;           /     \
;;          *       *
;;         /|\    //|\\
;;     >  @ @ @  [#@@@@]
;;
;; Back to distribution phase, fix overflow by splitting the node:
;;              O
;;              |
;;            ..*..
;;           /  |  \
;;     >    *  [*   *]
;;         /|\ / \ /|\
;;         @@@ # @ @@@
;;
;;              *
;;              |
;;     >      .[*].
;;           /  |  \
;;          *   *   *
;;         /|\ / \ /|\
;;         @@@ # @ @@@
;;
;;     >       [*]
;;              |
;;            ..*..
;;           /  |  \
;;          *   *   *
;;         /|\ / \ /|\
;;         @@@ # @ @@@
;;
;; Now that we're back at the root, we can serialize out the resulting tree.
;;
;;              *
;;              |
;;     >      .[+].
;;           /  |  \
;;          +   +   +
;;         /|\ / \ /|\
;;         @@@ # @ @@@
;;
;; If the upward recursion reaches a branch with a single child, we're on a path
;; up to the root, so return the subtree directly, decreasing the height of the
;; tree.
;;
;;     >       [*]
;;              |
;;            ..+..
;;           /  |  \
;;          +   +   +
;;         /|\ / \ /|\
;;         @@@ # @ @@@
;;
;; Resulting balanced tree:
;;
;;            ..+..
;;           /  |  \
;;          +   +   +
;;         /|\ / \ /|\
;;         @@@ # @ @@@


;; ### References
;;
;; https://pdfs.semanticscholar.org/85eb/4cf8dfd51708418881e2b5356d6778645a1a.pdf
;; Insight: instead of flushing all the updates, select a related subgroup that
;; minimizes repeated changes to the same node path.


(defn build-index
  "Given a sequence of partitions, builds an index tree with the given
