B+ tree

B+ tree node format where K=4. (p_i represents the pointers, k_i represents the search keys).

As with other trees, B+ trees can be represented as a collection of three types of nodes: root, internal (a.k.a. interior), and leaf. In B+ trees, the following properties are maintained for these nodes:

• If ${\textstyle k_{i}}$ exists in any node in a B+ tree, then ${\displaystyle k_{i-1}}$ exists in that node where ${\displaystyle i\geq 1}$.
• All leaf nodes have the same number of ancestors (i.e., they are all at the same depth).

The pointer properties of nodes are summarized in the tables below:

• K: Maximum number of potential search keys for each node in a B+ tree. (this value is constant over the entire tree).
• ${\displaystyle p_{i}}$: The pointer at the zero-based node index ${\displaystyle i}$.
• ${\displaystyle k_{i}}$: The search key at the zero-based node index ${\displaystyle i}$.

Internal Node Pointer Structure

${\displaystyle p_{0}}$ when ${\displaystyle k_{0}}$ exists	${\displaystyle p_{i}}$ when ${\displaystyle k_{i-1}}$ and ${\displaystyle k_{i}}$ exist	${\displaystyle p_{i}}$ when ${\displaystyle k_{i-1}}$ exists, and ${\displaystyle k_{i}}$ does not exist	${\displaystyle p_{i}}$ when ${\displaystyle k_{i-1}}$ and ${\displaystyle k_{i}}$ do not exist
Points to subtree in which all search keys are less than ${\displaystyle k_{0}}$.	Points to subtree in which all search keys are greater than or equal to ${\displaystyle k_{i-1}}$ and are less than ${\displaystyle k_{i}}$.	Points to subtree in which all search keys are greater than or equal to ${\displaystyle k_{i-1}}$.	Here, ${\displaystyle p_{i}}$ is empty.

Leaf Node Pointer Structure

${\displaystyle p_{i}}$ when ${\displaystyle k_{i}}$ exists	${\displaystyle p_{i}}$ when ${\displaystyle k_{i}}$ does not exist and ${\displaystyle i\neq K}$	${\displaystyle p_{K}}$
Points to a record with a value equal to ${\displaystyle k_{i}}$.	Here, ${\displaystyle p_{i}}$ is empty.	Points to the next leaf in the tree.

The node bounds are summarized in the table below:

Node Type	Min Number of Keys	Max Number of Keys	Min Number of Child Nodes	Max Number of Child Nodes
Root Node (when it is a leaf node)	0	${\displaystyle K}$	0	0
Root Node (when it is an internal node)	1	${\displaystyle K}$	2[1]	${\displaystyle K+1}$
Internal Node	${\displaystyle \lfloor K/2\rfloor }$	${\displaystyle K}$	${\displaystyle \lceil (K+1)/2\rceil }$ ${\displaystyle \equiv \lfloor K/2\rfloor +1}$	${\displaystyle K+1}$
Leaf Node	${\displaystyle \lceil K/2\rceil }$	${\displaystyle K}$	0	0

[3][4]

A simple B+ tree example linking the keys 1–7 to data values d₁-d₇. The linked list (red) allows rapid in-order traversal. This particular tree's branching factor is ${\displaystyle b}$=4. Both keys in leaf and internal nodes are colored gray here.

By definition, each value contained within the B+ tree is a key contained in exactly one leaf node. Each key is required to be directly comparable with every other key, which forms a total order.[5] This enables each leaf node to keep all of its keys sorted at all times, which then enables each internal node to construct an ordered collection of intervals representing the contiguous extent of values contained in a given leaf. Internal nodes higher in the tree can then construct their own intervals, which recursively aggregate the intervals contained in their own child internal nodes. Eventually, the root of a B+ Tree represents the whole range of values in the tree, where every internal node represents a subinterval.

For this recursive interval information to be retained, internal nodes must additionally contain ${\displaystyle m-1}$ copies of keys ${\displaystyle l_{i}}$ for ${\displaystyle i\in [1,m-1]}$ representing the least element within the interval covered by the child with index i (which may itself be an internal node, or a leaf). Where m represents the actual number of children for a given internal node.

We are looking for a value k in the B+ Tree. This means that starting from the root, we are looking for the leaf which may contain the value k. At each node, we figure out which internal node we should follow. An internal B+ Tree node has at most ${\displaystyle m\leq b}$ children, where every one of them represents a different sub-interval. We select the corresponding child via a linear search of the m entries, then when we finally get to a leaf, we do a linear search of its n elements for the desired key. Because we only traverse one branch of all the children at each rung of the tree, we achieve ${\displaystyle O(\log N)}$ runtime, where N is the total number of keys stored in the leaves of the B+ tree.[3]

function search(k, root) is
    let leaf = leaf_search(k, root)
    for leaf_key in leaf.keys():
        if k = leaf_key:
             return true
    return false

function leaf_search(k, node) is
    if node is a leaf:
        return node
    let p = node.children()
    let l = node.left_sided_intervals()
    assert ${\displaystyle |p|=|l|+1}$
    let m = p.len()
    for i from 1 to m - 1:
        if ${\displaystyle k\leq l[i]}$:
            return leaf_search(k, p[i])
    return leaf_search(k, p[m])

Note that this pseudocode uses 1-based array indexing.

• Perform a search to determine which node the new record should go into.
• If the node is not full (at most ${\displaystyle b-1}$ entries after the insertion), add the record.
• Otherwise, before inserting the new record
  • Split the node.
    • original node has ⎡(L+1)/2⎤ items
    • new node has ⎣(L+1)/2⎦ items
  • Copy ⎡(L+1)/2⎤-th key to the parent, and insert the new node to the parent.
  • Repeat until a parent is found that need not split.
  • Insert the new record into the new node.
• If the root splits, treat it as if it has an empty parent and split as outline above.

B+ trees grow at the root and not at the leaves.[1]

Given a collection of data records, we want to create a B+ tree index on some key field. One approach is to insert each record into an empty tree. However, it is quite expensive, because each entry requires us to start from the root and go down to the appropriate leaf page. An efficient alternative is to use bulk-loading.

• The first step is to sort the data entries according to a search key in ascending order.
• We allocate an empty page to serve as the root, and insert a pointer to the first page of entries into it.
• When the root is full, we split the root, and create a new root page.
• Keep inserting entries to the right most index page just above the leaf level, until all entries are indexed.

Note :

• when the right-most index page above the leaf level fills up, it is split;
• this action may, in turn, cause a split of the right-most index page one step closer to the root;
• splits only occur on the right-most path from the root to the leaf level.[8]

The purpose of the delete algorithm is to remove the desired entry node from the tree structure. We recursively call the delete algorithm on the appropriate node until no node is found. For each function call, we traverse along, using the index to navigate until we find the node, remove it, and then work back up to the root.

At entry L that we wish to remove:

- If L is at least half-full, done

- If L has only d-1 entries, try to re-distribute, borrowing from sibling (adjacent node with same parent as L).

           After the re-distribution of two sibling nodes happens, the parent node must be updated to reflect this change. The index key that points to the second sibling must take the smallest value of that node to be the index key.

- If re-distribute fails, merge L and sibling. After merging, the parent node is updated by deleting the index key that point to the deleted entry. In other words, if merge occurred, must delete entry (pointing to L or sibling) from parent of L.

Note: merge could propagate to root, which means decreasing height.[9]

B+ tree deletion

The ReiserFS, NSS, XFS, JFS, ReFS, and BFS filesystems all use this type of tree for metadata indexing; BFS also uses B+ trees for storing directories. NTFS uses B+ trees for directory and security-related metadata indexing. EXT4 uses extent trees (a modified B+ tree data structure) for file extent indexing.[11] APFS uses B+ trees to store mappings from filesystem object IDs to their locations on disk, and to store filesystem records (including directories), though these trees' leaf nodes lack sibling pointers.[12]

Relational database management systems such as IBM Db2,[10] Informix,[10] Microsoft SQL Server,[10] Oracle 8,[10] Sybase ASE,[10] and SQLite[13] support this type of tree for table indices, though each such system implements the basic B+ tree structure with variations and extensions. Many NoSQL database management systems such as CouchDB[14] and Tokyo Cabinet[15] also support this type of tree for data access and storage.

Finding objects in a high-dimensional database that are comparable to a particular query object is one of the most often utilized and yet expensive procedures in such systems. In such situations, finding the closest neighbor using a B+ tree is productive.[16]

B+ tree is efficiently used to construct an indexed search method called iDistance. iDistance searches for k nearest neighbors (kNN) in high-dimension metric spaces. The data in those high-dimension spaces is divided based on space or partition strategies, and each partition has an index value that is close with the respect to the partition. From here, those points can be efficiently implemented using B+ tree, thus, the queries are mapped to single dimensions ranged search. In other words, the iDistance technique can be viewed as a way of accelerating the sequential scan. Instead of scanning records from the beginning to the end of the data file, the iDistance starts the scan from spots where the nearest neighbors can be obtained early with a very high probability.[17]

Nonvolatile random-access memory (NVRAM) has been using B+ tree structure as the main memory access technique for the Internet Of Things (IoT) system because of its non static power consumption and high solidity of cell memory.  B+ can regulate the trafficking of data to memory efficiently. Moreover, with advanced strategies on frequencies of some highly used leaf or reference point, the B+ tree shows significant results in increasing the endurance of database systems.[18]

• Interactive B+ Tree Implementation in C
• Interactive B+ Tree Implementation in C++
• Memory based B+ tree implementation as C++ template library
• 2019 improvement of previous
• Stream based B+ tree implementation as C++ template library
• Open Source JavaScript B+ Tree Implementation
• Perl implementation of B+ trees
• Java/C#/Python implementations of B+ trees
• C# B+ tree and related "A-List" data structures
• File based B+Tree in C# with threading and MVCC support
• Fast semi-persistent in-memory B+ Tree in TypeScript/JavaScript, MIT License
• JavaScript B+ Tree, MIT License
• JavaScript B+ Tree, Interactive and Open Source