> See also: > - [[Tree Data Structures]] # B-Tree > [Introduction of B-Tree](https://www.geeksforgeeks.org/introduction-of-b-tree-2/) > [B-Tree Visualization/Sandbox](https://www.cs.usfca.edu/~galles/visualization/BTree.html) B-Tree stands for “balanced search tree)” In traditional binary search trees, it is possible for the height of the structure to grow significantly. B-Tree nodes can store many values and can have many children Primarily used in disks and other secondary memory storage devices | Algorithm | Time Complexity | | :-------: | :-------------: | | Search | $O(\log n)$ | | Insert | $O(\log n)$ | | Delete | $O(\log n)$ | The key feature about B-Trees is that each node can have more than 1 key (value) associated with it. A B-Tree with a degree of $t=4$ is known as a **2-3-4 Tree** ## B-Trees Properties Every B-Tree is pre-defined with a *minimum degree* value ($t$). - $t \ge 2$ Every node, except for the root, must contain at least $t-1$ keys - All leaf nodes are on the same level - The number of children of a node is equal to the the number of keys it has + 1. ## B-Tree Operations ### Initializing ```java class Node { int n; // Current number of keys within node int[] keys; // Array of keys/values within node Node[] children; // Array of pointers to children boolean leaf; // Is this node a leaf? } ``` - Some implementations may also store the minimum degree value within each `Node` object. ```java class BTree { private Node root; } ``` ### Searching Searching a B-Tree is very similar to traditional BST searching, as both structures follow the property of ```java Node BtreeSearch(Node cur, int k) { int i = 0; while (i < cur.n && k >) } ``` ### Insertion We cannot insert a key into a node that is already full (has $2t-1$ keys), so we instead split the target node We can ensure that there is a suitable empty space and perform the insertion at the same time, avoiding multiple passes through the tree. - We also split the leaf node (if one is ) because of the “split child” system, B-Trees will grow upwards following insertions as opposed to BSTs which grow downwards The insertion of a node in a B-Tree only happens at a leaf node ``` r= T.root if ``` - `B-Tree-Insert(T,k)` - `B-Tree-Insert-NonFull(s,k)` --- `B-Tree-Split-Child(s,1)` Regardless of the minimum degree value specified, the maximum # of keys that can be stored in a node will always be an odd number ($2t-1$) ### Deletion There are several goals the following cases aim to achieve when performing a deletion: - Ensure that the node containing the deleted key as at least $t$ keys (to still satisfy minimum degree, $t-1$, following deletion) - Aim to push nodes up towards the root **Rules** 1. If the key is stored in a leaf node, simply delete the key 2. If the node isn’t a leaf: 1. Look at the child pointer that precedes the key to be deleted. 2. Does the child node have at least $t$ keys - leaf delete - predecessor delete #### Rule 1 > **Rule 1:** Simply delete from #### Rule 2A #### Rule 2B =00= #### Rule 2C #### Rule 3A #### Rule 3B --- I think a bit of my confusion is coming from what we consider to be a “leaf node”. In RB-Trees we kind of blend together the true leaf nodes and the “NULL nodes”