Questions about the tree structure used to implement :array

Hey all, my first post.

Reading through the source code for array, the representation is described as a functional, extendible array with a leafsize of 10.

With 10 values, an array is represented as:

{"v1", "v2", "v3", "v4", "v5", "v6", "v7", "v8", "v9", "v10"}

With 11 values, the tree changes:

{{"v1", "v2", "v3", "v4", "v5", "v6", "v7", "v8", "v9", "v10"},
   {"v11", :undefined, :undefined, :undefined, :undefined, :undefined,
    :undefined, :undefined, :undefined, :undefined}, 10, 10, 10, 10, 10, 10, 10,
   10, 10}

As far as I can tell, this changes the representation to have 1 node with 10 leaves:

                              node = {leaf1, leaf2, 10, 10, 10, 10, 10, 10, 10, 10, (# elements cache)}
                                      /         \ 
 {v1, v2, v3, v4, v5, v6, v7, v7, v9, v10}      {v11, :undefined, ...}

The last element of an internal node caches the number of elements that may be stored in each of its subtrees.

The 2 leafs are wrapped in an expanded node which stores a cache of how many elements may be stored in each subtree.

Questions

  1. Am I understanding the node/leaf definitions correctly?
  2. Is there a name/type/category of tree that I can google to better understand this implementation?

thanks, and appreciate any resources or input!

3 Likes

1. Am I understanding the node/leaf definitions correctly?

Yes I think that

Not to my knowledge, I just wanted/needed a faster implementation than gb_trees in Wings3D to store values and since my keys was always integers I didn’t need to store them.

So I created a wide tree without keys, think my initial implementation had ~30 leafs on each level, than @richardc came in and optimized from a size perspective and improved the code.

3 Likes

You could call it an m-ary tree (m-ary tree - Wikipedia) with a fanout of 10. Like @dgud said, I did the measurements and the maths and found that the best tradeoff was around 8-12, so I picked 10. There is not much else that’s special except for being very careful to avoid allocating new tuples except when necessary, and to minimize the computations and indirections needed to look up an element.

5 Likes