B+ Tree
Learn the fundamentals such as insertion, deletion, and search for B+ trees and discuss its use cases.
We'll cover the following...
B+ trees are the defacto on-disk data structures used in relational databases such as MySQL, Postgresql, and document databases such as MongoDB.
Introduction
B+ tree is an extension of B- tree, which addresses the shortcomings of B- tree. In a B+ tree, internal nodes act as separator keys, and only the leaf nodes store the key-value pair. This leads the B+ tree to hold more keys per node, increasing fanout and reducing height.
B+ trees link all the leaf nodes storing the actual key-value pair in the form of a linked list enabling a more efficient traversal of the key-value pairs without ascending to the parent node. Furthermore, keeping all the leaf nodes at the bottom of the tree also lets key-value pairs be stored in contiguous blocks on disk for efficient retrieval.
Properties
All the properties and the conditions of B-Tree also hold good for B+Tree.
Insertion only happens on the leaf nodes, not internal and root nodes.
All the leaf nodes of the B- tree are at the same level. A B+ tree stores a value or pointer to the value associated with the key on only leaf nodes.
A B+ tree links the leaf nodes with each other in the form of a linked list.
Keys in a given node of a B+Tree are strictly in increasing order allowing for binary search.
A B+ tree with order M has the following properties:
It can have a maximum of M children per node.
It can have a maximum of M-1 keys per node.
It should have a minimum of
internal nodes. It should have a minimum of
...