Now for the fun stuff: the add method for

It’s about time I started on something exciting!  It’s time to implement the add method in my btree library.

Here’s how it works:

Find the appropriate leaf node in which to add the new key-value pair by searching down the tree by keys.  If the key is already found, then no change occurs.

Insert the key into the leaf node.  If the leaf node is larger than the designated upper bound (I often use 4 elements as the upper bound, but the user can specify this in my implementation [a feature which may or may not disappear by the end]), pop out the middle element, turn it into a branch with its leaves on either side being the two remaining halves of the leaf node, and integrate that element into the branch above.

Keep going until you reach the root!

This is a preliminary post to keep me on track as I get my bearings about this add method.  Once it’s completely implemented, expect a detailed code analysis that discusses, in particular, the intricacies of ownership and borrowing in Rust, which were major struggles for me at first.  I still have much to learn, but I hope I can give an adequate explanation of Rust’s idiosyncrasies, which make it extremely safe and reliable w/r/t memory and pointers.

Stay tuned!

This entry was posted in Uncategorized and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s