|Introduction to B-Trees|
|A B-tree is a tree data structure that keeps data sorted and allows searches, insertions, and deletions in logarithmic amortized time. Unlike self-balancing binary search trees, it is optimized for systems that read and write large blocks of data. It is most commonly used in database and file systems.|
|The B-Tree Rules|
|Important properties of a B-tree:
The set formulation of the B-tree rules: Every B-tree depends on a positive constant integer called MINIMUM, which is used to determine how many elements are held in a single node.
|Searching for a Target in a Set|
Adding an Element to a B-Tree
It is easier to add a new element to a B-tree if we relax one of the B-tree rules.
Loose addition allows the root node of the B-tree to have MAXIMUM + 1 elements. For example, suppose we want to add 18 to the tree:
The above result is an illegal B-tree. Our plan is to perform a loose addition first, and then fix the root's problem.
The Loose Addition Operation for a B-Tree:
Fixing a Child with an Excess Element:
Fixing the Root with an Excess Element:
|Removing an Element from a B-Tree|
Loose removal rule: Loose removal allows to leave a root that has one element too few.
Fixing Shortage in a Child:
When fixShortage(i) is activated, we know that subset[i] has MINIMUM - 1 elements. There are four cases that we need to consider:
Case 1: Transfer an extra element from subset[i-1]. Suppose subset[i-1] has more than the MINIMUM number of elements.
Case 2: Transfer an extra element from subset[i+1]. Suppose subset[i+1] has more than the MINIMUM number of elements.
Case 3: Combine subset[i] with subset[i-1]. Suppose subset[i-1] has only MINIMUM elements.
Case 4: Combine subset[i] with subset[i+1]. Suppose subset[i+1] has only MINIMUM elements.
We may need to continue activating fixShortage() until the B-tree rules are satisfied.
Removing the Biggest Element from a B-Tree:
A more concrete example for node deletion: