B-Tree
What is a tree? The basic structure of a tree is simple. A tree is a data structure. we call it a tree because its structure resembles an upside down tree. the top node of the tree is called the root, the child nodes of the root are called branches, and nodes without children are called leaf nodes. Values are stored on each node and nodes are accessible via their parent nodes.
So what is a B-Tree? The basic structure of a B-Tree is slightly different from a traditional tree. It still has root, branch and leaf nodes, but unlike a traditional tree structure, all the leaf nodes must be at the same depth as each other. this means that the leaf nodes will all be n branch nodes from the root. This is achieved by the b-tree’s unique features.
What makes a B-Tree unique? Each node of a B-Tree contains keys. The minimum amount of keys on the root is 1. If k is the number of keys on a node that node will have k+1 child nodes. This is because of how data is stored on a B-Tree. If we look at the constructor function below for a B-Tree node, you’ll notice that this._children is the size this._children plus one.
const NKEYS = 4;function BTreeNode() {this._keys = arrayOfSize(NKEYS);this._children = arrayOfSize(NKEYS + 1);}
If the node contains one key, the children to the left of the node will contain lesser values, and the node to the right will contain larger values. If there are two keys, k1 and k2 , the left child contains values less than k1, the middle child will contain values between k1 and k2, and the right child will contain values greater than k2. As nodes fill up with values, they split. The tree then balances by passing the values. If a node on the left right of the tree fills, it passes its value up and a new tier or leaf nodes is created.
What are the benefits of B-Trees? The time complexities for search, insert, and delete is O(log n). B-Trees are still a self balancing tree like a binary tree, except it can contain more than two child nodes per node. They are great for storing large amounts of data. Since large amounts of data need to be stored on disk drives and not in memory, speed of read time is important. With the help of an auxiliary index can help speed searches, having only 1% of the entries of the B-Tree, it can tell you on which blocks to start your search, cutting your time down immensely.
B-Trees are a self-balancing data structure. They are ideally suited for working on large databases of information. Their unique structure allows them to store multiple values on each node and always have one more child node than number of the values stored. All leaf nodes are at the same depth, which helps to balance the tree and keep the time complexity for search, insert and delete to O(log n).
Resources:
Info:
https://www.cpp.edu/~ftang/courses/CS241/notes/b-tree.htm
https://www.geeksforgeeks.org/b-tree-set-1-introduction-2/
https://medium.com/basecs/busying-oneself-with-b-trees-78bbf10522e7
https://www.bluerwhite.org/btree/
https://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html
Graphics:
https://www.cpp.edu/~ftang/courses/CS241/notes/b-tree.htm
https://en.wikipedia.org/wiki/Tree_(data_structure)
https://pixabay.com/vectors/tree-autumn-winter-forest-1994653/
