This post marks the birth of a novel datastructure:

The Fingerprint Tree

The Fingerprint Tree has the following amazing properties:

  1. It's a B-Tree
  2. Concatenation and split is O(log n)
  3. A canonical representation