[erlang-questions] Data structures are strange things

[Richard O'Keefe]

If you take a look at a typical 2-3-4 tree implementation in Java
    http://www.cs.berkeley.edu/~jrs/61bs02/hw/hw7/dict/Tree234.java
>>  http://www.cs.berkeley.edu/~jrs/61bs02/hw/hw7/dict/Tree234Node.java
you'll see nodes containing

	an integer saying how many keys there are
	three keys
	four links to children nodes
	a link to a parent node

Allow one word for "what is the class of this object" and that's
10 words per node.

Using Erlang tuples, we'd have
	{K1,C0,C1}			4 words
	{K1,K2,C0,C1,C2}		6 words
	{K1,K2,K3,C0,C1,C2,C3}		8 words
WAM-based Prolog systems would take the same space;
SML/NJ should be able to shave a word off each (using the bottom
2 bits of a pointer to say which of the three cases applies).

In a functional language, when you make a change you create new nodes,
so no node ever has to change size/shape.  You _could_ do that in Java
too, but people often don't think of it.

It seems pretty clear that the Prolog/Erlang/SML version of a 2-3-4
tree is going to take *less* space than a binary tree in the same
language.  Since in these languages there is often a strong correlation
between space and time, I find Robert Virding's results pleasant but
not that surprising.