B+ Tree Algorithm

A B+ tree is an m-ary tree data structure, closely related to the B-tree, built from a root, internal nodes and leaves, each of which can hold a large and variable number of children. It can be understood as a B-tree in which the internal nodes store only keys rather than key-value pairs, with an additional level of linked leaf nodes added at the bottom that hold all of the actual data, so that every value lives in a leaf rather than being spread across the tree at different depths the way a plain B-tree allows. Because its nodes typically hold on the order of a hundred or more child pointers, a B+ tree keeps the number of disk or memory-block reads needed to find a value very low compared to a binary search tree, and its linked leaves allow fast sequential scans and range queries, which is why B+ trees are the structure of choice for file system metadata and for database table and index storage in block-oriented storage systems.