B+ Tree
Overview
Judging by its name - we can guess that B+ Tree is similar but not identical to B Tree. There are a few key differences that we will now examine (if you haven't learnt the previous section on B Tree, now it's a good moment to do it).
-
You already know what internal nodes and leaf nodes are. The internal nodes in a B Tree store data/keys and pointers (arrows from the animations). But the internal nodes of a B+ Tree don't store data on their own - they are used only for navigation to the leaf nodes. The actual and important data is stored only in the leaf nodes.
-
Speaking of leaf nodes - the ones in B+ tree are linked like a... you've guessed it - linked list. So once you access them, you have a sequential access between them (which is not possible in a B Tree).
-
And last but not least is that a B+ Tree allows duplicate keys (seen in the animation, because they are used for navigation as we already mentioned). Also, the height of a B+ Tree tends to be lower and searches tend to be faster.
In the animation, we see how a B+ tree of degree 3 is built by the process of insertion. It's a bit trickier than insertion in B Tree, so let's explain it:
- If we insert a new record in an empty tree (like the start at the animation), we consider it as root node
- Any other insertion of a record will be targeted against a node. The target node can be either full or not (full node - reached the maximum number of record inside the node, based on the order of the tree).
- If we insert into a not full node - it's simple, just insert the record in the node (like the insertion of '2' after '1' in the animation at the start)
- But if the target node becomes full, we should split it and favor the right side (for instance, if the has values 1,2,3 - we split it as 1 | 2,3). Then we copy the first node of the right side (2) and move it to the parent as a pointer.
- This process is repeated until we find a parent with a non full node so we can insert the new node without splitting.
Unline other trees, this process of insertion makes the B+ tree grow from bottom up - leaf nodes always stay at the same level and nodes are copied and propagated above.
In conclusion - these differences between B and B+ trees are not necessarily in favor in one or the other. Rather, each one has different main purposes. The B Tree is easier to comprehend and, as already mentioned in its section, best suited for file systems, data storage and generally for improved I/O. While the B+ Tree is mainly used in database systems where more searching, querying, speed and flexibility is needed.
Code
class BPlusTreeNode:
def __init__(self, is_leaf=True):
self.keys = []
self.children = []
self.is_leaf = is_leaf
self.next = None
def insert(self, key):
if self.is_leaf:
self.insert_leaf(key)
else:
self.insert_non_leaf(key)
def insert_leaf(self, key):
self.keys.append(key)
self.keys.sort()
def insert_non_leaf(self, key):
i = 0
while i < len(self.keys) and key > self.keys[i]:
i += 1
self.children[i].insert(key)
def search(self, key):
if self.is_leaf:
return key if key in self.keys else None
else:
i = 0
while i < len(self.keys) and key >= self.keys[i]:
i += 1
return self.children[i].search(key)
class BPlusTree:
def __init__(self):
self.root = BPlusTreeNode()
def insert(self, key):
self.root.insert(key)
def search(self, key):
return self.root.search(key)
# Example usage:
b_plus_tree = BPlusTree()
keys = [1, 2, 3, 4, 5, 6]
for key in keys:
b_plus_tree.insert(key)
print(b_plus_tree.search(3))
print(b_plus_tree.search(7))
class BPlusTreeNode {
constructor(isLeaf = true) {
this.keys = [];
this.children = [];
this.isLeaf = isLeaf;
this.next = null;
}
insert(key) {
if (this.isLeaf) {
this.insertLeaf(key);
} else {
this.insertNonLeaf(key);
}
}
insertLeaf(key) {
this.keys.push(key);
this.keys.sort((a, b) => a - b);
}
insertNonLeaf(key) {
let i = 0;
while (i < this.keys.length && key > this.keys[i]) {
i++;
}
this.children[i].insert(key);
}
search(key) {
if (this.isLeaf) {
return this.keys.includes(key) ? key : null;
} else {
let i = 0;
while (i < this.keys.length && key >= this.keys[i]) {
i++;
}
return this.children[i].search(key);
}
}
}
class BPlusTree {
constructor() {
this.root = new BPlusTreeNode();
}
insert(key) {
this.root.insert(key);
}
search(key) {
return this.root.search(key);
}
}
// Example usage:
const bPlusTree = new BPlusTree();
const keys = [1, 2, 3, 4, 5, 6];
keys.forEach((key) => bPlusTree.insert(key));
console.log(bPlusTree.search(3)); // Should print 3
console.log(bPlusTree.search(7)); // Should print null since 7 is not in the tree
class BPlusTreeNode {
public $keys = [];
public $children = [];
public $isLeaf;
public $next;
public function __construct($isLeaf = true) {
$this->isLeaf = $isLeaf;
}
public function insert($key) {
if ($this->isLeaf) {
$this->insertLeaf($key);
} else {
$this->insertNonLeaf($key);
}
}
public function insertLeaf($key) {
$this->keys[] = $key;
sort($this->keys);
}
public function insertNonLeaf($key) {
$i = 0;
while ($i < count($this->keys) && $key > $this->keys[$i]) {
$i++;
}
$this->children[$i]->insert($key);
}
public function search($key) {
if ($this->isLeaf) {
return in_array($key, $this->keys) ? $key : null;
} else {
$i = 0;
while ($i < count($this->keys) && $key >= $this->keys[$i]) {
$i++;
}
return $this->children[$i]->search($key);
}
}
}
class BPlusTree {
public $root;
public function __construct() {
$this->root = new BPlusTreeNode();
}
public function insert($key) {
$this->root->insert($key);
}
public function search($key) {
return $this->root->search($key);
}
}
// Example usage:
$bPlusTree = new BPlusTree();
$keys = [1, 2, 3, 4, 5, 6];
foreach ($keys as $key) {
$bPlusTree->insert($key);
}
echo $bPlusTree->search(3); // Should print 3
echo $bPlusTree->search(7); // Should print an empty string since 7 is not in the tree