Internally the tree consists of segments and index_nodes:

struct index_node {
  index_node *parent_pointer;
  std::uint16_t parent_index_;
  std::uint16_t length_;
  std::array<size_type, base_max> sizes;
  std::array<void *, base_max> pointers;
}

using segment = value_type *; // Of size segment_max.

An index_node of height greater than 2 always contains other index_nodes as children. An index_node of height 2 always contains segments as chidlren. A segment is always of height 1 and is simply an array of value_type. Height 0 is the empty tree.

The size array stores the recursive size of all its children.

The segmented_tree::seq container looks like this:

struct seq {
  size_type height;
  size_type size;
  void * root;
};

The height of the tree can be used to determine what type root points to.

Iterators look like this:

struct iterator {
  segment segment;
  size_type segment_index;
  size_type segment_length;
  index_node *parent;
  index_node *parent_index
  size_type position;
};

Storing the position enables constant time comparison between iterators. This is possible because any destructive operation that would invalidate the position invalidates all iterators anyways. Additionally, a segment's metadata is stored here instead of the segment as an optimization. This is worthwhile because segments are mutated exponentially more often than any node above it and cache misses are reduced.

All searches start from the root of the tree. To find a given index in the tree you start from the root and perform linear searches on each index_node and walk down the tree until you reach a segment at height 1.

If the segment pointed to by the iterator is not full then insert the element in segment and walk up the tree updating sizes. If the segement is full then split the segment into two and insert the new segment into the parent index_node. The index_node repeats this process. If the root is passed then create a new root index_node containing two children and increase the height.

If the segment pointed to by the iterator is not at its minimum value then remove the element from the segment and walk up the tree updating sizes. If the segement is at its minimum size then try to steal an element from a sibling. If this succeeds then walk up the tree updating sizes. Otherwise, merge the segment with a neighbor and remove the neighbor from the parent index_node. The index_node repeats this process. If a root index_node of length 2 is hit, then make the remaning child the new root and decrease the height.