The Bey in B-Trees

My first year of code has really (self)taught me a lot about the caveats that come with writing JavaScript. Often as developers, when learning a series of new methods and soon-after confronting a task we think to ourselves: "What's the best way to do this? and even more often we soon after find ourselves responding: "Well, it depends."

This same question often comes up in our decision-making about how we store and utilize our data. Managing small amounts of data is usually a fairly easy task to accomplish, and with the use of Abstract Data Structures like Trees, Binary Search Trees(BSTs), Linked Lists, Graph, and Hash Tables, we can easily access data and perform retrieval and alteration methods, often meeting our needs with a linear or constant time complexity.

But what happens when we begin generating massive amounts of data and need to be able to sort through it quickly and efficiently, but without negatively impacting the time complexity?

Luckily we can answer this question easily; the writing's on the wall: The B-Tree.

Say My Name

It's still highly ambiguous what the 'B' in 'B-Tree' actually stands for (Binary, Balanced, Rudolf Bayer who invented them...?), but for the sake of this lesson in real-life relatability on just how special B-Trees are, from here on out, the 'B' stands for Beyonce. A gifted, unique, and incredibly powerful figure in modern society.

Upgrade U

Bey-Trees are superior data structures that are similar in their construct to Binary Search Trees, but with some upgrades. Like BSTs, Bey-Trees have the the ability to add, search, and remove nodes, but also have the super power of being able to self-balance.

Bey-Trees maintain sorted data in condensed child nodes, and changes to the tree are made in relation to the root as opposed to just being appended on to the end of the branches.

Also like BSTs, Bey-Trees contain two children, but that is the absolute minimum number of children they might have, and if one is really harnessing the power of Bey-Trees, the minimum number of children should increase exponentially.

Formation

The amount of children a Bey-Tree can have is determined by the loosely named properties called the degree, which is the minimum number of children on a branch, and also the order; the maximum amount of children can have until it must be re-balanced.

When a Bey-Tree is initially constructed, the order is simply generated as an empty array with an allotted amount of space for children to eventually be pushed in to.

Children of the key are sorted based on their numerical value in relation to the parent key. For example, a Bey-tree with an order of 4 can have at most 4 children before it is re-balanced.

Children with a value less than that of their parent key are pushed to the left of the parent, while children with a value greater are pushed to the right.

By decreasing the height of the Bey-Tree via use of sorted data through parent keys, Bey-Trees easily store and retrieve data using the indices at the parent key. Therefore while a Bey-Tree can have at minimum number of 2 children, the more data, or records it holds, the faster it can perform it's task, i.e., sorting, maintaining, and organizing data in logarithmic time.

Here's a little snippet of what a Bey-Tree instance might look like:

const formation = 3;
//the maximum num. of children before a function is called to rebalance the tree

const BeyTreeNode = function (keys, dChildren, parent) {
const beyNode = Object.create(BeyTreeNode.prototype);
beyNode.keys = keys || [];
//parents to determine less than, greater than, or in between

beyNode.dChildren = dChildren || new Array(formation);
//creates an empty array with spaces for children --> [ , , ];

beyNode.parent = parent || null;
Return beyNode;
}

//classic Methods
BeyTreeNode.prototype.insert = function(){};
BeyTreeNode.prototype.find = function(){};
BeyTreeNode.prototype.remove = function(){}

//B-Tree Unique Method
BeyTreeNode.prototype.handleOverflow = function(){}

In Conclusion

The next time you're looking for truly the best way to store all of your data, look no further, as the Bey-Tree provides a reliable, succinct method for ccessing super bowl amounts of data all while maintaining speedy logarithmic time.

Thanks for reading!