 ;; - 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.
-
+;;
+;; The batch-update algorithm has the following goals:
+;; - **Log scaling:** visit `O(log_b(n))` nodes for `n` nodes updated.
+;; - **Minimize garbage:** avoid storing nodes which are not part of the final
+;;   tree.
+;; - **Deduplication:** reuse existing stored nodes where possible.
+;;
+;; In the following diagrams, these symbols are used:
+;; - `O` - unchanged index node
+;; - `*` - candidate index node
+;; - `+` - persisted index node
+;; - `#` - unchanged partition leaf
+;; - `@` - persisted partition leaf
+;; - `U` - underflowing partition leaf
+;; - `x` - node which has had all children deleted
 
 ;; ### 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.
+;;
+;;     >        .[O].         [????|?????]
+;;             /     \
+;;            /       \
+;;           O        .O.
+;;          / \      / | \
+;;         O   O    O  O  O
+;;        /|\  |\  / \/|\/ \
+;;       # # # # # # ##### #
+;;
+;;              ..O..              |?????]
+;;             /     \
+;;            /       \
+;;     >    [O]       .O.     [??|???]
+;;          / \      / | \
+;;         O   O    O  O  O
+;;        /|\  |\  / \/|\/ \
+;;       # # # # # # ##### #
+;;
+;;              ..O..              |?????]
+;;             /     \
+;;            /       \
+;;           O        .O.        |???]
+;;          / \      / | \
+;;     >  [O]  O    O  O  O   [?|?]
+;;        /|\  |\  / \/|\/ \
+;;       # # # # # # ##### #
+;;
+;;              ..O..              |?????]
+;;             /     \
+;;            /       \
+;;           O        .O.        |???]
+;;          / \      / | \
+;;         O   O    O  O  O     |?]
+;;        /|\  |\  / \/|\/ \
+;;     >[#]# # # # # ##### #  [?]
 
 ,,,
 

;; 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.

,,,


;; ### Redistribute Children
;;
;; In the **distribution** phase, any candidate children which have over or

;; 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
