B+ Tree
Explore the B+ tree data structure used in databases like MySQL, Postgresql, and MongoDB. Understand its properties, efficient search method using binary search, and how insertion and deletion maintain balance. This lesson helps you grasp how B+ trees organize data for fast retrieval and efficient storage on disk.
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
...