Questions concerning "Simple Components"

Questions concerning "Simple Components"

[Jeremiah]

I really like a lot of the items found in the Simple Components library, but had a few questions on their usage.  Specifically:

Generic_B_Trees have a generic package parameter "Width" which has the following description from the website:
"Width is the size of the bucket of key-value pairs allocated per tree node;"

This doesn't make a lot of sense to me.  I'm sure I am just missing something simple, but what is the "bucket" being referenced?  Is it terminology for how many key value pairs can be created before more memory has to be allocated?  The "per tree node" part also throws me off a little bit because on a binary tree, I would expect only one key/value pair per node.  That said, I could be misunderstanding some of the terminology.  Can anyone add some clarity to what exactly the Width parameter does?

2nd question:
I really like the concept of Generic_External_B_Tree which use persistent storage to save data.  One thing I am trying to get a better handle on is a better way to handle the Root node address returned from Get_Root_Address.  I need this value to create the tree in a later application invocation.  I know I could just save it in another file or possibly add a root address value to all my tree nodes, but both of those methods seem wasteful.  What methods do yall use to store the root node address?  I thought about just writing it to the beginning of the Persistent_Array, but I don't know how well mixing types (a raw Byte_Index and a Generic_External_B_Tree) in a single Persistent_Array will work.  I'm still digging through the code to see if I could do this in some manner, but if any of yall have suggestions on how to better manage the root node address, I would appreciate it.

Simple Components reference:
http://www.dmitry-kazakov.de/ada/components.htm#b-tree

Re: Questions concerning "Simple Components"

[Niklas Holsti]

On 15-11-04 04:16 , Jeremiah wrote:
> I really like a lot of the items found in the Simple Components
> library, but had a few questions on their usage.  Specifically:
>
> Generic_B_Trees have a generic package parameter "Width" which has
> the following description from the website: "Width is the size of the
> bucket of key-value pairs allocated per tree node;"
>
> This doesn't make a lot of sense to me.  I'm sure I am just missing
> something simple, but what is the "bucket" being referenced?  Is it
> terminology for how many key value pairs can be created before more
> memory has to be allocated?  The "per tree node" part also throws me
> off a little bit because on a binary tree, I would expect only one
> key/value pair per node.

B-trees are _not_ generally binary trees; the branching factor is 
typically much larger than 2. See https://en.wikipedia.org/wiki/B-tree.

I'm not familiar with the Simple Components, but the description of 
"Width"  sounds as if it sets the maximum number of key-and-value pairs 
that can be stored in one leaf node of the B-tree. The internal nodes 
also have multiple keys per node, but the corresponding values are 
pointers to child nodes, so perhaps there is a different parameter to 
set the number of key-and-pointer pairs in internal nodes.

Hopefully Dmitry will follow with a better explanation...

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: Questions concerning "Simple Components"

[Dmitry A. Kazakov]

On Tue, 3 Nov 2015 18:16:07 -0800 (PST), Jeremiah wrote:

> Generic_B_Trees have a generic package parameter "Width" which has the
> following description from the website:
> "Width is the size of the bucket of key-value pairs allocated per tree node;"
> 
> This doesn't make a lot of sense to me.  I'm sure I am just missing
> something simple, but what is the "bucket" being referenced?  Is it
> terminology for how many key value pairs can be created before more memory
> has to be allocated?

Yes

> The "per tree node" part also throws me off a little
> bit because on a binary tree, I would expect only one key/value pair per
> node.

Yes, in a logical view the container consists of key/value pairs. The
physical view of it is a hierarchy of buckets having fixed size.

> That said, I could be misunderstanding some of the terminology. 
> Can anyone add some clarity to what exactly the Width parameter does?

Width is the number of pairs in the bucket. Depending on the tree
(definite/indefinite) a bucket contains either the pairs as-is or
references to the pairs allocated elsewhere. The persistent B-tree buckets
have the size to fit into one block for optimal I/O.

> I really like the concept of Generic_External_B_Tree which use persistent
> storage to save data.  One thing I am trying to get a better handle on is
> a better way to handle the Root node address returned from
> Get_Root_Address.  I need this value to create the tree in a later
> application invocation.  I know I could just save it in another file or
> possibly add a root address value to all my tree nodes, but both of those
> methods seem wasteful.  What methods do yall use to store the root node
> address?

The persistent memory pool the tree resides in has a root index reserved in
particular for this purpose. The tree root address can be kept there. See:
Get_Root_Index, Set_Root_Index.

http://www.dmitry-kazakov.de/ada/components.htm#Persistent.Memory_Pools.Set_Root_Index

There are 16 independent values you can store there. Note that the root
address may change on tree update. After you have updated the tree before
committing the pool, get the root address and store it into one of the root
index values.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Questions concerning "Simple Components"

[Jeremiah]

On Wednesday, November 4, 2015 at 4:09:56 AM UTC-5, Dmitry A. Kazakov wrote:
> > That said, I could be misunderstanding some of the terminology. 
> > Can anyone add some clarity to what exactly the Width parameter does?
> 
> Width is the number of pairs in the bucket. Depending on the tree
> (definite/indefinite) a bucket contains either the pairs as-is or
> references to the pairs allocated elsewhere. The persistent B-tree buckets
> have the size to fit into one block for optimal I/O.
That makes sense.  Thank you!

> > I really like the concept of Generic_External_B_Tree which use persistent
> > storage to save data.  One thing I am trying to get a better handle on is
> > a better way to handle the Root node address returned from
> > Get_Root_Address.  I need this value to create the tree in a later
> > application invocation.  I know I could just save it in another file or
> > possibly add a root address value to all my tree nodes, but both of those
> > methods seem wasteful.  What methods do yall use to store the root node
> > address?
> 
> The persistent memory pool the tree resides in has a root index reserved in
> particular for this purpose. The tree root address can be kept there. See:
> Get_Root_Index, Set_Root_Index.
> 
> http://www.dmitry-kazakov.de/ada/components.htm#Persistent.Memory_Pools.Set_Root_Index
> 
> There are 16 independent values you can store there. Note that the root
> address may change on tree update. After you have updated the tree before
> committing the pool, get the root address and store it into one of the root
> index values.

Gotcha.  Sorry that I missed that.  I appreciate the response!