The Bey in B-Trees
Tags: javascript, beginners, firstyearincode, codenewbie
Published: 2019-11-25 14:09:48

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."*  

![Alt Text](https://media.giphy.com/media/60rUZAj7OHOiCsbPJY/giphy.gif)

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.  

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/2tvsggrnyqf5ssqxfh5r.gif)

####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*. 

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/3qjdloecz4uiv7uk4x4q.gif)

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.

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/6eg7dt51rl7gz733wqh8.gif)

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. 

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/ca8p7rs2k0rujwxefnez.png)

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.

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/198w8aghn9bkd4k9a5k8.png)

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.

![Alt Text](https://media.giphy.com/media/hSotU9iXeON0bdENjT/giphy.gif)

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:

```javascript

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.

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/tzpwt2l61zm96drh5f58.gif)

Thanks for reading!