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
- Am I understanding the node/leaf definitions correctly?
- Is there a name/type/category of tree that I can google to better understand this implementation?
thanks, and appreciate any resources or input!