Increase the number of inner node types #61
Description
There is a section of the ART paper which reads:
As a consequence, the worst-case space consumption is 52 bytes for any adaptive radix tree, even for arbitrarily long keys. It can also be shown analogously that with six node types [^1], the worst-case space consumption can be reduced to 34 bytes per key.
The footnote reads:
1: The Node4 type is replaced by the new node types Node2 and Node5 and the Node48 type is replaced by the new Node32 and Node64 types.
The nodes carry their tag in the pointers to the node, using the bits that are always empty due to alignment. All the nodes are aligned to at least 8, leaving 3 bits empty. This gives us a total of 8 possible values, 5 of which are currently used for node types. We could add 3 more node types and use those to make the memory usage grow more slowly.
I think we would need some more realistic macro benchmark programs to aid in making that decision.
Other required work would be making the InnerNode48 generic over number of keys.