B+ Tree

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.